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 static void
  32 realloc_queue (SgenPointerQueue *queue)
  33 {
  34         size_t new_size = queue->size ? queue->size + queue->size/2 : 1024;
  35         void **new_data = sgen_alloc_internal_dynamic (sizeof (void*) * new_size, INTERNAL_MEM_PIN_QUEUE, TRUE);
  36         memcpy (new_data, queue->data, sizeof (void*) * queue->next_slot);
  37         sgen_free_internal_dynamic (queue->data, sizeof (void*) * queue->size, INTERNAL_MEM_PIN_QUEUE);
  38         queue->data = new_data;
  39         queue->size = new_size;
  40         SGEN_LOG (4, "Reallocated pointer queue to size: %lu", new_size);
  41 }
  42
  43 void
  44 sgen_pointer_queue_add (SgenPointerQueue *queue, void *ptr)
  45 {
  46         if (queue->next_slot >= queue->size)
  47                 realloc_queue (queue);
  48
  49         queue->data [queue->next_slot++] = ptr;
  50 }
  51
  52 size_t
  53 sgen_pointer_queue_search (SgenPointerQueue *queue, void *addr)
  54 {
  55         size_t first = 0, last = queue->next_slot;
  56         while (first < last) {
  57                 size_t middle = first + ((last - first) >> 1);
  58                 if (addr <= queue->data [middle])
  59                         last = middle;
  60                 else
  61                         first = middle + 1;
  62         }
  63         g_assert (first == last);
  64         return first;
  65 }
  66
  67 /*
  68  * Removes all NULL pointers from the queue.
  69  */
  70 void
  71 sgen_pointer_queue_remove_nulls (SgenPointerQueue *queue)
  72 {
  73         void **start, **cur, **end;
  74         start = cur = queue->data;
  75         end = queue->data + queue->next_slot;
  76         while (cur < end) {
  77                 if (*cur)
  78                         *start++ = *cur++;
  79                 else
  80                         ++cur;
  81         }
  82         queue->next_slot = start - queue->data;
  83 }
  84
  85 /*
  86  * Sorts the pointers in the queue, then removes duplicates.
  87  */
  88 void
  89 sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
  90 {
  91         void **start, **cur, **end;
  92         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
  93         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
  94         SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
  95         if (queue->next_slot > 1)
  96                 sgen_sort_addresses (queue->data, queue->next_slot);
  97         start = cur = queue->data;
  98         end = queue->data + queue->next_slot;
  99         while (cur < end) {
 100                 *start = *cur++;
 101                 while (cur < end && *start == *cur)
 102                         cur++;
 103                 start++;
 104         };
 105         queue->next_slot = start - queue->data;
 106         SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
 107 }
 108
 109 /*
 110  * Does a linear search through the pointer queue to find `ptr`.  Returns the index if
 111  * found, otherwise (size_t)-1.
 112  */
 113 size_t
 114 sgen_pointer_queue_find (SgenPointerQueue *queue, void *ptr)
 115 {
 116         size_t i;
 117         for (i = 0; i < queue->next_slot; ++i)
 118                 if (queue->data [i] == ptr)
 119                         return i;
 120         return (size_t)-1;
 121 }
 122
 123 #endif