mono/sgen/sgen-pointer-queue.c

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