Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.