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 void
  68 sgen_pointer_queue_sort_uniq (SgenPointerQueue *queue)
  69 {
  70         void **start, **cur, **end;
  71         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
  72         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
  73         SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue->next_slot);
  74         if (queue->next_slot > 1)
  75                 sgen_sort_addresses (queue->data, queue->next_slot);
  76         start = cur = queue->data;
  77         end = queue->data + queue->next_slot;
  78         while (cur < end) {
  79                 *start = *cur++;
  80                 while (*start == *cur && cur < end)
  81                         cur++;
  82                 start++;
  83         };
  84         queue->next_slot = start - queue->data;
  85         SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue->next_slot);
  86 }
  87
  88 #endif