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  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   8  */
   9
  10 #ifndef __MONO_SGEN_ARRAY_LIST_H__
  11 #define __MONO_SGEN_ARRAY_LIST_H__
  12
  13 #include <glib.h>
  14
  15 #define SGEN_ARRAY_LIST_BUCKETS (32)
  16 #define SGEN_ARRAY_LIST_MIN_BUCKET_BITS (5)
  17 #define SGEN_ARRAY_LIST_MIN_BUCKET_SIZE (1 << SGEN_ARRAY_LIST_MIN_BUCKET_BITS)
  18
  19 typedef void (*SgenArrayListBucketAllocCallback) (gpointer *bucket, guint32 new_bucket_size, gboolean alloc);
  20 typedef gboolean (*SgenArrayListIsSlotSetFunc) (volatile gpointer *slot);
  21 typedef gboolean (*SgenArrayListSetSlotFunc) (volatile gpointer *slot, gpointer ptr, int data);
  22
  23 /*
  24  * 'entries' is an array of pointers to buckets of increasing size. The first
  25  * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
  26  * previous, i.e.:
  27  *
  28  *           |-------|-- MIN_BUCKET_SIZE
  29  *    [0] -> xxxxxxxx
  30  *    [1] -> xxxxxxxxxxxxxxxx
  31  *    [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  32  *    ...
  33  *
  34  * 'slot_hint' denotes the position of the last allocation, so that the
  35  * whole array needn't be searched on every allocation.
  36  *
  37  * The size of the spine, 'SGEN_ARRAY_LIST_BUCKETS', is chosen so
  38  * that the maximum number of entries is no less than G_MAXUINT32.
  39  */
  40
  41 typedef struct {
  42         volatile gpointer *volatile entries [SGEN_ARRAY_LIST_BUCKETS];
  43         volatile guint32 capacity;
  44         volatile guint32 slot_hint;
  45         volatile guint32 next_slot;
  46         SgenArrayListBucketAllocCallback bucket_alloc_callback;
  47         SgenArrayListIsSlotSetFunc is_slot_set_func;
  48         SgenArrayListSetSlotFunc set_slot_func;
  49         int mem_type; /* sgen internal mem type or -1 for malloc allocation */
  50 } SgenArrayList;
  51
  52 #if defined(__GNUC__)
  53 static inline guint32
  54 sgen_clz (guint32 x)
  55 {
  56         return __builtin_clz (x);
  57 }
  58 #elif !defined(ENABLE_MSVC_LZCNT) && defined(_MSC_VER)
  59 static inline guint32
  60 sgen_clz (guint32 x)
  61 {
  62         gulong leading_zero_bits;
  63         return _BitScanReverse (&leading_zero_bits, (gulong)x) ? 31 - leading_zero_bits : 32;
  64 }
  65 #elif defined(ENABLE_MSVC_LZCNT) && defined(_MSC_VER)
  66 static inline guint32
  67 sgen_clz (guint32 x)
  68 {
  69         return __lzcnt (x);
  70 }
  71 #else
  72 static inline guint32
  73 sgen_clz (guint32 x)
  74 {
  75         guint count = 0;
  76         while (x) {
  77                 ++count;
  78                 x >>= 1;
  79         }
  80         return 32 - count;
  81 }
  82 #endif
  83
  84 /*
  85  * Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
  86  * of the bucket containing a slot.
  87  */
  88 static inline guint32
  89 sgen_array_list_index_bucket (guint32 index)
  90 {
  91         return CHAR_BIT * sizeof (index) - sgen_clz (index + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE) - 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS;
  92 }
  93
  94 static inline guint32
  95 sgen_array_list_bucket_size (guint32 index)
  96 {
  97         return 1 << (index + SGEN_ARRAY_LIST_MIN_BUCKET_BITS);
  98 }
  99
 100 static inline void
 101 sgen_array_list_bucketize (guint32 index, guint32 *bucket, guint32 *offset)
 102 {
 103         *bucket = sgen_array_list_index_bucket (index);
 104         *offset = index - sgen_array_list_bucket_size (*bucket) + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE;
 105 }
 106
 107 static inline volatile gpointer *
 108 sgen_array_list_get_slot (SgenArrayList *array, guint32 index)
 109 {
 110         guint32 bucket, offset;
 111
 112         SGEN_ASSERT (0, index < array->capacity, "Why are we accessing an entry that is not allocated");
 113
 114         sgen_array_list_bucketize (index, &bucket, &offset);
 115         return &(array->entries [bucket] [offset]);
 116 }
 117
 118 #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) }
 119
 120 #define SGEN_ARRAY_LIST_FOREACH_SLOT(array, slot) {                     \
 121         guint32 __bucket, __offset;                                     \
 122         const guint32 __max_bucket = sgen_array_list_index_bucket ((array)->capacity); \
 123         guint32 __index = 0;                                            \
 124         const guint32 __next_slot = (array)->next_slot;                 \
 125         for (__bucket = 0; __bucket < __max_bucket; ++__bucket) {       \
 126                 volatile gpointer *__entries = (array)->entries [__bucket]; \
 127                 for (__offset = 0; __offset < sgen_array_list_bucket_size (__bucket); ++__offset, ++__index) { \
 128                         if (__index >= __next_slot)                     \
 129                                 break;                                  \
 130                         slot = &__entries [__offset];
 131
 132 #define SGEN_ARRAY_LIST_END_FOREACH_SLOT        } } }
 133
 134 #define SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, begin, end, slot, index) {    \
 135         for (index = (begin); index < (end); index++) {         \
 136                 guint32 __bucket, __offset;                             \
 137                 volatile gpointer *__entries;                           \
 138                 sgen_array_list_bucketize (index, &__bucket, &__offset); \
 139                 __entries = (array)->entries [__bucket];                \
 140                 slot = &__entries [__offset];
 141
 142 #define SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE  } }
 143
 144 guint32 sgen_array_list_alloc_block (SgenArrayList *array, guint32 slots_to_add);
 145 guint32 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set);
 146 guint32 sgen_array_list_find (SgenArrayList *array, gpointer ptr);
 147 gboolean sgen_array_list_default_cas_setter (volatile gpointer *slot, gpointer ptr, int data);
 148 gboolean sgen_array_list_default_is_slot_set (volatile gpointer *slot);
 149 void sgen_array_list_remove_nulls (SgenArrayList *array);
 150
 151 #endif