Skip to content

Commit f92af2b

Browse files
funny-falconfunny-falcon
committed
st macroses for packed table
1 parent c3328a2 commit f92af2b

File tree

1 file changed

+49
-43
lines changed

1 file changed

+49
-43
lines changed

‎st.c‎

Lines changed: 49 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,8 @@ struct st_table_entry {
2727

2828
#define ST_DEFAULT_MAX_DENSITY 5
2929
#define ST_DEFAULT_INIT_TABLE_SIZE 11
30+
#define ST_DEFAULT_SECOND_TABLE_SIZE 19
31+
#define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
3032

3133
/*
3234
* DEFAULT_MAX_DENSITY is the default for the largest we allow the
@@ -76,6 +78,24 @@ static void rehash(st_table *);
7678
#define do_hash(key,table) (unsigned int)(st_index_t)(*(table)->type->hash)((key))
7779
#define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
7880

81+
/* preparation for possible packing improvements */
82+
#define PKEY_POS(i, num_bins) ((i)*2)
83+
#define PVAL_POS(i, num_bins) ((i)*2+1)
84+
#define PKEY(table, i) (st_data_t)(table)->bins[PKEY_POS(i, (table)->num_bins)]
85+
#define PVAL(table, i) (st_data_t)(table)->bins[PVAL_POS(i, (table)->num_bins)]
86+
#define PKEY_SET(table, i, v) do{ (table)->bins[PKEY_POS(i, (table)->num_bins)] = (st_table_entry *)(v); } while(0)
87+
#define PVAL_SET(table, i, v) do{ (table)->bins[PVAL_POS(i, (table)->num_bins)] = (st_table_entry *)(v); } while(0)
88+
/* this function depends much on packed layout, so that it placed here */
89+
static inline void
90+
remove_packed_entry(st_table *table, st_index_t i)
91+
{
92+
table->num_entries--;
93+
if (i < table->num_entries) {
94+
memmove(table->bins + 2*i, table->bins + 2*(i+1),
95+
sizeof(st_table_entry *) * 2 * (table->num_entries - i));
96+
}
97+
}
98+
7999
/*
80100
* MINSIZE is the minimum size of a dictionary.
81101
*/
@@ -87,7 +107,7 @@ Table of prime numbers 2^n+a, 2<=n<=30.
87107
*/
88108
static const unsigned int primes[] = {
89109
ST_DEFAULT_INIT_TABLE_SIZE,
90-
16 + 3,
110+
ST_DEFAULT_SECOND_TABLE_SIZE,
91111
32 + 5,
92112
64 + 3,
93113
128 + 3,
@@ -162,8 +182,6 @@ stat_col(void)
162182
}
163183
#endif
164184

165-
#define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
166-
167185
st_table*
168186
st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
169187
{
@@ -326,7 +344,7 @@ static inline st_index_t
326344
find_packed_index(st_table *table, st_data_t key)
327345
{
328346
st_index_t i = 0;
329-
while (i < table->num_entries && (st_data_t)table->bins[i*2] != key) i++;
347+
while (i < table->num_entries && PKEY(table, i) != key) i++;
330348
return i;
331349
}
332350

@@ -341,7 +359,7 @@ st_lookup(st_table *table, register st_data_t key, st_data_t *value)
341359
if (table->entries_packed) {
342360
st_index_t i = find_packed_index(table, key);
343361
if (i < table->num_entries) {
344-
if (value != 0) *value = (st_data_t)table->bins[i*2+1];
362+
if (value != 0) *value = PVAL(table, i);
345363
return 1;
346364
}
347365
return 0;
@@ -368,7 +386,7 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
368386
if (table->entries_packed) {
369387
st_index_t i = find_packed_index(table, key);
370388
if (i < table->num_entries) {
371-
if (result != 0) *result = (st_data_t)table->bins[i*2];
389+
if (result != 0) *result = PKEY(table, i);
372390
return 1;
373391
}
374392
return 0;
@@ -389,10 +407,6 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
389407
#undef collision_check
390408
#define collision_check 1
391409

392-
#define MORE_PACKABLE_P(table) \
393-
((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \
394-
(table)->num_entries+1 <= MAX_PACKED_NUMHASH)
395-
396410
static void
397411
add_direct(st_table * table, st_data_t key, st_data_t value,
398412
st_index_t hash_val, st_index_t bin_pos)
@@ -426,16 +440,18 @@ static void
426440
unpack_entries(register st_table *table)
427441
{
428442
st_index_t i;
429-
struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2];
443+
struct st_table_entry *packed_bins[ST_DEFAULT_INIT_TABLE_SIZE];
430444
st_table tmp_table = *table;
431445

432-
memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * table->num_entries*2);
446+
memcpy(packed_bins, table->bins, sizeof(st_table_entry *) * ST_DEFAULT_INIT_TABLE_SIZE);
433447
table->bins = packed_bins;
434448
tmp_table.entries_packed = 0;
435449
tmp_table.num_entries = 0;
436450
memset(tmp_table.bins, 0, sizeof(struct st_table_entry *) * tmp_table.num_bins);
437451
for (i = 0; i < table->num_entries; i++) {
438-
st_insert(&tmp_table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]);
452+
st_index_t hash_val = PKEY(table, i); /* do_hash(PKEY(table, i), &tmp_table); */
453+
add_direct(&tmp_table, PKEY(table, i), PVAL(table, i),
454+
hash_val, hash_val % tmp_table.num_bins);
439455
}
440456
*table = tmp_table;
441457
}
@@ -444,10 +460,10 @@ static int
444460
add_packed_direct(st_table *table, st_data_t key, st_data_t value)
445461
{
446462
int res = 1;
447-
if (MORE_PACKABLE_P(table)) {
463+
if (table->num_entries < MAX_PACKED_NUMHASH) {
448464
st_index_t i = table->num_entries++;
449-
table->bins[i*2] = (struct st_table_entry*)key;
450-
table->bins[i*2+1] = (struct st_table_entry*)value;
465+
PKEY_SET(table, i, key);
466+
PVAL_SET(table, i, value);
451467
}
452468
else {
453469
unpack_entries(table);
@@ -466,7 +482,7 @@ st_insert(register st_table *table, register st_data_t key, st_data_t value)
466482
if (table->entries_packed) {
467483
st_index_t i = find_packed_index(table, key);
468484
if (i < table->num_entries) {
469-
table->bins[i*2+1] = (struct st_table_entry*)value;
485+
PVAL_SET(table, i, value);
470486
return 1;
471487
}
472488
if (add_packed_direct(table, key, value)) {
@@ -498,7 +514,7 @@ st_insert2(register st_table *table, register st_data_t key, st_data_t value,
498514
if (table->entries_packed) {
499515
st_index_t i = find_packed_index(table, key);
500516
if (i < table->num_entries) {
501-
table->bins[i*2+1] = (struct st_table_entry*)value;
517+
PVAL_SET(table, i, value);
502518
return 1;
503519
}
504520
if (add_packed_direct(table, key, value)) {
@@ -626,16 +642,6 @@ remove_entry(st_table *table, st_table_entry *ptr)
626642
table->num_entries--;
627643
}
628644

629-
static inline void
630-
remove_packed_entry(st_table *table, st_index_t pos)
631-
{
632-
table->num_entries--;
633-
if (pos < table->num_entries) {
634-
memmove(&table->bins[pos*2], &table->bins[(pos+1)*2],
635-
sizeof(struct st_table_entry*) * 2*(table->num_entries-pos));
636-
}
637-
}
638-
639645
int
640646
st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
641647
{
@@ -646,7 +652,7 @@ st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
646652
if (table->entries_packed) {
647653
st_index_t i = find_packed_index(table, *key);
648654
if (i < table->num_entries) {
649-
if (value != 0) *value = (st_data_t)table->bins[i*2+1];
655+
if (value != 0) *value = PVAL(table, i);
650656
remove_packed_entry(table, i);
651657
return 1;
652658
}
@@ -680,8 +686,8 @@ st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *val
680686
if (table->entries_packed) {
681687
st_index_t i = find_packed_index(table, *key);
682688
if (i < table->num_entries) {
683-
if (value != 0) *value = (st_data_t)table->bins[i*2+1];
684-
table->bins[i*2] = (void *)never;
689+
if (value != 0) *value = PVAL(table, i);
690+
PKEY_SET(table, i, never);
685691
return 1;
686692
}
687693
if (value != 0) *value = 0;
@@ -713,13 +719,13 @@ st_cleanup_safe(st_table *table, st_data_t never)
713719

714720
if (table->entries_packed) {
715721
st_index_t i = 0, j = 0;
716-
while ((st_data_t)table->bins[i*2] != never) {
722+
while (PKEY(table, i) != never) {
717723
if (i++ == table->num_entries) return;
718724
}
719725
for (j = i; ++i < table->num_entries;) {
720-
if ((st_data_t)table->bins[i*2] == never) continue;
721-
table->bins[j*2] = table->bins[i*2];
722-
table->bins[j*2+1] = table->bins[i*2+1];
726+
if (PKEY(table, i) == never) continue;
727+
PKEY_SET(table, j, PKEY(table, i));
728+
PVAL_SET(table, j, PVAL(table, i));
723729
j++;
724730
}
725731
table->num_entries = j;
@@ -751,10 +757,10 @@ st_update(st_table *table, st_data_t key, int (*func)(st_data_t key, st_data_t *
751757
if (table->entries_packed) {
752758
st_index_t i = find_packed_index(table, key);
753759
if (i < table->num_entries) {
754-
value = (st_data_t)table->bins[i*2+1];
760+
value = PVAL(table, i);
755761
switch ((*func)(key, &value, arg)) {
756762
case ST_CONTINUE:
757-
table->bins[i*2+1] = (struct st_table_entry*)value;
763+
PVAL_SET(table, i, value);
758764
break;
759765
case ST_DELETE:
760766
remove_packed_entry(table, i);
@@ -805,14 +811,14 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
805811
for (i = 0; i < table->num_entries; i++) {
806812
st_index_t j;
807813
st_data_t key, val;
808-
key = (st_data_t)table->bins[i*2];
809-
val = (st_data_t)table->bins[i*2+1];
814+
key = PKEY(table, i);
815+
val = PVAL(table, i);
810816
retval = (*func)(key, val, arg);
811817
if (!table->entries_packed) goto unpacked;
812818
switch (retval) {
813819
case ST_CHECK: /* check if hash is modified during iteration */
814820
for (j = 0; j < table->num_entries; j++) {
815-
if ((st_data_t)table->bins[j*2] == key)
821+
if (PKEY(table, j) == key)
816822
break;
817823
}
818824
if (j == table->num_entries) {
@@ -892,13 +898,13 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
892898
for (i = table->num_entries-1; 0 <= i; i--) {
893899
int j;
894900
st_data_t key, val;
895-
key = (st_data_t)table->bins[i*2];
896-
val = (st_data_t)table->bins[i*2+1];
901+
key = PKEY(table, i);
902+
val = PVAL(table, i);
897903
retval = (*func)(key, val, arg);
898904
switch (retval) {
899905
case ST_CHECK: /* check if hash is modified during iteration */
900906
for (j = 0; j < table->num_entries; j++) {
901-
if ((st_data_t)table->bins[j*2] == key)
907+
if (PKEY(table, j) == key)
902908
break;
903909
}
904910
if (j == table->num_entries) {

0 commit comments

Comments
 (0)