/**
 * \file
 * A pointer queue that can be sorted.
 *
 * Copyright (C) 2014 Xamarin Inc
 *
 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
 */

#ifdef HAVE_SGEN_GC

#include <string.h>

#include "mono/sgen/sgen-gc.h"
#include "mono/sgen/sgen-pointer-queue.h"

void
sgen_pointer_queue_clear (SgenPointerQueue *queue)
{
	queue->next_slot = 0;
}

void
sgen_pointer_queue_init (SgenPointerQueue *queue, int mem_type)
{
	queue->next_slot = 0;
	queue->size = 0;
	queue->data = NULL;
	queue->mem_type = mem_type;
}

static void
realloc_queue (SgenPointerQueue *queue)
{
	size_t new_size = queue->size ? queue->size + queue->size/2 : 1024;
	void **new_data = (void **)sgen_alloc_internal_dynamic (sizeof (void*) * new_size, queue->mem_type, TRUE);

	memcpy (new_data, queue->data, sizeof (void*) * queue->next_slot);
	sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
	queue->data = new_data;
	queue->size = new_size;
	SGEN_LOG (4, "Reallocated pointer queue to size: %lu", new_size);
}

gboolean
sgen_pointer_queue_will_grow (SgenPointerQueue *queue)
{
	return queue->next_slot >= queue->size;
}

void
sgen_pointer_queue_add (SgenPointerQueue *queue, void *ptr)
{
	if (sgen_pointer_queue_will_grow (queue))
		realloc_queue (queue);

	queue->data [queue->next_slot++] = ptr;
}

void*
sgen_pointer_queue_pop (SgenPointerQueue *queue)
{
	g_assert (queue->next_slot);

	return queue->data [--queue->next_slot];
}

size_t
sgen_pointer_queue_search (SgenPointerQueue *queue, void *addr)
{
	size_t first = 0, last = queue->next_slot;
	while (first < last) {
		size_t middle = first + ((last - first) >> 1);
		if (addr <= queue->data [middle])
			last = middle;
		else
			first = middle + 1;
	}
	g_assert (first == last);
	return first;
}

/*
 * Removes all NULL pointers from the queue.
 */
void
sgen_pointer_queue_remove_nulls (SgenPointerQueue *queue)
{
	void **start, **cur, **end;
	start = cur = queue->data;
	end = queue->data + queue->next_slot;
	while (cur < end) {
		if (*cur)
			*start++ = *cur++;
		else
			++cur;
	}
	queue->next_slot = start - queue->data;
}

/*
 * Sorts the pointers in the queue, then removes duplicates.
 */
void
sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
{
	void **start, **cur, **end;
	/* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
	/* it may be better to keep ranges of pinned memory instead of individually pinning objects */
	SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
	if (queue->next_slot > 1)
		sgen_sort_addresses (queue->data, queue->next_slot);
	start = cur = queue->data;
	end = queue->data + queue->next_slot;
	while (cur < end) {
		*start = *cur++;
		while (cur < end && *start == *cur)
			cur++;
		start++;
	};
	queue->next_slot = start - queue->data;
	SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
}

/*
 * Does a linear search through the pointer queue to find `ptr`.  Returns the index if
 * found, otherwise (size_t)-1.
 */
size_t
sgen_pointer_queue_find (SgenPointerQueue *queue, void *ptr)
{
	size_t i;
	for (i = 0; i < queue->next_slot; ++i)
		if (queue->data [i] == ptr)
			return i;
	return (size_t)-1;
}

gboolean
sgen_pointer_queue_is_empty (SgenPointerQueue *queue)
{
	return !queue->next_slot;
}

void
sgen_pointer_queue_free (SgenPointerQueue *queue)
{
	sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
}

#endif