3 * A pointer queue that can be sorted.
5 * Copyright (C) 2014 Xamarin Inc
7 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
14 #include "mono/sgen/sgen-gc.h"
15 #include "mono/sgen/sgen-pointer-queue.h"
18 sgen_pointer_queue_clear (SgenPointerQueue *queue)
24 sgen_pointer_queue_init (SgenPointerQueue *queue, int mem_type)
29 queue->mem_type = mem_type;
33 realloc_queue (SgenPointerQueue *queue)
35 size_t new_size = queue->size ? queue->size + queue->size/2 : 1024;
36 void **new_data = (void **)sgen_alloc_internal_dynamic (sizeof (void*) * new_size, queue->mem_type, TRUE);
38 memcpy (new_data, queue->data, sizeof (void*) * queue->next_slot);
39 sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
40 queue->data = new_data;
41 queue->size = new_size;
42 SGEN_LOG (4, "Reallocated pointer queue to size: %lu", new_size);
46 sgen_pointer_queue_will_grow (SgenPointerQueue *queue)
48 return queue->next_slot >= queue->size;
52 sgen_pointer_queue_add (SgenPointerQueue *queue, void *ptr)
54 if (sgen_pointer_queue_will_grow (queue))
55 realloc_queue (queue);
57 queue->data [queue->next_slot++] = ptr;
61 sgen_pointer_queue_pop (SgenPointerQueue *queue)
63 g_assert (queue->next_slot);
65 return queue->data [--queue->next_slot];
69 sgen_pointer_queue_search (SgenPointerQueue *queue, void *addr)
71 size_t first = 0, last = queue->next_slot;
72 while (first < last) {
73 size_t middle = first + ((last - first) >> 1);
74 if (addr <= queue->data [middle])
79 g_assert (first == last);
84 * Removes all NULL pointers from the queue.
87 sgen_pointer_queue_remove_nulls (SgenPointerQueue *queue)
89 void **start, **cur, **end;
90 start = cur = queue->data;
91 end = queue->data + queue->next_slot;
98 queue->next_slot = start - queue->data;
102 * Sorts the pointers in the queue, then removes duplicates.
105 sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
107 void **start, **cur, **end;
108 /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
109 /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
110 SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
111 if (queue->next_slot > 1)
112 sgen_sort_addresses (queue->data, queue->next_slot);
113 start = cur = queue->data;
114 end = queue->data + queue->next_slot;
117 while (cur < end && *start == *cur)
121 queue->next_slot = start - queue->data;
122 SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
126 * Does a linear search through the pointer queue to find `ptr`. Returns the index if
127 * found, otherwise (size_t)-1.
130 sgen_pointer_queue_find (SgenPointerQueue *queue, void *ptr)
133 for (i = 0; i < queue->next_slot; ++i)
134 if (queue->data [i] == ptr)
140 sgen_pointer_queue_is_empty (SgenPointerQueue *queue)
142 return !queue->next_slot;
146 sgen_pointer_queue_free (SgenPointerQueue *queue)
148 sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);