[ruby-dev:24569] ordered hash

なかだです。

たしかruby-talkでHashを順序つきにするという話が出ていたと思うん
ですが、いつのだか分からなくなったのでdevに振ります。


Index: st.c
===================================================================
RCS file: /cvs/ruby/src/ruby/st.c,v
retrieving revision 1.30
diff -U2 -p -d -r1.30 st.c
--- st.c	23 Sep 2004 00:51:31 -0000	1.30
+++ st.c	22 Oct 2004 16:18:59 -0000
@@ -20,4 +20,5 @@ struct st_table_entry {
     st_data_t record;
     st_table_entry *next;
+    st_table_entry *forw, *back;
 };
 
@@ -170,4 +171,5 @@ st_init_table_with_size(type, size)
     tbl->num_bins = size;
     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
+    tbl->head = 0;
 
     return tbl;
@@ -270,5 +272,5 @@ st_lookup(table, key, value)
 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
 do {\
-    st_table_entry *entry;\
+    st_table_entry *entry, *head;\
     if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
 	rehash(table);\
@@ -282,4 +284,12 @@ do {\
     entry->record = value;\
     entry->next = table->bins[bin_pos];\
+    if (head = table->head) {\
+	entry->forw = head;\
+	(entry->back = head->back)->forw = entry;\
+	head->back = entry;\
+    }\
+    else {\
+	table->head = entry->forw = entry->back = entry;\
+    }\
     table->bins[bin_pos] = entry;\
     table->num_entries++;\
@@ -326,23 +336,21 @@ rehash(table)
 {
     register st_table_entry *ptr, *next, **new_bins;
-    int i, old_num_bins = table->num_bins, new_num_bins;
+    int i, new_num_bins;
     unsigned int hash_val;
 
-    new_num_bins = new_size(old_num_bins+1);
-    new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
+    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;
 
-    for(i = 0; i < old_num_bins; i++) {
-	ptr = table->bins[i];
-	while (ptr != 0) {
-	    next = ptr->next;
+    if (ptr = table->head) {
+	do {
 	    hash_val = ptr->hash % new_num_bins;
 	    ptr->next = new_bins[hash_val];
 	    new_bins[hash_val] = ptr;
-	    ptr = next;
-	}
+	} while ((ptr = ptr->forw) != table->head);
     }
-    free(table->bins);
-    table->num_bins = new_num_bins;
-    table->bins = new_bins;
 }
 
@@ -352,6 +360,7 @@ st_copy(old_table)
 {
     st_table *new_table;
-    st_table_entry *ptr, *entry;
-    int i, num_bins = old_table->num_bins;
+    st_table_entry *ptr, *entry, *prev, **tail;
+    int num_bins = old_table->num_bins;
+    unsigned int hash_val;
 
     new_table = alloc(st_table);
@@ -369,23 +378,43 @@ st_copy(old_table)
     }
 
-    for(i = 0; i < num_bins; i++) {
-	new_table->bins[i] = 0;
-	ptr = old_table->bins[i];
-	while (ptr != 0) {
+    if (ptr = old_table->head) {
+	prev = 0;
+	tail = &new_table->head;
+	do {
 	    entry = alloc(st_table_entry);
 	    if (entry == 0) {
-		free(new_table->bins);
-		free(new_table);
+		st_free_table(new_table);
 		return 0;
 	    }
 	    *entry = *ptr;
-	    entry->next = new_table->bins[i];
-	    new_table->bins[i] = entry;
-	    ptr = ptr->next;
-	}
+	    hash_val = entry->hash % num_bins;
+	    entry->next = new_table->bins[hash_val];
+	    new_table->bins[hash_val] = entry;
+	    entry->back = prev;
+	    *tail = prev = entry;
+	    tail = &entry->forw;
+	} while ((ptr = ptr->forw) != old_table->head);
+	entry = new_table->head;
+	entry->back = prev;
+	*tail = entry;
     }
+
     return new_table;
 }
 
+#define REMOVE_ENTRY(table, ptr) do {\
+    if (ptr == ptr->forw) {\
+	table->head = 0;\
+    }\
+    else {\
+	st_table_entry *forw = ptr->forw, *back = ptr->back;\
+	forw->back = back;\
+	back->forw = forw;\
+	if (ptr == table->head) table->head = forw;\
+    }\
+    table->num_entries--;\
+} while (0)
+
+
 int
 st_delete(table, key, value)
@@ -395,36 +424,21 @@ st_delete(table, key, value)
 {
     unsigned int hash_val;
-    st_table_entry *tmp;
+    st_table_entry **prev;
     register st_table_entry *ptr;
 
     hash_val = do_hash_bin(*key, table);
-    ptr = table->bins[hash_val];
-
-    if (ptr == 0) {
-	if (value != 0) *value = 0;
-	return 0;
-    }
-
-    if (EQUAL(table, *key, ptr->key)) {
-	table->bins[hash_val] = ptr->next;
-	table->num_entries--;
-	if (value != 0) *value = ptr->record;
-	*key = ptr->key;
-	free(ptr);
-	return 1;
-    }
 
-    for(; ptr->next != 0; ptr = ptr->next) {
-	if (EQUAL(table, ptr->next->key, *key)) {
-	    tmp = ptr->next;
-	    ptr->next = ptr->next->next;
-	    table->num_entries--;
-	    if (value != 0) *value = tmp->record;
-	    *key = tmp->key;
-	    free(tmp);
+    for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) {
+	if (EQUAL(table, *key, ptr->key)) {
+	    *prev = ptr->next;
+	    REMOVE_ENTRY(table, ptr);
+	    if (value != 0) *value = ptr->record;
+	    *key = ptr->key;
+	    free(ptr);
 	    return 1;
 	}
     }
 
+    if (value != 0) *value = 0;
     return 0;
 }
@@ -443,12 +457,7 @@ st_delete_safe(table, key, value, never)
     ptr = table->bins[hash_val];
 
-    if (ptr == 0) {
-	if (value != 0) *value = 0;
-	return 0;
-    }
-
-    for(; ptr != 0; ptr = ptr->next) {
+    for (; ptr != 0; ptr = ptr->next) {
 	if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
-	    table->num_entries--;
+	    REMOVE_ENTRY(table, ptr);
 	    *key = ptr->key;
 	    if (value != 0) *value = ptr->record;
@@ -458,15 +467,8 @@ st_delete_safe(table, key, value, never)
     }
 
+    if (value != 0) *value = 0;
     return 0;
 }
 
-static int
-delete_never(key, value, never)
-    st_data_t key, value, never;
-{
-    if (value == never) return ST_DELETE;
-    return ST_CONTINUE;
-}
-
 void
 st_cleanup_safe(table, never)
@@ -474,11 +476,24 @@ st_cleanup_safe(table, never)
     st_data_t never;
 {
-    int num_entries = table->num_entries;
+    st_table_entry *ptr, **last, *tmp;
+    int i;
 
-    st_foreach(table, delete_never, never);
-    table->num_entries = num_entries;
+    for (i = 0; i < table->num_bins; i++) {
+	ptr = *(last = &table->bins[i]);
+	while (ptr != 0) {
+	    if (ptr->forw == 0) {
+		tmp = ptr;
+		*last = ptr = ptr->next;
+		free(tmp);
+		table->num_entries--;
+	    }
+	    else {
+		ptr = *(last = &ptr->next);
+	    }
+	}
+    }
 }
 
-void
+int
 st_foreach(table, func, arg)
     st_table *table;
@@ -486,46 +501,94 @@ st_foreach(table, func, arg)
     st_data_t arg;
 {
-    st_table_entry *ptr, *last, *tmp;
+    st_table_entry *ptr, **last, *tmp;
     enum st_retval retval;
     int i;
 
-    for(i = 0; i < table->num_bins; i++) {
-	last = 0;
-	for(ptr = table->bins[i]; ptr != 0;) {
+    if ((ptr = table->head) != 0) {
+	do {
 	    retval = (*func)(ptr->key, ptr->record, arg, 0);
 	    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;
+	      case ST_CHECK:	/* check if hash is modified during iteration */
+		i = ptr->hash % table->num_bins;
+		for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
+		    if (!tmp) {
+			/* call func with error notice */
+			retval = (*func)(0, 0, arg, 1);
+			return 0;
 		    }
 		}
-		if (!tmp) {
-		    /* call func with error notice */
-		    retval = (*func)(0, 0, arg, 1);
-		    return;
-		}
 		/* fall through */
-	    case ST_CONTINUE:
-		last = ptr;
-		ptr = ptr->next;
+	      case ST_CONTINUE:
+		ptr = ptr->forw;
 		break;
-	    case ST_STOP:
-		return;
-	    case ST_DELETE:
-		tmp = ptr;
-		if (last == 0) {
-		    table->bins[i] = ptr->next;
+	      case ST_STOP:
+		return 0;
+	      case ST_DELETE:
+		last = &table->bins[ptr->hash % table->num_bins];
+		for (; (tmp = *last) != 0; last = &tmp->next) {
+		    if (ptr == tmp) {
+			tmp = ptr->forw;
+			*last = ptr->next;
+			REMOVE_ENTRY(table, ptr);
+			free(ptr);
+			if (ptr == tmp) return 1;
+			ptr = tmp;
+			break;
+		    }
 		}
-		else {
-		    last->next = ptr->next;
+	    }
+	} while (ptr != table->head);
+    }
+    return 1;
+}
+
+int
+st_reverse_foreach(table, func, arg)
+    st_table *table;
+    int (*func)();
+    st_data_t arg;
+{
+    st_table_entry *ptr, **last, *tmp;
+    enum st_retval retval;
+    int i, end;
+
+    if ((ptr = table->head) != 0) {
+	ptr = ptr->back;
+	do {
+	    end = ptr == table->head;
+	    retval = (*func)(ptr->key, ptr->record, arg, 0);
+	    switch (retval) {
+	      case ST_CHECK:	/* check if hash is modified during iteration */
+		i = ptr->hash % table->num_bins;
+		for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
+		    if (!tmp) {
+			/* call func with error notice */
+			retval = (*func)(0, 0, arg, 1);
+			return 0;
+		    }
+		}
+		/* fall through */
+	      case ST_CONTINUE:
+		ptr = ptr->back;
+		break;
+	      case ST_STOP:
+		return 0;
+	      case ST_DELETE:
+		last = &table->bins[ptr->hash % table->num_bins];
+		for (; (tmp = *last) != 0; last = &tmp->next) {
+		    if (ptr == tmp) {
+			tmp = ptr->back;
+			*last = ptr->next;
+			REMOVE_ENTRY(table, ptr);
+			free(ptr);
+			if (ptr == tmp) return 1;
+			ptr = tmp;
+			break;
+		    }
 		}
-		ptr = ptr->next;
-		free(tmp);
-		table->num_entries--;
 	    }
-	}
+	} while (!end);
     }
+    return 1;
 }
 
Index: st.h
===================================================================
RCS file: /cvs/ruby/src/ruby/st.h,v
retrieving revision 1.10
diff -U2 -p -d -r1.10 st.h
--- st.h	23 Sep 2004 00:51:31 -0000	1.10
+++ st.h	22 Oct 2004 15:06:24 -0000
@@ -22,4 +22,5 @@ struct st_table {
     int num_entries;
     struct st_table_entry **bins;
+    struct st_table_entry *head;
 };
 
@@ -42,5 +43,5 @@ int st_delete_safe _((st_table *, st_dat
 int st_insert _((st_table *, st_data_t, st_data_t));
 int st_lookup _((st_table *, st_data_t, st_data_t *));
-void st_foreach _((st_table *, int (*)(), st_data_t));
+int st_foreach _((st_table *, int (*)(), st_data_t));
 void st_add_direct _((st_table *, st_data_t, st_data_t));
 void st_free_table _((st_table *));


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