[PATCH] unordered

[PATCH] unordered

[Eric Wong]

---
 include/ruby/st.h |   8 +-
 st.c              | 399 ++++++++++++++++++++++++++++++++++++++++--------------
 string.c          |   1 +
 3 files changed, 302 insertions(+), 106 deletions(-)

diff --git a/include/ruby/st.h b/include/ruby/st.h
index 190bad2..dc3186b 100644
--- a/include/ruby/st.h
+++ b/include/ruby/st.h
@@ -68,8 +68,7 @@ struct st_hash_type {
 
 struct st_table {
     const struct st_hash_type *type;
-    st_index_t num_bins;
-    unsigned int entries_packed : 1;
+    unsigned int ordered : 1;
 #ifdef __GNUC__
     /*
      * C spec says,
@@ -82,6 +81,11 @@ struct st_table {
      */
     __extension__
 #endif
+    st_index_t num_bins : ST_INDEX_BITS - 1;
+    unsigned int entries_packed : 1;
+#ifdef __GNUC__
+    __extension__
+#endif
     st_index_t num_entries : ST_INDEX_BITS - 1;
     union {
 	struct {
diff --git a/st.c b/st.c
index 887b9dc..b6a97b4 100644
--- a/st.c
+++ b/st.c
@@ -17,12 +17,23 @@
 #include "ccan/list/list.h"
 
 typedef struct st_table_entry st_table_entry;
+typedef struct st_utable_entry st_utable_entry;
+
+struct st_utable_entry {
+    st_index_t hash;
+    st_data_t key;
+    st_data_t record;
+    st_utable_entry *next;
+};
 
 struct st_table_entry {
+    /* st_utable_entry { */
     st_index_t hash;
     st_data_t key;
     st_data_t record;
     st_table_entry *next;
+    /* } */
+
     struct list_node olist;
 };
 
@@ -93,7 +104,8 @@ static void rehash(st_table *);
 
 /* preparation for possible allocation improvements */
 #define st_alloc_entry() (st_table_entry *)malloc(sizeof(st_table_entry))
-#define st_free_entry(entry) free(entry)
+#define st_alloc_uentry() (st_utable_entry *)malloc(sizeof(st_utable_entry))
+#define st_free_entry(table, entry) free(entry)
 #define st_alloc_table() (st_table *)malloc(sizeof(st_table))
 #define st_dealloc_table(table) free(table)
 #define st_alloc_bins(size) (st_table_entry **)calloc(size, sizeof(st_table_entry *))
@@ -193,6 +205,12 @@ stat_col(void)
 }
 #endif
 
+static int
+st_ordered_p(const st_table *table)
+{
+    return table->ordered;
+}
+
 static struct list_head *
 st_head(const st_table *tbl)
 {
@@ -220,6 +238,7 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
 
 
     tbl = st_alloc_table();
+    tbl->ordered = 1;
     tbl->type = type;
     tbl->num_entries = 0;
     tbl->entries_packed = size <= MAX_PACKED_HASH;
@@ -290,13 +309,28 @@ st_clear(st_table *table)
         return;
     }
 
-    list_for_each_safe(st_head(table), ptr, next, olist) {
-	/* list_del is not needed */
-	st_free_entry(ptr);
+    if (st_ordered_p(table)) {
+	list_for_each_safe(st_head(table), ptr, next, olist) {
+	    /* list_del is not needed */
+	    st_free_entry(table, ptr);
+	}
+	list_head_init(st_head(table));
+    }
+    else {
+	st_index_t i;
+
+	for (i = 0; i < table->num_bins; i++) {
+	    st_utable_entry *ptr = (st_utable_entry *)table->bins[i];
+
+	    while (ptr) {
+		st_utable_entry *next = ptr->next;
+		st_free_entry(table, ptr);
+		ptr = next;
+	    }
+	}
     }
     table->num_entries = 0;
     MEMZERO(table->bins, st_table_entry*, table->num_bins);
-    list_head_init(st_head(table));
 }
 
 void
@@ -314,7 +348,11 @@ st_memsize(const st_table *table)
 	return table->num_bins * sizeof (void *) + sizeof(st_table);
     }
     else {
-	return table->num_entries * sizeof(struct st_table_entry) + table->num_bins * sizeof (void *) + sizeof(st_table);
+	size_t ent_size = st_ordered_p(table) ? sizeof(st_table_entry)
+	                                      : sizeof(st_utable_entry);
+
+	return table->num_entries * ent_size +
+	       table->num_bins * sizeof (void *) + sizeof(st_table);
     }
 }
 
@@ -346,10 +384,10 @@ count_collision(const struct st_hash_type *type)
 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) \
     ((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = hash_pos(hash_val, (table)->num_bins))))
 
-static st_table_entry *
+static st_utable_entry *
 find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos)
 {
-    register st_table_entry *ptr = table->bins[bin_pos];
+    register st_utable_entry *ptr = (st_utable_entry *)table->bins[bin_pos];
     FOUND_ENTRY;
     if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {
 	COLLISION;
@@ -383,7 +421,7 @@ int
 st_lookup(st_table *table, register st_data_t key, st_data_t *value)
 {
     st_index_t hash_val;
-    register st_table_entry *ptr;
+    register st_utable_entry *ptr;
 
     hash_val = do_hash(key, table);
 
@@ -411,7 +449,7 @@ int
 st_get_key(st_table *table, register st_data_t key, st_data_t *result)
 {
     st_index_t hash_val;
-    register st_table_entry *ptr;
+    register st_utable_entry *ptr;
 
     hash_val = do_hash(key, table);
 
@@ -438,11 +476,11 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
 #undef collision_check
 #define collision_check 1
 
-static inline st_table_entry *
+static inline void *
 new_entry(st_table * table, st_data_t key, st_data_t value,
-	st_index_t hash_val, register st_index_t bin_pos)
+	st_index_t hash_val, register st_index_t bin_pos, void *ptr)
 {
-    register st_table_entry *entry = st_alloc_entry();
+    register st_table_entry *entry = ptr;
 
     entry->next = table->bins[bin_pos];
     table->bins[bin_pos] = entry;
@@ -457,14 +495,19 @@ static inline void
 add_direct(st_table *table, st_data_t key, st_data_t value,
 	   st_index_t hash_val, register st_index_t bin_pos)
 {
-    register st_table_entry *entry;
     if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) {
 	rehash(table);
         bin_pos = hash_pos(hash_val, table->num_bins);
     }
 
-    entry = new_entry(table, key, value, hash_val, bin_pos);
-    list_add_tail(st_head(table), &entry->olist);
+    if (st_ordered_p(table)) {
+      register st_table_entry *ptr;
+
+      ptr = new_entry(table, key, value, hash_val, bin_pos, st_alloc_entry());
+      list_add_tail(st_head(table), &ptr->olist);
+    } else {
+      new_entry(table, key, value, hash_val, bin_pos, st_alloc_uentry());
+    }
     table->num_entries++;
 }
 
@@ -473,7 +516,6 @@ unpack_entries(register st_table *table)
 {
     st_index_t i;
     st_packed_entry packed_bins[MAX_PACKED_HASH];
-    register st_table_entry *entry;
     st_table tmp_table = *table;
 
     MEMCPY(packed_bins, PACKED_BINS(table), st_packed_entry, MAX_PACKED_HASH);
@@ -491,18 +533,34 @@ unpack_entries(register st_table *table)
      * walkable during GC (GC may be triggered by new_entry call)
      */
     i = 0;
-    list_head_init(st_head(&tmp_table));
-    do {
-	st_data_t key = packed_bins[i].key;
-	st_data_t val = packed_bins[i].val;
-	st_index_t hash = packed_bins[i].hash;
-	entry = new_entry(&tmp_table, key, val, hash,
-			  hash_pos(hash, ST_DEFAULT_INIT_TABLE_SIZE));
-	list_add_tail(st_head(&tmp_table), &entry->olist);
-    } while (++i < MAX_PACKED_HASH);
-    *table = tmp_table;
-    list_head_init(st_head(table));
-    list_append_list(st_head(table), st_head(&tmp_table));
+    if (st_ordered_p(table)) {
+	register st_table_entry *entry;
+
+	list_head_init(st_head(&tmp_table));
+	do {
+	    st_data_t key = packed_bins[i].key;
+	    st_data_t val = packed_bins[i].val;
+	    st_index_t hash = packed_bins[i].hash;
+	    entry = new_entry(&tmp_table, key, val, hash,
+			      hash_pos(hash, ST_DEFAULT_INIT_TABLE_SIZE),
+			      st_alloc_entry());
+	    list_add_tail(st_head(&tmp_table), &entry->olist);
+	} while (++i < MAX_PACKED_HASH);
+	*table = tmp_table;
+	list_head_init(st_head(table));
+	list_append_list(st_head(table), st_head(&tmp_table));
+    }
+    else {
+	do {
+	    st_data_t key = packed_bins[i].key;
+	    st_data_t val = packed_bins[i].val;
+	    st_index_t hash = packed_bins[i].hash;
+	    new_entry(&tmp_table, key, val, hash,
+			hash_pos(hash, ST_DEFAULT_INIT_TABLE_SIZE),
+			st_alloc_uentry());
+	} while (++i < MAX_PACKED_HASH);
+	*table = tmp_table;
+    }
 }
 
 static void
@@ -527,7 +585,7 @@ st_insert(register st_table *table, register st_data_t key, st_data_t value)
 {
     st_index_t hash_val;
     register st_index_t bin_pos;
-    register st_table_entry *ptr;
+    register st_utable_entry *ptr;
 
     hash_val = do_hash(key, table);
 
@@ -559,7 +617,7 @@ st_insert2(register st_table *table, register st_data_t key, st_data_t value,
 {
     st_index_t hash_val;
     register st_index_t bin_pos;
-    register st_table_entry *ptr;
+    register st_utable_entry *ptr;
 
     hash_val = do_hash(key, table);
 
@@ -604,26 +662,44 @@ st_add_direct(st_table *table, st_data_t key, st_data_t value)
 static void
 rehash(register st_table *table)
 {
-    register st_table_entry *ptr, **new_bins;
+    st_table_entry **new_bins;
     st_index_t new_num_bins, hash_val;
 
     new_num_bins = new_size(table->num_bins+1);
     new_bins = st_realloc_bins(table->bins, new_num_bins, table->num_bins);
-    table->num_bins = new_num_bins;
     table->bins = new_bins;
 
-    list_for_each(st_head(table), ptr, olist) {
-	hash_val = hash_pos(ptr->hash, new_num_bins);
-	ptr->next = new_bins[hash_val];
-	new_bins[hash_val] = ptr;
+    if (st_ordered_p(table)) {
+	st_table_entry *ptr;
+
+	list_for_each(st_head(table), ptr, olist) {
+	    hash_val = hash_pos(ptr->hash, new_num_bins);
+	    ptr->next = new_bins[hash_val];
+	    new_bins[hash_val] = ptr;
+	}
+    }
+    else {
+	st_index_t i;
+
+	for (i = 0; i < table->num_bins; i++) {
+	    st_table_entry *ptr = table->bins[i];
+	    while (ptr) {
+		st_table_entry *next = ptr->next;
+		hash_val = hash_pos(ptr->hash, new_num_bins);
+		ptr->next = new_bins[hash_val];
+		new_bins[hash_val] = ptr;
+		ptr = next;
+	    }
+	}
     }
+
+    table->num_bins = new_num_bins;
 }
 
 st_table*
 st_copy(st_table *old_table)
 {
     st_table *new_table;
-    st_table_entry *ptr, *entry;
     st_index_t num_bins = old_table->num_bins;
 
     new_table = st_alloc_table();
@@ -644,21 +720,41 @@ st_copy(st_table *old_table)
         return new_table;
     }
 
-    list_head_init(st_head(new_table));
+    if (st_ordered_p(new_table)) {
+	st_table_entry *ptr, *entry;
+
+	list_head_init(st_head(new_table));
+
+	list_for_each(st_head(old_table), ptr, olist) {
+	    entry = new_entry(new_table, ptr->key, ptr->record, ptr->hash,
+				hash_pos(ptr->hash, num_bins),
+				st_alloc_entry());
+	    list_add_tail(st_head(new_table), &entry->olist);
+	}
+    }
+    else {
+	st_index_t i;
+	st_table_entry *ptr;
 
-    list_for_each(st_head(old_table), ptr, olist) {
-	entry = new_entry(new_table, ptr->key, ptr->record, ptr->hash,
-			    hash_pos(ptr->hash, num_bins));
-	list_add_tail(st_head(new_table), &entry->olist);
+	for (i = 0; i < num_bins; i++) {
+	    for (ptr = old_table->bins[i]; ptr; ptr = ptr->next) {
+		new_entry(new_table, ptr->key, ptr->record, ptr->hash,
+			    hash_pos(ptr->hash, num_bins),
+			    st_alloc_uentry());
+	    }
+	}
     }
 
     return new_table;
 }
 
 static inline void
-remove_entry(st_table *table, st_table_entry *ptr)
+remove_entry(st_table *table, void *ptr)
 {
-    list_del(&ptr->olist);
+    if (st_ordered_p(table)) {
+	st_table_entry *entry = ptr;
+        list_del(&entry->olist);
+    }
     table->num_entries--;
 }
 
@@ -690,7 +786,7 @@ st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
 	    remove_entry(table, ptr);
 	    if (value != 0) *value = ptr->record;
 	    *key = ptr->key;
-	    st_free_entry(ptr);
+	    st_free_entry(table, ptr);
 	    return 1;
 	}
     }
@@ -742,6 +838,9 @@ st_shift(register st_table *table, register st_data_t *key, st_data_t *value)
     st_table_entry **prev;
     register st_table_entry *ptr;
 
+    /* shift makes no sense on unordered hashes, I guess */
+    if (!st_ordered_p(table)) return -1;
+
     if (table->num_entries == 0) {
         if (value != 0) *value = 0;
         return 0;
@@ -761,7 +860,7 @@ st_shift(register st_table *table, register st_data_t *key, st_data_t *value)
     *prev = ptr->next;
     if (value != 0) *value = ptr->record;
     *key = ptr->key;
-    st_free_entry(ptr);
+    st_free_entry(table, ptr);
     return 1;
 }
 
@@ -793,7 +892,7 @@ st_cleanup_safe(st_table *table, st_data_t never)
 	    if (ptr->key == never) {
 		tmp = ptr;
 		*last = ptr = ptr->next;
-		st_free_entry(tmp);
+		st_free_entry(table, tmp);
 	    }
 	    else {
 		ptr = *(last = &ptr->next);
@@ -806,7 +905,7 @@ int
 st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg)
 {
     st_index_t hash_val, bin_pos;
-    register st_table_entry *ptr, **last, *tmp;
+    register st_utable_entry *ptr, **last, *tmp;
     st_data_t value = 0, old_key;
     int retval, existing = 0;
 
@@ -869,12 +968,12 @@ st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data
 	    break;
 	  case ST_DELETE:
 	    if (!existing) break;
-	    last = &table->bins[bin_pos];
+	    last = (st_utable_entry **)&table->bins[bin_pos];
 	    for (; (tmp = *last) != 0; last = &tmp->next) {
 		if (ptr == tmp) {
 		    *last = ptr->next;
 		    remove_entry(table, ptr);
-		    st_free_entry(ptr);
+		    st_free_entry(table, ptr);
 		    break;
 		}
 	    }
@@ -902,12 +1001,16 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t
 	    if (key == never) continue;
 	    retval = (*func)(key, val, arg, 0);
 	    if (!table->entries_packed) {
-		FIND_ENTRY(table, ptr, hash, i);
+		st_utable_entry *uptr;
+
+		FIND_ENTRY(table, uptr, hash, i);
 		if (retval == ST_CHECK) {
-		    if (!ptr) goto deleted;
+		    if (!uptr) goto deleted;
 		}
 		if (table->num_entries == 0) return 0;
+		if (!st_ordered_p(table)) return 1; /* error, unsupported */
 		head = st_head(table);
+		ptr = (st_table_entry *)uptr;
 		next = list_entry(ptr->olist.next, st_table_entry, olist);
 		goto unpacked;
 	    }
@@ -933,39 +1036,80 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t
 	}
 	return 0;
     }
-
-    head = st_head(table);
-    list_for_each_safe(head, ptr, next, olist) {
-	if (ptr->key != never) {
-	    i = hash_pos(ptr->hash, table->num_bins);
-	    retval = (*func)(ptr->key, ptr->record, arg, 0);
-	  unpacked:
-	    switch (retval) {
-	      case ST_CHECK:	/* check if hash is modified during iteration */
-		for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
-		    if (!tmp) {
-		      deleted:
-			/* call func with error notice */
-			retval = (*func)(0, 0, arg, 1);
-			return 1;
+    else if (st_ordered_p(table)) {
+	head = st_head(table);
+	list_for_each_safe(head, ptr, next, olist) {
+	    if (ptr->key != never) {
+		i = hash_pos(ptr->hash, table->num_bins);
+		retval = (*func)(ptr->key, ptr->record, arg, 0);
+	      unpacked:
+		switch (retval) {
+		  case ST_CHECK:
+		    /* check if hash is modified during iteration */
+		    for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
+			if (!tmp) {
+			  deleted:
+			    /* call func with error notice */
+			    retval = (*func)(0, 0, arg, 1);
+			    return 1;
+			}
+		    }
+		    /* fall through */
+		  case ST_CONTINUE:
+		    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) {
+			    remove_entry(table, ptr);
+			    ptr->key = ptr->record = never;
+			    ptr->hash = 0;
+			    break;
+			}
 		    }
+		    if (table->num_entries == 0) return 0;
 		}
-		/* fall through */
-	      case ST_CONTINUE:
-		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) {
-			remove_entry(table, ptr);
-			ptr->key = ptr->record = never;
-			ptr->hash = 0;
-			break;
+	    }
+	}
+    }
+    else { /* unordered + unpacked */
+	st_index_t i;
+
+	for (i = 0; i < table->num_bins; i++) {
+	    for (ptr = table->bins[i]; ptr != 0;) {
+		if (ptr->key == never) goto continue_never;
+		retval = (*func)(ptr->key, ptr->record, arg, 0);
+		switch (retval) {
+		case ST_CHECK:
+		    /* check if hash is modified during iteration */
+		    for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
+			if (!tmp) {
+			    /* call func with error notice */
+			    retval = (*func)(0, 0, arg, 1);
+			    return 1;
+			}
+		    }
+		    /* fall through */
+		case ST_CONTINUE:
+continue_never:
+		    ptr = ptr->next;
+		    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) {
+			    remove_entry(table, ptr);
+			    ptr->key = ptr->record = never;
+			    ptr->hash = 0;
+			    break;
+			}
 		    }
+		    if (table->num_entries == 0) return 0;
 		}
-		if (table->num_entries == 0) return 0;
 	    }
 	}
     }
@@ -989,9 +1133,12 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 	    hash = PHASH(table, i);
 	    retval = (*func)(key, val, arg, 0);
 	    if (!table->entries_packed) {
-		FIND_ENTRY(table, ptr, hash, i);
-		if (!ptr) return 0;
+		st_utable_entry *uptr;
+		FIND_ENTRY(table, uptr, hash, i);
+		if (!uptr) return 0;
+		if (!st_ordered_p(table)) return 1; /* error, unsupported */
 		head = st_head(table);
+		ptr = (st_table_entry *)uptr;
 		next = list_entry(ptr->olist.next, st_table_entry, olist);
 		goto unpacked;
 	    }
@@ -1009,29 +1156,63 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 	}
 	return 0;
     }
+    else if (st_ordered_p(table)) {
+	head = st_head(table);
+	list_for_each_safe(head, ptr, next, olist) {
+	    i = hash_pos(ptr->hash, table->num_bins);
+	    retval = (*func)(ptr->key, ptr->record, arg, 0);
+	  unpacked:
+	    switch (retval) {
+	      case ST_CONTINUE:
+		break;
+	      case ST_CHECK:
+	      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) {
+			*last = ptr->next;
+			remove_entry(table, ptr);
+			st_free_entry(table, ptr);
+			break;
+		    }
+		}
+		if (table->num_entries == 0) return 0;
+	    }
+	}
+    }
+    else { /* unordered */
+	st_index_t i;
 
-    head = st_head(table);
-    list_for_each_safe(head, ptr, next, olist) {
-	i = hash_pos(ptr->hash, table->num_bins);
-	retval = (*func)(ptr->key, ptr->record, arg, 0);
-      unpacked:
-	switch (retval) {
-	  case ST_CONTINUE:
-	    break;
-	  case ST_CHECK:
-	  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) {
-		    *last = ptr->next;
-		    remove_entry(table, ptr);
-		    st_free_entry(ptr);
-		    break;
+	for (i = 0; i < table->num_bins; i++) {
+	    st_utable_entry *utmp;
+	    st_utable_entry **ulast = 0;
+	    st_utable_entry *uptr = (st_utable_entry *)table->bins[i];
+
+	    while (uptr) {
+		retval = (*func)(uptr->key, uptr->record, arg);
+		switch (retval) {
+		case ST_CHECK:
+		case ST_STOP:
+		    return 0;
+		case ST_DELETE:
+		    ulast = (st_utable_entry **)&table->bins[hash_pos(
+		                                uptr->hash, table->num_bins)];
+		    for (; (utmp = *ulast) != 0; ulast = &utmp->next) {
+			if (uptr == utmp) {
+			    *ulast = uptr->next;
+			    remove_entry(table, uptr);
+			    st_free_entry(table, uptr);
+			    break;
+			}
+		    }
+		    if (table->num_entries == 0) return 0;
+		    /* fall through */
+		case ST_CONTINUE:
+		    uptr = uptr->next;
 		}
 	    }
-	    if (table->num_entries == 0) return 0;
 	}
     }
     return 0;
@@ -1043,6 +1224,9 @@ get_keys(st_table *table, st_data_t *keys, st_index_t size, int check, st_data_t
     st_data_t key;
     st_data_t *keys_start = keys;
 
+    /* unsupported in unordered mode */
+    if (!st_ordered_p(table)) return (st_index_t)-1;
+
     if (table->entries_packed) {
 	st_index_t i;
 
@@ -1086,6 +1270,9 @@ get_values(st_table *table, st_data_t *values, st_index_t size, int check, st_da
     st_data_t key;
     st_data_t *values_start = values;
 
+    /* unsupported in unordered mode */
+    if (!st_ordered_p(table)) return (st_index_t)-1;
+
     if (table->entries_packed) {
 	st_index_t i;
 
@@ -1132,6 +1319,8 @@ st_reverse_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, s
     enum st_retval retval;
     st_index_t i;
 
+    if (!st_ordered_p(table)) return -1;
+
     if (table->entries_packed) {
 	for (i = table->real_entries; 0 < i;) {
 	    st_data_t key, val;
@@ -1221,6 +1410,8 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
     struct list_head *head;
     st_index_t i;
 
+    if (!st_ordered_p(table)) return -1;
+
     if (table->entries_packed) {
 	for (i = table->real_entries; 0 < i;) {
 	    st_data_t key, val;
diff --git a/string.c b/string.c
index 34c77a5..166acf0 100644
--- a/string.c
+++ b/string.c
@@ -9285,4 +9285,5 @@ Init_frozen_strings(void)
 {
     assert(!frozen_strings);
     frozen_strings = st_init_table_with_size(&fstring_hash_type, 1000);
+    frozen_strings->ordered = 0;
 }
-- 
EW