/src/ruby/id_table.c

Source
/* This file is included by symbol.c */

#include "id_table.h"

#ifndef ID_TABLE_DEBUG
#define ID_TABLE_DEBUG 0
#endif

#if ID_TABLE_DEBUG == 0
#undef NDEBUG
#define NDEBUG
#endif
#include "ruby_assert.h"

typedef rb_id_serial_t id_key_t;

static inline ID
key2id(id_key_t key)
{
    return rb_id_serial_to_id(key);
}

static inline id_key_t
id2key(ID id)
{
    return rb_id_to_serial(id);
}

/* simple open addressing with quadratic probing.
   uses mark-bit on collisions - need extra 1 bit,
   ID is strictly 3 bits larger than rb_id_serial_t */

typedef struct rb_id_item {
    id_key_t key;
#if SIZEOF_VALUE == 8
    int      collision;
#endif
    VALUE    val;
} item_t;

#if SIZEOF_VALUE == 8
#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key)
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items && (tbl)->items[i].key)
#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].collision)
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].collision = 1)
static inline void
ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
{
    tbl->items[i].key = key;
}
#else
#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key >> 1)
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key > 1)
#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].key & 1)
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].key |= 1)
static inline void
ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
{
    tbl->items[i].key = (key << 1) | ITEM_COLLIDED(tbl, i);
}
#endif

static inline int
round_capa(int capa)
{
    /* minsize is 4 */
    capa >>= 2;
    capa |= capa >> 1;
    capa |= capa >> 2;
    capa |= capa >> 4;
    capa |= capa >> 8;
    capa |= capa >> 16;
    return (capa + 1) << 2;
}

struct rb_id_table *
rb_id_table_init(struct rb_id_table *tbl, size_t s_capa)
{
    int capa = (int)s_capa;
    MEMZERO(tbl, struct rb_id_table, 1);
    if (capa > 0) {
        capa = round_capa(capa);
        tbl->capa = (int)capa;
        tbl->items = ZALLOC_N(item_t, capa);
    }
    return tbl;
}

struct rb_id_table *
rb_id_table_create(size_t capa)
{
    struct rb_id_table *tbl = ALLOC(struct rb_id_table);
    return rb_id_table_init(tbl, capa);
}

void
rb_id_table_free_items(struct rb_id_table *tbl)
{
    xfree(tbl->items);
}

void
rb_id_table_free(struct rb_id_table *tbl)
{
    xfree(tbl->items);
    xfree(tbl);
}

void
rb_id_table_clear(struct rb_id_table *tbl)
{
    tbl->num = 0;
    tbl->used = 0;
    MEMZERO(tbl->items, item_t, tbl->capa);
}

size_t
rb_id_table_size(const struct rb_id_table *tbl)
{
    return (size_t)tbl->num;
}

size_t
rb_id_table_memsize(const struct rb_id_table *tbl)
{
    return sizeof(item_t) * tbl->capa + sizeof(struct rb_id_table);
}

static int
hash_table_index(struct rb_id_table* tbl, id_key_t key)
{
    if (tbl->capa > 0) {
        int mask = tbl->capa - 1;
        int ix = key & mask;
        int d = 1;
        while (key != ITEM_GET_KEY(tbl, ix)) {
            if (!ITEM_COLLIDED(tbl, ix))
                return -1;
            ix = (ix + d) & mask;
            d++;
        }
        return ix;
    }
    return -1;
}

static void
hash_table_raw_insert(struct rb_id_table *tbl, id_key_t key, VALUE val)
{
    int mask = tbl->capa - 1;
    int ix = key & mask;
    int d = 1;
    RUBY_ASSERT(key != 0);
    while (ITEM_KEY_ISSET(tbl, ix)) {
        ITEM_SET_COLLIDED(tbl, ix);
        ix = (ix + d) & mask;
        d++;
    }
    tbl->num++;
    if (!ITEM_COLLIDED(tbl, ix)) {
        tbl->used++;
    }
    ITEM_SET_KEY(tbl, ix, key);
    tbl->items[ix].val = val;
}

static int
hash_delete_index(struct rb_id_table *tbl, int ix)
{
    if (ix >= 0) {
        if (!ITEM_COLLIDED(tbl, ix)) {
            tbl->used--;
        }
        tbl->num--;
        ITEM_SET_KEY(tbl, ix, 0);
        tbl->items[ix].val = 0;
        return TRUE;
    }
    else {
        return FALSE;
    }
}

static void
hash_table_extend(struct rb_id_table* tbl)
{
    if (tbl->used + (tbl->used >> 1) >= tbl->capa) {
        int new_cap = round_capa(tbl->num + (tbl->num >> 1));
        int i;
        item_t* old;
        struct rb_id_table tmp_tbl = {0, 0, 0};
        if (new_cap < tbl->capa) {
            new_cap = round_capa(tbl->used + (tbl->used >> 1));
        }
        tmp_tbl.capa = new_cap;
        tmp_tbl.items = ZALLOC_N(item_t, new_cap);
        for (i = 0; i < tbl->capa; i++) {
            id_key_t key = ITEM_GET_KEY(tbl, i);
            if (key != 0) {
                hash_table_raw_insert(&tmp_tbl, key, tbl->items[i].val);
            }
        }
        old = tbl->items;
        *tbl = tmp_tbl;
        xfree(old);
    }
}

#if ID_TABLE_DEBUG && 0
static void
hash_table_show(struct rb_id_table *tbl)
{
    const id_key_t *keys = tbl->keys;
    const int capa = tbl->capa;
    int i;

    fprintf(stderr, "tbl: %p (capa: %d, num: %d, used: %d)\n", tbl, tbl->capa, tbl->num, tbl->used);
    for (i=0; i<capa; i++) {
        if (ITEM_KEY_ISSET(tbl, i)) {
            fprintf(stderr, " -> [%d] %s %d\n", i, rb_id2name(key2id(keys[i])), (int)keys[i]);
        }
    }
}
#endif

int
rb_id_table_lookup(struct rb_id_table *tbl, ID id, VALUE *valp)
{
    id_key_t key = id2key(id);
    int index = hash_table_index(tbl, key);

    if (index >= 0) {
        *valp = tbl->items[index].val;
        return TRUE;
    }
    else {
        return FALSE;
    }
}

static int
rb_id_table_insert_key(struct rb_id_table *tbl, const id_key_t key, const VALUE val)
{
    const int index = hash_table_index(tbl, key);

    if (index >= 0) {
        tbl->items[index].val = val;
    }
    else {
        hash_table_extend(tbl);
        hash_table_raw_insert(tbl, key, val);
    }
    return TRUE;
}

int
rb_id_table_insert(struct rb_id_table *tbl, ID id, VALUE val)
{
    return rb_id_table_insert_key(tbl, id2key(id), val);
}

int
rb_id_table_delete(struct rb_id_table *tbl, ID id)
{
    const id_key_t key = id2key(id);
    int index = hash_table_index(tbl, key);
    return hash_delete_index(tbl, index);
}

void
rb_id_table_foreach(struct rb_id_table *tbl, rb_id_table_foreach_func_t *func, void *data)
{
    int i, capa = tbl->capa;

    for (i=0; i<capa; i++) {
        if (ITEM_KEY_ISSET(tbl, i)) {
            const id_key_t key = ITEM_GET_KEY(tbl, i);
            enum rb_id_table_iterator_result ret = (*func)(key2id(key), tbl->items[i].val, data);
            RUBY_ASSERT(key != 0);

            if (ret == ID_TABLE_DELETE)
                hash_delete_index(tbl, i);
            else if (ret == ID_TABLE_STOP)
                return;
        }
    }
}

void
rb_id_table_foreach_values(struct rb_id_table *tbl, rb_id_table_foreach_values_func_t *func, void *data)
{
    int i, capa = tbl->capa;

    if (!tbl->items) {
        return;
    }

    for (i=0; i<capa; i++) {
        if (ITEM_KEY_ISSET(tbl, i)) {
            enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);

            if (ret == ID_TABLE_DELETE)
                hash_delete_index(tbl, i);
            else if (ret == ID_TABLE_STOP)
                return;
        }
    }
}

void
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)
{
    int i, capa = tbl->capa;

    for (i = 0; i < capa; i++) {
        if (ITEM_KEY_ISSET(tbl, i)) {
            enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);

            if (ret == ID_TABLE_REPLACE) {
                VALUE val = tbl->items[i].val;
                ret = (*replace)(&val, data, TRUE);
                tbl->items[i].val = val;
            }

            if (ret == ID_TABLE_STOP)
                return;
        }
    }
}

static void
managed_id_table_free(void *data)
{
    struct rb_id_table *tbl = (struct rb_id_table *)data;
    rb_id_table_free_items(tbl);
}

static size_t
managed_id_table_memsize(const void *data)
{
    const struct rb_id_table *tbl = (const struct rb_id_table *)data;
    return rb_id_table_memsize(tbl) - sizeof(struct rb_id_table);
}

const rb_data_type_t rb_managed_id_table_type = {
    .wrap_struct_name = "VM/managed_id_table",
    .function = {
        .dmark = NULL, // Nothing to mark
        .dfree = managed_id_table_free,
        .dsize = managed_id_table_memsize,
    },
    .flags = RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_WB_PROTECTED | RUBY_TYPED_EMBEDDABLE,
};

static inline struct rb_id_table *
managed_id_table_ptr(VALUE obj)
{
    RUBY_ASSERT(RB_TYPE_P(obj, T_DATA));
    RUBY_ASSERT(rb_typeddata_inherited_p(RTYPEDDATA_TYPE(obj), &rb_managed_id_table_type));

    return RTYPEDDATA_GET_DATA(obj);
}

VALUE
rb_managed_id_table_create(const rb_data_type_t *type, size_t capa)
{
    struct rb_id_table *tbl;
    VALUE obj = TypedData_Make_Struct(0, struct rb_id_table, type, tbl);
    RB_OBJ_SET_SHAREABLE(obj);
    rb_id_table_init(tbl, capa); // NOTE: this can cause GC, so dmark and dsize need to check tbl->items
    return obj;
}

VALUE
rb_managed_id_table_new(size_t capa)
{
    return rb_managed_id_table_create(&rb_managed_id_table_type, capa);
}

static enum rb_id_table_iterator_result
managed_id_table_dup_i(ID id, VALUE val, void *data)
{
    struct rb_id_table *new_tbl = (struct rb_id_table *)data;
    rb_id_table_insert(new_tbl, id, val);
    return ID_TABLE_CONTINUE;
}

VALUE
rb_managed_id_table_dup(VALUE old_table)
{
    struct rb_id_table *new_tbl;
    VALUE obj = TypedData_Make_Struct(0, struct rb_id_table, RTYPEDDATA_TYPE(old_table), new_tbl);
    struct rb_id_table *old_tbl = managed_id_table_ptr(old_table);
    rb_id_table_init(new_tbl, old_tbl->num + 1);
    rb_id_table_foreach(old_tbl, managed_id_table_dup_i, new_tbl);
    return obj;
}

int
rb_managed_id_table_lookup(VALUE table, ID id, VALUE *valp)
{
    return rb_id_table_lookup(managed_id_table_ptr(table), id, valp);
}

int
rb_managed_id_table_insert(VALUE table, ID id, VALUE val)
{
    return rb_id_table_insert(managed_id_table_ptr(table), id, val);
}

size_t
rb_managed_id_table_size(VALUE table)
{
    return rb_id_table_size(managed_id_table_ptr(table));
}

void
rb_managed_id_table_foreach(VALUE table, rb_id_table_foreach_func_t *func, void *data)
{
    rb_id_table_foreach(managed_id_table_ptr(table), func, data);
}

void
rb_managed_id_table_foreach_values(VALUE table, rb_id_table_foreach_values_func_t *func, void *data)
{
    rb_id_table_foreach_values(managed_id_table_ptr(table), func, data);
}

int
rb_managed_id_table_delete(VALUE table, ID id)
{
    return rb_id_table_delete(managed_id_table_ptr(table), id);
}

Coverage Report

Created: 2026-03-31 07:30

Line	Count	Source
1		/* This file is included by symbol.c */
2
3		#include "id_table.h"
4
5		#ifndef ID_TABLE_DEBUG
6		#define ID_TABLE_DEBUG 0
7		#endif
8
9		#if ID_TABLE_DEBUG == 0
10		#undef NDEBUG
11		#define NDEBUG
12		#endif
13		#include "ruby_assert.h"
14
15		typedef rb_id_serial_t id_key_t;
16
17		static inline ID
18		key2id(id_key_t key)
19	6.75k	{
20	6.75k	return rb_id_serial_to_id(key);
21	6.75k	}
22
23		static inline id_key_t
24		id2key(ID id)
25	314k	{
26	314k	return rb_id_to_serial(id);
27	314k	}
28
29		/* simple open addressing with quadratic probing.
30		uses mark-bit on collisions - need extra 1 bit,
31		ID is strictly 3 bits larger than rb_id_serial_t */
32
33		typedef struct rb_id_item {
34		id_key_t key;
35		#if SIZEOF_VALUE == 8
36		int collision;
37		#endif
38		VALUE val;
39		} item_t;
40
41		#if SIZEOF_VALUE == 8
42	405k	#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key)
43	320M	#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items && (tbl)->items[i].key)
44	202k	#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].collision)
45	40.0k	#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].collision = 1)
46		static inline void
47		ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
48	63.6k	{
49	63.6k	tbl->items[i].key = key;
50	63.6k	}
51		#else
52		#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key >> 1)
53		#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key > 1)
54		#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].key & 1)
55		#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].key \|= 1)
56		static inline void
57		ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
58		{
59		tbl->items[i].key = (key << 1) \| ITEM_COLLIDED(tbl, i);
60		}
61		#endif
62
63		static inline int
64		round_capa(int capa)
65	6.47k	{
66		/* minsize is 4 */
67	6.47k	capa >>= 2;
68	6.47k	capa \|= capa >> 1;
69	6.47k	capa \|= capa >> 2;
70	6.47k	capa \|= capa >> 4;
71	6.47k	capa \|= capa >> 8;
72	6.47k	capa \|= capa >> 16;
73	6.47k	return (capa + 1) << 2;
74	6.47k	}
75
76		struct rb_id_table *
77		rb_id_table_init(struct rb_id_table *tbl, size_t s_capa)
78	7.31k	{
79	7.31k	int capa = (int)s_capa;
80	7.31k	MEMZERO(tbl, struct rb_id_table, 1);
81	7.31k	if (capa > 0) {
82	407	capa = round_capa(capa);
83	407	tbl->capa = (int)capa;
84	407	tbl->items = ZALLOC_N(item_t, capa);
85	407	}
86	7.31k	return tbl;
87	7.31k	}
88
89		struct rb_id_table *
90		rb_id_table_create(size_t capa)
91	6.90k	{
92	6.90k	struct rb_id_table *tbl = ALLOC(struct rb_id_table);
93	6.90k	return rb_id_table_init(tbl, capa);
94	6.90k	}
95
96		void
97		rb_id_table_free_items(struct rb_id_table *tbl)
98	0	{
99	0	xfree(tbl->items);
100	0	}
101
102		void
103		rb_id_table_free(struct rb_id_table *tbl)
104	9	{
105	9	xfree(tbl->items);
106	9	xfree(tbl);
107	9	}
108
109		void
110		rb_id_table_clear(struct rb_id_table *tbl)
111	0	{
112	0	tbl->num = 0;
113	0	tbl->used = 0;
114	0	MEMZERO(tbl->items, item_t, tbl->capa);
115	0	}
116
117		size_t
118		rb_id_table_size(const struct rb_id_table *tbl)
119	486	{
120	486	return (size_t)tbl->num;
121	486	}
122
123		size_t
124		rb_id_table_memsize(const struct rb_id_table *tbl)
125	0	{
126	0	return sizeof(item_t) * tbl->capa + sizeof(struct rb_id_table);
127	0	}
128
129		static int
130		hash_table_index(struct rb_id_table* tbl, id_key_t key)
131	314k	{
132	314k	if (tbl->capa > 0) {
133	294k	int mask = tbl->capa - 1;
134	294k	int ix = key & mask;
135	294k	int d = 1;
136	349k	while (key != ITEM_GET_KEY(tbl, ix)) {
137	138k	if (!ITEM_COLLIDED(tbl, ix))
138	84.2k	return -1;
139	54.3k	ix = (ix + d) & mask;
140	54.3k	d++;
141	54.3k	}
142	210k	return ix;
143	294k	}
144	20.3k	return -1;
145	314k	}
146
147		static void
148		hash_table_raw_insert(struct rb_id_table *tbl, id_key_t key, VALUE val)
149	63.3k	{
150	63.3k	int mask = tbl->capa - 1;
151	63.3k	int ix = key & mask;
152	63.3k	int d = 1;
153	63.3k	RUBY_ASSERT(key != 0);
154	103k	while (ITEM_KEY_ISSET(tbl, ix)) {
155	40.0k	ITEM_SET_COLLIDED(tbl, ix);
156	40.0k	ix = (ix + d) & mask;
157	40.0k	d++;
158	40.0k	}
159	63.3k	tbl->num++;
160	63.3k	if (!ITEM_COLLIDED(tbl, ix)) {
161	63.3k	tbl->used++;
162	63.3k	}
163	63.3k	ITEM_SET_KEY(tbl, ix, key);
164	63.3k	tbl->items[ix].val = val;
165	63.3k	}
166
167		static int
168		hash_delete_index(struct rb_id_table *tbl, int ix)
169	306	{
170	306	if (ix >= 0) {
171	306	if (!ITEM_COLLIDED(tbl, ix)) {
172	306	tbl->used--;
173	306	}
174	306	tbl->num--;
175	306	ITEM_SET_KEY(tbl, ix, 0);
176	306	tbl->items[ix].val = 0;
177	306	return TRUE;
178	306	}
179	0	else {
180	0	return FALSE;
181	0	}
182	306	}
183
184		static void
185		hash_table_extend(struct rb_id_table* tbl)
186	28.7k	{
187	28.7k	if (tbl->used + (tbl->used >> 1) >= tbl->capa) {
188	6.06k	int new_cap = round_capa(tbl->num + (tbl->num >> 1));
189	6.06k	int i;
190	6.06k	item_t* old;
191	6.06k	struct rb_id_table tmp_tbl = {0, 0, 0};
192	6.06k	if (new_cap < tbl->capa) {
193	0	new_cap = round_capa(tbl->used + (tbl->used >> 1));
194	0	}
195	6.06k	tmp_tbl.capa = new_cap;
196	6.06k	tmp_tbl.items = ZALLOC_N(item_t, new_cap);
197	55.8k	for (i = 0; i < tbl->capa; i++) {
198	49.7k	id_key_t key = ITEM_GET_KEY(tbl, i);
199	49.7k	if (key != 0) {
200	34.6k	hash_table_raw_insert(&tmp_tbl, key, tbl->items[i].val);
201	34.6k	}
202	49.7k	}
203	6.06k	old = tbl->items;
204	6.06k	*tbl = tmp_tbl;
205	6.06k	xfree(old);
206	6.06k	}
207	28.7k	}
208
209		#if ID_TABLE_DEBUG && 0
210		static void
211		hash_table_show(struct rb_id_table *tbl)
212		{
213		const id_key_t *keys = tbl->keys;
214		const int capa = tbl->capa;
215		int i;
216
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]);
221		}
222		}
223		}
224		#endif
225
226		int
227		rb_id_table_lookup(struct rb_id_table tbl, ID id, VALUE valp)
228	286k	{
229	286k	id_key_t key = id2key(id);
230	286k	int index = hash_table_index(tbl, key);
231
232	286k	if (index >= 0) {
233	210k	*valp = tbl->items[index].val;
234	210k	return TRUE;
235	210k	}
236	75.8k	else {
237	75.8k	return FALSE;
238	75.8k	}
239	286k	}
240
241		static int
242		rb_id_table_insert_key(struct rb_id_table *tbl, const id_key_t key, const VALUE val)
243	28.7k	{
244	28.7k	const int index = hash_table_index(tbl, key);
245
246	28.7k	if (index >= 0) {
247	27	tbl->items[index].val = val;
248	27	}
249	28.7k	else {
250	28.7k	hash_table_extend(tbl);
251	28.7k	hash_table_raw_insert(tbl, key, val);
252	28.7k	}
253	28.7k	return TRUE;
254	28.7k	}
255
256		int
257		rb_id_table_insert(struct rb_id_table *tbl, ID id, VALUE val)
258	28.7k	{
259	28.7k	return rb_id_table_insert_key(tbl, id2key(id), val);
260	28.7k	}
261
262		int
263		rb_id_table_delete(struct rb_id_table *tbl, ID id)
264	0	{
265	0	const id_key_t key = id2key(id);
266	0	int index = hash_table_index(tbl, key);
267	0	return hash_delete_index(tbl, index);
268	0	}
269
270		void
271		rb_id_table_foreach(struct rb_id_table tbl, rb_id_table_foreach_func_t func, void *data)
272	189	{
273	189	int i, capa = tbl->capa;
274
275	15.0k	for (i=0; i<capa; i++) {
276	14.9k	if (ITEM_KEY_ISSET(tbl, i)) {
277	6.75k	const id_key_t key = ITEM_GET_KEY(tbl, i);
278	6.75k	enum rb_id_table_iterator_result ret = (*func)(key2id(key), tbl->items[i].val, data);
279	6.75k	RUBY_ASSERT(key != 0);
280
281	6.75k	if (ret == ID_TABLE_DELETE)
282	0	hash_delete_index(tbl, i);
283	6.75k	else if (ret == ID_TABLE_STOP)
284	0	return;
285	6.75k	}
286	14.9k	}
287	189	}
288
289		void
290		rb_id_table_foreach_values(struct rb_id_table tbl, rb_id_table_foreach_values_func_t func, void *data)
291	36.9M	{
292	36.9M	int i, capa = tbl->capa;
293
294	36.9M	if (!tbl->items) {
295	19.9M	return;
296	19.9M	}
297
298	337M	for (i=0; i<capa; i++) {
299	320M	if (ITEM_KEY_ISSET(tbl, i)) {
300	143M	enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
301
302	143M	if (ret == ID_TABLE_DELETE)
303	306	hash_delete_index(tbl, i);
304	143M	else if (ret == ID_TABLE_STOP)
305	0	return;
306	143M	}
307	320M	}
308	17.0M	}
309
310		void
311		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)
312	0	{
313	0	int i, capa = tbl->capa;
314
315	0	for (i = 0; i < capa; i++) {
316	0	if (ITEM_KEY_ISSET(tbl, i)) {
317	0	enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
318
319	0	if (ret == ID_TABLE_REPLACE) {
320	0	VALUE val = tbl->items[i].val;
321	0	ret = (*replace)(&val, data, TRUE);
322	0	tbl->items[i].val = val;
323	0	}
324
325	0	if (ret == ID_TABLE_STOP)
326	0	return;
327	0	}
328	0	}
329	0	}
330
331		static void
332		managed_id_table_free(void *data)
333	0	{
334	0	struct rb_id_table tbl = (struct rb_id_table )data;
335	0	rb_id_table_free_items(tbl);
336	0	}
337
338		static size_t
339		managed_id_table_memsize(const void *data)
340	0	{
341	0	const struct rb_id_table tbl = (const struct rb_id_table )data;
342	0	return rb_id_table_memsize(tbl) - sizeof(struct rb_id_table);
343	0	}
344
345		const rb_data_type_t rb_managed_id_table_type = {
346		.wrap_struct_name = "VM/managed_id_table",
347		.function = {
348		.dmark = NULL, // Nothing to mark
349		.dfree = managed_id_table_free,
350		.dsize = managed_id_table_memsize,
351		},
352		.flags = RUBY_TYPED_FREE_IMMEDIATELY \| RUBY_TYPED_WB_PROTECTED \| RUBY_TYPED_EMBEDDABLE,
353		};
354
355		static inline struct rb_id_table *
356		managed_id_table_ptr(VALUE obj)
357	209k	{
358	209k	RUBY_ASSERT(RB_TYPE_P(obj, T_DATA));
359	209k	RUBY_ASSERT(rb_typeddata_inherited_p(RTYPEDDATA_TYPE(obj), &rb_managed_id_table_type));
360
361	209k	return RTYPEDDATA_GET_DATA(obj);
362	209k	}
363
364		VALUE
365		rb_managed_id_table_create(const rb_data_type_t *type, size_t capa)
366	398	{
367	398	struct rb_id_table *tbl;
368	398	VALUE obj = TypedData_Make_Struct(0, struct rb_id_table, type, tbl);
369	398	RB_OBJ_SET_SHAREABLE(obj);
370	398	rb_id_table_init(tbl, capa); // NOTE: this can cause GC, so dmark and dsize need to check tbl->items
371	398	return obj;
372	398	}
373
374		VALUE
375		rb_managed_id_table_new(size_t capa)
376	12	{
377	12	return rb_managed_id_table_create(&rb_managed_id_table_type, capa);
378	12	}
379
380		static enum rb_id_table_iterator_result
381		managed_id_table_dup_i(ID id, VALUE val, void *data)
382	0	{
383	0	struct rb_id_table new_tbl = (struct rb_id_table )data;
384	0	rb_id_table_insert(new_tbl, id, val);
385	0	return ID_TABLE_CONTINUE;
386	0	}
387
388		VALUE
389		rb_managed_id_table_dup(VALUE old_table)
390	0	{
391	0	struct rb_id_table *new_tbl;
392	0	VALUE obj = TypedData_Make_Struct(0, struct rb_id_table, RTYPEDDATA_TYPE(old_table), new_tbl);
393	0	struct rb_id_table *old_tbl = managed_id_table_ptr(old_table);
394	0	rb_id_table_init(new_tbl, old_tbl->num + 1);
395	0	rb_id_table_foreach(old_tbl, managed_id_table_dup_i, new_tbl);
396	0	return obj;
397	0	}
398
399		int
400		rb_managed_id_table_lookup(VALUE table, ID id, VALUE *valp)
401	208k	{
402	208k	return rb_id_table_lookup(managed_id_table_ptr(table), id, valp);
403	208k	}
404
405		int
406		rb_managed_id_table_insert(VALUE table, ID id, VALUE val)
407	621	{
408	621	return rb_id_table_insert(managed_id_table_ptr(table), id, val);
409	621	}
410
411		size_t
412		rb_managed_id_table_size(VALUE table)
413	0	{
414	0	return rb_id_table_size(managed_id_table_ptr(table));
415	0	}
416
417		void
418		rb_managed_id_table_foreach(VALUE table, rb_id_table_foreach_func_t func, void data)
419	0	{
420	0	rb_id_table_foreach(managed_id_table_ptr(table), func, data);
421	0	}
422
423		void
424		rb_managed_id_table_foreach_values(VALUE table, rb_id_table_foreach_values_func_t func, void data)
425	0	{
426	0	rb_id_table_foreach_values(managed_id_table_ptr(table), func, data);
427	0	}
428
429		int
430		rb_managed_id_table_delete(VALUE table, ID id)
431	0	{
432	0	return rb_id_table_delete(managed_id_table_ptr(table), id);
433	0	}