2 * sgen-array-list.h: A pointer array that doesn't use reallocs.
4 * Copyright (C) 2016 Xamarin Inc
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;
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.
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.
20 #ifndef __MONO_SGEN_ARRAY_LIST_H__
21 #define __MONO_SGEN_ARRAY_LIST_H__
25 #define SGEN_ARRAY_LIST_BUCKETS (32)
26 #define SGEN_ARRAY_LIST_MIN_BUCKET_BITS (5)
27 #define SGEN_ARRAY_LIST_MIN_BUCKET_SIZE (1 << SGEN_ARRAY_LIST_MIN_BUCKET_BITS)
29 typedef void (*SgenArrayListBucketAllocCallback
) (gpointer
*bucket
, guint32 new_bucket_size
, gboolean alloc
);
30 typedef gboolean (*SgenArrayListIsSlotSetFunc
) (volatile gpointer
*slot
);
31 typedef gboolean (*SgenArrayListSetSlotFunc
) (volatile gpointer
*slot
, gpointer ptr
, int data
);
34 * 'entries' is an array of pointers to buckets of increasing size. The first
35 * bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
38 * |-------|-- MIN_BUCKET_SIZE
40 * [1] -> xxxxxxxxxxxxxxxx
41 * [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
44 * 'slot_hint' denotes the position of the last allocation, so that the
45 * whole array needn't be searched on every allocation.
47 * The size of the spine, 'SGEN_ARRAY_LIST_BUCKETS', is chosen so
48 * that the maximum number of entries is no less than G_MAXUINT32.
52 volatile gpointer
*volatile entries
[SGEN_ARRAY_LIST_BUCKETS
];
53 volatile guint32 capacity
;
54 volatile guint32 slot_hint
;
55 volatile guint32 next_slot
;
56 SgenArrayListBucketAllocCallback bucket_alloc_callback
;
57 SgenArrayListIsSlotSetFunc is_slot_set_func
;
58 SgenArrayListSetSlotFunc set_slot_func
;
59 int mem_type
; /* sgen internal mem type or -1 for malloc allocation */
63 * Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
64 * of the bucket containing a slot.
67 sgen_array_list_index_bucket (guint32 index
)
70 return CHAR_BIT
* sizeof (index
) - __builtin_clz (index
+ SGEN_ARRAY_LIST_MIN_BUCKET_SIZE
) - 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS
;
73 index
+= SGEN_ARRAY_LIST_MIN_BUCKET_SIZE
;
78 return count
- 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS
;
83 sgen_array_list_bucket_size (guint32 index
)
85 return 1 << (index
+ SGEN_ARRAY_LIST_MIN_BUCKET_BITS
);
89 sgen_array_list_bucketize (guint32 index
, guint32
*bucket
, guint32
*offset
)
91 *bucket
= sgen_array_list_index_bucket (index
);
92 *offset
= index
- sgen_array_list_bucket_size (*bucket
) + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE
;
95 static inline volatile gpointer
*
96 sgen_array_list_get_slot (SgenArrayList
*array
, guint32 index
)
98 guint32 bucket
, offset
;
100 SGEN_ASSERT (0, index
< array
->capacity
, "Why are we accessing an entry that is not allocated");
102 sgen_array_list_bucketize (index
, &bucket
, &offset
);
103 return &(array
->entries
[bucket
] [offset
]);
106 #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 #define SGEN_ARRAY_LIST_FOREACH_SLOT(array, slot) { \
109 guint32 __bucket, __offset; \
110 const guint32 __max_bucket = sgen_array_list_index_bucket ((array)->capacity); \
111 guint32 __index = 0; \
112 const guint32 __next_slot = (array)->next_slot; \
113 for (__bucket = 0; __bucket < __max_bucket; ++__bucket) { \
114 volatile gpointer *__entries = (array)->entries [__bucket]; \
115 for (__offset = 0; __offset < sgen_array_list_bucket_size (__bucket); ++__offset, ++__index) { \
116 if (__index >= __next_slot) \
118 slot = &__entries [__offset];
120 #define SGEN_ARRAY_LIST_END_FOREACH_SLOT } } }
122 #define SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, begin, end, slot, index) { \
123 for (index = (begin); index < (end); index++) { \
124 guint32 __bucket, __offset; \
125 volatile gpointer *__entries; \
126 sgen_array_list_bucketize (index, &__bucket, &__offset); \
127 __entries = (array)->entries [__bucket]; \
128 slot = &__entries [__offset];
130 #define SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE } }
132 guint32
sgen_array_list_alloc_block (SgenArrayList
*array
, guint32 slots_to_add
);
133 guint32
sgen_array_list_add (SgenArrayList
*array
, gpointer ptr
, int data
, gboolean increase_size_before_set
);
134 guint32
sgen_array_list_find (SgenArrayList
*array
, gpointer ptr
);
135 void sgen_array_list_remove_nulls (SgenArrayList
*array
);