/**
|
* \file
|
* A pointer array that doesn't use reallocs.
|
*
|
* Copyright (C) 2016 Xamarin Inc
|
*
|
* This library is free software; you can redistribute it and/or
|
* modify it under the terms of the GNU Library General Public
|
* License 2.0 as published by the Free Software Foundation;
|
*
|
* This library is distributed in the hope that it will be useful,
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
* Library General Public License for more details.
|
*
|
* You should have received a copy of the GNU Library General Public
|
* License 2.0 along with this library; if not, write to the Free
|
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
*/
|
|
#ifndef __MONO_SGEN_ARRAY_LIST_H__
|
#define __MONO_SGEN_ARRAY_LIST_H__
|
|
#include <glib.h>
|
|
#define SGEN_ARRAY_LIST_BUCKETS (32)
|
#define SGEN_ARRAY_LIST_MIN_BUCKET_BITS (5)
|
#define SGEN_ARRAY_LIST_MIN_BUCKET_SIZE (1 << SGEN_ARRAY_LIST_MIN_BUCKET_BITS)
|
|
typedef void (*SgenArrayListBucketAllocCallback) (gpointer *bucket, guint32 new_bucket_size, gboolean alloc);
|
typedef gboolean (*SgenArrayListIsSlotSetFunc) (volatile gpointer *slot);
|
typedef gboolean (*SgenArrayListSetSlotFunc) (volatile gpointer *slot, gpointer ptr, int data);
|
|
/*
|
* 'entries' is an array of pointers to buckets of increasing size. The first
|
* bucket has size 'MIN_BUCKET_SIZE', and each bucket is twice the size of the
|
* previous, i.e.:
|
*
|
* |-------|-- MIN_BUCKET_SIZE
|
* [0] -> xxxxxxxx
|
* [1] -> xxxxxxxxxxxxxxxx
|
* [2] -> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
|
* ...
|
*
|
* 'slot_hint' denotes the position of the last allocation, so that the
|
* whole array needn't be searched on every allocation.
|
*
|
* The size of the spine, 'SGEN_ARRAY_LIST_BUCKETS', is chosen so
|
* that the maximum number of entries is no less than G_MAXUINT32.
|
*/
|
|
typedef struct {
|
volatile gpointer *volatile entries [SGEN_ARRAY_LIST_BUCKETS];
|
volatile guint32 capacity;
|
volatile guint32 slot_hint;
|
volatile guint32 next_slot;
|
SgenArrayListBucketAllocCallback bucket_alloc_callback;
|
SgenArrayListIsSlotSetFunc is_slot_set_func;
|
SgenArrayListSetSlotFunc set_slot_func;
|
int mem_type; /* sgen internal mem type or -1 for malloc allocation */
|
} SgenArrayList;
|
|
/*
|
* Computes floor(log2(index + MIN_BUCKET_SIZE)) - 1, giving the index
|
* of the bucket containing a slot.
|
*/
|
static inline guint32
|
sgen_array_list_index_bucket (guint32 index)
|
{
|
#ifdef __GNUC__
|
return CHAR_BIT * sizeof (index) - __builtin_clz (index + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE) - 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS;
|
#else
|
guint count = 0;
|
index += SGEN_ARRAY_LIST_MIN_BUCKET_SIZE;
|
while (index) {
|
++count;
|
index >>= 1;
|
}
|
return count - 1 - SGEN_ARRAY_LIST_MIN_BUCKET_BITS;
|
#endif
|
}
|
|
static inline guint32
|
sgen_array_list_bucket_size (guint32 index)
|
{
|
return 1 << (index + SGEN_ARRAY_LIST_MIN_BUCKET_BITS);
|
}
|
|
static inline void
|
sgen_array_list_bucketize (guint32 index, guint32 *bucket, guint32 *offset)
|
{
|
*bucket = sgen_array_list_index_bucket (index);
|
*offset = index - sgen_array_list_bucket_size (*bucket) + SGEN_ARRAY_LIST_MIN_BUCKET_SIZE;
|
}
|
|
static inline volatile gpointer *
|
sgen_array_list_get_slot (SgenArrayList *array, guint32 index)
|
{
|
guint32 bucket, offset;
|
|
SGEN_ASSERT (0, index < array->capacity, "Why are we accessing an entry that is not allocated");
|
|
sgen_array_list_bucketize (index, &bucket, &offset);
|
return &(array->entries [bucket] [offset]);
|
}
|
|
#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) }
|
|
#define SGEN_ARRAY_LIST_FOREACH_SLOT(array, slot) { \
|
guint32 __bucket, __offset; \
|
const guint32 __max_bucket = sgen_array_list_index_bucket ((array)->capacity); \
|
guint32 __index = 0; \
|
const guint32 __next_slot = (array)->next_slot; \
|
for (__bucket = 0; __bucket < __max_bucket; ++__bucket) { \
|
volatile gpointer *__entries = (array)->entries [__bucket]; \
|
for (__offset = 0; __offset < sgen_array_list_bucket_size (__bucket); ++__offset, ++__index) { \
|
if (__index >= __next_slot) \
|
break; \
|
slot = &__entries [__offset];
|
|
#define SGEN_ARRAY_LIST_END_FOREACH_SLOT } } }
|
|
#define SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, begin, end, slot, index) { \
|
for (index = (begin); index < (end); index++) { \
|
guint32 __bucket, __offset; \
|
volatile gpointer *__entries; \
|
sgen_array_list_bucketize (index, &__bucket, &__offset); \
|
__entries = (array)->entries [__bucket]; \
|
slot = &__entries [__offset];
|
|
#define SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE } }
|
|
guint32 sgen_array_list_alloc_block (SgenArrayList *array, guint32 slots_to_add);
|
guint32 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set);
|
guint32 sgen_array_list_find (SgenArrayList *array, gpointer ptr);
|
gboolean sgen_array_list_default_cas_setter (volatile gpointer *slot, gpointer ptr, int data);
|
gboolean sgen_array_list_default_is_slot_set (volatile gpointer *slot);
|
void sgen_array_list_remove_nulls (SgenArrayList *array);
|
|
#endif
|
