33 #define STATIC_ASSERT(name, expr) typedef int static_assert_##name##_check[(expr) ? 1 : -1];
35 #define ST_DEFAULT_MAX_DENSITY 5
36 #define ST_DEFAULT_INIT_TABLE_SIZE 11
37 #define ST_DEFAULT_SECOND_TABLE_SIZE 19
38 #define ST_DEFAULT_PACKED_TABLE_SIZE 18
39 #define PACKED_UNIT (int)(sizeof(st_packed_entry) / sizeof(st_table_entry*))
40 #define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry))
55 #define type_numhash st_hashtype_num
77 #define malloc xmalloc
78 #define calloc xcalloc
79 #define realloc xrealloc
80 #define free(x) xfree(x)
83 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
85 #define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
87 #define do_hash(key,table) (st_index_t)(*(table)->type->hash)((key))
88 #define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
91 #define st_alloc_entry() (st_table_entry *)malloc(sizeof(st_table_entry))
92 #define st_free_entry(entry) free(entry)
93 #define st_alloc_table() (st_table *)malloc(sizeof(st_table))
94 #define st_dealloc_table(table) free(table)
95 #define st_alloc_bins(size) (st_table_entry **)calloc(size, sizeof(st_table_entry *))
96 #define st_free_bins(bins, size) free(bins)
106 #define bins as.big.bins
107 #define head as.big.head
108 #define tail as.big.tail
109 #define real_entries as.packed.real_entries
112 #define PACKED_BINS(table) ((table)->as.packed.entries)
113 #define PACKED_ENT(table, i) PACKED_BINS(table)[i]
114 #define PKEY(table, i) PACKED_ENT((table), (i)).key
115 #define PVAL(table, i) PACKED_ENT((table), (i)).val
116 #define PHASH(table, i) PACKED_ENT((table), (i)).hash
117 #define PKEY_SET(table, i, v) (PKEY((table), (i)) = (v))
118 #define PVAL_SET(table, i, v) (PVAL((table), (i)) = (v))
119 #define PHASH_SET(table, i, v) (PHASH((table), (i)) = (v))
189 for (i=3; i<31; i++) {
190 if ((1<<i) > size)
return 1<<
i;
196 for (i = 0, newsize =
MINSIZE; i <
numberof(primes); i++, newsize <<= 1) {
197 if (newsize > size)
return primes[
i];
212 int all, total, num,
str, strcase;
214 static int init_st = 0;
219 char fname[10+
sizeof(long)*3];
220 FILE *
f = fopen((
snprintf(fname,
sizeof(fname),
"/tmp/col%ld", (
long)getpid()), fname),
"w");
221 fprintf(f,
"collision: %d / %d (%6.2f)\n", collision.all, collision.total,
222 ((
double)collision.all / (collision.total)) * 100);
223 fprintf(f,
"num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase);
236 const char *
e =
getenv(
"ST_HASH_LOG");
237 if (!e || !*e) init_st = 1;
319 for (i = 0; i < table->
num_bins; i++) {
320 ptr = table->
bins[
i];
352 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
353 ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
363 else if (type == &type_strhash) {
366 else if (type == &type_strcasehash) {
370 #define COLLISION (collision_check ? count_collision(table->type) : (void)0)
371 #define FOUND_ENTRY (collision_check ? collision.total++ : (void)0)
377 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) \
378 ((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = (hash_val)%(table)->num_bins)))
399 (
PHASH(table, i) != hash_val || !
EQUAL(table, key,
PKEY(table, i)))) {
411 #define collision_check 0
419 hash_val =
do_hash(key, table);
424 if (value != 0) *value =
PVAL(table, i);
436 if (value != 0) *value = ptr->
record;
447 hash_val =
do_hash(key, table);
452 if (result != 0) *result =
PKEY(table, i);
464 if (result != 0) *result = ptr->
key;
469 #undef collision_check
470 #define collision_check 1
480 entry->
hash = hash_val;
494 bin_pos = hash_val % table->
num_bins;
497 entry =
new_entry(table, key, value, hash_val, bin_pos);
499 if (table->
head != 0) {
520 table->
as.
packed.entries = packed_bins;
522 #if ST_DEFAULT_INIT_TABLE_SIZE == ST_DEFAULT_PACKED_TABLE_SIZE
529 chain = &tmp_table.
head;
534 entry =
new_entry(&tmp_table, key, val, hash,
537 entry->
back = preventry;
539 chain = &entry->
fore;
540 }
while (++i < MAX_PACKED_HASH);
570 hash_val =
do_hash(key, table);
585 add_direct(table, key, value, hash_val, bin_pos);
602 hash_val =
do_hash(key, table);
619 add_direct(table, key, value, hash_val, bin_pos);
633 hash_val =
do_hash(key, table);
651 table->
bins = new_bins;
653 if ((ptr = table->
head) != 0) {
655 hash_val = ptr->
hash % new_num_bins;
656 ptr->
next = new_bins[hash_val];
657 new_bins[hash_val] =
ptr;
658 }
while ((ptr = ptr->
fore) != 0);
671 if (new_table == 0) {
675 *new_table = *old_table;
678 if (new_table->
bins == 0) {
688 if ((ptr = old_table->
head) != 0) {
690 tailp = &new_table->
head;
698 hash_val = entry->
hash % num_bins;
699 entry->
next = new_table->
bins[hash_val];
702 *tailp = prev =
entry;
703 tailp = &entry->
fore;
704 }
while ((ptr = ptr->
fore) != 0);
705 new_table->
tail = prev;
714 if (ptr->
fore == 0 && ptr->
back == 0) {
735 hash_val =
do_hash(*key, table);
740 if (value != 0) *value =
PVAL(table, i);
741 *key =
PKEY(table, i);
745 if (value != 0) *value = 0;
750 for (;(ptr = *prev) != 0; prev = &ptr->
next) {
754 if (value != 0) *value = ptr->
record;
761 if (value != 0) *value = 0;
771 hash_val =
do_hash(*key, table);
776 if (value != 0) *value =
PVAL(table, i);
777 *key =
PKEY(table, i);
781 if (value != 0) *value = 0;
787 for (; ptr != 0; ptr = ptr->
next) {
788 if ((ptr->
key != never) &&
EQUAL(table, ptr->
key, *key)) {
791 if (value != 0) *value = ptr->
record;
797 if (value != 0) *value = 0;
808 if (value != 0) *value = 0;
813 if (value != 0) *value =
PVAL(table, 0);
814 *key =
PKEY(table, 0);
820 while ((ptr = *prev) != table->
head) prev = &ptr->
next;
822 if (value != 0) *value = ptr->
record;
837 while (
PKEY(table, i) != never) {
841 if (
PKEY(table, i) == never)
continue;
851 for (i = 0; i < table->
num_bins; i++) {
852 ptr = *(last = &table->
bins[
i]);
854 if (ptr->
key == never) {
856 *last = ptr = ptr->
next;
860 ptr = *(last = &ptr->
next);
874 hash_val =
do_hash(key, table);
879 key =
PKEY(table, i);
880 value =
PVAL(table, i);
898 if (!existing)
break;
924 if (!existing)
break;
925 last = &table->
bins[bin_pos];
926 for (; (tmp = *
last) != 0; last = &tmp->
next) {
952 key =
PKEY(table, i);
953 val =
PVAL(table, i);
954 hash =
PHASH(table, i);
955 if (key == never)
continue;
960 if (!ptr)
goto deleted;
961 goto unpacked_continue;
967 if (
PHASH(table, i) == 0 &&
PKEY(table, i) == never) {
993 if (ptr->
key == never)
994 goto unpacked_continue;
1000 for (tmp = table->
bins[i]; tmp != ptr; tmp = tmp->
next) {
1004 retval = (*func)(0, 0,
arg, 1);
1017 for (; (tmp = *
last) != 0; last = &tmp->
next) {
1028 }
while (ptr && table->
head);
1043 key =
PKEY(table, i);
1044 val =
PVAL(table, i);
1045 hash =
PHASH(table, i);
1084 for (; (tmp = *
last) != 0; last = &tmp->
next) {
1095 }
while (ptr && table->
head);
1110 for (i = 0; i <
size; i++) {
1111 key =
PKEY(table, i);
1112 if (check && key == never)
continue;
1119 for (; ptr && keys < keys_end; ptr = ptr->
fore) {
1121 if (check && key == never)
continue;
1126 return keys - keys_start;
1132 return get_keys(table, keys, size, 0, 0);
1138 return get_keys(table, keys, size, 1, never);
1151 for (i = 0; i <
size; i++) {
1152 key =
PKEY(table, i);
1153 if (check && key == never)
continue;
1154 *values++ =
PVAL(table, i);
1160 for (; ptr && values < values_end; ptr = ptr->
fore) {
1162 if (check && key == never)
continue;
1167 return values - values_start;
1173 return get_values(table, values, size, 0, 0);
1179 return get_values(table, values, size, 1, never);
1194 key =
PKEY(table, i);
1195 val =
PVAL(table, i);
1205 retval = (*func)(0, 0,
arg, 1);
1221 if ((ptr = table->
head) != 0) {
1228 for (tmp = table->
bins[i]; tmp != ptr; tmp = tmp->
next) {
1231 retval = (*func)(0, 0,
arg, 1);
1243 for (; (tmp = *
last) != 0; last = &tmp->
next) {
1257 }
while (ptr && table->
head);
1331 #define FNV1_32A_INIT 0x811c9dc5
1336 #define FNV_32_PRIME 0x01000193
1342 register const char *
string = (
const char *)arg;
1350 hval ^= (
unsigned int)*
string++;
1359 #ifndef UNALIGNED_WORD_ACCESS
1360 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
1361 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD64) || \
1362 defined(__mc68020__)
1363 # define UNALIGNED_WORD_ACCESS 1
1366 #ifndef UNALIGNED_WORD_ACCESS
1367 # define UNALIGNED_WORD_ACCESS 0
1375 #define MurmurMagic_1 (st_index_t)0xc6a4a793
1376 #define MurmurMagic_2 (st_index_t)0x5bd1e995
1378 #define MurmurMagic MurmurMagic_1
1380 #if SIZEOF_ST_INDEX_T > 4
1381 #define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2)
1383 #define MurmurMagic MurmurMagic_2
1420 #define murmur_step(h, k) murmur((h), (k), 16)
1423 #define murmur1(h) murmur_step((h), 16)
1425 #define murmur1(h) murmur_step((h), 24)
1436 #define data_at(n) (st_index_t)((unsigned char)data[(n)])
1437 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
1438 #if SIZEOF_ST_INDEX_T > 4
1439 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4
1440 #if SIZEOF_ST_INDEX_T > 8
1441 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \
1442 UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8
1443 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16
1445 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8
1447 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4
1450 #if !UNALIGNED_WORD_ACCESS
1457 #ifdef WORDS_BIGENDIAN
1458 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1459 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
1461 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1462 t |= data_at(n) << CHAR_BIT*(n)
1465 #undef UNALIGNED_ADD
1468 #ifdef WORDS_BIGENDIAN
1482 #ifdef WORDS_BIGENDIAN
1483 t = (t << sr) | (d >> sl);
1485 t = (t >> sr) | (d << sl);
1493 pack = len < (size_t)align ? (
int)len : align;
1496 #ifdef WORDS_BIGENDIAN
1497 # define UNALIGNED_ADD(n) case (n) + 1: \
1498 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1500 # define UNALIGNED_ADD(n) case (n) + 1: \
1501 d |= data_at(n) << CHAR_BIT*(n)
1504 #undef UNALIGNED_ADD
1506 #ifdef WORDS_BIGENDIAN
1507 t = (t << sr) | (d >> sl);
1509 t = (t >> sr) | (d << sl);
1513 if (len < (
size_t)align)
goto skip_tail;
1532 #ifdef WORDS_BIGENDIAN
1533 # define UNALIGNED_ADD(n) case (n) + 1: \
1534 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1536 # define UNALIGNED_ADD(n) case (n) + 1: \
1537 t |= data_at(n) << CHAR_BIT*(n)
1540 #undef UNALIGNED_ADD
1544 # if !UNALIGNED_WORD_ACCESS
1566 #ifdef WORDS_BIGENDIAN
1567 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
1570 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
1573 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
1578 #ifndef WORDS_BIGENDIAN
1579 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
1582 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
1585 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
1600 #undef st_hash_start
1610 register const char *
string = (
const char *)arg;
1618 unsigned int c1, c2;
1621 c1 = (
unsigned char)*s1++;
1622 c2 = (
unsigned char)*s2++;
1623 if (c1 ==
'\0' || c2 ==
'\0') {
1624 if (c1 !=
'\0')
return 1;
1625 if (c2 !=
'\0')
return -1;
1628 if ((
unsigned int)(c1 -
'A') <= (
'Z' -
'A')) c1 +=
'a' -
'A';
1629 if ((
unsigned int)(c2 -
'A') <= (
'Z' -
'A')) c2 +=
'a' -
'A';
1642 unsigned int c1, c2;
1645 c1 = (
unsigned char)*s1++;
1646 c2 = (
unsigned char)*s2++;
1647 if (c1 ==
'\0' || c2 ==
'\0') {
1648 if (c1 !=
'\0')
return 1;
1649 if (c2 !=
'\0')
return -1;
1652 if ((
unsigned int)(c1 -
'A') <= (
'Z' -
'A')) c1 +=
'a' -
'A';
1653 if ((
unsigned int)(c2 -
'A') <= (
'Z' -
'A')) c2 +=
'a' -
'A';
1667 register const char *
string = (
const char *)arg;
1674 unsigned int c = (
unsigned char)*
string++;
1675 if ((
unsigned int)(c -
'A') <= (
'Z' -
'A')) c +=
'a' -
'A';
RUBY_SYMBOL_EXPORT_BEGIN typedef unsigned long st_data_t
st_index_t st_keys(st_table *table, st_data_t *keys, st_index_t size)
static st_index_t new_size(st_index_t size)
st_table * st_init_table_with_size(const struct st_hash_type *, st_index_t)
#define PVAL_SET(table, i, v)
size_t strlen(const char *)
int st_lookup(st_table *, st_data_t, st_data_t *)
void st_add_direct(st_table *, st_data_t, st_data_t)
static st_index_t get_keys(st_table *table, st_data_t *keys, st_index_t size, int check, st_data_t never)
static st_table_entry * new_entry(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val, register st_index_t bin_pos)
int st_shift(st_table *, st_data_t *, st_data_t *)
static st_index_t find_packed_index(st_table *table, st_index_t hash_val, st_data_t key)
st_table * st_init_numtable(void)
SSL_METHOD *(* func)(void)
int st_update_callback_func(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
st_table * st_init_strcasetable(void)
int st_numcmp(st_data_t, st_data_t)
int st_insert2(st_table *, st_data_t, st_data_t, st_data_t(*)(st_data_t))
struct st_hash_type * type
#define MEMMOVE(p1, p2, type, n)
void rb_raise(VALUE exc, const char *fmt,...)
size_t st_memsize(const st_table *)
st_table * st_init_strtable(void)
#define st_free_entry(entry)
#define st_dealloc_table(table)
static void add_packed_direct(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val)
st_index_t st_hash(const void *ptr, size_t len, st_index_t h)
#define ST_DEFAULT_MAX_DENSITY
static void unpack_entries(register st_table *table)
#define SIZEOF_ST_INDEX_T
unsigned int entries_packed
#define MEMZERO(p, type, n)
int st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg)
int st_delete(st_table *, st_data_t *, st_data_t *)
#define FIND_ENTRY(table, ptr, hash_val, bin_pos)
#define STATIC_ASSERT(name, expr)
static struct st_hash_type type_strcasehash
#define st_alloc_bins(size)
#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)
st_index_t st_numhash(st_data_t)
static 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)
static const unsigned int primes[]
static st_index_t strhash(st_data_t)
#define PHASH_SET(table, i, v)
static st_table_entry * find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos)
static struct st_hash_type type_strhash
static st_table_entry ** st_realloc_bins(st_table_entry **bins, st_index_t newsize, st_index_t oldsize)
static st_index_t find_packed_index_from(st_table *table, st_index_t hash_val, st_data_t key, st_index_t i)
struct st_table_entry * head
static void rehash(st_table *)
int st_foreach(st_table *, int(*)(ANYARGS), st_data_t)
int st_locale_insensitive_strncasecmp(const char *s1, const char *s2, size_t n)
st_index_t st_hash_uint(st_index_t h, st_index_t i)
int st_get_key(st_table *, st_data_t, st_data_t *)
static void remove_safe_packed_entry(st_table *table, st_index_t i, st_data_t never)
st_table * st_init_strcasetable_with_size(st_index_t)
#define PTR_NOT_EQUAL(table, ptr, hash_val, key)
struct st_table_entry ** bins
#define ST_DEFAULT_SECOND_TABLE_SIZE
#define st_free_bins(bins, size)
int st_reverse_foreach(st_table *, int(*)(ANYARGS), st_data_t)
#define MEMCPY(p1, p2, type, n)
st_index_t st_values(st_table *table, st_data_t *values, st_index_t size)
static void remove_packed_entry(st_table *table, st_index_t i)
st_index_t st_values_check(st_table *table, st_data_t *values, st_index_t size, st_data_t never)
#define do_hash(key, table)
struct st_hash_type st_hashtype_num
#define EQUAL(table, x, y)
#define ST_DEFAULT_PACKED_TABLE_SIZE
static st_index_t get_values(st_table *table, st_data_t *values, st_index_t size, int check, st_data_t never)
int st_insert(st_table *, st_data_t, st_data_t)
int st_foreach_check(st_table *, int(*)(ANYARGS), st_data_t, st_data_t)
void st_clear(st_table *)
int st_locale_insensitive_strcasecmp(const char *s1, const char *s2)
st_table * st_init_table(const struct st_hash_type *)
st_index_t st_keys_check(st_table *table, st_data_t *keys, st_index_t size, st_data_t never)
st_index_t st_hash_uint32(st_index_t h, uint32_t i)
#define ST_DEFAULT_INIT_TABLE_SIZE
#define PACKED_BINS(table)
st_table * st_copy(st_table *)
st_table * st_init_strtable_with_size(st_index_t)
struct st_packed_entry st_packed_entry
st_table * st_init_numtable_with_size(st_index_t)
static st_index_t strcasehash(st_data_t)
int st_delete_safe(st_table *, st_data_t *, st_data_t *, st_data_t)
st_index_t st_hash_end(st_index_t h)
void st_cleanup_safe(st_table *, st_data_t)
struct st_table_entry * tail
static void remove_entry(st_table *table, st_table_entry *ptr)
void st_free_table(st_table *)
#define PACKED_ENT(table, i)
struct st_table::@106::@108 packed
#define PKEY_SET(table, i, v)