28 #define ST_DEFAULT_MAX_DENSITY 5
29 #define ST_DEFAULT_INIT_TABLE_SIZE 11
62 #define malloc xmalloc
63 #define calloc xcalloc
64 #define free(x) xfree(x)
67 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
69 #define alloc(type) (type*)malloc((size_t)sizeof(type))
70 #define Calloc(n,s) (char*)calloc((n),(s))
72 #define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
75 #define do_hash(key,table) (unsigned int)(st_index_t)(*(table)->type->hash)((key))
76 #define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
87 static const unsigned int primes[] = {
125 for (i=3; i<31; i++) {
126 if ((1<<i) > size)
return 1<<
i;
133 if (newsize > size)
return primes[
i];
148 int all, total, num, str, strcase;
150 static int init_st = 0;
155 char fname[10+
sizeof(
long)*3];
156 FILE *f = fopen((
snprintf(fname,
sizeof(fname),
"/tmp/col%ld", (
long)getpid()), fname),
"w");
157 fprintf(f,
"collision: %d / %d (%6.2f)\n", collision.all, collision.total,
158 ((
double)collision.all / (collision.total)) * 100);
159 fprintf(f,
"num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase);
164 #define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
174 const char *e =
getenv(
"ST_HASH_LOG");
175 if (!e || !*e) init_st = 1;
251 for(i = 0; i < table->
num_bins; i++) {
252 ptr = table->
bins[
i];
284 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
285 ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
292 if (type == &type_numhash) {
295 else if (type == &type_strhash) {
298 else if (type == &type_strcasehash) {
302 #define COLLISION (collision_check ? count_collision(table->type) : (void)0)
303 #define FOUND_ENTRY (collision_check ? collision.total++ : (void)0)
309 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
310 (bin_pos) = (hash_val)%(table)->num_bins;\
311 (ptr) = (table)->bins[(bin_pos)];\
313 if (PTR_NOT_EQUAL((table), (ptr), (hash_val), key)) {\
315 while (PTR_NOT_EQUAL((table), (ptr)->next, (hash_val), key)) {\
316 (ptr) = (ptr)->next;\
318 (ptr) = (ptr)->next;\
322 #define collision_check 0
341 hash_val =
do_hash(key, table);
348 if (value != 0) *value = ptr->
record;
370 hash_val =
do_hash(key, table);
377 if (result != 0) *result = ptr->
key;
382 #undef collision_check
383 #define collision_check 1
385 #define MORE_PACKABLE_P(table) \
386 ((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \
387 (table)->num_entries+1 <= MAX_PACKED_NUMHASH)
389 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
391 st_table_entry *entry;\
392 if ((table)->num_entries > ST_DEFAULT_MAX_DENSITY * (table)->num_bins) {\
394 (bin_pos) = (hash_val) % (table)->num_bins;\
397 entry = alloc(st_table_entry);\
399 entry->hash = (hash_val);\
401 entry->record = (value);\
402 entry->next = (table)->bins[(bin_pos)];\
403 if ((table)->head != 0) {\
405 (entry->back = (table)->tail)->fore = entry;\
406 (table)->tail = entry;\
409 (table)->head = (table)->tail = entry;\
410 entry->fore = entry->back = 0;\
412 (table)->bins[(bin_pos)] = entry;\
413 (table)->num_entries++;\
424 table->
bins = packed_bins;
459 hash_val =
do_hash(key, table);
463 ADD_DIRECT(table, key, value, hash_val, bin_pos);
498 hash_val =
do_hash(key, table);
503 ADD_DIRECT(table, key, value, hash_val, bin_pos);
530 hash_val =
do_hash(key, table);
531 bin_pos = hash_val % table->
num_bins;
532 ADD_DIRECT(table, key, value, hash_val, bin_pos);
544 for (i = 0; i < new_num_bins; ++
i) new_bins[i] = 0;
546 table->
bins = new_bins;
548 if ((ptr = table->
head) != 0) {
550 hash_val = ptr->
hash % new_num_bins;
551 ptr->
next = new_bins[hash_val];
552 new_bins[hash_val] = ptr;
553 }
while ((ptr = ptr->
fore) != 0);
566 if (new_table == 0) {
570 *new_table = *old_table;
574 if (new_table->
bins == 0) {
584 if ((ptr = old_table->
head) != 0) {
586 tail = &new_table->
head;
594 hash_val = entry->
hash % num_bins;
595 entry->
next = new_table->
bins[hash_val];
596 new_table->
bins[hash_val] = entry;
598 *tail = prev = entry;
600 }
while ((ptr = ptr->
fore) != 0);
601 new_table->
tail = prev;
607 #define REMOVE_ENTRY(table, ptr) do \
609 if ((ptr)->fore == 0 && (ptr)->back == 0) { \
614 st_table_entry *fore = (ptr)->fore, *back = (ptr)->back; \
615 if (fore) fore->back = back; \
616 if (back) back->fore = fore; \
617 if ((ptr) == (table)->head) (table)->head = fore; \
618 if ((ptr) == (table)->tail) (table)->tail = back; \
620 (table)->num_entries--; \
641 if (value != 0) *value = 0;
647 for (prev = &table->
bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->
next) {
651 if (value != 0) *value = ptr->
record;
658 if (value != 0) *value = 0;
673 table->
bins[i*2] = (
void *)never;
677 if (value != 0) *value = 0;
682 ptr = table->
bins[hash_val];
684 for (; ptr != 0; ptr = ptr->
next) {
685 if ((ptr->
key != never) &&
EQUAL(table, ptr->
key, *key)) {
688 if (value != 0) *value = ptr->
record;
694 if (value != 0) *value = 0;
706 if (value != 0) *value = 0;
720 prev = &table->
bins[hash_val];
721 for (;(ptr = *prev) != 0; prev = &ptr->
next) {
722 if (ptr == table->
head) {
725 if (value != 0) *value = ptr->
record;
733 if (value != 0) *value = 0;
750 table->
bins[j*2] = table->
bins[i*2];
751 table->
bins[j*2+1] = table->
bins[i*2+1];
758 for (i = 0; i < table->
num_bins; i++) {
759 ptr = *(last = &table->
bins[
i]);
761 if (ptr->
key == never) {
763 *last = ptr = ptr->
next;
767 ptr = *(last = &ptr->
next);
786 retval = (*func)(
key, val,
arg);
790 if (!ptr)
goto deleted;
791 goto unpacked_continue;
830 for (tmp = table->
bins[i]; tmp != ptr; tmp = tmp->
next) {
834 retval = (*func)(0, 0,
arg, 1);
847 for (; (tmp = *
last) != 0; last = &tmp->
next) {
853 if (ptr == tmp)
return 0;
859 }
while (ptr && table->
head);
878 retval = (*func)(
key, val,
arg);
887 retval = (*func)(0, 0,
arg, 1);
905 if ((ptr = table->
head) != 0) {
912 for (tmp = table->
bins[i]; tmp != ptr; tmp = tmp->
next) {
915 retval = (*func)(0, 0,
arg, 1);
927 for (; (tmp = *
last) != 0; last = &tmp->
next) {
941 }
while (ptr && table->
head);
1015 #define FNV1_32A_INIT 0x811c9dc5
1020 #define FNV_32_PRIME 0x01000193
1026 register const char *
string = (
const char *)arg;
1034 hval ^= (
unsigned int)*
string++;
1043 #ifndef UNALIGNED_WORD_ACCESS
1044 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
1045 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \
1046 defined(__mc68020__)
1047 # define UNALIGNED_WORD_ACCESS 1
1050 #ifndef UNALIGNED_WORD_ACCESS
1051 # define UNALIGNED_WORD_ACCESS 0
1059 #define MurmurMagic_1 (st_index_t)0xc6a4a793
1060 #define MurmurMagic_2 (st_index_t)0x5bd1e995
1062 #define MurmurMagic MurmurMagic_1
1064 #if SIZEOF_ST_INDEX_T > 4
1065 #define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2)
1067 #define MurmurMagic MurmurMagic_2
1104 #define murmur_step(h, k) murmur((h), (k), 16)
1107 #define murmur1(h) murmur_step((h), 16)
1109 #define murmur1(h) murmur_step((h), 24)
1115 const char *data = ptr;
1120 #define data_at(n) (st_index_t)((unsigned char)data[(n)])
1121 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
1122 #if SIZEOF_ST_INDEX_T > 4
1123 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4
1124 #if SIZEOF_ST_INDEX_T > 8
1125 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \
1126 UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8
1127 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16
1129 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8
1131 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4
1134 #if !UNALIGNED_WORD_ACCESS
1141 #ifdef WORDS_BIGENDIAN
1142 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1143 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
1145 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1146 t |= data_at(n) << CHAR_BIT*(n)
1149 #undef UNALIGNED_ADD
1152 #ifdef WORDS_BIGENDIAN
1166 #ifdef WORDS_BIGENDIAN
1167 t = (t << sr) | (d >> sl);
1169 t = (t >> sr) | (d << sl);
1177 pack = len < (size_t)align ? (
int)len : align;
1180 #ifdef WORDS_BIGENDIAN
1181 # define UNALIGNED_ADD(n) case (n) + 1: \
1182 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1184 # define UNALIGNED_ADD(n) case (n) + 1: \
1185 d |= data_at(n) << CHAR_BIT*(n)
1188 #undef UNALIGNED_ADD
1190 #ifdef WORDS_BIGENDIAN
1191 t = (t << sr) | (d >> sl);
1193 t = (t >> sr) | (d << sl);
1197 if (len < (
size_t)align)
goto skip_tail;
1216 #ifdef WORDS_BIGENDIAN
1217 # define UNALIGNED_ADD(n) case (n) + 1: \
1218 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1220 # define UNALIGNED_ADD(n) case (n) + 1: \
1221 t |= data_at(n) << CHAR_BIT*(n)
1224 #undef UNALIGNED_ADD
1228 # if !UNALIGNED_WORD_ACCESS
1250 #ifdef WORDS_BIGENDIAN
1251 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
1254 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
1257 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
1262 #ifndef WORDS_BIGENDIAN
1263 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
1266 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
1269 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
1284 #undef st_hash_start
1294 register const char *
string = (
const char *)arg;
1302 unsigned int c1, c2;
1305 c1 = (
unsigned char)*s1++;
1306 c2 = (
unsigned char)*s2++;
1307 if (c1 ==
'\0' || c2 ==
'\0') {
1308 if (c1 !=
'\0')
return 1;
1309 if (c2 !=
'\0')
return -1;
1312 if ((
unsigned int)(c1 -
'A') <= (
'Z' -
'A')) c1 +=
'a' -
'A';
1313 if ((
unsigned int)(c2 -
'A') <= (
'Z' -
'A')) c2 +=
'a' -
'A';
1326 unsigned int c1, c2;
1329 c1 = (
unsigned char)*s1++;
1330 c2 = (
unsigned char)*s2++;
1331 if (c1 ==
'\0' || c2 ==
'\0') {
1332 if (c1 !=
'\0')
return 1;
1333 if (c2 !=
'\0')
return -1;
1336 if ((
unsigned int)(c1 -
'A') <= (
'Z' -
'A')) c1 +=
'a' -
'A';
1337 if ((
unsigned int)(c2 -
'A') <= (
'Z' -
'A')) c2 +=
'a' -
'A';
1351 register const char *
string = (
const char *)arg;
1358 unsigned int c = (
unsigned char)*
string++;
1359 if ((
unsigned int)(c -
'A') <= (
'Z' -
'A')) c +=
'a' -
'A';
static st_index_t new_size(st_index_t size)
#define REMOVE_ENTRY(table, ptr)
void st_cleanup_safe(st_table *table, st_data_t never)
size_t strlen(const char *)
st_index_t st_hash_uint32(st_index_t h, uint32_t i)
st_index_t st_numhash(st_data_t n)
void st_clear(st_table *table)
st_table * st_init_strcasetable_with_size(st_index_t size)
static const struct st_hash_type type_strhash
st_index_t st_hash_start(st_index_t h)
void rb_raise(VALUE exc, const char *fmt,...)
st_table * st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
st_table * st_init_numtable(void)
int st_strncasecmp(const char *s1, const char *s2, size_t n)
static void unpack_entries(register st_table *table)
unsigned int entries_packed
RUBY_EXTERN void * memmove(void *, const void *, size_t)
#define do_hash_bin(key, table)
#define MAX_PACKED_NUMHASH
#define FIND_ENTRY(table, ptr, hash_val, bin_pos)
st_table * st_init_strtable_with_size(st_index_t size)
st_table * st_init_strtable(void)
#define SIZEOF_ST_INDEX_T
st_table * st_init_strcasetable(void)
st_index_t st_hash_end(st_index_t h)
#define UNALIGNED_ADD_ALL
static st_index_t murmur_finish(st_index_t h)
#define murmur_step(h, k)
static st_index_t murmur(st_index_t h, st_index_t k, int r)
int st_get_key(st_table *table, register st_data_t key, st_data_t *result)
static const unsigned int primes[]
static st_index_t strhash(st_data_t)
int st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
int st_foreach(st_table *table, int(*func)(ANYARGS), st_data_t arg)
struct st_table_entry * head
static void rehash(st_table *)
SSL_METHOD *(* func)(void)
st_index_t st_hash(const void *ptr, size_t len, st_index_t h)
static const struct st_hash_type type_strcasehash
struct st_table_entry ** bins
register unsigned int len
int st_lookup(st_table *table, register st_data_t key, st_data_t *value)
int st_shift(register st_table *table, register st_data_t *key, st_data_t *value)
int st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never)
st_table * st_copy(st_table *old_table)
int st_insert2(register st_table *table, register st_data_t key, st_data_t value, st_data_t(*func)(st_data_t))
#define do_hash(key, table)
void st_add_direct(st_table *table, st_data_t key, st_data_t value)
#define EQUAL(table, x, y)
int st_reverse_foreach(st_table *, int(*)(ANYARGS), st_data_t)
#define ADD_DIRECT(table, key, value, hash_val, bin_pos)
const struct st_hash_type * type
int st_numcmp(st_data_t x, st_data_t y)
int st_strcasecmp(const char *s1, const char *s2)
void st_free_table(st_table *table)
static st_index_t strcasehash(st_data_t)
size_t st_memsize(const st_table *table)
st_index_t st_hash_uint(st_index_t h, st_index_t i)
struct st_table_entry * tail
static const struct st_hash_type type_numhash
st_table * st_init_table(const struct st_hash_type *type)
st_table * st_init_numtable_with_size(st_index_t size)
#define MORE_PACKABLE_P(table)
int st_insert(register st_table *table, register st_data_t key, st_data_t value)