HelenOS sources
This source file includes following definitions.
- nop_remove_callback
- hash_table_create
- hash_table_destroy
- hash_table_empty
- hash_table_size
- hash_table_clear
- clear_items
- hash_table_insert
- hash_table_insert_unique
- hash_table_find
- hash_table_find_next
- hash_table_remove
- hash_table_remove_item
- hash_table_apply
- round_up_size
- alloc_table
- shrink_if_needed
- grow_if_needed
- resize
#include <adt/hash_table.h>
#include <adt/list.h>
#include <assert.h>
#include <stdlib.h>
#include <str.h>
#define HT_MIN_BUCKETS 89
#define HT_MAX_LOAD 2
static size_t round_up_size(size_t);
static bool alloc_table(size_t, list_t **);
static void clear_items(hash_table_t *);
static void resize(hash_table_t *, size_t);
static void grow_if_needed(hash_table_t *);
static void shrink_if_needed(hash_table_t *);
static void nop_remove_callback(ht_link_t *item)
{
}
bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load,
const hash_table_ops_t *op)
{
assert(h);
assert(op && op->hash && op->key_hash && op->key_equal);
if (!op || !op->hash || !op->key_hash || !op->key_equal)
return false;
h->bucket_cnt = round_up_size(init_size);
if (!alloc_table(h->bucket_cnt, &h->bucket))
return false;
h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
h->item_cnt = 0;
h->op = op;
h->full_item_cnt = h->max_load * h->bucket_cnt;
h->apply_ongoing = false;
return true;
}
void hash_table_destroy(hash_table_t *h)
{
assert(h && h->bucket);
assert(!h->apply_ongoing);
clear_items(h);
free(h->bucket);
h->bucket = NULL;
h->bucket_cnt = 0;
}
bool hash_table_empty(hash_table_t *h)
{
assert(h && h->bucket);
return h->item_cnt == 0;
}
size_t hash_table_size(hash_table_t *h)
{
assert(h && h->bucket);
return h->item_cnt;
}
void hash_table_clear(hash_table_t *h)
{
assert(h && h->bucket);
assert(!h->apply_ongoing);
clear_items(h);
if (HT_MIN_BUCKETS < h->bucket_cnt) {
resize(h, HT_MIN_BUCKETS);
}
}
static void clear_items(hash_table_t *h)
{
if (h->item_cnt == 0)
return;
void (*remove_cb)(ht_link_t *) = h->op->remove_callback ? h->op->remove_callback : nop_remove_callback;
for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
list_foreach_safe(h->bucket[idx], cur, next) {
assert(cur);
ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
list_remove(cur);
remove_cb(cur_link);
}
}
h->item_cnt = 0;
}
void hash_table_insert(hash_table_t *h, ht_link_t *item)
{
assert(item);
assert(h && h->bucket);
assert(!h->apply_ongoing);
size_t idx = h->op->hash(item) % h->bucket_cnt;
list_append(&item->link, &h->bucket[idx]);
++h->item_cnt;
grow_if_needed(h);
}
bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item)
{
assert(item);
assert(h && h->bucket && h->bucket_cnt);
assert(h->op && h->op->hash && h->op->equal);
assert(!h->apply_ongoing);
size_t idx = h->op->hash(item) % h->bucket_cnt;
list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
if (h->op->equal(cur_link, item))
return false;
}
list_append(&item->link, &h->bucket[idx]);
++h->item_cnt;
grow_if_needed(h);
return true;
}
ht_link_t *hash_table_find(const hash_table_t *h, const void *key)
{
assert(h && h->bucket);
size_t idx = h->op->key_hash(key) % h->bucket_cnt;
list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
if (h->op->key_equal(key, cur_link)) {
return cur_link;
}
}
return NULL;
}
ht_link_t *
hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
{
assert(item);
assert(h && h->bucket);
size_t idx = h->op->hash(item) % h->bucket_cnt;
for (link_t *cur = item->link.next; cur != &first->link;
cur = cur->next) {
assert(cur);
if (cur == &h->bucket[idx].head)
continue;
ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
if (h->op->equal(cur_link, item)) {
return cur_link;
}
}
return NULL;
}
size_t hash_table_remove(hash_table_t *h, const void *key)
{
assert(h && h->bucket);
assert(!h->apply_ongoing);
size_t idx = h->op->key_hash(key) % h->bucket_cnt;
size_t removed = 0;
list_foreach_safe(h->bucket[idx], cur, next) {
ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
if (h->op->key_equal(key, cur_link)) {
++removed;
list_remove(cur);
if (h->op->remove_callback)
h->op->remove_callback(cur_link);
}
}
h->item_cnt -= removed;
shrink_if_needed(h);
return removed;
}
void hash_table_remove_item(hash_table_t *h, ht_link_t *item)
{
assert(item);
assert(h && h->bucket);
assert(link_in_use(&item->link));
list_remove(&item->link);
--h->item_cnt;
if (h->op->remove_callback)
h->op->remove_callback(item);
shrink_if_needed(h);
}
void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg)
{
assert(f);
assert(h && h->bucket);
if (h->item_cnt == 0)
return;
h->apply_ongoing = true;
for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
list_foreach_safe(h->bucket[idx], cur, next) {
ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
if (!f(cur_link, arg))
goto out;
}
}
out:
h->apply_ongoing = false;
shrink_if_needed(h);
grow_if_needed(h);
}
static size_t round_up_size(size_t size)
{
size_t rounded_size = HT_MIN_BUCKETS;
while (rounded_size < size) {
rounded_size = 2 * rounded_size + 1;
}
return rounded_size;
}
static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
{
assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
list_t *buckets = malloc(bucket_cnt * sizeof(list_t));
if (!buckets)
return false;
for (size_t i = 0; i < bucket_cnt; i++)
list_initialize(&buckets[i]);
*pbuckets = buckets;
return true;
}
static inline void shrink_if_needed(hash_table_t *h)
{
if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) {
size_t new_bucket_cnt = h->bucket_cnt / 2;
resize(h, new_bucket_cnt);
}
}
static inline void grow_if_needed(hash_table_t *h)
{
if (h->full_item_cnt < h->item_cnt) {
size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
resize(h, new_bucket_cnt);
}
}
static void resize(hash_table_t *h, size_t new_bucket_cnt)
{
assert(h && h->bucket);
assert(HT_MIN_BUCKETS <= new_bucket_cnt);
if (h->apply_ongoing)
return;
list_t *new_buckets;
if (!alloc_table(new_bucket_cnt, &new_buckets))
return;
if (0 < h->item_cnt) {
for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
list_foreach_safe(h->bucket[old_idx], cur, next) {
ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt;
list_remove(cur);
list_append(cur, &new_buckets[new_idx]);
}
}
}
free(h->bucket);
h->bucket = new_buckets;
h->bucket_cnt = new_bucket_cnt;
h->full_item_cnt = h->max_load * h->bucket_cnt;
}
HelenOS homepage, sources at GitHub