ruby-changes:45344
From: ko1 <ko1@a...>
Date: Wed, 25 Jan 2017 12:03:58 +0900 (JST)
Subject: [ruby-changes:45344] ko1:r57416 (trunk): swithc id_table data structure.
ko1 2017-01-25 12:03:52 +0900 (Wed, 25 Jan 2017) New Revision: 57416 https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=57416 Log: swithc id_table data structure. * id_table.c: swtich to "simple open addressing with quadratic probing" by Yura Sokolov. For more detail measurements, see [Feature #12180] * id_table.c: remove other algorithms to simplify the source code. Modified files: trunk/id_table.c Index: id_table.c =================================================================== --- id_table.c (revision 57415) +++ id_table.c (revision 57416) @@ -11,205 +11,8 @@ https://github.com/ruby/ruby/blob/trunk/id_table.c#L11 #endif #include "ruby_assert.h" -/* - * st - * 0: using st with debug information. - * 1: using st. - * array - * 11: simple array. ids = [ID1, ID2, ...], values = [val1, val2, ...] - * 12: simple array, and use rb_id_serial_t instead of ID. - * 13: simple array, and use rb_id_serial_t instead of ID. Swap recent access. - * 14: sorted array, and use rb_id_serial_t instead of ID. - * 15: sorted array, and use rb_id_serial_t instead of ID, linear small part. - * hash - * 21: funny falcon's Coalesced Hashing implementation [Feature #6962] - * 22: simple open addressing with quadratic probing. - * mix (array + hash) - * 31: array(12) (capa <= 32) + hash(22) - * 32: array(14) (capa <= 32) + hash(22) - * 33: array(12) (capa <= 64) + hash(22) - * 34: array(14) (capa <= 64) + hash(22) - * 35: array(15) (capa <= 64) + hash(22) - */ - -#ifndef ID_TABLE_IMPL -#define ID_TABLE_IMPL 34 -#endif - -#if ID_TABLE_IMPL == 0 -#define ID_TABLE_NAME st -#define ID_TABLE_IMPL_TYPE struct st_id_table - -#define ID_TABLE_USE_ST 1 -#define ID_TABLE_USE_ST_DEBUG 1 - -#elif ID_TABLE_IMPL == 1 -#define ID_TABLE_NAME st -#define ID_TABLE_IMPL_TYPE struct st_id_table - -#define ID_TABLE_USE_ST 1 -#define ID_TABLE_USE_ST_DEBUG 0 - -#elif ID_TABLE_IMPL == 11 -#define ID_TABLE_NAME list -#define ID_TABLE_IMPL_TYPE struct list_id_table - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 - -#elif ID_TABLE_IMPL == 12 -#define ID_TABLE_NAME list -#define ID_TABLE_IMPL_TYPE struct list_id_table - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_ID_SERIAL 1 - -#elif ID_TABLE_IMPL == 13 -#define ID_TABLE_NAME list -#define ID_TABLE_IMPL_TYPE struct list_id_table - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_ID_SERIAL 1 -#define ID_TABLE_SWAP_RECENT_ACCESS 1 - -#elif ID_TABLE_IMPL == 14 -#define ID_TABLE_NAME list -#define ID_TABLE_IMPL_TYPE struct list_id_table - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_ID_SERIAL 1 -#define ID_TABLE_USE_LIST_SORTED 1 - -#elif ID_TABLE_IMPL == 15 -#define ID_TABLE_NAME list -#define ID_TABLE_IMPL_TYPE struct list_id_table - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_ID_SERIAL 1 -#define ID_TABLE_USE_LIST_SORTED 1 -#define ID_TABLE_USE_LIST_SORTED_LINEAR_SMALL_RANGE 1 - -#elif ID_TABLE_IMPL == 21 -#define ID_TABLE_NAME hash -#define ID_TABLE_IMPL_TYPE sa_table - -#define ID_TABLE_USE_COALESCED_HASHING 1 -#define ID_TABLE_USE_ID_SERIAL 1 - -#elif ID_TABLE_IMPL == 22 -#define ID_TABLE_NAME hash -#define ID_TABLE_IMPL_TYPE struct hash_id_table - -#define ID_TABLE_USE_SMALL_HASH 1 -#define ID_TABLE_USE_ID_SERIAL 1 - -#elif ID_TABLE_IMPL == 31 -#define ID_TABLE_NAME mix -#define ID_TABLE_IMPL_TYPE struct mix_id_table - -#define ID_TABLE_USE_MIX 1 -#define ID_TABLE_USE_MIX_LIST_MAX_CAPA 32 - -#define ID_TABLE_USE_ID_SERIAL 1 - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_SMALL_HASH 1 - -#elif ID_TABLE_IMPL == 32 -#define ID_TABLE_NAME mix -#define ID_TABLE_IMPL_TYPE struct mix_id_table - -#define ID_TABLE_USE_MIX 1 -#define ID_TABLE_USE_MIX_LIST_MAX_CAPA 32 - -#define ID_TABLE_USE_ID_SERIAL 1 - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_LIST_SORTED 1 - -#define ID_TABLE_USE_SMALL_HASH 1 - -#elif ID_TABLE_IMPL == 33 -#define ID_TABLE_NAME mix -#define ID_TABLE_IMPL_TYPE struct mix_id_table - -#define ID_TABLE_USE_MIX 1 -#define ID_TABLE_USE_MIX_LIST_MAX_CAPA 64 - -#define ID_TABLE_USE_ID_SERIAL 1 - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_SMALL_HASH 1 - -#elif ID_TABLE_IMPL == 34 -#define ID_TABLE_NAME mix -#define ID_TABLE_IMPL_TYPE struct mix_id_table - -#define ID_TABLE_USE_MIX 1 -#define ID_TABLE_USE_MIX_LIST_MAX_CAPA 64 - -#define ID_TABLE_USE_ID_SERIAL 1 - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_LIST_SORTED 1 - -#define ID_TABLE_USE_SMALL_HASH 1 - -#elif ID_TABLE_IMPL == 35 -#define ID_TABLE_NAME mix -#define ID_TABLE_IMPL_TYPE struct mix_id_table - -#define ID_TABLE_USE_MIX 1 -#define ID_TABLE_USE_MIX_LIST_MAX_CAPA 64 - -#define ID_TABLE_USE_ID_SERIAL 1 - -#define ID_TABLE_USE_LIST 1 -#define ID_TABLE_USE_CALC_VALUES 1 -#define ID_TABLE_USE_LIST_SORTED 1 -#define ID_TABLE_USE_LIST_SORTED_LINEAR_SMALL_RANGE 1 - -#define ID_TABLE_USE_SMALL_HASH 1 - -#else -#error -#endif - -#if ID_TABLE_SWAP_RECENT_ACCESS && ID_TABLE_USE_LIST_SORTED -#error -#endif - -/* IMPL(create) will be "hash_id_table_create" and so on */ -#define IMPL1(name, op) TOKEN_PASTE(name, _id##op) /* expand `name' */ -#define IMPL(op) IMPL1(ID_TABLE_NAME, _table##op) /* but prevent `op' */ - -#ifdef __GNUC__ -# define UNUSED(func) static func __attribute__((unused)) -#else -# define UNUSED(func) static func -#endif - -UNUSED(ID_TABLE_IMPL_TYPE *IMPL(_create)(size_t)); -UNUSED(void IMPL(_free)(ID_TABLE_IMPL_TYPE *)); -UNUSED(void IMPL(_clear)(ID_TABLE_IMPL_TYPE *)); -UNUSED(size_t IMPL(_size)(const ID_TABLE_IMPL_TYPE *)); -UNUSED(size_t IMPL(_memsize)(const ID_TABLE_IMPL_TYPE *)); -UNUSED(int IMPL(_insert)(ID_TABLE_IMPL_TYPE *, ID, VALUE)); -UNUSED(int IMPL(_lookup)(ID_TABLE_IMPL_TYPE *, ID, VALUE *)); -UNUSED(int IMPL(_delete)(ID_TABLE_IMPL_TYPE *, ID)); -UNUSED(void IMPL(_foreach)(ID_TABLE_IMPL_TYPE *, rb_id_table_foreach_func_t *, void *)); -UNUSED(void IMPL(_foreach_values)(ID_TABLE_IMPL_TYPE *, rb_id_table_foreach_values_func_t *, void *)); - -#if ID_TABLE_USE_ID_SERIAL typedef rb_id_serial_t id_key_t; + static inline ID key2id(id_key_t key) { @@ -221,932 +24,7 @@ id2key(ID id) https://github.com/ruby/ruby/blob/trunk/id_table.c#L24 { return rb_id_to_serial(id); } -#else /* ID_TABLE_USE_ID_SERIAL */ - -typedef ID id_key_t; -#define key2id(key) key -#define id2key(id) id - -#endif /* ID_TABLE_USE_ID_SERIAL */ - -/*************************************************************** - * 0: using st with debug information. - * 1: using st. - ***************************************************************/ -#if ID_TABLE_USE_ST -#if ID_TABLE_USE_ST_DEBUG -#define ID_TABLE_MARK 0x12345678 - -struct st_id_table { - struct st_table *st; - unsigned int check; -}; - -static struct st_table * -tbl2st(struct st_id_table *tbl) -{ - if (tbl->check != ID_TABLE_MARK) rb_bug("tbl2st: check error %x", tbl->check); - return tbl->st; -} - -static struct st_id_table * -st_id_table_create(size_t size) -{ - struct st_id_table *tbl = ALLOC(struct st_id_table); - tbl->st = st_init_numtable_with_size(size); - tbl->check = ID_TABLE_MARK; - return tbl; -} - -static void -st_id_table_free(struct st_id_table *tbl) -{ - st_free_table(tbl->st); - xfree(tbl); -} -#else /* ID_TABLE_USE_ST_DEBUG */ - -struct st_id_table { - struct st_table st; -}; - -static struct st_table * -tbl2st(struct st_id_table *tbl) -{ - return (struct st_table *)tbl; -} - -static struct st_id_table * -st_id_table_create(size_t size) -{ - return (struct st_id_table *)st_init_numtable_with_size(size); -} - -static void -st_id_table_free(struct st_id_table *tbl) -{ - st_free_table((struct st_table*)tbl); -} - -#endif /* ID_TABLE_USE_ST_DEBUG */ - -static void -st_id_table_clear(struct st_id_table *tbl) -{ - st_clear(tbl2st(tbl)); -} - -static size_t -st_id_table_size(const struct st_id_table *tbl) -{ - return tbl2st(tbl)->num_entries; -} - -static size_t -st_id_table_memsize(const struct st_id_table *tbl) -{ - size_t header_size = ID_TABLE_USE_ST_DEBUG ? sizeof(struct st_id_table) : 0; - return header_size + st_memsize(tbl2st(tbl)); -} - -static int -st_id_table_lookup(struct st_id_table *tbl, ID id, VALUE *val) -{ - return st_lookup(tbl2st(tbl), (st_data_t)id, (st_data_t *)val); -} - -static int -st_id_table_insert(struct st_id_table *tbl, ID id, VALUE val) -{ - return st_insert(tbl2st(tbl), id, val); -} - -static int -st_id_table_delete(struct st_id_table *tbl, ID id) -{ - return st_delete(tbl2st(tbl), (st_data_t *)&id, NULL); -} - -static void -st_id_table_foreach(struct st_id_table *tbl, rb_id_table_foreach_func_t *func, void *data) -{ - st_foreach(tbl2st(tbl), (int (*)(ANYARGS))func, (st_data_t)data); -} - -struct values_iter_data { - rb_id_table_foreach_values_func_t *values_i; - void *data; -}; - -static int -each_values(st_data_t key, st_data_t val, st_data_t ptr) -{ - struct values_iter_data *values_iter_data = (struct values_iter_data *)ptr; - return values_iter_data->values_i(val, values_iter_data->data); -} - -static void -st_id_table_foreach_values(struct st_id_table *tbl, rb_id_table_foreach_values_func_t *func, void *data) -{ - struct values_iter_data values_iter_data; - values_iter_data.values_i = func; - values_iter_data.data = data; - st_foreach(tbl2st(tbl), each_values, (st_data_t)&values_iter_data); -} -#endif /* ID_TABLE_USE_ST */ - -#if ID_TABLE_USE_LIST - -#define LIST_MIN_CAPA 4 - -struct list_id_table { - int capa; - int num; - id_key_t *keys; -#if ID_TABLE_USE_CALC_VALUES == 0 - VALUE *values_; -#endif -}; - -#if ID_TABLE_USE_CALC_VALUES -#define TABLE_VALUES(tbl) ((VALUE *)((tbl)->keys + (tbl)->capa)) -#else -#define TABLE_VALUES(tbl) (tbl)->values_ -#endif - -static struct list_id_table * -list_id_table_init(struct list_id_table *tbl, size_t capa) -{ - if (capa > 0) { -#if ID_TABLE_USE_CALC_VALUES && \ - (UNALIGNED_WORD_ACCESS == 0) && (SIZEOF_VALUE == 8) - /* Workaround for 8-byte word alignment on 64-bit SPARC. - * This code assumes that sizeof(ID) == 4, sizeof(VALUE) == 8, and - * xmalloc() returns 8-byte aligned memory block. - */ - if (capa & (size_t)1) capa += 1; -#endif - tbl->capa = (int)capa; -#if ID_TABLE_USE_CALC_VALUES - tbl->keys = (id_key_t *)xmalloc(sizeof(id_key_t) * capa + sizeof(VALUE) * capa); -#else - tbl->keys = ALLOC_N(id_key_t, capa); - tbl->values_ = ALLOC_N(VALUE, capa); -#endif - } - return tbl; -} - -#ifndef ID_TABLE_USE_MIX -static struct list_id_table * -list_id_table_create(size_t capa) -{ - struct list_id_table *tbl = ZALLOC(struct list_id_table); - return list_id_table_init(tbl, capa); -} -#endif - -static void -list_id_table_free(struct list_id_table *tbl) -{ - xfree(tbl->keys); -#if ID_TABLE_USE_CALC_VALUES == 0 - xfree(tbl->values_); -#endif - xfree(tbl); -} - -static void -list_id_table_clear(struct list_id_table *tbl) -{ - tbl->num = 0; -} - -static size_t -list_id_table_size(const struct list_id_table *tbl) -{ - return (size_t)tbl->num; -} - -static size_t -list_id_table_memsize(const struct list_id_table *tbl) -{ - return (sizeof(id_key_t) + sizeof(VALUE)) * tbl->capa + sizeof(struct list_id_table); -} - -static void -list_table_extend(struct list_id_table *tbl) -{ - if (tbl->capa == tbl->num) { - const int capa = tbl->capa == 0 ? LIST_MIN_CAPA : (tbl->capa * 2); - -#if ID_TABLE_USE_CALC_VALUES - { - VALUE *old_values, *new_values; - VALUE *debug_values = NULL; - const int num = tbl->num; - const int size = sizeof(id_key_t) * capa + sizeof(VALUE) * capa; - int i; - - if (num > 0) { - VALUE *orig_values = (VALUE *)(tbl->keys + num); - debug_values = ALLOC_N(VALUE, num); - - for (i=0; i<num; i++) { - debug_values[i] = orig_values[i]; - } - - if (0) - for (i=0; i< 2 * num; i++) { - unsigned char *cs = (unsigned char *)&tbl->keys[i]; - size_t j; - fprintf(stderr, ">> %3d | %p - ", i, cs); - for (j=0; j<sizeof(VALUE); j++) { - fprintf(stderr, "%x ", cs[j]); - } - fprintf(stderr, "\n"); - } - } - - tbl->keys = (id_key_t *)xrealloc(tbl->keys, size); - old_values = (VALUE *)(tbl->keys + num); - new_values = (VALUE *)(tbl->keys + capa); - - /* [ keys (num) ] [ values (num) ] - * ^ old_values - * realloc => - * [ keys (capa = num * 2) ] [ values (capa = num * 2) ] - * ^ new_values - */ - - /* memmove */ - if (0) { - fprintf(stderr, "memmove: %p -> %p (%d, capa: %d)\n", - old_values, new_values, num, capa); - } - assert(num < capa); - assert(num == 0 || old_values < new_values); - - for (i=num-1; i>=0; i--) { - new_values[i] = old_values[i]; - } - - if (num > 0) { - for (i=0; i<num; i++) { - assert(debug_values[i] == new_values[i]); - } - xfree(debug_values); - } - } - - tbl->capa = capa; -#else - tbl->capa = capa; - tbl->keys = (id_key_t *)xrealloc(tbl->keys, sizeof(id_key_t) * capa); - tbl->values_ = (VALUE *)xrealloc(tbl->values_, sizeof(VALUE) * capa); -#endif - } -} - -#if ID_TABLE_DEBUG -static void -list_table_show(struct list_id_table *tbl) -{ - const id_key_t *keys = tbl->keys; - const int num = tbl->num; - int i; - - fprintf(stderr, "tbl: %p (num: %d)\n", tbl, num); - for (i=0; i<num; i++) { - fprintf(stderr, " -> [%d] %s %d\n", i, rb_id2name(key2id(keys[i])), (int)keys[i]); - } -} -#endif - -static void -tbl_assert(struct list_id_table *tbl) -{ -#if ID_TABLE_DEBUG -#if ID_TABLE_USE_LIST_SORTED - const id_key_t *keys = tbl->keys; - const int num = tbl->num; - int i; - - for (i=0; i<num-1; i++) { - if (keys[i] >= keys[i+1]) { - list_table_show(tbl); - rb_bug(": not sorted."); - } - } -#endif -#endif -} - -#if ID_TABLE_USE_LIST_SORTED -static int -list_ids_bsearch(const id_key_t *keys, id_key_t key, int num) -{ - int p, min = 0, max = num; - -#if ID_TABLE_USE_LIST_SORTED_LINEAR_SMALL_RANGE - if (num <= 64) { - if (num > 32) { - if (keys[num/2] <= key) { - min = num/2; - } else { - max = num/2; - } - } - for (p = min; p<num && keys[p] < key; p++) { - assert(keys[p] != 0); - } - return (p<num && keys[p] == key) ? p : -p-1; - } -#endif /* ID_TABLE_USE_LIST_SORTED_LINEAR_SMALL_RANGE */ - - while (1) { - p = min + (max - min) / 2; - - if (min >= max) { - break; - } - else { - id_key_t kp = keys[p]; - assert(p < max); - assert(p >= min); - - if (kp > key) max = p; - else if (kp < key) min = p+1; - else { - assert(kp == key); - assert(p >= 0); - assert(p < num); - return p; - } - } - } - - assert(min == max); - assert(min == p); - return -p-1; -} -#endif /* ID_TABLE_USE_LIST_SORTED */ - -static int -list_table_index(struct list_id_table *tbl, id_key_t key) -{ - const int num = tbl->num; - const id_key_t *keys = tbl->keys; - -#if ID_TABLE_USE_LIST_SORTED - return list_ids_bsearch(keys, key, num); -#else /* ID_TABLE_USE_LIST_SORTED */ - int i; - - for (i=0; i<num; i++) { - assert(keys[i] != 0); - - if (keys[i] == key) { - return (int)i; - } - } - return -1; -#endif -} - -static int -list_id_table_lookup(struct list_id_table *tbl, ID id, VALUE *valp) -{ - id_key_t key = id2key(id); - int index = list_table_index(tbl, key); - - if (index >= 0) { - *valp = TABLE_VALUES(tbl)[index]; - -#if ID_TABLE_SWAP_RECENT_ACCESS - if (index > 0) { - VALUE *values = TABLE_VALUES(tbl); - id_key_t tk = tbl->keys[index-1]; - VALUE tv = values[index-1]; - tbl->keys[index-1] = tbl->keys[index]; - tbl->keys[index] = tk; - values[index-1] = values[index]; - values[index] = tv; - } -#endif /* ID_TABLE_SWAP_RECENT_ACCESS */ - return TRUE; - } - else { - return FALSE; - } -} - -static int -list_id_table_insert(struct list_id_table *tbl, ID id, VALUE val) -{ - const id_key_t key = id2key(id); - const int index = list_table_index(tbl, key); - - if (index >= 0) { - TABLE_VALUES(tbl)[index] = val; - } - else { - list_table_extend(tbl); - { - const int num = tbl->num++; -#if ID_TABLE_USE_LIST_SORTED - const int insert_index = -(index + 1); - id_key_t *keys = tbl->keys; - VALUE *values = TABLE_VALUES(tbl); - int i; - - if (0) fprintf(stderr, "insert: %d into %d on\n", (int)key, insert_index); - - for (i=num; i>insert_index; i--) { - keys[i] = keys[i-1]; - values[i] = values[i-1]; - } - keys[i] = key; - values[i] = val; - - tbl_assert(tbl); -#else - tbl->keys[num] = key; - TABLE_VALUES(tbl)[num] = val; -#endif - } - } - - return TRUE; -} - -static int -list_delete_index(struct list_id_table *tbl, id_key_t key, int index) -{ - if (index >= 0) { - VALUE *values = TABLE_VALUES(tbl); - -#if ID_TABLE_USE_LIST_SORTED - int i; - const int num = tbl->num; - id_key_t *keys = tbl->keys; - - for (i=index+1; i<num; i++) { /* compaction */ - keys[i-1] = keys[i]; - values[i-1] = values[i]; - } -#else - tbl->keys[index] = tbl->keys[tbl->num-1]; - values[index] = values[tbl->num-1]; -#endif - tbl->num--; - tbl_assert(tbl); - - return TRUE; - } - else { - return FALSE; - } -} - -static int -list_id_table_delete(struct list_id_table *tbl, ID id) -{ - const id_key_t key = id2key(id); - int index = list_table_index(tbl, key); - return list_delete_index(tbl, key, index); -} - -#define FOREACH_LAST() do { \ - switch (ret) { \ - case ID_TABLE_ITERATOR_RESULT_END: \ - case ID_TABLE_CONTINUE: \ - case ID_TABLE_STOP: \ - break; \ - case ID_TABLE_DELETE: \ - list_delete_index(tbl, key, i); \ - values = TABLE_VALUES(tbl); \ - num = tbl->num; \ - i--; /* redo same index */ \ - break; \ - } \ -} while (0) - -static void -list_id_table_foreach(struct list_id_table *tbl, rb_id_table_foreach_func_t *func, void *data) -{ - int num = tbl->num; - int i; - const id_key_t *keys = tbl->keys; - const VALUE *values = TABLE_VALUES(tbl); - - for (i=0; i<num; i++) { - const id_key_t key = keys[i]; - enum rb_id_table_iterator_result ret = (*func)(key2id(key), values[i], data); - assert(key != 0); - - FOREACH_LAST(); - if (ret == ID_TABLE_STOP) return; - } -} - -static void -list_id_table_foreach_values(struct list_id_table *tbl, rb_id_table_foreach_values_func_t *func, void *data) -{ - int num = tbl->num; - int i; - const id_key_t *keys = tbl->keys; - VALUE *values = TABLE_VALUES(tbl); - - for (i=0; i<num; i++) { - const id_key_t key = keys[i]; - enum rb_id_table_iterator_result ret = (*func)(values[i], data); - assert(key != 0); - - FOREACH_LAST(); - if (ret == ID_TABLE_STOP) return; - } -} -#endif /* ID_TABLE_USE_LIST */ - - -#if ID_TABLE_USE_COALESCED_HASHING -/* implementation is based on - * https://bugs.ruby-lang.org/issues/6962 by funny_falcon - */ - -typedef unsigned int sa_index_t; - -#define SA_EMPTY 0 -#define SA_LAST 1 -#define SA_OFFSET 2 -#define SA_MIN_SIZE 4 - -typedef struct sa_entry { - sa_index_t next; - id_key_t key; - VALUE value; -} sa_entry; - -typedef struct { - sa_index_t num_bins; - sa_index_t num_entries; - sa_index_t free_pos; - sa_entry *entries; -} sa_table; - -static void -sa_init_table(register sa_table *table, sa_index_t num_bins) -{ - if (num_bins) { - table->num_entries = 0; - table->entries = ZALLOC_N(sa_entry, num_bins); - table->num_bins = num_bins; - table->free_pos = num_bins; - } -} - -static sa_table* -hash_id_table_create(size_t size) -{ - sa_table* table = ZALLOC(sa_table); - sa_init_table(table, (sa_index_t)size); - return table; -} - -static void -hash_id_table_clear(sa_table *table) -{ - xfree(table->entries); - memset(table, 0, sizeof(sa_table)); -} - -static void -hash_id_table_free(sa_table *table) -{ - xfree(table->entries); - xfree(table); -} - -static size_t -hash_id_table_memsize(const sa_table *table) -{ - return sizeof(sa_table) + table->num_bins * sizeof (sa_entry); -} - -static inline sa_index_t -calc_pos(register s (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/