mono/metadata/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  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License 2.0 as published by the Free Software Foundation;
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License 2.0 along with this library; if not, write to the Free
  17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #include "utils/mono-compiler.h"
  21 #include "metadata/sgen-gc.h"
  22 #include "metadata/sgen-pointer-queue.h"
  23
  24 #ifdef HAVE_SGEN_GC
  25
  26 void
  27 sgen_pointer_queue_clear (SgenPointerQueue *queue)
  28 {
  29         queue->next_slot = 0;
  30 }
  31
  32 void
  33 sgen_pointer_queue_init (SgenPointerQueue *queue, int mem_type)
  34 {
  35         queue->next_slot = 0;
  36         queue->size = 0;
  37         queue->data = NULL;
  38         queue->mem_type = mem_type;
  39 }
  40
  41 static void
  42 realloc_queue (SgenPointerQueue *queue)
  43 {
  44         size_t new_size = queue->size ? queue->size + queue->size/2 : 1024;
  45         void **new_data = sgen_alloc_internal_dynamic (sizeof (void*) * new_size, queue->mem_type, TRUE);
  46
  47         memcpy (new_data, queue->data, sizeof (void*) * queue->next_slot);
  48         sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
  49         queue->data = new_data;
  50         queue->size = new_size;
  51         SGEN_LOG (4, "Reallocated pointer queue to size: %lu", new_size);
  52 }
  53
  54 gboolean
  55 sgen_pointer_queue_will_grow (SgenPointerQueue *queue)
  56 {
  57         return queue->next_slot >= queue->size;
  58 }
  59
  60 void
  61 sgen_pointer_queue_add (SgenPointerQueue *queue, void *ptr)
  62 {
  63         if (sgen_pointer_queue_will_grow (queue))
  64                 realloc_queue (queue);
  65
  66         queue->data [queue->next_slot++] = ptr;
  67 }
  68
  69 void*
  70 sgen_pointer_queue_pop (SgenPointerQueue *queue)
  71 {
  72         g_assert (queue->next_slot);
  73
  74         return queue->data [--queue->next_slot];
  75 }
  76
  77 size_t
  78 sgen_pointer_queue_search (SgenPointerQueue *queue, void *addr)
  79 {
  80         size_t first = 0, last = queue->next_slot;
  81         while (first < last) {
  82                 size_t middle = first + ((last - first) >> 1);
  83                 if (addr <= queue->data [middle])
  84                         last = middle;
  85                 else
  86                         first = middle + 1;
  87         }
  88         g_assert (first == last);
  89         return first;
  90 }
  91
  92 /*
  93  * Removes all NULL pointers from the queue.
  94  */
  95 void
  96 sgen_pointer_queue_remove_nulls (SgenPointerQueue *queue)
  97 {
  98         void **start, **cur, **end;
  99         start = cur = queue->data;
 100         end = queue->data + queue->next_slot;
 101         while (cur < end) {
 102                 if (*cur)
 103                         *start++ = *cur++;
 104                 else
 105                         ++cur;
 106         }
 107         queue->next_slot = start - queue->data;
 108 }
 109
 110 /*
 111  * Sorts the pointers in the queue, then removes duplicates.
 112  */
 113 void
 114 sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
 115 {
 116         void **start, **cur, **end;
 117         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
 118         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
 119         SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
 120         if (queue->next_slot > 1)
 121                 sgen_sort_addresses (queue->data, queue->next_slot);
 122         start = cur = queue->data;
 123         end = queue->data + queue->next_slot;
 124         while (cur < end) {
 125                 *start = *cur++;
 126                 while (cur < end && *start == *cur)
 127                         cur++;
 128                 start++;
 129         };
 130         queue->next_slot = start - queue->data;
 131         SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
 132 }
 133
 134 /*
 135  * Does a linear search through the pointer queue to find `ptr`.  Returns the index if
 136  * found, otherwise (size_t)-1.
 137  */
 138 size_t
 139 sgen_pointer_queue_find (SgenPointerQueue *queue, void *ptr)
 140 {
 141         size_t i;
 142         for (i = 0; i < queue->next_slot; ++i)
 143                 if (queue->data [i] == ptr)
 144                         return i;
 145         return (size_t)-1;
 146 }
 147
 148 gboolean
 149 sgen_pointer_queue_is_empty (SgenPointerQueue *queue)
 150 {
 151         return !queue->next_slot;
 152 }
 153
 154 void
 155 sgen_pointer_queue_free (SgenPointerQueue *queue)
 156 {
 157         sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
 158 }
 159
 160 #endif