# Ordered/unordered st\_table

**URL:** <https://www.ruby-forum.com/t/ordered-unordered-st-table/113718>\
**Category:** Development\
**Created:** [September 4, 2007, 11:08am UTC](https://www.ruby-forum.com/t/ordered-unordered-st-table/113718 "2007-09-04T11:08:24Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![nobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/e9c0ed/32.png) [@nobu](https://www.ruby-forum.com/u/nobu)\
**Post date:** [September 4, 2007, 11:08am UTC](https://www.ruby-forum.com/t/ordered-unordered-st-table/113718/1 "2007-09-04T11:08:24Z")

</div>

e$B$J$+$@$G$9!#e(B

e$B$D$$$G$K!"e(Bst\_tablee$B$N=g=x$NM-L5$r@ZBX$($k%Q%C%A$G$9!#e(B

# 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;

+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);

---

<div class="post-metadata">

**Author:** ![nobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/e9c0ed/32.png) [@nobu](https://www.ruby-forum.com/u/nobu)\
**Post date:** [September 8, 2007, 5:45pm UTC](https://www.ruby-forum.com/t/ordered-unordered-st-table/113718/2 "2007-09-08T17:45:20Z")

</div>

In article [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid),  
Nobuyoshi N. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> e$B$D$$$G$K!"e(Bst\_tablee$B$N=g=x$NM-L5$r@ZBX$($k%Q%C%A$G$9!#e(B

r13412 e$B$K%Q%C%A$rEv$F$FB,$C$F$\_$^$7$?!#e(B

e$BMWAG$NB?$$e(B st\_table (e$B$?$@$7e(B Hash e$B0J30e(B)  
e$B$,8z$/$O$:$J$N$G!"$^e(B  
e$B$:$O%7%s%%k$rBgNL$K@8@.$7$F$\_$^$9!#e(B

e$B%Q%C%AA0e(B:  
% time ./ruby -e ‘s = “a”; 1000000.times { s.intern; s.succ! }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 95048 kB  
./ruby -e 6.52s user 0.12s system 99% cpu 6.667 total

e$B%Q%C%A8ee(B:  
% time ./ruby -e ‘s = “a”; 1000000.times { s.intern; s.succ! }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 79336 kB  
./ruby -e 6.92s user 0.12s system 98% cpu 7.169 total

95Mbytes e$B$+$ie(B 79Mbytes e$B$H!"$=$l$J$j$K8:$C$F$$$^$9!#e(B16%  
e$B$/$ie(B  
e$B$$$G$9$+!#e(B

e$B$^$?!"e(B(rdoc e$B$GLdBj$K$J$C$?e(B) iv\_tbl e$B$N1F6A$r$_$k$?$a$Ke(B  
26e$B8D$Ne(B  
e$B%$%s%9%?%s%9JQ?t$,$"$k%\*%V%8%'%/%H$r$?$/$5$s@8@.$7$F$_$^$9!#e(B

e$B%Q%C%AA0e(B:  
% time ./ruby -e ’  
class C  
def initialize  
@a = @b = @c = @d = @e = @f = @g = @h = @i = @j = @k = @l = @m =  
@n = @o = @p = @q = @r = @s = @t = @u = @v = @w = @x = @y = @z = 0  
end  
end  
a = []; 100000.times { a \<\< C.new }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 96896 kB  
./ruby -e 2.68s user 0.12s system 98% cpu 2.833 total

e$B%Q%C%A8ee(B:  
% time ./ruby -e ’  
class C  
def initialize  
@a = @b = @c = @d = @e = @f = @g = @h = @i = @j = @k = @l = @m =  
@n = @o = @p = @q = @r = @s = @t = @u = @v = @w = @x = @y = @z = 0  
end  
end  
a = []; 100000.times { a \<\< C.new }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 74420 kB  
./ruby -e 2.60s user 0.11s system 97% cpu 2.774 total

e$B$3$l$be(B 97Mbytes e$B$+$ie(B 74Mbytes e$B$H!"e(B23%  
e$B$/$i$$8:$C$F$$$^$9!#e(B

numtable e$B$Ge(B linked list e$B$r;H$$$O$8$a$ke(B  
(e$B=g=x$r$D$1$J$$$3$H$Ke(B  
e$B$h$k8z2L$,=P;O$a$ke(B) e$B$N$O%$%s%9%?%s%9JQ?te(B  
6e$B$D$J$N$G!"$=$3$rB,$Ce(B  
e$B$F$\_$k$H0J2\<$N$h$&$K$J$j$^$9!#e(B

e$B%Q%C%AA0e(B:  
% time ./ruby -e ’  
class C  
def initialize  
@a = @b = @c = @d = @e = @f = 0  
end  
end  
a = []; 100000.times { a \<\< C.new }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 34348 kB  
./ruby -e 0.86s user 0.05s system 98% cpu 0.920 total

e$B%Q%C%A8ee(B:  
% time ./ruby -e ’  
class C  
def initialize  
@a = @b = @c = @d = @e = @f = 0  
end  
end  
a = []; 100000.times { a \<\< C.new }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 27576 kB  
./ruby -e 0.80s user 0.06s system 99% cpu 0.873 total

e$B$3$N\>l9g$G$be(B 34Mbytes e$B$+$ie(B 28Mbytes e$B$He(B 20%  
e$B$/$i$$8:$C$F$$$^e(B  
e$B$9!#e(B

e$B$R$H$D$N%_%V%8%'%/%H$KBP$7$F%$%s%9%?%s%9JQ?t$re(B 1000e$B8D$/$i$$e(B  
e$B:n$l$P7`E_$J%a%b%j:o8:$r\<B8=$9$kNc$r:n$l$k$+$b$7$l$^$;$s!#e(B

e$B$J$\*!"e(Brdoc  
e$B\<+?H$bB,$j$^$7$?$,!“e(B(e$BEvA3$N$3$H$G$O$”$j$^$9$,e(B) e$B$b$O$de(B  
e$B$\<$s$\<$s8z$-$^$;$s!#e(B