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