0001-introduce-st_foreach_update-st_foreach_update_check.patch

From d05d3e3b95d354f5f59232ace4db24ff859a5bcd Mon Sep 17 00:00:00 2001
From: Masaya TARUI <tarui@prx.jp>
Date: Tue, 4 Mar 2014 20:22:13 +0900
Subject: [PATCH] introduce st_foreach_update, st_foreach_update_check

---
 hash.c     |  47 ++++++++++------
 internal.h |   5 ++
 st.c       | 177 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 214 insertions(+), 15 deletions(-)

diff --git a/hash.c b/hash.c
index ccc0d44..ad107c4 100644
--- a/hash.c
+++ b/hash.c
@@ -170,6 +170,14 @@ struct foreach_safe_arg {
     st_data_t arg;
 };
 
+typedef int rb_foreach_update_func(VALUE*, VALUE*, VALUE, int);
+
+struct hash_foreach_update_arg {
+    VALUE hash;
+    rb_foreach_update_func *func;
+    VALUE arg;
+};
+
 static int
 foreach_safe_i(st_data_t key, st_data_t value, st_data_t args, int error)
 {
@@ -259,6 +267,17 @@ hash_foreach_call(VALUE arg)
     return Qnil;
 }
 
+static VALUE
+hash_foreach_update_call(VALUE argp)
+{
+    struct hash_foreach_update_arg *arg = (struct hash_foreach_update_arg *)argp;
+    VALUE hash = arg->hash;
+    if (st_foreach_update_check(RHASH(hash)->ntbl, arg->func, arg->arg, (st_data_t)Qundef)) {
+	rb_raise(rb_eRuntimeError, "hash modified during iteration");
+    }
+    return Qnil;
+}
+
 void
 rb_hash_foreach(VALUE hash, int (*func)(ANYARGS), VALUE farg)
 {
@@ -612,12 +631,13 @@ struct rehash_arg {
 };
 
 static int
-rb_hash_rehash_i(VALUE key, VALUE value, VALUE arg)
+rb_hash_rehash_i(VALUE *key, VALUE *value, VALUE arg, int error)
 {
-    st_table *tbl = (st_table *)arg;
-
-    st_insert(tbl, (st_data_t)key, (st_data_t)value);
-    return ST_CONTINUE;
+    if (error) {
+	return ST_STOP;
+	/* rb_bug("unexcepted error in Hash#reash"); */
+    }
+    return ST_CHECK;
 }
 
 /*
@@ -643,8 +663,7 @@ rb_hash_rehash_i(VALUE key, VALUE value, VALUE arg)
 static VALUE
 rb_hash_rehash(VALUE hash)
 {
-    VALUE tmp;
-    st_table *tbl;
+    struct hash_foreach_update_arg arg;
 
     if (RHASH_ITER_LEV(hash) > 0) {
 	rb_raise(rb_eRuntimeError, "rehash during iteration");
@@ -652,14 +671,12 @@ rb_hash_rehash(VALUE hash)
     rb_hash_modify_check(hash);
     if (!RHASH(hash)->ntbl)
         return hash;
-    tmp = hash_alloc(0);
-    tbl = st_init_table_with_size(RHASH(hash)->ntbl->type, RHASH(hash)->ntbl->num_entries);
-    RHASH(tmp)->ntbl = tbl;
-
-    rb_hash_foreach(hash, rb_hash_rehash_i, (VALUE)tbl);
-    st_free_table(RHASH(hash)->ntbl);
-    RHASH(hash)->ntbl = tbl;
-    RHASH(tmp)->ntbl = 0;
+
+    RHASH_ITER_LEV(hash)++;
+    arg.hash = hash;
+    arg.func = rb_hash_rehash_i;
+    arg.arg  = hash;
+    rb_ensure(hash_foreach_update_call, (VALUE)&arg, hash_foreach_ensure, hash);
 
     return hash;
 }
diff --git a/internal.h b/internal.h
index 3309b65..34b1592 100644
--- a/internal.h
+++ b/internal.h
@@ -815,6 +815,11 @@ VALUE rb_reg_check_preprocess(VALUE);
 int rb_get_next_signal(void);
 int rb_sigaltstack_size(void);
 
+/* st.c */
+int st_foreach_update(st_table *table, int (*func)(ANYARGS), st_data_t arg);
+int st_foreach_update_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t never);
+
+
 /* strftime.c */
 #ifdef RUBY_ENCODING_H
 size_t rb_strftime_timespec(char *s, size_t maxsize, const char *format, rb_encoding *enc,
diff --git a/st.c b/st.c
index 808c30c..c56a535 100644
--- a/st.c
+++ b/st.c
@@ -1025,6 +1025,183 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t
     return 0;
 }
 
+inline void update_direct(st_table *table, struct st_table_entry *ptr)
+{
+    st_index_t hash_val,hash_pos;
+    st_table_entry **last;
+    hash_val = do_hash(ptr->key, table);
+    if (hash_val == ptr->hash)
+	return;
+    hash_pos = hash_pos(hash_val, table->num_bins);
+    last = &table->bins[hash_pos(ptr->hash, table->num_bins)];
+    while (*last) {
+	if (*last == ptr) {
+	    *last = ptr->next;
+	    break;
+	}
+	last = &(*last)->next;
+    }
+    ptr->hash = hash_val;
+    ptr->next = table->bins[hash_pos];
+    table->bins[hash_pos]=ptr;
+}
+
+/* don't insert or delete in func */
+int
+st_foreach_update(st_table *table, int (*func)(ANYARGS), st_data_t arg)
+{
+    st_table_entry *ptr, **last, *tmp;
+    enum st_retval retval;
+    st_index_t i;
+
+    if (table->entries_packed) {
+	for (i = 0; i < table->real_entries; i++) {
+	    retval = (*func)(&PKEY(table, i), &PVAL(table, i), arg);
+	    /* TODO?: check modify */
+	    switch (retval) {
+	      case ST_CHECK:
+		PHASH_SET(table, i, do_hash(PKEY(table, i), table));
+		break;
+	      case ST_CONTINUE:
+		break;
+	      case ST_STOP:
+		return 0;
+	      case ST_DELETE:
+		remove_packed_entry(table, i);
+		i--;
+		break;
+	    }
+	}
+	return 0;
+    }
+    ptr = table->head;
+    if (ptr != 0) {
+	do {
+	    i = hash_pos(ptr->hash, table->num_bins);
+	    retval = (*func)(&ptr->key, &ptr->record, arg);
+	    switch (retval) {
+	      case ST_CHECK:
+		update_direct(table,ptr);
+		/* fall through */
+	      case ST_CONTINUE:
+		ptr = ptr->fore;
+		break;
+	      case ST_STOP:
+		return 0;
+	      case ST_DELETE:
+		last = &table->bins[hash_pos(ptr->hash, table->num_bins)];
+		for (; (tmp = *last) != 0; last = &tmp->next) {
+		    if (ptr == tmp) {
+			tmp = ptr->fore;
+			*last = ptr->next;
+			remove_entry(table, ptr);
+			st_free_entry(ptr);
+			ptr = tmp;
+			break;
+		    }
+		}
+	    }
+	} while (ptr && table->head);
+    }
+    return 0;
+}
+
+/* use st_delete_safe for delete into func */
+int
+st_foreach_update_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t never)
+{
+    st_table_entry *ptr, **last, *tmp;
+    st_data_t r_key, r_val;
+    enum st_retval retval;
+    st_index_t i;
+
+    if (table->entries_packed) {
+	for (i = 0; i < table->real_entries; i++) {
+	    st_data_t key, val;
+	    key = PKEY(table, i);
+	    if (key == never) continue;
+	    val = PVAL(table, i);
+	    r_key = key;
+	    r_val = val;
+	    retval = (*func)(&r_key, &r_val, arg, 0);
+	    if (!table->entries_packed) {
+		ptr = table->head;
+		if (ptr == 0) goto unexcepted;
+		while(i--){
+		    ptr=ptr->fore;
+		    if (ptr == table->head) goto unexcepted;
+		}
+		goto unpacked;
+	    }
+	    switch (retval) {
+	      case ST_CHECK:
+		if (PKEY(table, i) == never) break; /* deleted */
+		PKEY_SET(table, i, r_key);
+		PVAL_SET(table, i, r_val);
+		PHASH_SET(table, i, do_hash(r_key, table));
+		/* fall through */
+	      case ST_CONTINUE:
+		break;
+	      case ST_STOP:
+		return 0;
+	      case ST_DELETE:
+		remove_safe_packed_entry(table, i, never);
+		break;
+	    }
+	}
+	return 0;
+    }
+
+    ptr = table->head;
+    if (ptr != 0) {
+	do {
+	    if (ptr->key == never)
+		goto unpacked_continue;
+	    i = hash_pos(ptr->hash, table->num_bins);
+	    r_key = ptr->key;
+	    r_val = ptr->record;
+	    retval = (*func)(&r_key, &r_val, arg, 0);
+	  unpacked:
+	    switch (retval) {
+	      case ST_CHECK:
+		if (ptr->key != never) {
+		    ptr->key=r_key;
+		    ptr->record=r_val;
+		    update_direct(table,ptr);
+		}
+		/* fall through */
+	      case ST_CONTINUE:
+	      unpacked_continue:
+		ptr = ptr->fore;
+		break;
+	      case ST_STOP:
+		return 0;
+	      case ST_DELETE:
+		if (ptr->key == never) goto unpacked_continue;
+		last = &table->bins[hash_pos(ptr->hash, table->num_bins)];
+		for (; (tmp = *last) != 0; last = &tmp->next) {
+		    if (ptr == tmp) {
+			tmp = ptr->fore;
+			remove_entry(table, ptr);
+			ptr->key = ptr->record = never;
+			ptr->hash = 0;
+			ptr = tmp;
+			break;
+		    }
+		}
+		if (*last == 0) {
+		  unexcepted:
+		    retval = (*func)(NULL, NULL, arg, 1);
+		    return 1;
+		}
+	    }
+	} while (ptr && table->head);
+    }
+    return 0;
+}
+
+
+
 int
 st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 {
-- 
1.8.1.2