Skip to content

Pack small st_table (not only type_numhash) #71

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
funny-falcon wants to merge 12 commits into from
Closed

Pack small st_table (not only type_numhash) #71

Changes from 1 commit
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
d0e49c1
st use function instead of macro
funny-falcon Dec 21, 2011
9bfa872
pack ordinary st_table as well as num_tables
funny-falcon Dec 22, 2011
2cba783
use bigger packed table size
funny-falcon Dec 22, 2011
1fabec8
optimize packed table access and unpack
funny-falcon Dec 22, 2011
0f8a62d
optimize st_foreach for usual case
funny-falcon Dec 22, 2011
4e0e433
...
funny-falcon Dec 22, 2011
81329be
remove unnessesary hash check
funny-falcon Dec 22, 2011
f56d55e
optimize new_size
funny-falcon Dec 26, 2011
b0cff67
add tunability to hash
funny-falcon Dec 26, 2011
92914bb
fix for trunk st_update
funny-falcon Dec 31, 2011
f37a569
fix error
funny-falcon Dec 31, 2011
9cc6fcb
fix error + use outter bin_pos calculation (faster a bit)
funny-falcon Jan 3, 2012
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
fix error + use outter bin_pos calculation (faster a bit)
  • Loading branch information
@funny-falcon
funny-falcon committed Jan 3, 2012
commit 9cc6fcbda19a6ed5249b622635c5cd3a5e0655fc
31 changes: 16 additions & 15 deletions st.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -375,9 +375,8 @@ count_collision(const struct st_hash_type *type)
#endif

static st_table_entry *
find_entry(st_table *table, st_data_t key, st_index_t hash_val)
find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos)
{
st_index_t bin_pos = hash_val % table->num_bins;
register st_table_entry *ptr = table->bins[bin_pos];
FOUND_ENTRY;
if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {
Expand Down Expand Up @@ -422,7 +421,7 @@ st_lookup(st_table *table, register st_data_t key, st_data_t *value)
return 0;
}

ptr = find_entry(table, key, hash_val);
ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);

if (ptr == 0) {
return 0;
Expand Down Expand Up @@ -450,7 +449,7 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
return 0;
}

ptr = find_entry(table, key, hash_val);
ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);

if (ptr == 0) {
return 0;
Expand All @@ -466,12 +465,12 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)

static void
add_direct(st_table * table, st_data_t key, st_data_t value,
st_index_t hash_val)
st_index_t hash_val, st_index_t bin_pos)
{
st_table_entry *entry;
register st_index_t bin_pos;
if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) {
rehash(table);
bin_pos = hash_val % table->num_bins;
}
entry = alloc(st_table_entry);

Expand All @@ -487,7 +486,6 @@ add_direct(st_table * table, st_data_t key, st_data_t value,
table->head = table->tail = entry;
entry->back = 0;
}
bin_pos = hash_val % table->num_bins;
entry->next = table->bins[bin_pos];
table->bins[bin_pos] = entry;
table->num_entries++;
Expand All @@ -503,7 +501,8 @@ unpack_entries(register st_table *table)
calloc(ST_DEFAULT_INIT_TABLE_SIZE, sizeof(st_table_entry *));
tmp_table.num_bins = ST_DEFAULT_INIT_TABLE_SIZE;
for (i = 0; i < table->num_entries; i++) {
add_direct(&tmp_table, PKEY(table, i), PVAL(table, i), PHASH(table, i));
add_direct(&tmp_table, PKEY(table, i), PVAL(table, i),
PHASH(table, i), PHASH(table, i) % tmp_table.num_bins);
}
xfree(table->bins);
*table = tmp_table;
Expand Down Expand Up @@ -534,7 +533,7 @@ add_packed_direct(st_table *table, st_data_t key, st_data_t value, st_index_t ha
int
st_insert(register st_table *table, register st_data_t key, st_data_t value)
{
st_index_t hash_val;
st_index_t hash_val, bin_pos;
register st_table_entry *ptr;

hash_val = do_hash(key, table);
Expand All @@ -550,10 +549,11 @@ st_insert(register st_table *table, register st_data_t key, st_data_t value)
}
}

ptr = find_entry(table, key, hash_val);
bin_pos = hash_val % table->num_bins;
ptr = find_entry(table, key, hash_val, bin_pos);

if (ptr == 0) {
add_direct(table, key, value, hash_val);
add_direct(table, key, value, hash_val, bin_pos);
return 0;
}
else {
Expand All @@ -566,7 +566,7 @@ int
st_insert2(register st_table *table, register st_data_t key, st_data_t value,
st_data_t (*func)(st_data_t))
{
st_index_t hash_val;
st_index_t hash_val, bin_pos;
register st_table_entry *ptr;

hash_val = do_hash(key, table);
Expand All @@ -582,11 +582,12 @@ st_insert2(register st_table *table, register st_data_t key, st_data_t value,
}
}

ptr = find_entry(table, key, hash_val);
bin_pos = hash_val % table->num_bins;
ptr = find_entry(table, key, hash_val, bin_pos);

if (ptr == 0) {
key = (*func)(key);
add_direct(table, key, value, hash_val);
add_direct(table, key, value, hash_val, bin_pos);
return 0;
}
else {
Expand All @@ -607,7 +608,7 @@ st_add_direct(st_table *table, st_data_t key, st_data_t value)
}
}

add_direct(table, key, value, hash_val);
add_direct(table, key, value, hash_val, hash_val % table->num_bins);
}

static void
Expand Down