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 void
  55 sgen_pointer_queue_add (SgenPointerQueue *queue, void *ptr)
  56 {
  57         if (queue->next_slot >= queue->size)
  58                 realloc_queue (queue);
  59
  60         queue->data [queue->next_slot++] = ptr;
  61 }
  62
  63 void*
  64 sgen_pointer_queue_pop (SgenPointerQueue *queue)
  65 {
  66         g_assert (queue->next_slot);
  67
  68         return queue->data [--queue->next_slot];
  69 }
  70
  71 size_t
  72 sgen_pointer_queue_search (SgenPointerQueue *queue, void *addr)
  73 {
  74         size_t first = 0, last = queue->next_slot;
  75         while (first < last) {
  76                 size_t middle = first + ((last - first) >> 1);
  77                 if (addr <= queue->data [middle])
  78                         last = middle;
  79                 else
  80                         first = middle + 1;
  81         }
  82         g_assert (first == last);
  83         return first;
  84 }
  85
  86 /*
  87  * Removes all NULL pointers from the queue.
  88  */
  89 void
  90 sgen_pointer_queue_remove_nulls (SgenPointerQueue *queue)
  91 {
  92         void **start, **cur, **end;
  93         start = cur = queue->data;
  94         end = queue->data + queue->next_slot;
  95         while (cur < end) {
  96                 if (*cur)
  97                         *start++ = *cur++;
  98                 else
  99                         ++cur;
 100         }
 101         queue->next_slot = start - queue->data;
 102 }
 103
 104 /*
 105  * Sorts the pointers in the queue, then removes duplicates.
 106  */
 107 void
 108 sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
 109 {
 110         void **start, **cur, **end;
 111         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
 112         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
 113         SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
 114         if (queue->next_slot > 1)
 115                 sgen_sort_addresses (queue->data, queue->next_slot);
 116         start = cur = queue->data;
 117         end = queue->data + queue->next_slot;
 118         while (cur < end) {
 119                 *start = *cur++;
 120                 while (cur < end && *start == *cur)
 121                         cur++;
 122                 start++;
 123         };
 124         queue->next_slot = start - queue->data;
 125         SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
 126 }
 127
 128 /*
 129  * Does a linear search through the pointer queue to find `ptr`.  Returns the index if
 130  * found, otherwise (size_t)-1.
 131  */
 132 size_t
 133 sgen_pointer_queue_find (SgenPointerQueue *queue, void *ptr)
 134 {
 135         size_t i;
 136         for (i = 0; i < queue->next_slot; ++i)
 137                 if (queue->data [i] == ptr)
 138                         return i;
 139         return (size_t)-1;
 140 }
 141
 142 gboolean
 143 sgen_pointer_queue_is_empty (SgenPointerQueue *queue)
 144 {
 145         return !queue->next_slot;
 146 }
 147
 148 void
 149 sgen_pointer_queue_free (SgenPointerQueue *queue)
 150 {
 151         sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, queue->mem_type);
 152 }
 153
 154 #endif