mono/sgen/sgen-array-list.h

   1 /**
   2  * \file
   3  * A pointer array that doesn't use reallocs.
   4  *
   5  * Copyright (C) 2016 Xamarin Inc
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License 2.0 as published by the Free Software Foundation;
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public
  17  * License 2.0 along with this library; if not, write to the Free
  18  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  */
  20
  21 #ifndef __MONO_SGEN_ARRAY_LIST_H__
  22 #define __MONO_SGEN_ARRAY_LIST_H__
  23
  24 #include <glib.h>
  25
  26 #define SGEN_ARRAY_LIST_BUCKETS (32)
  27 #define SGEN_ARRAY_LIST_MIN_BUCKET_BITS (5)
  28 #define SGEN_ARRAY_LIST_MIN_BUCKET_SIZE (1 << SGEN_ARRAY_LIST_MIN_BUCKET_BITS)
  29
  30 typedef void (*SgenArrayListBucketAllocCallback) (gpointer *bucket, guint32 new_bucket_size, gboolean alloc);
  31 typedef gboolean (*SgenArrayListIsSlotSetFunc) (volatile gpointer *slot);
  32 typedef gboolean (*SgenArrayListSetSlotFunc) (volatile gpointer *slot, gpointer ptr, int data);
  33
  34 /*
  35  * 'entries' is an array of pointers to buckets of increasing size. The first
  36  * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
  37  * previous, i.e.:
  38  *
  39  *           |-------|-- MIN_BUCKET_SIZE
  40  *    [0] -> xxxxxxxx
  41  *    [1] -> xxxxxxxxxxxxxxxx
  42  *    [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  43  *    ...
  44  *
  45  * 'slot_hint' denotes the position of the last allocation, so that the
  46  * whole array needn't be searched on every allocation.
  47  *
  48  * The size of the spine, 'SGEN_ARRAY_LIST_BUCKETS', is chosen so
  49  * that the maximum number of entries is no less than G_MAXUINT32.
  50  */
  51
  52 typedef struct {
  53         volatile gpointer *volatile entries [SGEN_ARRAY_LIST_BUCKETS];
  54         volatile guint32 capacity;
  55         volatile guint32 slot_hint;
  56         volatile guint32 next_slot;
  57         SgenArrayListBucketAllocCallback bucket_alloc_callback;
  58         SgenArrayListIsSlotSetFunc is_slot_set_func;
  59         SgenArrayListSetSlotFunc set_slot_func;
  60         int mem_type; /* sgen internal mem type or -1 for malloc allocation */
  61 } SgenArrayList;
  62
  63 /*
  64  * Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
  65  * of the bucket containing a slot.
  66  */
  67 static inline guint32
  68 sgen_array_list_index_bucket (guint32 index)
  69 {
  70 #ifdef __GNUC__
  71         return CHAR_BIT * sizeof (index) - __builtin_clz (index + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE) - 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS;
  72 #else
  73         guint count = 0;
  74         index += SGEN_ARRAY_LIST_MIN_BUCKET_SIZE;
  75         while (index) {
  76                 ++count;
  77                 index >>= 1;
  78         }
  79         return count - 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS;
  80 #endif
  81 }
  82
  83 static inline guint32
  84 sgen_array_list_bucket_size (guint32 index)
  85 {
  86         return 1 << (index + SGEN_ARRAY_LIST_MIN_BUCKET_BITS);
  87 }
  88
  89 static inline void
  90 sgen_array_list_bucketize (guint32 index, guint32 *bucket, guint32 *offset)
  91 {
  92         *bucket = sgen_array_list_index_bucket (index);
  93         *offset = index - sgen_array_list_bucket_size (*bucket) + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE;
  94 }
  95
  96 static inline volatile gpointer *
  97 sgen_array_list_get_slot (SgenArrayList *array, guint32 index)
  98 {
  99         guint32 bucket, offset;
 100
 101         SGEN_ASSERT (0, index < array->capacity, "Why are we accessing an entry that is not allocated");
 102
 103         sgen_array_list_bucketize (index, &bucket, &offset);
 104         return &(array->entries [bucket] [offset]);
 105 }
 106
 107 #define SGEN_ARRAY_LIST_INIT(bucket_alloc_callback, is_slot_set_func, set_slot_func, mem_type)  { { NULL }, 0, 0, 0, (bucket_alloc_callback), (is_slot_set_func), (set_slot_func), (mem_type) }
 108
 109 #define SGEN_ARRAY_LIST_FOREACH_SLOT(array, slot) {                     \
 110         guint32 __bucket, __offset;                                     \
 111         const guint32 __max_bucket = sgen_array_list_index_bucket ((array)->capacity); \
 112         guint32 __index = 0;                                            \
 113         const guint32 __next_slot = (array)->next_slot;                 \
 114         for (__bucket = 0; __bucket < __max_bucket; ++__bucket) {       \
 115                 volatile gpointer *__entries = (array)->entries [__bucket]; \
 116                 for (__offset = 0; __offset < sgen_array_list_bucket_size (__bucket); ++__offset, ++__index) { \
 117                         if (__index >= __next_slot)                     \
 118                                 break;                                  \
 119                         slot = &__entries [__offset];
 120
 121 #define SGEN_ARRAY_LIST_END_FOREACH_SLOT        } } }
 122
 123 #define SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, begin, end, slot, index) {    \
 124         for (index = (begin); index < (end); index++) {         \
 125                 guint32 __bucket, __offset;                             \
 126                 volatile gpointer *__entries;                           \
 127                 sgen_array_list_bucketize (index, &__bucket, &__offset); \
 128                 __entries = (array)->entries [__bucket];                \
 129                 slot = &__entries [__offset];
 130
 131 #define SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE  } }
 132
 133 guint32 sgen_array_list_alloc_block (SgenArrayList *array, guint32 slots_to_add);
 134 guint32 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set);
 135 guint32 sgen_array_list_find (SgenArrayList *array, gpointer ptr);
 136 gboolean sgen_array_list_default_cas_setter (volatile gpointer *slot, gpointer ptr, int data);
 137 gboolean sgen_array_list_default_is_slot_set (volatile gpointer *slot);
 138 void sgen_array_list_remove_nulls (SgenArrayList *array);
 139
 140 #endif