6 #define ID_TABLE_DEBUG 0
9 #if ID_TABLE_DEBUG == 0
13 #include "ruby_assert.h"
15 typedef rb_id_serial_t id_key_t;
20 return rb_id_serial_to_id(key);
23 static inline id_key_t
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)
54 ITEM_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)
64 ITEM_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;
89 tbl->capa = (int)
capa;
96 rb_id_table_create(
size_t capa)
99 return rb_id_table_init(tbl, (
int)
capa);
120 return (
size_t)tbl->num;
130 hash_table_index(
struct rb_id_table* tbl, id_key_t key)
133 int mask = tbl->capa - 1;
136 while (key != ITEM_GET_KEY(tbl, ix)) {
137 if (!ITEM_COLLIDED(tbl, ix))
139 ix = (ix + d) & mask;
150 int mask = tbl->capa - 1;
154 while (ITEM_KEY_ISSET(tbl, ix)) {
155 ITEM_SET_COLLIDED(tbl, ix);
156 ix = (ix + d) & mask;
160 if (!ITEM_COLLIDED(tbl, ix)) {
163 ITEM_SET_KEY(tbl, ix, key);
164 tbl->items[ix].val = val;
171 if (!ITEM_COLLIDED(tbl, ix)) {
175 ITEM_SET_KEY(tbl, ix, 0);
176 tbl->items[ix].val = 0;
187 if (tbl->used + (tbl->used >> 1) >= tbl->capa) {
188 int new_cap = round_capa(tbl->num + (tbl->num >> 1));
192 if (new_cap < tbl->
capa) {
193 new_cap = round_capa(tbl->used + (tbl->used >> 1));
195 tmp_tbl.capa = new_cap;
197 for (i = 0; i < tbl->capa; i++) {
198 id_key_t key = ITEM_GET_KEY(tbl, i);
200 hash_table_raw_insert(&tmp_tbl, key, tbl->items[i].val);
209 #if ID_TABLE_DEBUG && 0
213 const id_key_t *keys = tbl->keys;
214 const int capa = tbl->capa;
217 fprintf(stderr,
"tbl: %p (capa: %d, num: %d, used: %d)\n", tbl, tbl->capa, tbl->num, tbl->used);
218 for (i=0; i<
capa; i++) {
219 if (ITEM_KEY_ISSET(tbl, i)) {
220 fprintf(stderr,
" -> [%d] %s %d\n", i,
rb_id2name(key2id(keys[i])), (
int)keys[i]);
229 id_key_t key = id2key(
id);
230 int index = hash_table_index(tbl, key);
233 *valp = tbl->items[index].val;
242 rb_id_table_insert_key(
struct rb_id_table *tbl,
const id_key_t key,
const VALUE val)
244 const int index = hash_table_index(tbl, key);
247 tbl->items[index].val = val;
250 hash_table_extend(tbl);
251 hash_table_raw_insert(tbl, key, val);
259 return rb_id_table_insert_key(tbl, id2key(
id), val);
265 const id_key_t key = id2key(
id);
266 int index = hash_table_index(tbl, key);
267 return hash_delete_index(tbl, index);
271 rb_id_table_foreach(
struct rb_id_table *tbl, rb_id_table_foreach_func_t *func,
void *data)
273 int i,
capa = tbl->capa;
275 for (i=0; i<
capa; i++) {
276 if (ITEM_KEY_ISSET(tbl, i)) {
277 const id_key_t key = ITEM_GET_KEY(tbl, i);
278 enum rb_id_table_iterator_result ret = (*func)(key2id(key), tbl->items[i].val, data);
281 if (ret == ID_TABLE_DELETE)
282 hash_delete_index(tbl, i);
283 else if (ret == ID_TABLE_STOP)
290 rb_id_table_foreach_values(
struct rb_id_table *tbl, rb_id_table_foreach_values_func_t *func,
void *data)
292 int i,
capa = tbl->capa;
294 for (i=0; i<
capa; i++) {
295 if (ITEM_KEY_ISSET(tbl, i)) {
296 enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
298 if (ret == ID_TABLE_DELETE)
299 hash_delete_index(tbl, i);
300 else if (ret == ID_TABLE_STOP)
307 rb_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)
309 int i,
capa = tbl->capa;
311 for (i = 0; i <
capa; i++) {
312 if (ITEM_KEY_ISSET(tbl, i)) {
313 enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
315 if (ret == ID_TABLE_REPLACE) {
316 VALUE val = tbl->items[i].val;
317 ret = (*replace)(&val, data, TRUE);
318 tbl->items[i].val = val;
321 if (ret == ID_TABLE_STOP)
#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 ZALLOC_N
Old name of RB_ZALLOC_N.
const char * rb_id2name(ID id)
Retrieves the name mapped to the given id.
int capa
Designed capacity of the buffer.
#define MEMZERO(p, type, n)
Handy macro to erase a region of memory.
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
uintptr_t VALUE
Type that represents a Ruby object.