mono/sgen/sgen-pointer-queue.c

   1 /*
   2  * sgen-pointer-queue.c: A pointer queue that can be sorted.
   3  *
   4  * Copyright (C) 2014 Xamarin Inc
   5  *
   6  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   7  */
   8
   9 #ifdef HAVE_SGEN_GC
  10
  11 #include <string.h>
  12
  13 #include "mono/sgen/sgen-gc.h"
  14 #include "mono/sgen/sgen-pointer-queue.h"
  15
  16 void
  17 sgen_pointer_queue_clear (SgenPointerQueue *queue)
  18 {
  19         queue->next_slot = 0;
  20 }
  21
  22 void
  23 sgen_pointer_queue_init (SgenPointerQueue *queue, int mem_type)
  24 {
  25         queue->next_slot = 0;
  26         queue->size = 0;
  27         queue->data = NULL;
  28         queue->mem_type = mem_type;
  29 }
  30
  31 static void
  32 realloc_queue (SgenPointerQueue *queue)
  33 {
  34         size_t new_size = queue->size ? queue->size + queue->size/2 : 1024;
  35         void **new_data = (void **)sgen_alloc_internal_dynamic (sizeof (void*) * new_size, queue->mem_type, TRUE);
  36
  37         memcpy (new_data, queue->data, sizeof (void*) * queue->next_slot);
  38         sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
  39         queue->data = new_data;
  40         queue->size = new_size;
  41         SGEN_LOG (4, "Reallocated pointer queue to size: %lu", new_size);
  42 }
  43
  44 gboolean
  45 sgen_pointer_queue_will_grow (SgenPointerQueue *queue)
  46 {
  47         return queue->next_slot >= queue->size;
  48 }
  49
  50 void
  51 sgen_pointer_queue_add (SgenPointerQueue *queue, void *ptr)
  52 {
  53         if (sgen_pointer_queue_will_grow (queue))
  54                 realloc_queue (queue);
  55
  56         queue->data [queue->next_slot++] = ptr;
  57 }
  58
  59 void*
  60 sgen_pointer_queue_pop (SgenPointerQueue *queue)
  61 {
  62         g_assert (queue->next_slot);
  63
  64         return queue->data [--queue->next_slot];
  65 }
  66
  67 size_t
  68 sgen_pointer_queue_search (SgenPointerQueue *queue, void *addr)
  69 {
  70         size_t first = 0, last = queue->next_slot;
  71         while (first < last) {
  72                 size_t middle = first + ((last - first) >> 1);
  73                 if (addr <= queue->data [middle])
  74                         last = middle;
  75                 else
  76                         first = middle + 1;
  77         }
  78         g_assert (first == last);
  79         return first;
  80 }
  81
  82 /*
  83  * Removes all NULL pointers from the queue.
  84  */
  85 void
  86 sgen_pointer_queue_remove_nulls (SgenPointerQueue *queue)
  87 {
  88         void **start, **cur, **end;
  89         start = cur = queue->data;
  90         end = queue->data + queue->next_slot;
  91         while (cur < end) {
  92                 if (*cur)
  93                         *start++ = *cur++;
  94                 else
  95                         ++cur;
  96         }
  97         queue->next_slot = start - queue->data;
  98 }
  99
 100 /*
 101  * Sorts the pointers in the queue, then removes duplicates.
 102  */
 103 void
 104 sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
 105 {
 106         void **start, **cur, **end;
 107         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
 108         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
 109         SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
 110         if (queue->next_slot > 1)
 111                 sgen_sort_addresses (queue->data, queue->next_slot);
 112         start = cur = queue->data;
 113         end = queue->data + queue->next_slot;
 114         while (cur < end) {
 115                 *start = *cur++;
 116                 while (cur < end && *start == *cur)
 117                         cur++;
 118                 start++;
 119         };
 120         queue->next_slot = start - queue->data;
 121         SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
 122 }
 123
 124 /*
 125  * Does a linear search through the pointer queue to find `ptr`.  Returns the index if
 126  * found, otherwise (size_t)-1.
 127  */
 128 size_t
 129 sgen_pointer_queue_find (SgenPointerQueue *queue, void *ptr)
 130 {
 131         size_t i;
 132         for (i = 0; i < queue->next_slot; ++i)
 133                 if (queue->data [i] == ptr)
 134                         return i;
 135         return (size_t)-1;
 136 }
 137
 138 gboolean
 139 sgen_pointer_queue_is_empty (SgenPointerQueue *queue)
 140 {
 141         return !queue->next_slot;
 142 }
 143
 144 void
 145 sgen_pointer_queue_free (SgenPointerQueue *queue)
 146 {
 147         sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
 148 }
 149
 150 #endif