# Packed st\_table

**URL:** <https://www.ruby-forum.com/t/packed-st-table/113721>\
**Category:** Development\
**Created:** [September 4, 2007, 11:23am UTC](https://www.ruby-forum.com/t/packed-st-table/113721 "2007-09-04T11:23:29Z")\
**Posts on this page:** 8\
**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:23am UTC](https://www.ruby-forum.com/t/packed-st-table/113721/1 "2007-09-04T11:23:29Z")

</div>

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

e$BEDCf$5$s$K!Ve(BHashe$B$N=g=x$O$I$C$A$G$b$$$$$+$i$3$C$A$r$d$l!W$H$$$o$le(B  
e$B$?$N$G!"e(Bst\_tablee$B$Ne(Bentries\_packede$B$r0lHL2=$7$F$\_$^$7$?!#e(B

# Index: st.c

— st.c (revision 13339)  
+++ st.c (working copy)  
@@ -61,5 +61,4 @@ static void rehash(st\_table \*);

#define alloc(type) (type\*)malloc((size\_t)sizeof(type))  
-#define Calloc(n,s) (char\*)calloc((n),(s))

#define EQUAL(table,x,y) ((x)==(y) || (\*table-\>type-\>compare)((x),(y))  
== 0)  
@@ -77,5 +76,5 @@ static void rehash(st\_table \*);  
Table of prime numbers 2^n+a, 2\<=n\<=30.  
\*/  
-static long primes[] = {  
+static const unsigned int primes[] = {  
8 + 3,  
16 + 3,  
@@ -110,5 +109,5 @@ static long primes[] = {

static int  
-new\_size(int size)  
+new\_size(unsigned int size)  
{  
int i;  
@@ -120,8 +119,8 @@ new\_size(int size)  
return -1;  
#else

- int newsize;

- unsigned int newsize;

- i \< (int )(sizeof(primes)/sizeof(primes[0]));

- i \< (int)(sizeof(primes)/sizeof(primes[0])) - 1;  
i++, newsize \<\<= 1)  
{  
@@ -146,5 +145,12 @@ stat\_col()  
#endif

-#define MAX\_PACKED\_NUMHASH 5  
+#define PACKED\_RATIO(table) ((table)-\>type == &type\_numhash ? 2 : 3)  
+#define PACKED\_COUNT(table, n) ((n) \* PACKED\_RATIO(table))  
+#define PACKABLE(table, n) \

- ((n) \* PACKED\_RATIO(table) \<= ST\_DEFAULT\_INIT\_TABLE\_SIZE)
- 

+#define PACKED\_EQUAL(table, i, r, hash\_val, key)\

- ((® \< 3 || (st\_data\_t)(table)-\>bins[(i)+2] == (hash\_val)) &&\
- 

```
EQUAL((table), (st_data_t)(table)->bins[i], (key)))

```

st\_table\*  
@@ -161,11 +167,12 @@ st\_init\_table\_with\_size(const struct st\_

```
 size = new_size(size); /* round up to prime number */

```

- if (size == -1) return 0;

- tbl-\>entries\_packed = type == &type\_numhash && size/2 \<=  
MAX\_PACKED\_NUMHASH;
- tbl-\>num\_bins = size;
- tbl-\>bins = (st\_table\_entry \*_)Calloc(size,  
sizeof(st\_table\_entry_));

- tbl-\>entries\_packed = 1;
- tbl-\>num\_bins = 0;
- tbl-\>bins = calloc(size, sizeof(st\_table\_entry\*));  
tbl-\>head = 0;

@@ -207,8 +214,9 @@ st\_clear(st\_table \*table)  
{  
register st\_table\_entry \*ptr, \*next;

- int i;

- unsigned int i;

- 

```
   table->num_bins = 0;
   return;

```

}  
@@ -263,10 +271,12 @@ st\_lookup(st\_table \*table, register st\_d

if (table-\>entries\_packed) {

- 

```
   int i;

```

- 

```
   for (i = 0; i < table->num_entries; i++) {

```

- 

```
       if ((st_data_t)table->bins[i*2] == key) {

```

- 

```
           if (value !=0) *value = (st_data_t)table->bins[i*2+1];

```

- 

```
           return 1;

```

- 

```
       }

```

- 

```
   unsigned int i, hash_val;

```

- const unsigned int r = PACKED\_RATIO(table);
- hash\_val = r \> 2 ? do\_hash(key, table) : key;
- for (i = 0; i \< table-\>num\_bins; i += r) {
- 

```
 if (PACKED_EQUAL(table, i, r, hash_val, key)) {

```

- if (value != 0) \*value = (st\_data\_t)table-\>bins[i+1];
- return 1;
- 

```
 }
   }
   return 0;

```

@@ -314,17 +324,45 @@ static void  
unpack\_entries(register st\_table \*table)  
{

- int i;
- struct st\_table\_entry _packed\_bins[MAX\_PACKED\_NUMHASH_2];
- int num\_entries = table-\>num\_entries;

- struct st\_table\_entry \*packed\_bins[ST\_DEFAULT\_INIT\_TABLE\_SIZE];
- unsigned int i, num\_bins = table-\>num\_bins;
- const unsigned int r = PACKED\_RATIO(table);

- memcpy(packed\_bins, table-\>bins, sizeof(struct st\_table\_entry _) \*  
num\_entries_2);

- memcpy(packed\_bins, table-\>bins, sizeof(struct st\_table\_entry \*) \*  
num\_bins);  
table-\>entries\_packed = 0;  
table-\>num\_entries = 0;
- table-\>num\_bins = ST\_DEFAULT\_INIT\_TABLE\_SIZE;  
memset(table-\>bins, 0, sizeof(struct st\_table\_entry \*) \*  
table-\>num\_bins);

- for (i = 0; i \< num\_entries; i++) {
- 

```
   st_insert(table, (st_data_t)packed_bins[i*2], 

```

(st\_data\_t)packed\_bins[i\*2+1]);

- for (i = 0; i \< num\_bins; i += r) {
- 

```
   st_data_t key = (st_data_t)packed_bins[i];

```

- st\_data\_t value = (st\_data\_t)packed\_bins[i+1];
- unsigned int hash\_val, bin\_pos;
- 
- hash\_val = r \> 2 ? (unsigned int)packed\_bins[i+2] : key;
- 

```
   bin_pos = hash_val % table->num_bins;

```

- ADD\_DIRECT(table, key, value, hash\_val, bin\_pos);  
}  
}

+static int  
+add\_direct\_packed(register st\_table \*table, const unsigned int r,

- 

```
 st_data_t key, st_data_t value, unsigned int hash_val)

```

+{

- unsigned int i;
- 
- if (table-\>num\_bins \>= ST\_DEFAULT\_INIT\_TABLE\_SIZE / r \* r) {
- table-\>bins = xrealloc(table-\>bins, sizeof(struct st\_table\_entry \*) \*  
(table-\>num\_bins+r));
- }
- else if (!PACKABLE(table, table-\>num\_bins+r)) {
- return 0;
- }
- i = table-\>num\_bins;
- table-\>num\_bins += r;
- table-\>num\_entries++;
- table-\>bins[i] = (struct st\_table\_entry\*)key;
- table-\>bins[i+1] = (struct st\_table\_entry\*)value;
- if (r \> 2) table-\>bins[i+2] = (struct st\_table\_entry\*)hash\_val;
- return 1;  
+}
- 

int  
st\_insert(register st\_table \*table, register st\_data\_t key, st\_data\_t  
value)  
@@ -334,20 +372,17 @@ st\_insert(register st\_table \*table, regi

```
 if (table->entries_packed) {

```

- 

```
   int i;

```

- 

```
   for (i = 0; i < table->num_entries; i++) {

```

- 

```
       if ((st_data_t)table->bins[i*2] == key) {

```

- 

```
           table->bins[i*2+1] = (struct st_table_entry*)value;

```

- 

```
   unsigned int i, hash_val;

```

- const unsigned int r = PACKED\_RATIO(table);
- hash\_val = r \> 2 ? do\_hash(key, table) : key;
- 

```
   for (i = 0; i < table->num_bins; i += r) {

```

- 

```
 if (PACKED_EQUAL(table, i, r, hash_val, key)) {

```

- 

```
           table->bins[i+1] = (struct st_table_entry*)value;
           return 1;
       }
   }

```

- 

```
   if ((table->num_entries+1) * 2 <= table->num_bins && 

```

table-\>num\_entries+1 \<= MAX\_PACKED\_NUMHASH) {

- 

```
       i = table->num_entries++;

```

- 

```
       table->bins[i*2] = (struct st_table_entry*)key;

```

- 

```
       table->bins[i*2+1] = (struct st_table_entry*)value;

```

- if (add\_direct\_packed(table, r, key, value, hash\_val)) {  
return 0;  
}

- 

```
   else {

```

- 

```
       unpack_entries(table);

```

- 

```
   }

```

- unpack\_entries(table);  
}

@@ -371,14 +406,11 @@ st\_add\_direct(st\_table \*table, st\_data\_t

```
 if (table->entries_packed) {

```

- 

```
   int i;

```

- 

```
   if ((table->num_entries+1) * 2 <= table->num_bins && 

```

table-\>num\_entries+1 \<= MAX\_PACKED\_NUMHASH) {

- 

```
       i = table->num_entries++;

```

- 

```
       table->bins[i*2] = (struct st_table_entry*)key;

```

- 

```
       table->bins[i*2+1] = (struct st_table_entry*)value;

```

- 

```
   unsigned int hash_val;

```

- const unsigned int r = PACKED\_RATIO(table);
- hash\_val = r \> 2 ? do\_hash(key, table) : key;
- if (add\_direct\_packed(table, r, key, value, hash\_val)) {  
return;  
}

- 

```
   else {

```

- 

```
       unpack_entries(table);

```

- 

```
   }

```

- unpack\_entries(table);  
}

@@ -392,10 +424,11 @@ rehash(register st\_table \*table)  
{  
register st\_table\_entry \*ptr, \*\*new\_bins;

- int i, new\_num\_bins;

- unsigned int i, 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\*));

- if (size == -1) return;
- new\_num\_bins = (unsigned int)size;
- new\_bins = 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;  
@@ -416,5 +449,5 @@ st\_copy(st\_table \*old\_table)  
st\_table \*new\_table;  
st\_table\_entry \*ptr, \*entry, \*prev, \*\*tail;

- int num\_bins = old\_table-\>num\_bins;

- unsigned int num\_bins = old\_table-\>num\_bins;  
unsigned int hash\_val;

@@ -425,6 +458,5 @@ st\_copy(st\_table \*old\_table)

```
 *new_table = *old_table;

```

- new\_table-\>bins = (st\_table\_entry\*\*)
- Calloc((unsigned)num\_bins, sizeof(st\_table\_entry\*));

- new\_table-\>bins = calloc(num\_bins, sizeof(st\_table\_entry\*));

- 

```
   int i;

```

- 

```
   for (i = 0; i < table->num_entries; i++) {

```

- 

```
       if ((st_data_t)table->bins[i*2] == *key) {

```

- 

```
           if (value != 0) *value = (st_data_t)table->bins[i*2+1];

```

- 

```
   unsigned int i;

```

- const unsigned int r = PACKED\_RATIO(table);
- hash\_val = r \> 2 ? do\_hash(\*key, table) : 0;
- 

```
   for (i = 0; i < table->num_bins; i += r) {

```

- 

```
       if (PACKED_EQUAL(table, i, r, hash_val, *key)) {

```

- 

```
           if (value != 0) *value = (st_data_t)table->bins[i+1];
           table->num_entries--;

```

- 

```
           memmove(&table->bins[i*2], &table->bins[(i+1)*2],

```

- 

```
                   sizeof(struct st_table_entry*) * 

```

2\*(table-\>num\_entries-i));

- table-\>num\_bins -= r;
- 

```
           memmove(&table->bins[i], &table->bins[i+r],

```

- 

```
                   sizeof(struct st_table_entry*) * 

```

(table-\>num\_bins-i));  
return 1;  
}  
@@ -522,4 +557,20 @@ st\_delete\_safe(register st\_table \*table,  
register st\_table\_entry \*ptr;

- if (table-\>entries\_packed) {
- 

```
   unsigned int i;

```

- const unsigned int r = PACKED\_RATIO(table);
- hash\_val = r \> 2 ? do\_hash(\*key, table) : 0;
- 

```
   for (i = 0; i < table->num_bins; i += r) {

```

- 

```
       if (PACKED_EQUAL(table, i, r, hash_val, *key)) {

```

- 

```
           if (value != 0) *value = (st_data_t)table->bins[i+1];

```

- table-\>num\_entries–;
- 

```
           table->bins[i] = table->bins[i+1] = (struct 

```

st\_table\_entry \*)never;

- 

```
           return 1;

```

- 

```
       }

```

- 

```
   }

```

- 

```
   if (value != 0) *value = 0;

```

- 

```
   return 0;

```

- }
- hash\_val = do\_hash\_bin(\*key, table);  
ptr = table-\>bins[hash\_val];  
@@ -543,5 +594,18 @@ st\_cleanup\_safe(st\_table \*table, st\_data  
{  
st\_table\_entry \*ptr, \*\*last, \*tmp;

- int i;

- unsigned int i;

- 
- if (table-\>entries\_packed) {

- 

```
   unsigned int j;

```

- const unsigned int r = PACKED\_RATIO(table);

- 

```
   for (i = j = 0; i < table->num_bins; i += r) {

```

- 

```
       if ((st_data_t)table->bins[i] != never && i > j) {

```

- memcpy(&table-\>bins[j], table-\>bins[i],

- 

```
      sizeof(st_table_entry *) * r);

```

- j++;

- 

```
       }

```

- 

```
   }

```

- 

```
   return;

```

- }

- int i, end;

- unsigned int i;

- int end;

- 

```
   for (i = 0; i < table->num_entries; i++) {

```

- 

```
       int j;

```

- const unsigned int r = PACKED\_RATIO(table);
- 

```
   for (i = 0; i < table->num_bins; i += r) {
       st_data_t key, val;

```

- 

```
       key = (st_data_t)table->bins[i*2];

```

- 

```
       val = (st_data_t)table->bins[i*2+1];

```

- 

```
       key = (st_data_t)table->bins[i];

```

- 

```
       val = (st_data_t)table->bins[i+1];
       retval = (*func)(key, val, arg);
       switch (retval) {
   case ST_CHECK: /* check if hash is modified during iteration 

```

\*/

- 

```
           for (j = 0; j < table->num_entries; j++) {

```

- 

```
               if ((st_data_t)table->bins[j*2] == key)

```

- 

```
                   break;

```

- 

```
           }

```

- 

```
           if (j == table->num_entries) {

```

- 

```
               /* call func with error notice */

```

- 

```
               retval = (*func)(0, 0, arg, 1);

```

- 

```
               return 1;

```

- 

```
           }

```

/\* fall through \*/  
case ST\_CONTINUE:  
@@ -592,7 +648,7 @@ st\_foreach(st\_table \*table, int (\*func)(  
case ST\_DELETE:  
table-\>num\_entries–;
- 

```
           memmove(&table->bins[i*2], &table->bins[(i+1)*2],

```

- 

```
                   sizeof(struct st_table_entry*) * 

```

2\*(table-\>num\_entries-i));

- 

```
           i--;

```

- if (i \>= (table-\>num\_bins -= r)) return 0;
- memmove(&table-\>bins[i], &table-\>bins[i+1],
- 

```
 sizeof(struct st_table_entry*) * (table->num_bins-i));
           break;
       }

```

@@ -645,24 +701,17 @@ st\_reverse\_foreach(st\_table \*table, int  
st\_table\_entry \*ptr, \*\*last, \*tmp;  
enum st\_retval retval;

- int i, end;

- unsigned int i;

- int end;

- 

```
   for (i = table->num_entries-1; 0 <= i; i--) {

```

- 

```
       int j;

```

- const unsigned int r = PACKED\_RATIO(table);
- 

```
   for (i = table->num_bins; i > 0;) {
       st_data_t key, val;

```

- 

```
       key = (st_data_t)table->bins[i*2];

```

- 

```
       val = (st_data_t)table->bins[i*2+1];

```

- 

```
 i -= r;

```

- 

```
       key = (st_data_t)table->bins[i];

```

- 

```
       val = (st_data_t)table->bins[i+1];
       retval = (*func)(key, val, arg);
       switch (retval) {
   case ST_CHECK: /* check if hash is modified during iteration 

```

\*/

- 

```
           for (j = 0; j < table->num_entries; j++) {

```

- 

```
               if ((st_data_t)table->bins[j*2] == key)

```

- 

```
                   break;

```

- 

```
           }

```

- 

```
           if (j == table->num_entries) {

```

- 

```
               /* call func with error notice */

```

- 

```
               retval = (*func)(0, 0, arg, 1);

```

- 

```
               return 1;

```

- 

```
           }

```

/\* fall through \*/  
case ST\_CONTINUE:  
@@ -672,6 +721,7 @@ st\_reverse\_foreach(st\_table \*table, int  
case ST\_DELETE:  
table-\>num\_entries–;
- 

```
           memmove(&table->bins[i*2], &table->bins[(i+1)*2],

```

- 

```
                   sizeof(struct st_table_entry*) * 

```

2\*(table-\>num\_entries-i));

- if (i \>= (table-\>num\_bins -= r)) break;
- 

```
           memmove(&table->bins[i], &table->bins[i+1],

```

- 

```
                   sizeof(struct st_table_entry*) * 

```

(table-\>num\_bins-i));  
break;  
}

---

<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 9, 2007, 10:39am UTC](https://www.ruby-forum.com/t/packed-st-table/113721/2 "2007-09-09T10:39:37Z")

</div>

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

At Sat, 8 Sep 2007 21:22:27 +0900,  
Tanaka A. wrote in [ruby-dev:31761]:

> e$BB,$C$F$_$?$H$3$m!"$I$&$be(B 1e$BMWAG$N\>l9g$7$+%a%b$j@aLs$N8z2L$,8+e(B  
> e$B$i$l$J$$$N$GD4$Y$F$_$?$H$3$m!"0J2\<$N$h$&$J=$@5$,I,MW$J$h$&$Ge(B

e$B$9$$$^$;$s!"$^$@$$$m$$$mESCf$@$C$?$h$&$G$9!#e(B

> e$B$9!#e(Badd\_direct\_packed e$B$N@hF,$N%3!\<%I$O$h$/$o$+$j$^$;$s$G$7$?!#e(B

e$B$3$l$O!"e(Biteratione$B$NESCf$Ge(Bunpacke$B$7$F$7$^$&$H$J$K$+$HITET9g$,5/$-e(B  
e$B$=$&$J$N$G!"C1=c$KDI2C$9$k$h$&$K$7$?$s$G$9$,!"e(Bforeache$B$N$[$&$Ge(B  
e$B%A%’%C%/$9$k$[$&$,$$$$$+$b$7$l$^$;$s!#e(B

[ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

diff -wU2 st.c st.c  
— st.c (working copy)  
+++ st.c (working copy)  
@@ -172,6 +172,6 @@  
tbl-\>type = type;  
tbl-\>num\_entries = 0;

- tbl-\>entries\_packed = 1;
- tbl-\>num\_bins = 0;

- tbl-\>entries\_packed = size == ST\_DEFAULT\_INIT\_TABLE\_SIZE;
- tbl-\>num\_bins = tbl-\>entries\_packed ? 0 : size;  
tbl-\>bins = calloc(size, sizeof(st\_table\_entry\*));  
tbl-\>head = 0;  
@@ -350,8 +350,5 @@  
unsigned int i;

- if (table-\>num\_bins \>= ST\_DEFAULT\_INIT\_TABLE\_SIZE / r \* r) {
- table-\>bins = xrealloc(table-\>bins, sizeof(struct st\_table\_entry \*) \*  
(table-\>num\_bins+r));
- }
- else if (!PACKABLE(table, table-\>num\_bins+r)) {

- if (!PACKABLE(table, table-\>num\_bins+r)) {  
return 0;  
}  
@@ -458,4 +455,6 @@

- if (old\_table-\>entries\_packed)

- num\_bins = ST\_DEFAULT\_INIT\_TABLE\_SIZE;  
new\_table-\>bins = calloc(num\_bins, sizeof(st\_table\_entry\*));

@@ -601,9 +600,10 @@  
for (i = j = 0; i \< table-\>num\_bins; i += r) {  
if ((st\_data\_t)table-\>bins[i] != never && i \> j) {

- memcpy(&table-\>bins[j], table-\>bins[i],

- memcpy(&table-\>bins[j], &table-\>bins[i],  
sizeof(st\_table\_entry \*) \* r);

- j++;

- j += r;  
}  
}
- 

```
   table->num_bins = j;
   return;

```

}  
@@ -639,4 +639,13 @@  
val = (st\_data\_t)table-\>bins[i+1];  
retval = (\*func)(key, val, arg);
- 

```
 if (!table->entries_packed) {

```

- if ((ptr = table-\>head) != 0) {
- 

```
   while (i > 0) {

```

- 

```
 ptr = ptr->fore;

```

- 

```
 i -= r;

```

- 

```
   }

```

- }
- goto linked;
- 

```
 }
       switch (retval) {
   case ST_CHECK: /* check if hash is modified during iteration 

```

\*/  
@@ -649,5 +658,5 @@  
table-\>num\_entries–;  
if (i \>= (table-\>num\_bins -= r)) return 0;

- memmove(&table-\>bins[i], &table-\>bins[i+1],

- memmove(&table-\>bins[i], &table-\>bins[i+r],  
sizeof(struct st\_table\_entry\*) \* (table-\>num\_bins-i));  
break;  
@@ -658,4 +667,5 @@

- 

```
 linked:

```

do {  
end = ptr-\>fore == table-\>head;  
@@ -712,4 +722,13 @@  
val = (st\_data\_t)table-\>bins[i+1];  
retval = (\*func)(key, val, arg);

- 

```
 if (!table->entries_packed) {

```

- if ((ptr = table-\>head) != 0) {

- 

```
   while (i > 0) {

```

- 

```
 ptr = ptr->fore;

```

- 

```
 i -= r;

```

- 

```
   }

```

- }

- goto linked;

- 

```
 }
       switch (retval) {
   case ST_CHECK: /* check if hash is modified during iteration 

```

\*/  
@@ -722,5 +741,5 @@  
table-\>num\_entries–;  
if (i \>= (table-\>num\_bins -= r)) break;

- 

```
           memmove(&table->bins[i], &table->bins[i+1],

```

- memmove(&table-\>bins[i], &table-\>bins[i+r],  
sizeof(struct st\_table\_entry\*) \*  
(table-\>num\_bins-i));  
break;  
@@ -732,4 +751,5 @@  
if ((ptr = table-\>head) != 0) {  
ptr = ptr-\>back;
- 

```
 linked:

```

do {  
end = ptr == table-\>head;

---

<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, 2:23pm UTC](https://www.ruby-forum.com/t/packed-st-table/113721/3 "2007-09-08T14:23:56Z")

</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$BEDCf$5$s$K!Ve(BHashe$B$N=g=x$O$I$C$A$G$b$$$$$+$i$3$C$A$r$d$l!W$H$$$o$le(B  
> e$B$?$N$G!"e(Bst\_tablee$B$Ne(Bentries\_packede$B$r0lHL2=$7$F$\_$^$7$?!#e(B

e$BB,$C$F$_$?$H$3$m!"$I$&$be(B 1e$BMWAG$N\>l9g$7$+%a%b$j@aLs$N8z2L$,8+e(B  
e$B$i$l$J$$$N$GD4$Y$F$_$?$H$3$m!"0J2\<$N$h$&$J=$@5$,I,MW$J$h$&$Ge(B  
e$B$9!#e(Badd\_direct\_packed  
e$B$N@hF,$N%3!\<%I$O$h$/$o$+$j$^$;$s$G$7$?!#e(B

ST\_DEFAULT\_INIT\_TABLE\_SIZE e$B0J30$G$be(B packed  
e$B$r2DG=$K$9$k$K$O!“e(B  
struct st\_table e$B$Ne(B head e$B$N$H$3$m$K%5%$%:$rF~$l$l$P$$$$$O$:$Ge(B  
e$B$9$,!”$d$C$F$^$;$s!#e(B

— st.c.nakada 2007-09-08 16:23:47.000000000 +0900  
+++ st.c 2007-09-08 21:02:11.000000000 +0900  
@@ -153,6 +153,8 @@ stat\_col()  
(((r) \< 3 || (st\_data\_t)(table)-\>bins[(i)+2] == (hash\_val)) &&  
EQUAL((table), (st\_data\_t)(table)-\>bins[i], (key)))

+static void unpack\_entries(register st\_table _table);  
+  
st\_table_  
st\_init\_table\_with\_size(const struct st\_hash\_type _type, int size)  
{  
@@ -175,6 +177,9 @@ st\_init\_table\_with\_size(const struct st\_  
tbl-\>num\_bins = 0;  
tbl-\>bins = calloc(size, sizeof(st\_table\_entry_));  
tbl-\>head = 0;

- if (size != ST\_DEFAULT\_INIT\_TABLE\_SIZE) {

- 

```
 unpack_entries(tbl);

```

- }

- /\*  
if (table-\>num\_bins \>= ST\_DEFAULT\_INIT\_TABLE\_SIZE / r \* r) {  
table-\>bins = xrealloc(table-\>bins, sizeof(struct st\_table\_entry \*) \*  
(table-\>num\_bins+r));  
}

- else if (!PACKABLE(table, table-\>num\_bins+r)) {

- else \*/

- if (!PACKABLE(table, table-\>num\_bins/r+1)) {  
return 0;  
}  
i = table-\>num\_bins;  
@@ -457,6 +464,8 @@ st\_copy(st\_table \*old\_table)  
}

- if (old\_table-\>entries\_packed)

- 

```
 num_bins = ST_DEFAULT_INIT_TABLE_SIZE;

```

new\_table-\>bins = calloc(num\_bins, sizeof(st\_table\_entry\*));

if (new\_table-\>bins == 0) {  
@@ -600,11 +609,12 @@ st\_cleanup\_safe(st\_table \*table, st\_data  
const unsigned int r = PACKED\_RATIO(table);  
for (i = j = 0; i \< table-\>num\_bins; i += r) {  
if ((st\_data\_t)table-\>bins[i] != never && i \> j) {

- memcpy(&table-\>bins[j], table-\>bins[i],

- memcpy(&table-\>bins[j], &table-\>bins[i],  
sizeof(st\_table\_entry \*) \* r);

- j++;

- j += r;  
}  
}
- 

```
   table->num_bins = j;
   return;

```

}

@@ -648,7 +658,7 @@ st\_foreach(st\_table \*table, int (\*func)(  
case ST\_DELETE:  
table-\>num\_entries–;  
if (i \>= (table-\>num\_bins -= r)) return 0;

- memmove(&table-\>bins[i], &table-\>bins[i+1],

- memmove(&table-\>bins[i], &table-\>bins[i+r],  
sizeof(struct st\_table\_entry\*) \* (table-\>num\_bins-i));  
break;  
}  
@@ -721,7 +731,7 @@ st\_reverse\_foreach(st\_table \*table, int  
case ST\_DELETE:  
table-\>num\_entries–;  
if (i \>= (table-\>num\_bins -= r)) break;

- 

```
           memmove(&table->bins[i], &table->bins[i+1],

```

- 

```
           memmove(&table->bins[i], &table->bins[i+r],
                   sizeof(struct st_table_entry*) * 

```

(table-\>num\_bins-i));  
break;  
}

e$B$G!"B,Dj7k2L$G$9$,!"0lHV8z$/$O$:$Ne(B 3e$BMWAG$Ne(B Hash  
e$B$G$O0J2\<$N$he(B  
e$B$&$K$J$j$^$9!#e(B

e$B@aLs$7$J$$$H0J2\<$N$h$&$Ke(B 199Mbytes e$B$+$+$j$^$9!#e(B

% time ./ruby -e ‘a = []; 1000000.times {|i| a \<\< {0=\>i,1=\>i,2=\>i} }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 199312 kB  
./ruby -e 7.37s user 0.31s system 99% cpu 7.711 total

e$B@aLs$9$k$H0J2\<$N$h$&$Ke(B 105Mbytes e$B$G:Q$\_$^$9!#e(B

% time ./ruby -e ‘a = []; 1000000.times {|i| a \<\< {0=\>i,1=\>i,2=\>i} }  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 105468 kB  
./ruby -e 4.43s user 0.15s system 99% cpu 4.607 total

e$B$b$A$m$s!"B.EY$be(B 7.7e$BIC$+$ie(B 4.6e$BIC$K9bB.2=$7$^$9!#e(B

e$B$G$O!“e(B11word e$B$Ne(B bins e$B$+$i$”$U$l$Fe(B linked list  
e$B$KJQ$o$ke(B 4e$BMWAGe(B  
e$B$J$i$I$&$+!“$H$$$&$H!”@aLs$7$J$$\>l9g$O0J2\<$N$h$&$K$J$j$^$9!#e(B

% time ./ruby -e ‘a = []; 1000000.times {|i| a \<\< {0=\>i,1=\>i,2=\>i,3=\>i}  
}  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 230468 kB  
./ruby -e 9.09s user 0.33s system 99% cpu 9.461 total

e$B@aLs$7$?\>l9g$O0J2\<$N$h$&$K$J$j$^$9!#e(B

% time ./ruby -e ‘a = []; 1000000.times {|i| a \<\< {0=\>i,1=\>i,2=\>i,3=\>i}  
}  
print File.read(“/proc/#{$$}/status”)[/^VmSize.\*\n/]’  
VmSize: 230472 kB  
./ruby -e 9.73s user 0.34s system 99% cpu 10.117 total

e$B$I$A$i$b;HMQ%a%b%j$,e(B 230Mbytes  
e$B$G$[$\F1$8$J$N$OM=A[$I$\*$j$G!"e(B  
e$BB.EYDc2\<$Oe(B 9.5e$BIC$+$ie(B 10.1e$BIC$H$$$&$/$i$$$G$9!#e(B

e$B$h$j8=\<BE\*$JNc$H$7$Fe(B REXML e$B$re(B…  
e$B$H;W$C$?$N$G$9$,!"e(BREXML e$B$Oe(B  
e$B:#$Oe(B character encodings differ e$B$K$h$jF0$+$J$$$h$&$J$N$G!"B,e(B  
e$BDj$G$-$^$;$s$G$7$?!#$&$%$`!#e(B

---

<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 9, 2007, 3:52pm UTC](https://www.ruby-forum.com/t/packed-st-table/113721/4 "2007-09-09T15:52: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$3$l$O!"e(Biteratione$B$NESCf$Ge(Bunpacke$B$7$F$7$^$&$H$J$K$+$HITET9g$,5/$-e(B  
> e$B$=$&$J$N$G!"C1=c$KDI2C$9$k$h$&$K$7$?$s$G$9$,!"e(Bforeache$B$N$[$&$Ge(B  
> e$B%A%'%C%/$9$k$[$&$,$$$$$+$b$7$l$^$;$s!#e(B

e$B$J$k$[$I!#$=$N\>u67$O9M$($F$$$^$;$s$G$7$?!#e(B

> [ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

2e$BMWAG$N$H$-e(B packed e$B$G$J$/$J$j$^$9!#e(B

(gdb) run -e ‘p({1=\>1,2=\>2})’  
Starting program: /home/src/ruby/phash/phash2/ruby/ruby -e  
‘p({1=\>1,2=\>2})’  
Failed to read a valid object file image from memory.  
[Thread debugging using libthread\_db enabled]  
[New Thread -1210640160 (LWP 18963)]  
[New Thread -1211372624 (LWP 18964)]  
[Switching to Thread -1210640160 (LWP 18963)]

Breakpoint 1, rb\_p (obj=3083657840) at io.c:4038  
4038 rb\_io\_write(rb\_stdout, rb\_obj\_as\_string(rb\_inspect(obj)));  
(gdb) p _((struct RHash_)obj)-\>ntbl  
$4 = {type = 0x81319a4, num\_bins = 11, entries\_packed = 0, num\_entries =  
2, bins = 0x8199e68, head = 0x8199e98}

> @@ -350,8 +350,5 @@  
> unsigned int i;
> 
> - if (table-\>num\_bins \>= ST\_DEFAULT\_INIT\_TABLE\_SIZE / r \* r) {
> - table-\>bins = xrealloc(table-\>bins, sizeof(struct st\_table\_entry \*) \* (table-\>num\_bins+r));
> - }
> - else if (!PACKABLE(table, table-\>num\_bins+r)) {
> 
> - if (!PACKABLE(table, table-\>num\_bins+r)) {  
> return 0;  
> }

PACKABLE e$B$NBhe(B2e$B0z?t$,LdBj$G$9$+$M!#e(B

---

<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 9, 2007, 4:04pm UTC](https://www.ruby-forum.com/t/packed-st-table/113721/5 "2007-09-09T16:04:21Z")

</div>

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:31765] Re: packed st\_table”  
on Sun, 9 Sep 2007 17:38:29 +0900, Nobuyoshi N.  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

|\> e$B$9!#e(Badd\_direct\_packed e$B$N@hF,$N%3!\<%I$O$h$/$o$+$j$^$;$s$G$7$?!#e(B  
|  
|e$B$3$l$O!"e(Biteratione$B$NESCf$Ge(Bunpacke$B$7$F$7$^$&$H$J$K$+$HITET9g$,5/$-e(B  
|e$B$=$&$J$N$G!"C1=c$KDI2C$9$k$h$&$K$7$?$s$G$9$,!"e(Bforeache$B$N$[$&$Ge(B  
|e$B%A%'%C%/$9$k$[$&$,$$$$$+$b$7$l$^$;$s!#e(B  
|  
|[ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

e$B$\*G$$;$7$^$9$N$GNI$5$=$&$J;~E@$G%3%\_%C%H$7$F$/$@$5$$!#e(B

---

<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 11, 2007, 6:00am UTC](https://www.ruby-forum.com/t/packed-st-table/113721/6 "2007-09-11T06:00:26Z")

</div>

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

At Sun, 9 Sep 2007 22:50:58 +0900,  
Tanaka A. wrote in [ruby-dev:31766]:

> > [ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B
> 
> 2e$BMWAG$N$H$-e(B packed e$B$G$J$/$J$j$^$9!#e(B

> PACKABLE e$B$NBhe(B2e$B0z?t$,LdBj$G$9$+$M!#e(B

e$B$?$7$+$K!"e(BPACKED\_RATIOe$B$r$+$1$A$c$$$1$^$;$s$M!#e(B

#define PACKABLE(table, n) ((n) \<= ST\_DEFAULT\_INIT\_TABLE\_SIZE)

e$B$HD\>$7$Fe(B[ruby-dev:31761]e$B$N%3!\<%I$r;n$7$F$\_$^$7$?!#e(B  
st-bench3.rbe$B$,e(B3e$BMWAG!"e(Bst-bench4.rbe$B$,e(B4e$BMWAG$G$9!#e(B

./miniruby-normal st-bench3.rb  
VmSize: 199740 kB

real 0m2.263s  
user 0m2.104s  
sys 0m0.168s

./miniruby-packed st-bench3.rb  
VmSize: 105896 kB

real 0m1.261s  
user 0m1.160s  
sys 0m0.100s

./miniruby-normal st-bench4.rb  
VmSize: 230892 kB

real 0m2.687s  
user 0m2.448s  
sys 0m0.248s

./miniruby-packed st-bench4.rb  
VmSize: 230896 kB

real 0m2.765s  
user 0m2.540s  
sys 0m0.216s

3e$BMWAG$^$G$N%a%b%j@aLs$H9bB.2=$O$?$7$+$K82Cx$G$9!#BP$9$ke(B4e$BMWAG$G$Ne(B  
e$BB.EYDc2\<$Oe(B3%e$B\<e!#e(B3%e$B$rBg$-$$$H$_$k$+!"e(B3e$BMWAG$^$G$N8z2L$KBP$9$k%H%l!\<e(B  
e$B%I%\*%U$H$_$k$+!#e(B

---

<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 25, 2007, 11:10pm UTC](https://www.ruby-forum.com/t/packed-st-table/113721/7 "2007-09-25T23:10:11Z")

</div>

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:31729] packed st\_table”  
on Tue, 4 Sep 2007 17:43:49 +0900, Nobuyoshi N.  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

|e$BEDCf$5$s$K!Ve(BHashe$B$N=g=x$O$I$C$A$G$b$$$$$+$i$3$C$A$r$d$l!W$H$$$o$le(B  
|e$B$?$N$G!"e(Bst\_tablee$B$Ne(Bentries\_packede$B$r0lHL2=$7$F$\_$^$7$?!#e(B

e$B%3!\<%IFI$s$G$d$C$F$k$3$H$OM}2r$7$^$7$?!#$G!“$3$l$G$I$N$/$i$$e(B  
e$B4r$7$$$s$G$7$g$&$M!#$D$^$j!“e(Bnumhashe$B$G$J$$MWAG$,e(B5e$B$D0J2\<$Ne(B  
st\_tablee$B$,$I$l$@$1$”$k$+$H$+!”%Q%U%)!\<%^%s%9\>e$N\>c32$OL5$$$+!"e(B  
e$B$H$+$G$9$,!#e(B

---

<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 28, 2007, 11:29am UTC](https://www.ruby-forum.com/t/packed-st-table/113721/8 "2007-09-28T11:29:40Z")

</div>

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

> e$B$h$j8=\<BE\*$JNc$H$7$Fe(B REXML e$B$re(B… e$B$H;W$C$?$N$G$9$,!"e(BREXML e$B$Oe(B  
> e$B:#$Oe(B character encodings differ e$B$K$h$jF0$+$J$$$h$&$J$N$G!"B,e(B  
> e$BDj$G$-$^$;$s$G$7$?!#$&$%$`!#e(B

e$B:G6a!“e(BREXML e$B$,F0$/$h$&$K$J$C$F$$$k$N$G!”;n$7$F$\_$^$7$?!#e(B  
(e$B$H$$$&$+!";n$7$F$b$7$g$&$,$J$$$3$H$,$o$+$C$?$H$$$&$+e(B)

RAA e$B$Ne(B all.html e$B$r$H$C$F$-$Fe(B tidy -asxml e$B$Ge(B XML  
e$B$GJQ49$7$Fe(B  
500kbytes e$B$/$i$$$K$J$C$?$N$re(B r13546 e$B$D$^$je(B T\_OBJECT  
e$B$N%Q%C%Ae(B  
e$B$,$“$?$C$?\>/$78e$/$i$$$Ne(B Ruby e$B$Ge(B REXML  
e$B$r;H$C$F%Q!\<%:$7$F$\_e(B  
e$B$^$7$?!#e(B  
(packed st\_table e$B$H$+$N%Q%C%A$O$\<$s$\<$s$”$F$F$^$;$se(B)

massif e$B$GF@$i$l$?%0%i%U$,e(B  
[http://cvs.m17n.org/~akr/diary/2007-09/r13546/massif.rexml-raa.png](http://cvs.m17n.org/~akr/diary/2007-09/r13546/massif.rexml-raa.png)  
e$B$G!“e(B  
[http://cvs.m17n.org/~akr/diary/2007-09/](http://cvs.m17n.org/~akr/diary/2007-09/)  
e$B$K;HMQ$7$?%9%/%j%W%H$J$I$,CV$$$F$”$j$^$9!#e(B

e$B%0%i%U$r8+$k$H!"J8;zNs$,\>CHq%a%b%j$NBgH\>$r@j$a$F$$$^$9!#e(B

e$B$J$N$G!“%O%C%7%e$r$$$8$C$F$b$\<$s$\<$s8z$-$=$&$K$”$j$^$;$s!#e(B

REXML e$B$r$I$&$K$+$7$?$1$l$P!“J8;zNs$r$I$&$K$+$9$kI,MW$,$”$k$Ge(B  
e$B$7$g$&!#e(B

e$BJ8;zNs$N\>CHq%a%b%j$,7c$7$/?6F0$7$F$$$k$3$H$+$i$\_$F!"0l;~E\*$Je(B  
e$BJ8;zNs$rBgNL$K@8@.$7$F$Oe(B GC e$B$G2s\<}$7$F$$$k$N$G$O$J$$$+$H$$$&e(B  
e$B5$$,$7$^$9!#$b$7$3$N?dB,$,@5$7$1$l$P!"0l;~E\*$JJ8;zNs%\*%V%8%'e(B  
e$B%/%H$r$J$k$Y$/@8@.$7$J$$$h$&$K$9$k$H$$$&$N$,8z$-$=$&$G$9!#e(B