Index: uspace/lib/block/block.c =================================================================== --- uspace/lib/block/block.c (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/block/block.c (revision 062d9000625057300f609429080872d6492b542e) @@ -62,6 +62,4 @@ static LIST_INITIALIZE(dcl); -#define CACHE_BUCKETS_LOG2 10 -#define CACHE_BUCKETS (1 << CACHE_BUCKETS_LOG2) typedef struct { @@ -233,23 +231,30 @@ } -static hash_index_t cache_hash(unsigned long *key) -{ - return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1); -} - -static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item) -{ - block_t *b = hash_table_get_instance(item, block_t, hash_link); - return b->lba == MERGE_LOUP32(key[0], key[1]); -} - -static void cache_remove_callback(link_t *item) -{ -} - -static hash_table_operations_t cache_ops = { +static size_t cache_key_hash(void *key) +{ + aoff64_t *lba = (aoff64_t*)key; + return *lba; +} + +static size_t cache_hash(const ht_link_t *item) +{ + block_t *b = hash_table_get_inst(item, block_t, hash_link); + return b->lba; +} + +static bool cache_key_equal(void *key, const ht_link_t *item) +{ + aoff64_t *lba = (aoff64_t*)key; + block_t *b = hash_table_get_inst(item, block_t, hash_link); + return b->lba == *lba; +} + + +static hash_table_ops_t cache_ops = { .hash = cache_hash, - .compare = cache_compare, - .remove_callback = cache_remove_callback + .key_hash = cache_key_hash, + .key_equal = cache_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -282,6 +287,5 @@ cache->blocks_cluster = cache->lblock_size / devcon->pblock_size; - if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2, - &cache_ops)) { + if (!hash_table_create(&cache->block_hash, 0, 0, &cache_ops)) { free(cache); return ENOMEM; @@ -321,9 +325,5 @@ } - unsigned long key[2] = { - LOWER32(b->lba), - UPPER32(b->lba) - }; - hash_table_remove(&cache->block_hash, key, 2); + hash_table_remove_item(&cache->block_hash, &b->hash_link); free(b->data); @@ -357,5 +357,4 @@ fibril_rwlock_initialize(&b->contents_lock); link_initialize(&b->free_link); - link_initialize(&b->hash_link); } @@ -377,9 +376,5 @@ cache_t *cache; block_t *b; - link_t *l; - unsigned long key[2] = { - LOWER32(ba), - UPPER32(ba) - }; + link_t *link; int rc; @@ -397,11 +392,11 @@ fibril_mutex_lock(&cache->lock); - l = hash_table_find(&cache->block_hash, key); - if (l) { + ht_link_t *hlink = hash_table_find(&cache->block_hash, &ba); + if (hlink) { found: /* * We found the block in the cache. */ - b = hash_table_get_instance(l, block_t, hash_link); + b = hash_table_get_inst(hlink, block_t, hash_link); fibril_mutex_lock(&b->lock); if (b->refcnt++ == 0) @@ -441,6 +436,6 @@ goto out; } - l = list_first(&cache->free_list); - b = list_get_instance(l, block_t, free_link); + link = list_first(&cache->free_list); + b = list_get_instance(link, block_t, free_link); fibril_mutex_lock(&b->lock); @@ -479,6 +474,6 @@ goto retry; } - l = hash_table_find(&cache->block_hash, key); - if (l) { + hlink = hash_table_find(&cache->block_hash, &ba); + if (hlink) { /* * Someone else must have already @@ -502,9 +497,5 @@ */ list_remove(&b->free_link); - unsigned long temp_key[2] = { - LOWER32(b->lba), - UPPER32(b->lba) - }; - hash_table_remove(&cache->block_hash, temp_key, 2); + hash_table_remove_item(&cache->block_hash, &b->hash_link); } @@ -514,5 +505,5 @@ b->lba = ba; b->pba = ba_ltop(devcon, b->lba); - hash_table_insert(&cache->block_hash, key, &b->hash_link); + hash_table_insert(&cache->block_hash, &b->hash_link); /* @@ -622,9 +613,5 @@ * Take the block out of the cache and free it. */ - unsigned long key[2] = { - LOWER32(block->lba), - UPPER32(block->lba) - }; - hash_table_remove(&cache->block_hash, key, 2); + hash_table_remove_item(&cache->block_hash, &block->hash_link); fibril_mutex_unlock(&block->lock); free(block->data); Index: uspace/lib/block/block.h =================================================================== --- uspace/lib/block/block.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/block/block.h (revision 062d9000625057300f609429080872d6492b542e) @@ -84,5 +84,5 @@ link_t free_link; /** Link for placing the block into the block hash table. */ - link_t hash_link; + ht_link_t hash_link; /** Buffer with the block data. */ void *data; Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/c/Makefile (revision 062d9000625057300f609429080872d6492b542e) @@ -124,5 +124,4 @@ generic/adt/list.c \ generic/adt/hash_table.c \ - generic/adt/hash_set.c \ generic/adt/dynamic_fifo.c \ generic/adt/char_map.c \ Index: uspace/lib/c/generic/adt/hash_set.c =================================================================== --- uspace/lib/c/generic/adt/hash_set.c (revision d94809517f828232745c791f5d7d49244768b43a) +++ (revision ) @@ -1,382 +1,0 @@ -/* - * Copyright (c) 2008 Jakub Jermar - * Copyright (c) 2011 Radim Vansa - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup libc - * @{ - */ -/** @file - */ - -#include -#include -#include -#include -#include -#include - -/** Create chained hash set - * - * @param h Hash set structure to be initialized. - * @param[in] hash Hash function - * @param[in] equals Equals function - * @param[in] init_size Initial hash set size - * - * @return True on success - * - */ -int hash_set_init(hash_set_t *h, hash_set_hash hash, hash_set_equals equals, - size_t init_size) -{ - assert(h); - assert(hash); - assert(equals); - - if (init_size < HASH_SET_MIN_SIZE) - init_size = HASH_SET_MIN_SIZE; - - h->table = malloc(init_size * sizeof(link_t)); - if (!h->table) - return false; - - for (size_t i = 0; i < init_size; i++) - list_initialize(&h->table[i]); - - h->size = init_size; - h->count = 0; - h->hash = hash; - h->equals = equals; - - return true; -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - * - */ -void hash_set_destroy(hash_set_t *h) -{ - assert(h); - free(h->table); -} - -/** Rehash the internal table to new table - * - * @param h Original hash set - * @param new_table Memory for the new table - * @param new_size Size of the new table - */ -static void hash_set_rehash(hash_set_t *h, list_t *new_table, - size_t new_size) -{ - assert(new_size >= HASH_SET_MIN_SIZE); - - for (size_t bucket = 0; bucket < new_size; bucket++) - list_initialize(&new_table[bucket]); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - next = cur->next; - list_append(cur, &new_table[h->hash(cur) % new_size]); - } - } - - list_t *old_table = h->table; - h->table = new_table; - free(old_table); - h->size = new_size; -} - -/** Insert item into the set. - * - * If the set already contains equivalent object, - * the function fails. - * - * @param h Hash table. - * @param key Array of all keys necessary to compute hash index. - * @param item Item to be inserted into the hash table. - * - * @return True if the object was inserted - * @return Ffalse if the set already contained equivalent object. - * - */ -int hash_set_insert(hash_set_t *h, link_t *item) -{ - assert(item); - assert(h); - assert(h->hash); - assert(h->equals); - - unsigned long hash = h->hash(item); - unsigned long chain = hash % h->size; - - list_foreach(h->table[chain], cur) { - if (h->equals(cur, item)) - return false; - } - - if (h->count + 1 > h->size) { - size_t new_size = h->size * 2; - list_t *temp = malloc(new_size * sizeof(list_t)); - if (temp != NULL) - hash_set_rehash(h, temp, new_size); - - /* - * If the allocation fails, just use the same - * old table and try to rehash next time. - */ - chain = hash % h->size; - } - - h->count++; - list_append(item, &h->table[chain]); - - return true; -} - -/** Search the hash set for a matching object and return it - * - * @param h Hash set - * @param item The item that should equal to the matched object - * - * @return Matching item on success, NULL if there is no such item. - * - */ -link_t *hash_set_find(hash_set_t *h, const link_t *item) -{ - assert(h); - assert(h->hash); - assert(h->equals); - - unsigned long chain = h->hash(item) % h->size; - - list_foreach(h->table[chain], cur) { - if (h->equals(cur, item)) - return cur; - } - - return NULL; -} - -/** Remove first matching object from the hash set and return it - * - * @param h Hash set. - * @param item The item that should be equal to the matched object - * - * @return The removed item or NULL if this is not found. - * - */ -link_t *hash_set_remove(hash_set_t *h, const link_t *item) -{ - assert(h); - assert(h->hash); - assert(h->equals); - - link_t *cur = hash_set_find(h, item); - if (cur) { - list_remove(cur); - - h->count--; - if (4 * h->count < h->size && h->size > HASH_SET_MIN_SIZE) { - size_t new_size = h->size / 2; - if (new_size < HASH_SET_MIN_SIZE) - /* possible e.g. if init_size == HASH_SET_MIN_SIZE + 1 */ - new_size = HASH_SET_MIN_SIZE; - - list_t *temp = malloc(new_size * sizeof (list_t)); - if (temp != NULL) - hash_set_rehash(h, temp, new_size); - } - } - - return cur; -} - -/** Remove all elements for which the function returned non-zero - * - * The function can also destroy the element. - * - * @param h Hash set. - * @param f Function to be applied. - * @param arg Argument to be passed to the function. - * - */ -void hash_set_remove_selected(hash_set_t *h, int (*f)(link_t *, void *), - void *arg) -{ - assert(h); - assert(h->table); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *prev = &h->table[bucket].head; - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - next = cur->next; - if (f(cur, arg)) { - prev->next = next; - next->prev = prev; - h->count--; - } else - prev = cur; - } - } - - if (4 * h->count < h->size && h->size > HASH_SET_MIN_SIZE) { - size_t new_size = h->size / 2; - if (new_size < HASH_SET_MIN_SIZE) - /* possible e.g. if init_size == HASH_SET_MIN_SIZE + 1 */ - new_size = HASH_SET_MIN_SIZE; - - list_t *temp = malloc(new_size * sizeof (list_t)); - if (temp != NULL) - hash_set_rehash(h, temp, new_size); - } -} - -/** Apply function to all items in hash set - * - * @param h Hash set. - * @param f Function to be applied. - * @param arg Argument to be passed to the function. - * - */ -void hash_set_apply(hash_set_t *h, void (*f)(link_t *, void *), void *arg) -{ - assert(h); - assert(h->table); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - - /* - * The next pointer must be stored prior to the functor - * call to allow using destructor as the functor (the - * free function could overwrite the cur->next pointer). - */ - next = cur->next; - f(cur, arg); - } - } -} - -/** Remove all elements from the set. - * - * The table is reallocated to the minimum size. - * - * @param h Hash set - * @param f Function (destructor?) applied to all element. Can be NULL. - * @param arg Argument to the destructor. - * - */ -void hash_set_clear(hash_set_t *h, void (*f)(link_t *, void *), void *arg) -{ - assert(h); - assert(h->table); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - next = cur->next; - list_remove(cur); - if (f != NULL) - f(cur, arg); - } - } - - assert(h->size >= HASH_SET_MIN_SIZE); - list_t *new_table = - realloc(h->table, HASH_SET_MIN_SIZE * sizeof(list_t)); - - /* We are shrinking, therefore we shouldn't get NULL */ - assert(new_table); - - if (h->table != new_table) { - /* Init the lists, pointers to itself are used in them */ - for (size_t bucket = 0; bucket < HASH_SET_MIN_SIZE; ++bucket) - list_initialize(&new_table[bucket]); - - h->table = new_table; - } - - h->count = 0; - h->size = HASH_SET_MIN_SIZE; -} - -/** Get hash set size - * - * @param hHash set - * - * @return Number of elements in the set. - * - */ -size_t hash_set_count(const hash_set_t *h) -{ - assert(h); - return h->count; -} - -/** Check whether element is contained in the hash set - * - * @param h Hash set - * @param item Item that should be equal to the matched object - * - * @return True if the hash set contains equal object - * @return False otherwise - * - */ -int hash_set_contains(const hash_set_t *h, const link_t *item) -{ - /* - * The hash_set_find cannot accept constant hash set, - * because we can modify the returned element. But in - * this case we are using it safely. - */ - return hash_set_find((hash_set_t *) h, item) != NULL; -} - -/** @} - */ Index: uspace/lib/c/generic/adt/hash_table.c =================================================================== --- uspace/lib/c/generic/adt/hash_table.c (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/c/generic/adt/hash_table.c (revision 062d9000625057300f609429080872d6492b542e) @@ -1,4 +1,6 @@ /* * Copyright (c) 2008 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -34,5 +36,15 @@ /* - * This is an implementation of generic chained hash table. + * This is an implementation of a generic resizable chained hash table. + * + * The table grows to 2*n+1 buckets each time, starting at n == 89, + * per Thomas Wang's recommendation: + * http://www.concentric.net/~Ttwang/tech/hashsize.htm + * + * This policy produces prime table sizes for the first five resizes + * and generally produces table sizes which are either prime or + * have fairly large (prime/odd) divisors. Having a prime table size + * mitigates the use of suboptimal hash functions and distributes + * items over the whole table. */ @@ -44,38 +56,99 @@ #include +/* Optimal initial bucket count. See comment above. */ +#define HT_MIN_BUCKETS 89 +/* The table is resized when the average load per bucket exceeds this number. */ +#define HT_MAX_LOAD 2 + + +static size_t round_up_size(size_t size); +static bool alloc_table(size_t bucket_cnt, list_t **pbuckets); +static void clear_items(hash_table_t *h); +static void resize(hash_table_t *h, size_t new_bucket_cnt); +static void grow_if_needed(hash_table_t *h); +static void shrink_if_needed(hash_table_t *h); + +/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */ +static void nop_remove_callback(ht_link_t *item) +{ + /* no-op */ +} + + /** Create chained hash table. * * @param h Hash table structure. Will be initialized by this call. - * @param m Number of hash table buckets. + * @param init_size Initial desired number of hash table buckets. Pass zero + * if you want the default initial size. * @param max_keys Maximal number of keys needed to identify an item. - * @param op Hash table operations structure. + * @param op Hash table operations structure. remove_callback() + * is optional and can be NULL if no action is to be taken + * upon removal. equal() is optional if and only if + * hash_table_insert_unique() will never be invoked. + * All other operations are mandatory. * * @return True on success * */ -bool hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, - hash_table_operations_t *op) +bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load, + hash_table_ops_t *op) { assert(h); - assert(op && op->hash && op->compare); - assert(max_keys > 0); - - h->entry = malloc(m * sizeof(list_t)); - if (!h->entry) + assert(op && op->hash && op->key_hash && op->key_equal); + + /* Check for compulsory ops. */ + if (!op || !op->hash || !op->key_hash || !op->key_equal) return false; - memset((void *) h->entry, 0, m * sizeof(list_t)); - - hash_count_t i; - for (i = 0; i < m; i++) - list_initialize(&h->entry[i]); - - h->entries = m; - h->max_keys = max_keys; + 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; + + if (h->op->remove_callback == 0) { + h->op->remove_callback = nop_remove_callback; + } return true; } +/** Destroy a hash table instance. + * + * @param h Hash table to be destroyed. + * + */ +void hash_table_destroy(hash_table_t *h) +{ + assert(h && h->bucket); + assert(!h->apply_ongoing); + + clear_items(h); + + free(h->bucket); + + h->bucket = 0; + h->bucket_cnt = 0; +} + +/** Returns true if there are no items in the table. */ +bool hash_table_empty(hash_table_t *h) +{ + assert(h && h->bucket); + return h->item_cnt == 0; +} + +/** Returns the number of items in the table. */ +size_t hash_table_size(hash_table_t *h) +{ + assert(h && h->bucket); + return h->item_cnt; +} + /** Remove all elements from the hash table * @@ -84,29 +157,32 @@ void hash_table_clear(hash_table_t *h) { - for (hash_count_t chain = 0; chain < h->entries; ++chain) { - link_t *cur; - link_t *next; - - for (cur = h->entry[chain].head.next; - cur != &h->entry[chain].head; - cur = next) { - next = cur->next; + assert(h && h->bucket); + assert(!h->apply_ongoing); + + clear_items(h); + + /* Shrink the table to its minimum size if possible. */ + if (HT_MIN_BUCKETS < h->bucket_cnt) { + resize(h, HT_MIN_BUCKETS); + } +} + +/** Unlinks and removes all items but does not resize. */ +static void clear_items(hash_table_t *h) +{ + if (h->item_cnt == 0) + return; + + 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); - h->op->remove_callback(cur); - } - } -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - * - */ -void hash_table_destroy(hash_table_t *h) -{ - assert(h); - assert(h->entry); - - free(h->entry); + h->op->remove_callback(cur_link); + } + } + + h->item_cnt = 0; } @@ -117,13 +193,52 @@ * @param item Item to be inserted into the hash table. */ -void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item) +void hash_table_insert(hash_table_t *h, ht_link_t *item) { assert(item); - assert(h && h->op && h->op->hash && h->op->compare); - - hash_index_t chain = h->op->hash(key); - assert(chain < h->entries); - - list_append(item, &h->entry[chain]); + 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); +} + + +/** Insert item into a hash table if not already present. + * + * @param h Hash table. + * @param key Array of all keys necessary to compute hash index. + * @param item Item to be inserted into the hash table. + * + * @return False if such an item had already been inserted. + * @return True if the inserted item was the only item with such a lookup key. + */ +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; + + /* Check for duplicates. */ + list_foreach(h->bucket[idx], cur) { + /* + * We could filter out items using their hashes first, but + * calling equal() might very well be just as fast. + */ + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, 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; } @@ -136,20 +251,45 @@ * */ -link_t *hash_table_find(hash_table_t *h, unsigned long key[]) -{ - assert(h && h->op && h->op->hash && h->op->compare); - - hash_index_t chain = h->op->hash(key); - assert(chain < h->entries); - - list_foreach(h->entry[chain], cur) { - if (h->op->compare(key, h->max_keys, cur)) { - /* - * The entry is there. - */ - return cur; - } - } - +ht_link_t *hash_table_find(const hash_table_t *h, void *key) +{ + assert(h && h->bucket); + + size_t idx = h->op->key_hash(key) % h->bucket_cnt; + + list_foreach(h->bucket[idx], cur) { + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + /* + * Is this is the item we are looking for? We could have first + * checked if the hashes match but op->key_equal() may very well be + * just as fast as op->hash(). + */ + if (h->op->key_equal(key, cur_link)) { + return cur_link; + } + } + + return NULL; +} + +/** Find the next item equal to item. */ +ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item) +{ + assert(item); + assert(h && h->bucket); + + /* Traverse the circular list until we reach the starting item again. */ + for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) { + assert(cur); + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + /* + * Is this is the item we are looking for? We could have first + * checked if the hashes match but op->equal() may very well be + * just as fast as op->hash(). + */ + if (h->op->equal(cur_link, item)) { + return cur_link; + } + } + return NULL; } @@ -163,76 +303,170 @@ * the hash table. * @param keys Number of keys in the 'key' array. - * - */ -void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys) -{ - assert(h && h->op && h->op->hash && h->op->compare && - h->op->remove_callback); - assert(keys <= h->max_keys); - - if (keys == h->max_keys) { - /* - * All keys are known, hash_table_find() can be used to find the - * entry. + * + * @return Returns the number of removed items. + */ +size_t hash_table_remove(hash_table_t *h, 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); + h->op->remove_callback(cur_link); + } + } + + h->item_cnt -= removed; + shrink_if_needed(h); + + return removed; +} + +/** Removes an item already present in the table. The item must be in the table.*/ +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; + h->op->remove_callback(item); + shrink_if_needed(h); +} + +/** Apply function to all items in hash table. + * + * @param h Hash table. + * @param f Function to be applied. Return false if no more items + * should be visited. The functor may only delete the supplied + * item. It must not delete the successor of the item passed + * in the first argument. + * @param arg Argument to be passed to the function. + */ +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); + /* + * The next pointer had already been saved. f() may safely + * delete cur (but not next!). + */ + if (!f(cur_link, arg)) + return; + } + } + + h->apply_ongoing = false; + + shrink_if_needed(h); + grow_if_needed(h); +} + +/** Rounds up size to the nearest suitable table size. */ +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; +} + +/** Allocates and initializes the desired number of buckets. True if successful.*/ +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; +} + + +/** Shrinks the table if the table is only sparely populated. */ +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) { + /* + * Keep the bucket_cnt odd (possibly also prime). + * Shrink from 2n + 1 to n. Integer division discards the +1. */ - - link_t *cur = hash_table_find(h, key); - if (cur) { - list_remove(cur); - h->op->remove_callback(cur); - } - + size_t new_bucket_cnt = h->bucket_cnt / 2; + resize(h, new_bucket_cnt); + } +} + +/** Grows the table if table load exceeds the maximum allowed. */ +static inline void grow_if_needed(hash_table_t *h) +{ + /* Grow the table if the average bucket load exceeds the maximum. */ + if (h->full_item_cnt < h->item_cnt) { + /* Keep the bucket_cnt odd (possibly also prime). */ + size_t new_bucket_cnt = 2 * h->bucket_cnt + 1; + resize(h, new_bucket_cnt); + } +} + +/** Allocates and rehashes items to a new table. Frees the old table. */ +static void resize(hash_table_t *h, size_t new_bucket_cnt) +{ + assert(h && h->bucket); + assert(HT_MIN_BUCKETS <= new_bucket_cnt); + + /* We are traversing the table and resizing would mess up the buckets. */ + if (h->apply_ongoing) return; - } - - /* - * Fewer keys were passed. - * Any partially matching entries are to be removed. - */ - hash_index_t chain; - for (chain = 0; chain < h->entries; chain++) { - for (link_t *cur = h->entry[chain].head.next; - cur != &h->entry[chain].head; - cur = cur->next) { - if (h->op->compare(key, keys, cur)) { - link_t *hlp; - - hlp = cur; - cur = cur->prev; - - list_remove(hlp); - h->op->remove_callback(hlp); - - continue; + + list_t *new_buckets; + + /* Leave the table as is if we cannot resize. */ + if (!alloc_table(new_bucket_cnt, &new_buckets)) + return; + + if (0 < h->item_cnt) { + /* Rehash all the items to the new table. */ + 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]); } } } -} - -/** Apply function to all items in hash table. - * - * @param h Hash table. - * @param f Function to be applied. - * @param arg Argument to be passed to the function. - * - */ -void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg) -{ - for (hash_index_t bucket = 0; bucket < h->entries; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->entry[bucket].head.next; cur != &h->entry[bucket].head; - cur = next) { - /* - * The next pointer must be stored prior to the functor - * call to allow using destructor as the functor (the - * free function could overwrite the cur->next pointer). - */ - next = cur->next; - f(cur, arg); - } - } -} + + free(h->bucket); + h->bucket = new_buckets; + h->bucket_cnt = new_bucket_cnt; + h->full_item_cnt = h->max_load * h->bucket_cnt; +} + /** @} Index: uspace/lib/c/generic/async.c =================================================================== --- uspace/lib/c/generic/async.c (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/c/generic/async.c (revision 062d9000625057300f609429080872d6492b542e) @@ -116,6 +116,4 @@ #include "private/libc.h" -#define CLIENT_HASH_TABLE_BUCKETS 32 -#define CONN_HASH_TABLE_BUCKETS 32 /** Session data */ @@ -205,5 +203,5 @@ /* Client connection data */ typedef struct { - link_t link; + ht_link_t link; task_id_t in_task_id; @@ -217,5 +215,5 @@ /** Hash table link. */ - link_t link; + ht_link_t link; /** Incoming client task ID. */ @@ -393,31 +391,31 @@ static LIST_INITIALIZE(timeout_list); -static hash_index_t client_hash(unsigned long key[]) -{ - assert(key); - - return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS); -} - -static int client_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - assert(key); - assert(keys == 2); - assert(item); - - client_t *client = hash_table_get_instance(item, client_t, link); - return (key[0] == LOWER32(client->in_task_id) && - (key[1] == UPPER32(client->in_task_id))); -} - -static void client_remove(link_t *item) -{ -} +static size_t client_key_hash(void *k) +{ + task_id_t key = *(task_id_t*)k; + return key; +} + +static size_t client_hash(const ht_link_t *item) +{ + client_t *client = hash_table_get_inst(item, client_t, link); + return client_key_hash(&client->in_task_id); +} + +static bool client_key_equal(void *k, const ht_link_t *item) +{ + task_id_t key = *(task_id_t*)k; + client_t *client = hash_table_get_inst(item, client_t, link); + return key == client->in_task_id; +} + /** Operations for the client hash table. */ -static hash_table_operations_t client_hash_table_ops = { +static hash_table_ops_t client_hash_table_ops = { .hash = client_hash, - .compare = client_compare, - .remove_callback = client_remove + .key_hash = client_key_hash, + .key_equal = client_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -429,38 +427,31 @@ * */ -static hash_index_t conn_hash(unsigned long key[]) -{ - assert(key); - - return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS); -} - -/** Compare hash table item with a key. - * - * @param key Array containing the source phone hash as the only item. - * @param keys Expected 1 but ignored. - * @param item Connection hash table item. - * - * @return True on match, false otherwise. - * - */ -static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - assert(key); - assert(item); - - connection_t *conn = hash_table_get_instance(item, connection_t, link); - return (key[0] == conn->in_phone_hash); -} - -static void conn_remove(link_t *item) -{ -} +static size_t conn_key_hash(void *key) +{ + sysarg_t in_phone_hash = *(sysarg_t*)key; + return in_phone_hash ; +} + +static size_t conn_hash(const ht_link_t *item) +{ + connection_t *conn = hash_table_get_inst(item, connection_t, link); + return conn_key_hash(&conn->in_phone_hash); +} + +static bool conn_key_equal(void *key, const ht_link_t *item) +{ + sysarg_t in_phone_hash = *(sysarg_t*)key; + connection_t *conn = hash_table_get_inst(item, connection_t, link); + return (in_phone_hash == conn->in_phone_hash); +} + /** Operations for the connection hash table. */ -static hash_table_operations_t conn_hash_table_ops = { +static hash_table_ops_t conn_hash_table_ops = { .hash = conn_hash, - .compare = conn_compare, - .remove_callback = conn_remove + .key_hash = conn_key_hash, + .key_equal = conn_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -510,6 +501,5 @@ futex_down(&async_futex); - unsigned long key = call->in_phone_hash; - link_t *hlp = hash_table_find(&conn_hash_table, &key); + ht_link_t *hlp = hash_table_find(&conn_hash_table, &call->in_phone_hash); if (!hlp) { @@ -518,5 +508,5 @@ } - connection_t *conn = hash_table_get_instance(hlp, connection_t, link); + connection_t *conn = hash_table_get_inst(hlp, connection_t, link); msg_t *msg = malloc(sizeof(*msg)); @@ -698,14 +688,10 @@ static client_t *async_client_get(task_id_t client_id, bool create) { - unsigned long key[2] = { - LOWER32(client_id), - UPPER32(client_id), - }; client_t *client = NULL; futex_down(&async_futex); - link_t *lnk = hash_table_find(&client_hash_table, key); + ht_link_t *lnk = hash_table_find(&client_hash_table, &client_id); if (lnk) { - client = hash_table_get_instance(lnk, client_t, link); + client = hash_table_get_inst(lnk, client_t, link); atomic_inc(&client->refcnt); } else if (create) { @@ -716,5 +702,5 @@ atomic_set(&client->refcnt, 1); - hash_table_insert(&client_hash_table, key, &client->link); + hash_table_insert(&client_hash_table, &client->link); } } @@ -727,13 +713,9 @@ { bool destroy; - unsigned long key[2] = { - LOWER32(client->in_task_id), - UPPER32(client->in_task_id) - }; - + futex_down(&async_futex); if (atomic_predec(&client->refcnt) == 0) { - hash_table_remove(&client_hash_table, key, 2); + hash_table_remove(&client_hash_table, &client->in_task_id); destroy = true; } else @@ -831,6 +813,5 @@ */ futex_down(&async_futex); - unsigned long key = fibril_connection->in_phone_hash; - hash_table_remove(&conn_hash_table, &key, 1); + hash_table_remove(&conn_hash_table, &fibril_connection->in_phone_hash); futex_up(&async_futex); @@ -916,8 +897,7 @@ /* Add connection to the connection hash table */ - unsigned long key = conn->in_phone_hash; futex_down(&async_futex); - hash_table_insert(&conn_hash_table, &key, &conn->link); + hash_table_insert(&conn_hash_table, &conn->link); futex_up(&async_futex); @@ -1111,10 +1091,8 @@ void __async_init(void) { - if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS, - 2, &client_hash_table_ops)) + if (!hash_table_create(&client_hash_table, 0, 0, &client_hash_table_ops)) abort(); - if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS, - 1, &conn_hash_table_ops)) + if (!hash_table_create(&conn_hash_table, 0, 0, &conn_hash_table_ops)) abort(); Index: uspace/lib/c/include/adt/hash.h =================================================================== --- uspace/lib/c/include/adt/hash.h (revision 062d9000625057300f609429080872d6492b542e) +++ uspace/lib/c/include/adt/hash.h (revision 062d9000625057300f609429080872d6492b542e) @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup genericadt + * @{ + */ +/** @file + */ +#ifndef KERN_HASH_H_ +#define KERN_HASH_H_ + +#include + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint32_t hash_mix32(uint32_t hash) +{ + /* + * Thomas Wang's modification of Bob Jenkin's hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * Public domain. + */ + hash = ~hash + (hash << 15); + hash = hash ^ (hash >> 12); + hash = hash + (hash << 2); + hash = hash ^ (hash >> 4); + hash = hash * 2057; + hash = hash ^ (hash >> 16); + return hash; +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint64_t hash_mix64(uint64_t hash) +{ + /* + * Thomas Wang's public domain 64-bit hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + */ + hash = (hash ^ 61) ^ (hash >> 16); + hash = hash + (hash << 3); + hash = hash ^ (hash >> 4); + hash = hash * 0x27d4eb2d; + hash = hash ^ (hash >> 15); + /* + * Lower order bits are mixed more thoroughly. Swap them with + * the higher order bits and make the resulting higher order bits + * more usable. + */ + return (hash << 32) | (hash >> 32); +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline size_t hash_mix(size_t hash) +{ +#ifdef __32_BITS__ + return hash_mix32(hash); +#elif defined(__64_BITS__) + return hash_mix64(hash); +#else +#error Unknown size_t size - cannot select proper hash mix function. +#endif +} + +/** Use to create a hash from multiple values. + * + * Typical usage: + * @code + * int car_id; + * bool car_convertible; + * // .. + * size_t hash = 0; + * hash = hash_combine(hash, car_id); + * hash = hash_combine(hash, car_convertible); + * // Now use hash as a hash of both car_id and car_convertible. + * @endcode + */ +static inline size_t hash_combine(size_t seed, size_t hash) +{ + /* + * todo: use Bob Jenkin's proper mixing hash pass: + * http://burtleburtle.net/bob/c/lookup3.c + */ + seed ^= hash + 0x9e3779b9 + + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5))); + return seed; +} + +#endif Index: uspace/lib/c/include/adt/hash_set.h =================================================================== --- uspace/lib/c/include/adt/hash_set.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ (revision ) @@ -1,84 +1,0 @@ -/* - * Copyright (c) 2006 Jakub Jermar - * Copyright (c) 2011 Radim Vansa - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup libc - * @{ - */ -/** @file - */ - -#ifndef LIBC_HASH_SET_H_ -#define LIBC_HASH_SET_H_ - -#include -#include - -#define HASH_SET_MIN_SIZE 8 - -typedef unsigned long (*hash_set_hash)(const link_t *); -typedef int (*hash_set_equals)(const link_t *, const link_t *); - -/** Hash table structure. */ -typedef struct { - list_t *table; - - /** Current table size */ - size_t size; - - /** - * Current number of entries. If count > size, - * the table is rehashed into table with double - * size. If (4 * count < size) && (size > min_size), - * the table is rehashed into table with half the size. - */ - size_t count; - - /** Hash function */ - hash_set_hash hash; - - /** Hash table item equals function */ - hash_set_equals equals; -} hash_set_t; - -extern int hash_set_init(hash_set_t *, hash_set_hash, hash_set_equals, size_t); -extern int hash_set_insert(hash_set_t *, link_t *); -extern link_t *hash_set_find(hash_set_t *, const link_t *); -extern int hash_set_contains(const hash_set_t *, const link_t *); -extern size_t hash_set_count(const hash_set_t *); -extern link_t *hash_set_remove(hash_set_t *, const link_t *); -extern void hash_set_remove_selected(hash_set_t *, - int (*)(link_t *, void *), void *); -extern void hash_set_destroy(hash_set_t *); -extern void hash_set_apply(hash_set_t *, void (*)(link_t *, void *), void *); -extern void hash_set_clear(hash_set_t *, void (*)(link_t *, void *), void *); - -#endif - -/** @} - */ Index: uspace/lib/c/include/adt/hash_table.h =================================================================== --- uspace/lib/c/include/adt/hash_table.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/c/include/adt/hash_table.h (revision 062d9000625057300f609429080872d6492b542e) @@ -1,4 +1,6 @@ /* * Copyright (c) 2006 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -39,58 +41,65 @@ #include #include +#include -typedef unsigned long hash_count_t; -typedef unsigned long hash_index_t; +/** Opaque hash table link type. */ +typedef struct ht_link { + link_t link; +} ht_link_t; /** Set of operations for hash table. */ typedef struct { - /** Hash function. - * - * @param key Array of keys needed to compute hash index. - * All keys must be passed. - * - * @return Index into hash table. - * - */ - hash_index_t (*hash)(unsigned long key[]); + /** Returns the hash of the key stored in the item (ie its lookup key). */ + size_t (*hash)(const ht_link_t *item); - /** Hash table item comparison function. - * - * @param key Array of keys that will be compared with item. It is - * not necessary to pass all keys. - * - * @return True if the keys match, false otherwise. - * - */ - int (*compare)(unsigned long key[], hash_count_t keys, link_t *item); + /** Returns the hash of the key. */ + size_t (*key_hash)(void *key); + /** True if the items are equal (have the same lookup keys). */ + bool (*equal)(const ht_link_t *item1, const ht_link_t *item2); + + /** Returns true if the key is equal to the item's lookup key. */ + bool (*key_equal)(void *key, const ht_link_t *item); + /** Hash table item removal callback. + * + * Must not invoke any mutating functions of the hash table. * * @param item Item that was removed from the hash table. - * */ - void (*remove_callback)(link_t *item); -} hash_table_operations_t; + void (*remove_callback)(ht_link_t *item); +} hash_table_ops_t; /** Hash table structure. */ typedef struct { - list_t *entry; - hash_count_t entries; - hash_count_t max_keys; - hash_table_operations_t *op; + hash_table_ops_t *op; + list_t *bucket; + size_t bucket_cnt; + size_t full_item_cnt; + size_t item_cnt; + size_t max_load; + bool apply_ongoing; } hash_table_t; -#define hash_table_get_instance(item, type, member) \ - list_get_instance((item), type, member) +#define hash_table_get_inst(item, type, member) \ + member_to_inst((item), type, member) -extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t, - hash_table_operations_t *); +extern bool hash_table_create(hash_table_t *, size_t, size_t, + hash_table_ops_t *); +extern void hash_table_destroy(hash_table_t *); + +extern bool hash_table_empty(hash_table_t *); +extern size_t hash_table_size(hash_table_t *); + extern void hash_table_clear(hash_table_t *); -extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *); -extern link_t *hash_table_find(hash_table_t *, unsigned long []); -extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t); -extern void hash_table_destroy(hash_table_t *); -extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *), - void *); +extern void hash_table_insert(hash_table_t *, ht_link_t *); +extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *); +extern ht_link_t *hash_table_find(const hash_table_t *, void *); +extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *); +extern size_t hash_table_remove(hash_table_t *, void *); +extern void hash_table_remove_item(hash_table_t *, ht_link_t *); +extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *), + void *); + #endif Index: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/c/include/adt/list.h (revision 062d9000625057300f609429080872d6492b542e) @@ -71,6 +71,43 @@ iterator != &(list).head; iterator = iterator->next) +/** Unlike list_foreach(), allows removing items while traversing a list. + * + * @code + * list_t mylist; + * typedef struct item { + * int value; + * link_t item_link; + * } item_t; + * + * //.. + * + * // Print each list element's value and remove the element from the list. + * list_foreach_safe(mylist, cur_link, next_link) { + * item_t *cur_item = list_get_instance(cur_link, item_t, item_link); + * printf("%d\n", cur_item->value); + * list_remove(cur_link); + * } + * @endcode + * + * @param list List to traverse. + * @param iterator Iterator to the current element of the list. + * The item this iterator points may be safely removed + * from the list. + * @param next_iter Iterator to the next element of the list. + */ +#define list_foreach_safe(list, iterator, next_iter) \ + for (link_t *iterator = (list).head.next, \ + *next_iter = iterator->next; \ + iterator != &(list).head; \ + iterator = next_iter, next_iter = iterator->next) + #define assert_link_not_used(link) \ assert(((link)->prev == NULL) && ((link)->next == NULL)) + +/** Returns true if the link is definitely part of a list. False if not sure. */ +static inline int link_in_use(link_t *link) +{ + return link->prev != NULL && link->next != NULL; +} /** Initialize doubly-linked circular list link Index: uspace/lib/c/include/macros.h =================================================================== --- uspace/lib/c/include/macros.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/c/include/macros.h (revision 062d9000625057300f609429080872d6492b542e) @@ -52,4 +52,10 @@ | ((((uint64_t) (up)) & 0xffffffff) << 32)) +#ifndef member_to_inst +#define member_to_inst(ptr_member, type, member_identif) \ + ((type*) (((void*)(ptr_member)) - ((void*)&(((type*)0)->member_identif)))) +#endif + + #endif Index: uspace/lib/nic/include/nic.h =================================================================== --- uspace/lib/nic/include/nic.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/nic/include/nic.h (revision 062d9000625057300f609429080872d6492b542e) @@ -40,4 +40,5 @@ #include +#include #include #include @@ -53,5 +54,5 @@ */ typedef struct nic_wol_virtue { - link_t item; + ht_link_t item; nic_wv_id_t id; nic_wv_type_t type; Index: uspace/lib/nic/include/nic_addr_db.h =================================================================== --- uspace/lib/nic/include/nic_addr_db.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/nic/include/nic_addr_db.h (revision 062d9000625057300f609429080872d6492b542e) @@ -43,14 +43,5 @@ #endif -#include - -/** - * Initial size of DB's hash set - */ -#define NIC_ADDR_DB_INIT_SIZE 8 -/** - * Maximal length of addresses in the DB (in bytes). - */ -#define NIC_ADDR_MAX_LENGTH 16 +#include /** @@ -58,25 +49,14 @@ */ typedef struct nic_addr_db { - hash_set_t set; + hash_table_t set; size_t addr_len; } nic_addr_db_t; -/** - * Helper structure for keeping the address in the hash set. - */ -typedef struct nic_addr_entry { - link_t item; - size_t addr_len; - uint8_t addr[NIC_ADDR_MAX_LENGTH]; -} nic_addr_entry_t; extern int nic_addr_db_init(nic_addr_db_t *db, size_t addr_len); extern void nic_addr_db_clear(nic_addr_db_t *db); extern void nic_addr_db_destroy(nic_addr_db_t *db); -extern size_t nic_addr_db_count(const nic_addr_db_t *db); extern int nic_addr_db_insert(nic_addr_db_t *db, const uint8_t *addr); extern int nic_addr_db_remove(nic_addr_db_t *db, const uint8_t *addr); -extern void nic_addr_db_remove_selected(nic_addr_db_t *db, - int (*func)(const uint8_t *, void *), void *arg); extern int nic_addr_db_contains(const nic_addr_db_t *db, const uint8_t *addr); extern void nic_addr_db_foreach(const nic_addr_db_t *db, Index: uspace/lib/nic/include/nic_wol_virtues.h =================================================================== --- uspace/lib/nic/include/nic_wol_virtues.h (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/nic/include/nic_wol_virtues.h (revision 062d9000625057300f609429080872d6492b542e) @@ -51,5 +51,5 @@ * Operations for table */ - hash_table_operations_t table_operations; + hash_table_ops_t table_operations; /** * WOL virtues hashed by their ID's. Index: uspace/lib/nic/src/nic_addr_db.c =================================================================== --- uspace/lib/nic/src/nic_addr_db.c (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/nic/src/nic_addr_db.c (revision 062d9000625057300f609429080872d6492b542e) @@ -35,4 +35,6 @@ * @brief Generic hash-set based database of addresses */ +#include "nic_addr_db.h" +#include "libarch/common.h" #include #include @@ -40,49 +42,72 @@ #include #include - -#include "nic_addr_db.h" - -/** - * Hash set helper function - */ -static int nic_addr_equals(const link_t *item1, const link_t *item2) -{ - assert(item1 && item2); - size_t addr_len = ((const nic_addr_entry_t *) item1)->addr_len; - - assert(addr_len == ((const nic_addr_entry_t *) item2)->addr_len); - - size_t i; - for (i = 0; i < addr_len; ++i) { - if (((nic_addr_entry_t *) item1)->addr[i] != - ((nic_addr_entry_t *) item2)->addr[i]) - return false; +#include +#include +#include + + +/** + * Helper structure for keeping the address in the hash set. + */ +typedef struct nic_addr_entry { + ht_link_t link; + uint8_t len; + uint8_t addr[1]; +} nic_addr_entry_t; + + +/* + * Hash table helper functions + */ +typedef struct { + size_t len; + const uint8_t *addr; +} addr_key_t; + +static bool nic_addr_key_equal(void *key_arg, const ht_link_t *item) +{ + addr_key_t *key = (addr_key_t*)key_arg; + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + + return 0 == bcmp(entry->addr, key->addr, entry->len); +} + +static size_t addr_hash(size_t len, const uint8_t *addr) +{ + size_t hash = 0; + + for (size_t i = 0; i < len; ++i) { + hash = (hash << 5) ^ addr[i]; } - return true; -} - -/** - * Hash set helper function - */ -static unsigned long nic_addr_hash(const link_t *item) -{ - assert(item); - const nic_addr_entry_t *entry = (const nic_addr_entry_t *) item; - unsigned long hash = 0; - - size_t i; - for (i = 0; i < entry->addr_len; ++i) { - hash = (hash << 8) ^ (hash >> 24) ^ entry->addr[i]; - } + return hash; } -/** - * Helper wrapper - */ -static void nic_addr_destroy(link_t *item, void *unused) -{ - free(item); -} +static size_t nic_addr_key_hash(void *k) +{ + addr_key_t *key = (addr_key_t*)k; + return addr_hash(key->len, key->addr); +} + +static size_t nic_addr_hash(const ht_link_t *item) +{ + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + return addr_hash(entry->len, entry->addr); +} + +static void nic_addr_removed(ht_link_t *item) +{ + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + + free(entry); +} + +static hash_table_ops_t set_ops = { + .hash = nic_addr_hash, + .key_hash = nic_addr_key_hash, + .key_equal = nic_addr_key_equal, + .equal = 0, + .remove_callback = nic_addr_removed +}; /** @@ -99,11 +124,11 @@ { assert(db); - if (addr_len > NIC_ADDR_MAX_LENGTH) { + + if (addr_len > UCHAR_MAX) return EINVAL; - } - if (!hash_set_init(&db->set, nic_addr_hash, nic_addr_equals, - NIC_ADDR_DB_INIT_SIZE)) { + + if (!hash_table_create(&db->set, 0, 0, &set_ops)) return ENOMEM; - } + db->addr_len = addr_len; return EOK; @@ -118,5 +143,5 @@ { assert(db); - hash_set_clear(&db->set, nic_addr_destroy, NULL); + hash_table_clear(&db->set); } @@ -129,20 +154,7 @@ { assert(db); - hash_set_apply(&db->set, nic_addr_destroy, NULL); - hash_set_destroy(&db->set); -} - -/** - * Get number of addresses in the db - * - * @param db - * - * @return Number of adresses - */ -size_t nic_addr_db_count(const nic_addr_db_t *db) -{ - assert(db); - return hash_set_count(&db->set); -} + hash_table_destroy(&db->set); +} + /** @@ -160,12 +172,22 @@ { assert(db && addr); - nic_addr_entry_t *entry = malloc(sizeof (nic_addr_entry_t)); - if (entry == NULL) { + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + if (hash_table_find(&db->set, &key)) + return EEXIST; + + nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1); + if (entry == NULL) return ENOMEM; - } - entry->addr_len = db->addr_len; + + entry->len = (uint8_t) db->addr_len; memcpy(entry->addr, addr, db->addr_len); - - return hash_set_insert(&db->set, &entry->item) ? EOK : EEXIST; + + hash_table_insert(&db->set, &entry->link); + return EOK; } @@ -182,11 +204,14 @@ { assert(db && addr); - nic_addr_entry_t entry; - entry.addr_len = db->addr_len; - memcpy(entry.addr, addr, db->addr_len); - - link_t *removed = hash_set_remove(&db->set, &entry.item); - free(removed); - return removed != NULL ? EOK : ENOENT; + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + if (hash_table_remove(&db->set, &key)) + return EOK; + else + return ENOENT; } @@ -202,9 +227,11 @@ { assert(db && addr); - nic_addr_entry_t entry; - entry.addr_len = db->addr_len; - memcpy(entry.addr, addr, db->addr_len); - - return hash_set_contains(&db->set, &entry.item); + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + return 0 != hash_table_find(&db->set, &key); } @@ -220,7 +247,10 @@ * Helper function for nic_addr_db_foreach */ -static void nic_addr_db_fe_helper(link_t *item, void *arg) { +static bool nic_addr_db_fe_helper(ht_link_t *item, void *arg) +{ nic_addr_db_fe_arg_t *hs = (nic_addr_db_fe_arg_t *) arg; - hs->func(((nic_addr_entry_t *) item)->addr, hs->arg); + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + hs->func(entry->addr, hs->arg); + return true; } @@ -237,39 +267,5 @@ { nic_addr_db_fe_arg_t hs = { .func = func, .arg = arg }; - hash_set_apply((hash_set_t *) &db->set, nic_addr_db_fe_helper, &hs); -} - -/** - * Helper structure for nic_addr_db_remove_selected - */ -typedef struct { - int (*func)(const uint8_t *, void *); - void *arg; -} nic_addr_db_rs_arg_t; - -/** - * Helper function for nic_addr_db_foreach - */ -static int nic_addr_db_rs_helper(link_t *item, void *arg) { - nic_addr_db_rs_arg_t *hs = (nic_addr_db_rs_arg_t *) arg; - int retval = hs->func(((nic_addr_entry_t *) item)->addr, hs->arg); - if (retval) { - free(item); - } - return retval; -} - -/** - * Removes all addresses for which the function returns non-zero. - * - * @param db - * @param func User-defined function - * @param arg Custom argument passed to the function - */ -void nic_addr_db_remove_selected(nic_addr_db_t *db, - int (*func)(const uint8_t *, void *), void *arg) -{ - nic_addr_db_rs_arg_t hs = { .func = func, .arg = arg }; - hash_set_remove_selected(&db->set, nic_addr_db_rs_helper, &hs); + hash_table_apply((hash_table_t*)&db->set, nic_addr_db_fe_helper, &hs); } Index: uspace/lib/nic/src/nic_wol_virtues.c =================================================================== --- uspace/lib/nic/src/nic_wol_virtues.c (revision d94809517f828232745c791f5d7d49244768b43a) +++ uspace/lib/nic/src/nic_wol_virtues.c (revision 062d9000625057300f609429080872d6492b542e) @@ -37,32 +37,28 @@ #include "nic_wol_virtues.h" +#include "nic.h" #include #include -#define NIC_WV_HASH_COUNT 32 - -/** - * Hash table helper function - */ -static int nic_wv_compare(unsigned long key[], hash_count_t keys, - link_t *item) + +/* + * Hash table helper functions + */ + +static size_t nic_wv_key_hash(void *key) +{ + return *(nic_wv_id_t*) key; +} + +static size_t nic_wv_hash(const ht_link_t *item) { nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item; - return (virtue->id == (nic_wv_id_t) key[0]); -} - -/** - * Hash table helper function - */ -static void nic_wv_rc(link_t *item) -{ -} - -/** - * Hash table helper function - */ -static hash_index_t nic_wv_hash(unsigned long keys[]) -{ - return keys[0] % NIC_WV_HASH_COUNT; + return virtue->id; +} + +static bool nic_wv_key_equal(void *key, const ht_link_t *item) +{ + nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item; + return (virtue->id == *(nic_wv_id_t*) key); } @@ -77,10 +73,12 @@ int nic_wol_virtues_init(nic_wol_virtues_t *wvs) { - bzero(wvs, sizeof (nic_wol_virtues_t)); - wvs->table_operations.compare = nic_wv_compare; + bzero(wvs, sizeof(nic_wol_virtues_t)); wvs->table_operations.hash = nic_wv_hash; - wvs->table_operations.remove_callback = nic_wv_rc; - if (!hash_table_create(&wvs->table, NIC_WV_HASH_COUNT, 1, - &wvs->table_operations)) { + wvs->table_operations.key_hash = nic_wv_key_hash; + wvs->table_operations.key_equal = nic_wv_key_equal; + wvs->table_operations.equal = 0; + wvs->table_operations.remove_callback = 0; + + if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) { return ENOMEM; } @@ -170,8 +168,6 @@ do { virtue->id = wvs->next_id++; - } while (NULL != - hash_table_find(&wvs->table, (unsigned long *) &virtue->id)); - hash_table_insert(&wvs->table, - (unsigned long *) &virtue->id, &virtue->item); + } while (NULL != hash_table_find(&wvs->table, &virtue->id)); + hash_table_insert(&wvs->table, &virtue->item); virtue->next = wvs->lists[virtue->type]; wvs->lists[virtue->type] = virtue; @@ -191,6 +187,6 @@ nic_wol_virtue_t *nic_wol_virtues_remove(nic_wol_virtues_t *wvs, nic_wv_id_t id) { - nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) - hash_table_find(&wvs->table, (unsigned long *) &id); + nic_wol_virtue_t *virtue = + (nic_wol_virtue_t *) hash_table_find(&wvs->table, &id); if (virtue == NULL) { return NULL; @@ -198,5 +194,5 @@ /* Remove from filter_table */ - hash_table_remove(&wvs->table, (unsigned long *) &id, 1); + hash_table_remove_item(&wvs->table, &virtue->item); /* Remove from filter_types */ @@ -235,6 +231,5 @@ * constant virtue the retyping is correct. */ - link_t *virtue = hash_table_find( - &((nic_wol_virtues_t *) wvs)->table, (unsigned long *) &id); + ht_link_t *virtue = hash_table_find(&((nic_wol_virtues_t *) wvs)->table, &id); return (const nic_wol_virtue_t *) virtue; }