6#define ID_TABLE_DEBUG 0
13#include "ruby_assert.h"
15typedef rb_id_serial_t id_key_t;
20 return rb_id_serial_to_id(key);
26 return rb_id_to_serial(
id);
49#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key)
50#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key)
51#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].collision)
52#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].collision = 1)
54ITEM_SET_KEY(
struct rb_id_table *tbl,
int i, id_key_t key)
56 tbl->items[i].key = key;
59#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key >> 1)
60#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key > 1)
61#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].key & 1)
62#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].key |= 1)
64ITEM_SET_KEY(
struct rb_id_table *tbl,
int i, id_key_t key)
66 tbl->items[i].key = (key << 1) | ITEM_COLLIDED(tbl, i);
80 return (
capa + 1) << 2;
84rb_id_table_init(
struct rb_id_table *tbl,
size_t s_capa)
86 int capa = (int)s_capa;
90 tbl->capa = (int)
capa;
97rb_id_table_create(
size_t capa)
100 return rb_id_table_init(tbl,
capa);
127 return (
size_t)tbl->num;
137hash_table_index(
struct rb_id_table* tbl, id_key_t key)
140 int mask = tbl->capa - 1;
143 while (key != ITEM_GET_KEY(tbl, ix)) {
144 if (!ITEM_COLLIDED(tbl, ix))
146 ix = (ix + d) & mask;
157 int mask = tbl->capa - 1;
161 while (ITEM_KEY_ISSET(tbl, ix)) {
162 ITEM_SET_COLLIDED(tbl, ix);
163 ix = (ix + d) & mask;
167 if (!ITEM_COLLIDED(tbl, ix)) {
170 ITEM_SET_KEY(tbl, ix, key);
171 tbl->items[ix].val = val;
178 if (!ITEM_COLLIDED(tbl, ix)) {
182 ITEM_SET_KEY(tbl, ix, 0);
183 tbl->items[ix].val = 0;
194 if (tbl->used + (tbl->used >> 1) >= tbl->capa) {
195 int new_cap = round_capa(tbl->num + (tbl->num >> 1));
199 if (new_cap < tbl->
capa) {
200 new_cap = round_capa(tbl->used + (tbl->used >> 1));
202 tmp_tbl.capa = new_cap;
204 for (i = 0; i < tbl->capa; i++) {
205 id_key_t key = ITEM_GET_KEY(tbl, i);
207 hash_table_raw_insert(&tmp_tbl, key, tbl->items[i].val);
216#if ID_TABLE_DEBUG && 0
220 const id_key_t *keys = tbl->keys;
221 const int capa = tbl->capa;
224 fprintf(stderr,
"tbl: %p (capa: %d, num: %d, used: %d)\n", tbl, tbl->capa, tbl->num, tbl->used);
225 for (i=0; i<
capa; i++) {
226 if (ITEM_KEY_ISSET(tbl, i)) {
227 fprintf(stderr,
" -> [%d] %s %d\n", i, rb_id2name(key2id(keys[i])), (
int)keys[i]);
236 id_key_t key = id2key(
id);
237 int index = hash_table_index(tbl, key);
240 *valp = tbl->items[index].val;
249rb_id_table_insert_key(
struct rb_id_table *tbl,
const id_key_t key,
const VALUE val)
251 const int index = hash_table_index(tbl, key);
254 tbl->items[index].val = val;
257 hash_table_extend(tbl);
258 hash_table_raw_insert(tbl, key, val);
266 return rb_id_table_insert_key(tbl, id2key(
id), val);
272 const id_key_t key = id2key(
id);
273 int index = hash_table_index(tbl, key);
274 return hash_delete_index(tbl, index);
278rb_id_table_foreach(
struct rb_id_table *tbl, rb_id_table_foreach_func_t *func,
void *data)
280 int i,
capa = tbl->capa;
282 for (i=0; i<
capa; i++) {
283 if (ITEM_KEY_ISSET(tbl, i)) {
284 const id_key_t key = ITEM_GET_KEY(tbl, i);
285 enum rb_id_table_iterator_result ret = (*func)(key2id(key), tbl->items[i].val, data);
288 if (ret == ID_TABLE_DELETE)
289 hash_delete_index(tbl, i);
290 else if (ret == ID_TABLE_STOP)
297rb_id_table_foreach_values(
struct rb_id_table *tbl, rb_id_table_foreach_values_func_t *func,
void *data)
299 int i,
capa = tbl->capa;
301 for (i=0; i<
capa; i++) {
302 if (ITEM_KEY_ISSET(tbl, i)) {
303 enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
305 if (ret == ID_TABLE_DELETE)
306 hash_delete_index(tbl, i);
307 else if (ret == ID_TABLE_STOP)
314rb_id_table_foreach_values_with_replace(
struct rb_id_table *tbl, rb_id_table_foreach_values_func_t *func, rb_id_table_update_value_callback_func_t *replace,
void *data)
316 int i,
capa = tbl->capa;
318 for (i = 0; i <
capa; i++) {
319 if (ITEM_KEY_ISSET(tbl, i)) {
320 enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
322 if (ret == ID_TABLE_REPLACE) {
323 VALUE val = tbl->items[i].val;
324 ret = (*replace)(&val, data, TRUE);
325 tbl->items[i].val = val;
328 if (ret == ID_TABLE_STOP)
335managed_id_table_free(
void *data)
338 rb_id_table_free_items(tbl);
342managed_id_table_memsize(
const void *data)
345 return rb_id_table_memsize(tbl) -
sizeof(
struct rb_id_table);
353 .dsize = managed_id_table_memsize,
355 .flags = RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_WB_PROTECTED | RUBY_TYPED_EMBEDDABLE,
359managed_id_table_ptr(
VALUE obj)
361 return RTYPEDDATA_GET_DATA(obj);
365rb_managed_id_table_new(
size_t capa)
369 rb_id_table_init(tbl,
capa);
373static enum rb_id_table_iterator_result
374managed_id_table_dup_i(
ID id,
VALUE val,
void *data)
377 rb_id_table_insert(new_tbl,
id, val);
378 return ID_TABLE_CONTINUE;
382rb_managed_id_table_dup(
VALUE old_table)
389 struct rb_id_table *old_tbl = RTYPEDDATA_GET_DATA(old_table);
390 rb_id_table_init(new_tbl, old_tbl->num + 1);
391 rb_id_table_foreach(old_tbl, managed_id_table_dup_i, new_tbl);
396rb_managed_id_table_lookup(
VALUE table,
ID id,
VALUE *valp)
401 return rb_id_table_lookup(RTYPEDDATA_GET_DATA(table),
id, valp);
405rb_managed_id_table_insert(
VALUE table,
ID id,
VALUE val)
410 return rb_id_table_insert(RTYPEDDATA_GET_DATA(table),
id, val);
414rb_managed_id_table_size(
VALUE table)
419 return rb_id_table_size(RTYPEDDATA_GET_DATA(table));
423rb_managed_id_table_foreach(
VALUE table, rb_id_table_foreach_func_t *func,
void *data)
428 rb_id_table_foreach(RTYPEDDATA_GET_DATA(table), func, data);
#define RUBY_ASSERT(...)
Asserts that the given expression is truthy if and only if RUBY_DEBUG is truthy.
#define ALLOC
Old name of RB_ALLOC.
#define xfree
Old name of ruby_xfree.
#define T_DATA
Old name of RUBY_T_DATA.
#define ZALLOC_N
Old name of RB_ZALLOC_N.
int rb_typeddata_inherited_p(const rb_data_type_t *child, const rb_data_type_t *parent)
Checks for the domestic relationship between the two.
int capa
Designed capacity of the buffer.
#define MEMZERO(p, type, n)
Handy macro to erase a region of memory.
void(* RUBY_DATA_FUNC)(void *)
This is the type of callbacks registered to RData.
#define TypedData_Make_Struct(klass, type, data_type, sval)
Identical to TypedData_Wrap_Struct, except it allocates a new data region internally instead of takin...
static const struct rb_data_type_struct * RTYPEDDATA_TYPE(VALUE obj)
Queries for the type of given object.
This is the struct that holds necessary info for a struct.
const char * wrap_struct_name
Name of structs of this kind.
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
uintptr_t VALUE
Type that represents a Ruby object.
static bool RB_TYPE_P(VALUE obj, enum ruby_value_type t)
Queries if the given object is of given type.