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