ruby-changes:39460
From: ko1 <ko1@a...>
Date: Wed, 12 Aug 2015 17:44:11 +0900 (JST)
Subject: [ruby-changes:39460] ko1:r51541 (trunk): * id_table.h: introduce ID key table.
ko1 2015-08-12 17:43:55 +0900 (Wed, 12 Aug 2015) New Revision: 51541 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=51541 Log: * id_table.h: introduce ID key table. [Feature #11420] This table only manage ID->VALUE table to reduce overhead of st. Some functions prefixed rb_id_table_* are provided. * id_table.c: implement rb_id_table_*. There are several algorithms to implement it. Now, there are roughly 4 types: * st * array * hash (implemented by Yura Sokolov) * mix of array and hash The macro ID_TABLE_IMPL can choose implementation. You can see detailes about them at the head of id_table.c. At the default, I choose 34 (mix of list and hash). This is not final decision. Please report your suitable parameters or your data structure. * symbol.c: introduce rb_id_serial_t and rb_id_to_serial() to represent ID by serial number. * internal.h: use id_table for method tables. * class.c, gc.c, marshal.c, vm.c, vm_method.c: ditto. Added files: trunk/id_table.c trunk/id_table.h Modified files: trunk/ChangeLog trunk/class.c trunk/common.mk trunk/gc.c trunk/internal.h trunk/marshal.c trunk/symbol.c trunk/symbol.h trunk/vm.c trunk/vm_method.c Index: symbol.c =================================================================== --- symbol.c (revision 51540) +++ symbol.c (revision 51541) @@ -107,7 +107,7 @@ enum id_entry_type { https://github.com/ruby/ruby/blob/trunk/symbol.c#L107 }; static struct symbols { - ID last_id; + rb_id_serial_t last_id; st_table *str_sym; VALUE ids; VALUE dsymbol_fstr_hash; @@ -143,8 +143,6 @@ WARN_UNUSED_RESULT(static ID attrsetname https://github.com/ruby/ruby/blob/trunk/symbol.c#L143 WARN_UNUSED_RESULT(static ID attrsetname_to_attr_id(VALUE name)); WARN_UNUSED_RESULT(static ID intern_str(VALUE str, int mutable)); -#define id_to_serial(id) (is_notop_id(id) ? id >> ID_SCOPE_SHIFT : id) - ID rb_id_attrset(ID id) { @@ -373,7 +371,7 @@ rb_str_symname_type(VALUE name, unsigned https://github.com/ruby/ruby/blob/trunk/symbol.c#L371 } static void -set_id_entry(ID num, VALUE str, VALUE sym) +set_id_entry(rb_id_serial_t num, VALUE str, VALUE sym) { size_t idx = num / ID_ENTRY_UNIT; VALUE ary, ids = global_symbols.ids; @@ -387,7 +385,7 @@ set_id_entry(ID num, VALUE str, VALUE sy https://github.com/ruby/ruby/blob/trunk/symbol.c#L385 } static VALUE -get_id_entry(ID num, const enum id_entry_type t) +get_id_entry(rb_id_serial_t num, const enum id_entry_type t) { if (num && num <= global_symbols.last_id) { size_t idx = num / ID_ENTRY_UNIT; @@ -401,6 +399,18 @@ get_id_entry(ID num, const enum id_entry https://github.com/ruby/ruby/blob/trunk/symbol.c#L399 return 0; } +static inline ID +rb_id_serial_to_id(rb_id_serial_t num) +{ + if (is_notop_id((ID)num)) { + VALUE sym = get_id_entry(num, ID_ENTRY_SYM); + return SYM2ID(sym); + } + else { + return (ID)num; + } +} + #if SYMBOL_DEBUG static int register_sym_update_callback(st_data_t *key, st_data_t *value, st_data_t arg, int existing) @@ -444,7 +454,7 @@ register_static_symid(ID id, const char https://github.com/ruby/ruby/blob/trunk/symbol.c#L454 static ID register_static_symid_str(ID id, VALUE str) { - ID num = id_to_serial(id); + rb_id_serial_t num = rb_id_to_serial(id); VALUE sym = STATIC_ID2SYM(id); OBJ_FREEZE(str); @@ -584,7 +594,7 @@ lookup_str_sym(const VALUE str) https://github.com/ruby/ruby/blob/trunk/symbol.c#L594 static VALUE lookup_id_str(ID id) { - return get_id_entry(id_to_serial(id), ID_ENTRY_STR); + return get_id_entry(rb_id_to_serial(id), ID_ENTRY_STR); } ID @@ -604,7 +614,9 @@ rb_intern3(const char *name, long len, r https://github.com/ruby/ruby/blob/trunk/symbol.c#L614 static ID next_id_base(void) { - if (global_symbols.last_id >= ~(ID)0 >> (ID_SCOPE_SHIFT+RUBY_SPECIAL_SHIFT)) { + rb_id_serial_t next_serial = global_symbols.last_id + 1; + + if (next_serial == 0) { return (ID)-1; } else { @@ -744,7 +756,7 @@ rb_sym2id(VALUE sym) https://github.com/ruby/ruby/blob/trunk/symbol.c#L756 RSYMBOL(sym)->id = id |= num; /* make it permanent object */ - set_id_entry(num >>= ID_SCOPE_SHIFT, fstr, sym); + set_id_entry(rb_id_to_serial(num), fstr, sym); rb_hash_delete_entry(global_symbols.dsymbol_fstr_hash, fstr); } } @@ -760,7 +772,7 @@ VALUE https://github.com/ruby/ruby/blob/trunk/symbol.c#L772 rb_id2sym(ID x) { if (!DYNAMIC_ID_P(x)) return STATIC_ID2SYM(x); - return get_id_entry(id_to_serial(x), ID_ENTRY_SYM); + return get_id_entry(rb_id_to_serial(x), ID_ENTRY_SYM); } @@ -1122,3 +1134,5 @@ rb_is_junk_name(VALUE name) https://github.com/ruby/ruby/blob/trunk/symbol.c#L1134 { return rb_str_symname_type(name, IDSET_ATTRSET_FOR_SYNTAX) == -1; } + +#include "id_table.c" Index: symbol.h =================================================================== --- symbol.h (revision 51540) +++ symbol.h (revision 51541) @@ -32,15 +32,6 @@ struct RSymbol { https://github.com/ruby/ruby/blob/trunk/symbol.h#L32 #define RSYMBOL(obj) (R_CAST(RSymbol)(obj)) -static inline int -id_type(ID id) -{ - if (id<=tLAST_OP_ID) { - return -1; - } - return (int)(id&ID_SCOPE_MASK); -} - #define is_notop_id(id) ((id)>tLAST_OP_ID) #define is_local_id(id) (id_type(id)==ID_LOCAL) #define is_global_id(id) (id_type(id)==ID_GLOBAL) @@ -51,6 +42,30 @@ id_type(ID id) https://github.com/ruby/ruby/blob/trunk/symbol.h#L42 #define is_junk_id(id) (id_type(id)==ID_JUNK) static inline int +id_type(ID id) +{ + if (is_notop_id(id)) { + return (int)(id&ID_SCOPE_MASK); + } + else { + return -1; + } +} + +typedef uint32_t rb_id_serial_t; + +static inline rb_id_serial_t +rb_id_to_serial(ID id) +{ + if (is_notop_id(id)) { + return (rb_id_serial_t)(id >> ID_SCOPE_SHIFT); + } + else { + return (rb_id_serial_t)id; + } +} + +static inline int sym_type(VALUE sym) { ID id; Index: id_table.c =================================================================== --- id_table.c (revision 0) +++ id_table.c (revision 51541) @@ -0,0 +1,1527 @@ https://github.com/ruby/ruby/blob/trunk/id_table.c#L1 +/* 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 +#define NDEBUG +#endif +#include <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) + * 34: 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 + +#if ID_TABLE_USE_ID_SERIAL +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); +} +#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(struct st_id_table *tbl) +{ + return tbl2st(tbl)->num_entries; +} + +static size_t +st_id_table_memsize(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, enum rb_id_table_iterator_result (*func)(ID id, VALUE val, void *data), void *data) +{ + st_foreach(tbl2st(tbl), (int (*)(ANYARGS))func, (st_data_t)data); +} + +struct values_iter_data { + enum rb_id_table_iterator_result (*values_i)(VALUE val, void *data); + 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, enum rb_id_table_iterator_result (*func)(VALUE val, void *data), 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) { + 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(struct list_id_table *tbl) +{ + return (size_t)tbl->num; +} + +static size_t +list_id_table_memsize(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 */ + // 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] = ke (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/