[ruby-dev:31731] ordered/unordered st_table

なかだです。

ついでに、st_tableの順序の有無を切替えるパッチです。


Index: hash.c
===================================================================
--- hash.c	(revision 13339)
+++ hash.c	(working copy)
@@ -233,4 +233,5 @@ rb_hash_tbl(VALUE hash)
     if (!RHASH(hash)->ntbl) {
         RHASH(hash)->ntbl = st_init_table(&objhash);
+	st_orderize(RHASH(hash)->ntbl);
     }
     return RHASH(hash)->ntbl;
@@ -402,4 +403,5 @@ rb_hash_rehash(VALUE hash)
         return hash;
     tbl = st_init_table_with_size(RHASH(hash)->ntbl->type, RHASH(hash)->ntbl->num_entries);
+    st_orderize(tbl);
     rb_hash_foreach(hash, rb_hash_rehash_i, (st_data_t)tbl);
     st_free_table(RHASH(hash)->ntbl);
Index: st.c
===================================================================
--- st.c	(revision 13339)
+++ st.c	(working copy)
@@ -7,4 +7,5 @@
 #include <stdlib.h>
 #endif
+#include <stddef.h>
 #include <string.h>
 
@@ -28,4 +29,10 @@ struct st_table_entry {
 };
 
+#define ST_UNORDER_MARK (st_table_entry *)-1
+#define ST_ORDERED_P(table) ((table)->head != ST_UNORDER_MARK)
+#define SIZEOF_ORDERED_ENTRY sizeof(st_table_entry)
+#define SIZEOF_UNORDERED_ENTRY offsetof(st_table_entry, fore)
+#define SIZEOF_ENTRY(table) (ST_ORDERED_P(table) ? SIZEOF_ORDERED_ENTRY : SIZEOF_UNORDERED_ENTRY)
+
 #define ST_DEFAULT_MAX_DENSITY 5
 #define ST_DEFAULT_INIT_TABLE_SIZE 11
@@ -168,5 +175,5 @@ st_init_table_with_size(const struct st_
     tbl->num_bins = size;
     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
-    tbl->head = 0;
+    tbl->head = ST_UNORDER_MARK;
 
     return tbl;
@@ -203,4 +210,13 @@ st_init_strtable_with_size(int size)
 }
 
+int
+st_orderize(st_table *table)
+{
+    if (ST_ORDERED_P(table)) return 0;
+    if (table->num_entries) return -1;
+    table->head = 0;
+    return 0;
+}
+
 void
 st_clear(st_table *table)
@@ -224,5 +240,5 @@ st_clear(st_table *table)
     }
     table->num_entries = 0;
-    table->head = 0;
+    if (ST_ORDERED_P(table)) table->head = 0;
 }
 
@@ -293,5 +309,5 @@ do {\
     }\
     \
-    entry = alloc(st_table_entry);\
+    entry = malloc(SIZEOF_ENTRY(table));\
     \
     entry->hash = hash_val;\
@@ -299,5 +315,7 @@ do {\
     entry->record = value;\
     entry->next = table->bins[bin_pos];\
-    if ((head = table->head) != 0) {\
+    if (!ST_ORDERED_P(table)) {\
+    }\
+    else if ((head = table->head) != 0) {\
 	entry->fore = head;\
 	(entry->back = head->back)->fore = entry;\
@@ -392,21 +410,39 @@ rehash(register st_table *table)
 {
     register st_table_entry *ptr, **new_bins;
-    int i, new_num_bins;
+    unsigned int i, old_num_bins = table->num_bins, new_num_bins;
     unsigned int hash_val;
+    int size = new_size(table->num_bins+1);
 
-    new_num_bins = new_size(table->num_bins+1);
-    new_bins = (st_table_entry**)
-	xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*));
-    for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0;
-    table->num_bins = new_num_bins;
-    table->bins = new_bins;
+    if (size < 0) return;
+    new_num_bins = (unsigned int)size;
+    if (!ST_ORDERED_P(table)) {
+	new_bins = calloc(new_num_bins, sizeof(st_table_entry*));
+
+	for (i = 0; i < old_num_bins; i++) {
+	    ptr = table->bins[i];
+	    while (ptr != 0) {
+		st_table_entry *next = ptr->next;
+		hash_val = ptr->hash % new_num_bins;
+		ptr->next = new_bins[hash_val];
+		new_bins[hash_val] = ptr;
+		ptr = next;
+	    }
+	}
+	free(table->bins);
+    }
+    else {
+	new_bins = xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*));
+	for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0;
 
-    if ((ptr = table->head) != 0) {
-	do {
-	    hash_val = ptr->hash % new_num_bins;
-	    ptr->next = new_bins[hash_val];
-	    new_bins[hash_val] = ptr;
-	} while ((ptr = ptr->fore) != table->head);
+	if ((ptr = table->head) != 0) {
+	    do {
+		hash_val = ptr->hash % new_num_bins;
+		ptr->next = new_bins[hash_val];
+		new_bins[hash_val] = ptr;
+	    } while ((ptr = ptr->fore) != table->head);
+	}
     }
+    table->num_bins = new_num_bins;
+    table->bins = new_bins;
 }
 
@@ -438,9 +474,28 @@ st_copy(st_table *old_table)
     }
 
-    if ((ptr = old_table->head) != 0) {
+    if (!ST_ORDERED_P(old_table)) {
+	unsigned int i;
+	for (i = 0; i < num_bins; i++) {
+	    ptr = old_table->bins[i];
+	    tail = &new_table->bins[i];
+	    while (ptr != 0) {
+		entry = malloc(SIZEOF_UNORDERED_ENTRY);
+		if (entry == 0) {
+		    st_free_table(new_table);
+		    return 0;
+		}
+		*entry = *ptr;
+		entry->next = 0;
+		*tail = entry;
+		tail = &entry->next;
+		ptr = ptr->next;
+	    }
+	}
+    }
+    else if ((ptr = old_table->head) != 0) {
 	prev = 0;
 	tail = &new_table->head;
 	do {
-	    entry = alloc(st_table_entry);
+	    entry = malloc(SIZEOF_ORDERED_ENTRY);
 	    if (entry == 0) {
 		st_free_table(new_table);
@@ -465,5 +520,8 @@ st_copy(st_table *old_table)
 #define REMOVE_ENTRY(table, ptr) do					\
     {									\
-	if (ptr == ptr->fore) {						\
+	if (!ST_ORDERED_P(table)) {					\
+	    /* do nothing  */						\
+	}								\
+	else if (ptr == ptr->fore) {					\
 	    table->head = 0;						\
 	}								\
@@ -601,5 +659,37 @@ st_foreach(st_table *table, int (*func)(
     }
 
-    if ((ptr = table->head) != 0) {
+    if (!ST_ORDERED_P(table)) {
+	for (i = 0; i < table->num_bins; i++) {
+	    for (ptr = *(last = &table->bins[i]); ptr != 0;) {
+		retval = (*func)(ptr->key, ptr->record, arg);
+		switch (retval) {
+		  case ST_CHECK:	/* check if hash is modified during iteration */
+		    tmp = 0;
+		    if (i < table->num_bins) {
+			for (tmp = table->bins[i]; tmp; tmp = tmp->next) {
+			    if (tmp == ptr) break;
+			}
+		    }
+		    if (!tmp) {
+			/* call func with error notice */
+			retval = (*func)(0, 0, arg, 1);
+			return 1;
+		    }
+		    /* fall through */
+		  case ST_CONTINUE:
+		    ptr = *(last = &ptr->next);
+		    break;
+		  case ST_STOP:
+		    return 0;
+		  case ST_DELETE:
+		    tmp = ptr;
+		    ptr = *last = ptr->next;
+		    free(tmp);
+		    table->num_entries--;
+		}
+	    }
+	}
+    }
+    else if ((ptr = table->head) != 0) {
 	do {
 	    end = ptr->fore == table->head;
@@ -647,4 +737,8 @@ st_reverse_foreach(st_table *table, int 
     int i, end;
 
+    if (!ST_ORDERED_P(table)) {
+	return st_foreach(table, func, arg);
+    }
+
     if (table->entries_packed) {
         for (i = table->num_entries-1; 0 <= i; i--) {
Index: include/ruby/st.h
===================================================================
--- include/ruby/st.h	(revision 13339)
+++ include/ruby/st.h	(working copy)
@@ -72,4 +72,5 @@ st_table *st_init_numtable_with_size(int
 st_table *st_init_strtable(void);
 st_table *st_init_strtable_with_size(int);
+int st_orderize(st_table *);
 int st_delete(st_table *, st_data_t *, st_data_t *);
 int st_delete_safe(st_table *, st_data_t *, st_data_t *, st_data_t);


-- 
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦