[前][次][番号順一覧][スレッド一覧]

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/

[前][次][番号順一覧][スレッド一覧]