Index: uspace/app/mkexfat/mkexfat.c =================================================================== --- uspace/app/mkexfat/mkexfat.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/app/mkexfat/mkexfat.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -49,4 +49,5 @@ #include #include +#include #include "exfat.h" #include "upcase.h" @@ -87,5 +88,4 @@ #define FIRST_FREE_CLUSTER 2 -#define min(x, y) ((x) < (y) ? (x) : (y)) typedef struct exfat_cfg { Index: uspace/app/trace/ipcp.c =================================================================== --- uspace/app/trace/ipcp.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/app/trace/ipcp.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -53,5 +53,5 @@ ipc_callid_t call_hash; - link_t link; + ht_link_t link; } pending_call_t; @@ -73,45 +73,32 @@ proto_t *proto_unknown; /**< Protocol with no known methods. */ -static size_t pending_call_key_hash(unsigned long key[]); -static size_t pending_call_hash(const link_t *item); -static bool pending_call_match(unsigned long key[], size_t keys, - const link_t *item); + +static size_t pending_call_key_hash(void *key) +{ + ipc_callid_t *call_id = (ipc_callid_t *)key; + return *call_id; +} + +static size_t pending_call_hash(const ht_link_t *item) +{ + pending_call_t *hs = hash_table_get_inst(item, pending_call_t, link); + return hs->call_hash; +} + +static bool pending_call_key_equal(void *key, const ht_link_t *item) +{ + ipc_callid_t *call_id = (ipc_callid_t *)key; + pending_call_t *hs = hash_table_get_inst(item, pending_call_t, link); + + return *call_id == hs->call_hash; +} static hash_table_ops_t pending_call_ops = { .hash = pending_call_hash, .key_hash = pending_call_key_hash, - .match = pending_call_match, + .key_equal = pending_call_key_equal, .equal = 0, .remove_callback = 0 }; - - -static size_t pending_call_key_hash(unsigned long key[]) -{ - size_t hash = 17; - hash = 31 * hash + key[1]; - hash = 31 * hash + key[0]; - return hash; -} - -static size_t pending_call_hash(const link_t *item) -{ - pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link); - unsigned long key[] = { - LOWER32(hs->call_hash), - UPPER32(hs->call_hash) - }; - return pending_call_key_hash(key); -} - -static bool pending_call_match(unsigned long key[], size_t keys, - const link_t *item) -{ - assert(keys == 2); - pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link); - - return MERGE_LOUP32(key[0], key[1]) == hs->call_hash; -} - @@ -184,5 +171,6 @@ } - hash_table_create(&pending_calls, 0, 2, &pending_call_ops); + bool ok = hash_table_create(&pending_calls, 0, 0, &pending_call_ops); + assert(ok); } @@ -338,5 +326,5 @@ void ipcp_call_in(ipc_call_t *call, ipc_callid_t hash) { - link_t *item; + ht_link_t *item; pending_call_t *pcall; @@ -350,10 +338,6 @@ hash = hash & ~IPC_CALLID_ANSWERED; - unsigned long key[] = { - LOWER32(hash), - UPPER32(hash) - }; - - item = hash_table_find(&pending_calls, key); + + item = hash_table_find(&pending_calls, &hash); if (item == NULL) return; /* No matching question found */ @@ -363,6 +347,6 @@ */ - pcall = hash_table_get_instance(item, pending_call_t, link); - hash_table_remove(&pending_calls, key, 2); + pcall = hash_table_get_inst(item, pending_call_t, link); + hash_table_remove(&pending_calls, &hash); parse_answer(hash, pcall, call); Index: uspace/app/trace/proto.c =================================================================== --- uspace/app/trace/proto.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/app/trace/proto.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -45,35 +45,32 @@ typedef struct { - unsigned srv; + int srv; proto_t *proto; - link_t link; + ht_link_t link; } srv_proto_t; typedef struct { - sysarg_t method; + int method; oper_t *oper; - link_t link; + ht_link_t link; } method_oper_t; - - - -static size_t srv_proto_key_hash(unsigned long key[]) -{ - return key[0]; -} - -static size_t srv_proto_hash(const link_t *item) -{ - srv_proto_t *sp = hash_table_get_instance(item, srv_proto_t, link); - unsigned long key = sp->srv; - return srv_proto_key_hash(&key); -} - -static bool srv_proto_match(unsigned long key[], size_t keys, const link_t *item) -{ - srv_proto_t *sp = hash_table_get_instance(item, srv_proto_t, link); - - return key[0] == sp->srv; +/* Hash table operations. */ + +static size_t srv_proto_key_hash(void *key) +{ + return *(int *)key; +} + +static size_t srv_proto_hash(const ht_link_t *item) +{ + srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link); + return sp->srv; +} + +static bool srv_proto_key_equal(void *key, const ht_link_t *item) +{ + srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link); + return sp->srv == *(int *)key; } @@ -81,5 +78,5 @@ .hash = srv_proto_hash, .key_hash = srv_proto_key_hash, - .match = srv_proto_match, + .key_equal = srv_proto_key_equal, .equal = 0, .remove_callback = 0 @@ -87,22 +84,19 @@ -static size_t method_oper_key_hash(unsigned long key[]) -{ - return key[0]; -} - -static size_t method_oper_hash(const link_t *item) -{ - method_oper_t *mo = hash_table_get_instance(item, method_oper_t, link); - unsigned long key = mo->method; - return method_oper_key_hash(&key); -} - -static bool method_oper_match(unsigned long key[], size_t keys, - const link_t *item) -{ - method_oper_t *mo = hash_table_get_instance(item, method_oper_t, link); - - return key[0] == mo->method; +static size_t method_oper_key_hash(void *key) +{ + return *(int *)key; +} + +static size_t method_oper_hash(const ht_link_t *item) +{ + method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link); + return mo->method; +} + +static bool method_oper_key_equal(void *key, const ht_link_t *item) +{ + method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link); + return mo->method == *(int *)key; } @@ -110,5 +104,5 @@ .hash = method_oper_hash, .key_hash = method_oper_key_hash, - .match = method_oper_match, + .key_equal = method_oper_key_equal, .equal = 0, .remove_callback = 0 @@ -118,5 +112,7 @@ void proto_init(void) { - hash_table_create(&srv_proto, 0, 1, &srv_proto_ops); + /* todo: check return value. */ + bool ok = hash_table_create(&srv_proto, 0, 0, &srv_proto_ops); + assert(ok); } @@ -139,12 +135,8 @@ proto_t *proto_get_by_srv(int srv) { - link_t *item; - srv_proto_t *sp; - - unsigned long key = srv; - item = hash_table_find(&srv_proto, &key); + ht_link_t *item = hash_table_find(&srv_proto, &srv); if (item == NULL) return NULL; - sp = hash_table_get_instance(item, srv_proto_t, link); + srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link); return sp->proto; } @@ -153,5 +145,7 @@ { proto->name = name; - hash_table_create(&proto->method_oper, 0, 1, &method_oper_ops); + /* todo: check return value. */ + bool ok = hash_table_create(&proto->method_oper, 0, 0, &method_oper_ops); + assert(ok); } @@ -184,13 +178,8 @@ oper_t *proto_get_oper(proto_t *proto, int method) { - unsigned long key; - link_t *item; - method_oper_t *mo; - - key = method; - item = hash_table_find(&proto->method_oper, &key); + ht_link_t *item = hash_table_find(&proto->method_oper, &method); if (item == NULL) return NULL; - mo = hash_table_get_instance(item, method_oper_t, link); + method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link); return mo->oper; } Index: uspace/lib/block/libblock.c =================================================================== --- uspace/lib/block/libblock.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/block/libblock.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -254,28 +254,21 @@ } -static size_t cache_key_hash(unsigned long *key) -{ - /* As recommended by Effective Java, 2nd Edition. */ - size_t hash = 17; - hash = 31 * hash + key[1]; - hash = 31 * hash + key[0]; - return hash; -} - -static size_t cache_hash(const link_t *item) -{ - block_t *b = hash_table_get_instance(item, block_t, hash_link); - unsigned long key[] = { - LOWER32(b->lba), - UPPER32(b->lba) - }; - - return cache_key_hash(key); -} - -static bool cache_match(unsigned long *key, size_t keys, const 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 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; } @@ -284,5 +277,5 @@ .hash = cache_hash, .key_hash = cache_key_hash, - .match = cache_match, + .key_equal = cache_key_equal, .equal = 0, .remove_callback = 0 @@ -317,5 +310,5 @@ cache->blocks_cluster = cache->lblock_size / devcon->pblock_size; - if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) { + if (!hash_table_create(&cache->block_hash, 0, 0, &cache_ops)) { free(cache); return ENOMEM; @@ -355,9 +348,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); @@ -391,5 +380,4 @@ fibril_rwlock_initialize(&b->contents_lock); link_initialize(&b->free_link); - link_initialize(&b->hash_link); } @@ -411,9 +399,5 @@ cache_t *cache; block_t *b; - link_t *l; - unsigned long key[2] = { - LOWER32(ba), - UPPER32(ba) - }; + link_t *link; int rc; @@ -431,11 +415,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) @@ -475,6 +459,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); @@ -516,6 +500,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 @@ -539,9 +523,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); } @@ -663,9 +643,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/libblock.h =================================================================== --- uspace/lib/block/libblock.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/block/libblock.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -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/generic/adt/hash_table.c =================================================================== --- uspace/lib/c/generic/adt/hash_table.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/c/generic/adt/hash_table.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -1,4 +1,6 @@ /* * Copyright (c) 2008 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -62,12 +64,11 @@ static size_t round_up_size(size_t size); static bool alloc_table(size_t bucket_cnt, list_t **pbuckets); -static void item_inserted(hash_table_t *h); -static void item_removed(hash_table_t *h); -static inline void remove_item(hash_table_t *h, link_t *item); -static size_t remove_duplicates(hash_table_t *h, unsigned long key[]); -static size_t remove_matching(hash_table_t *h, unsigned long key[], size_t key_cnt); +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(link_t *item) +static void nop_remove_callback(ht_link_t *item) { /* no-op */ @@ -90,10 +91,13 @@ * */ -bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_keys, +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->key_hash && op->match); - assert(max_keys > 0); + 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; h->bucket_cnt = round_up_size(init_size); @@ -102,14 +106,49 @@ return false; - h->max_keys = max_keys; - h->items = 0; + h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load; + h->item_cnt = 0; h->op = op; - - if (h->op->remove_callback == 0) + 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 * @@ -118,38 +157,32 @@ void hash_table_clear(hash_table_t *h) { + 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); - } - } - - h->items = 0; - - /* Shrink the table to its minimum size if possible. */ - if (HT_MIN_BUCKETS < h->bucket_cnt) { - list_t *new_buckets; - if (alloc_table(HT_MIN_BUCKETS, &new_buckets)) { - free(h->bucket); - h->bucket = new_buckets; - h->bucket_cnt = HT_MIN_BUCKETS; - } - } -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - * - */ -void hash_table_destroy(hash_table_t *h) -{ - assert(h); - assert(h->bucket); - - free(h->bucket); - - h->bucket = 0; - h->bucket_cnt = 0; + h->op->remove_callback(cur_link); + } + } + + h->item_cnt = 0; } @@ -160,16 +193,15 @@ * @param item Item to be inserted into the hash table. */ -void hash_table_insert(hash_table_t *h, link_t *item) +void hash_table_insert(hash_table_t *h, ht_link_t *item) { assert(item); assert(h && h->bucket); - assert(h->op && h->op->hash); + assert(!h->apply_ongoing); size_t idx = h->op->hash(item) % h->bucket_cnt; - assert(idx < h->bucket_cnt); - - list_append(item, &h->bucket[idx]); - item_inserted(h); + list_append(&item->link, &h->bucket[idx]); + ++h->item_cnt; + grow_if_needed(h); } @@ -184,14 +216,12 @@ * @return True if the inserted item was the only item with such a lookup key. */ -bool hash_table_insert_unique(hash_table_t *h, link_t *item) +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); - - size_t item_hash = h->op->hash(item); - size_t idx = item_hash % h->bucket_cnt; - - assert(idx < h->bucket_cnt); + assert(!h->apply_ongoing); + + size_t idx = h->op->hash(item) % h->bucket_cnt; /* Check for duplicates. */ @@ -201,10 +231,12 @@ * calling equal() might very well be just as fast. */ - if (h->op->equal(cur, item)) + 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, &h->bucket[idx]); - item_inserted(h); + list_append(&item->link, &h->bucket[idx]); + ++h->item_cnt; + grow_if_needed(h); return true; @@ -219,22 +251,19 @@ * */ -link_t *hash_table_find(const hash_table_t *h, unsigned long key[]) -{ - assert(h && h->bucket); - assert(h->op && h->op->key_hash && h->op->match); - - size_t key_hash = h->op->key_hash(key); - size_t idx = key_hash % h->bucket_cnt; - - assert(idx < h->bucket_cnt); - +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->match() may very well be + * checked if the hashes match but op->key_equal() may very well be * just as fast as op->hash(). */ - if (h->op->match(key, h->max_keys, cur)) { - return cur; + if (h->op->key_equal(key, cur_link)) { + return cur_link; } } @@ -243,26 +272,25 @@ } - -/** 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 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)(link_t *, void *), void *arg) -{ - for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { - list_foreach_safe(h->bucket[idx], cur, next) { - /* - * The next pointer had already been saved. f() may safely - * delete cur (but not next!). - */ - if (!f(cur, arg)) - return; - } - } +/** 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; } @@ -278,88 +306,77 @@ * @return Returns the number of removed items. */ -size_t hash_table_remove(hash_table_t *h, unsigned long key[], size_t key_cnt) -{ - assert(h && h->bucket); - assert(h && h->op && h->op->hash && - h->op->remove_callback); - assert(key_cnt <= h->max_keys); - - /* All keys are known, remove from a specific bucket. */ - if (key_cnt == h->max_keys) { - return remove_duplicates(h, key); - } else { - /* - * Fewer keys were passed. - * Any partially matching entries are to be removed. - */ - return remove_matching(h, key, key_cnt); - } +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, link_t *item) +void hash_table_remove_item(hash_table_t *h, ht_link_t *item) { assert(item); assert(h && h->bucket); - - remove_item(h, item); -} - -/** Unlink the item from a bucket, update statistics and resize if needed. */ -static inline void remove_item(hash_table_t *h, link_t *item) -{ - assert(item); - - list_remove(item); - item_removed(h); + assert(link_in_use(&item->link)); + + list_remove(&item->link); + --h->item_cnt; h->op->remove_callback(item); -} - -/** Removes all items matching key in the bucket key hashes to. */ -static size_t remove_duplicates(hash_table_t *h, unsigned long key[]) -{ - assert(h && h->bucket); - assert(h->op && h->op->key_hash && h->op->match); - - size_t key_hash = h->op->key_hash(key); - size_t idx = key_hash % h->bucket_cnt; - - assert(idx < h->bucket_cnt); - - size_t removed = 0; - - list_foreach_safe(h->bucket[idx], cur, next) { - if (h->op->match(key, h->max_keys, cur)) { - ++removed; - remove_item(h, cur); - } - } - - return removed; -} - -/** Removes all items in any bucket in the table that match the partial key. */ -static size_t remove_matching(hash_table_t *h, unsigned long key[], - size_t key_cnt) -{ - assert(h && h->bucket); - assert(key_cnt < h->max_keys); - - size_t removed = 0; - /* - * Fewer keys were passed. - * Any partially matching entries are to be removed. - */ + 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) { - if (h->op->match(key, key_cnt, cur)) { - ++removed; - remove_item(h, cur); - } - } - } - - return removed; - + 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); } @@ -392,35 +409,9 @@ } -/** 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); - - list_t *new_buckets; - - /* Leave the table as is if we cannot resize. */ - if (!alloc_table(new_bucket_cnt, &new_buckets)) - return; - - /* 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) { - size_t new_idx = h->op->hash(cur) % 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; -} - -/** Shrinks the table if needed. */ -static void item_removed(hash_table_t *h) -{ - --h->items; - - if (HT_MIN_BUCKETS < h->items && h->items <= HT_MAX_LOAD * h->bucket_cnt / 4) { + +/** 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). @@ -432,11 +423,9 @@ } -/** Grows the table if needed. */ -static void item_inserted(hash_table_t *h) -{ - ++h->items; - +/** 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 (HT_MAX_LOAD * h->bucket_cnt < h->items) { + 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; @@ -445,4 +434,39 @@ } +/** 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; + + 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]); + } + } + } + + 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 b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/c/generic/async.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -202,5 +202,5 @@ /* Client connection data */ typedef struct { - link_t link; + ht_link_t link; task_id_t in_task_id; @@ -214,5 +214,5 @@ /** Hash table link. */ - link_t link; + ht_link_t link; /** Incoming client task ID. */ @@ -390,32 +390,21 @@ static LIST_INITIALIZE(timeout_list); -static size_t client_key_hash(unsigned long key[]) -{ - assert(key); - /* LOWER32(in_task_id) */ - return key[0] >> 4; -} - -static size_t client_hash(const link_t *item) -{ - client_t *client = hash_table_get_instance(item, client_t, link); - - unsigned long key[2] = { - LOWER32(client->in_task_id), - UPPER32(client->in_task_id), - }; - - return client_key_hash(key); -} - -static bool client_match(unsigned long key[], size_t keys, const 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 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; } @@ -425,5 +414,5 @@ .hash = client_hash, .key_hash = client_key_hash, - .match = client_match, + .key_equal = client_key_equal, .equal = 0, .remove_callback = 0 @@ -437,46 +426,23 @@ * */ -static size_t conn_key_hash(unsigned long key[]) -{ - assert(key); - return key[0] >> 4; -} - -static size_t conn_hash(const link_t *item) -{ - connection_t *conn = hash_table_get_instance(item, connection_t, link); - unsigned long key = conn->in_phone_hash; - return conn_key_hash(&key); -} - -/** 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 bool conn_match(unsigned long key[], size_t keys, const 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 bool conn_equal(const link_t *item1, const link_t *item2) -{ - connection_t *c1 = hash_table_get_instance(item1, connection_t, link); - connection_t *c2 = hash_table_get_instance(item2, connection_t, link); - - return c1->in_phone_hash == c2->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. */ @@ -484,7 +450,7 @@ .hash = conn_hash, .key_hash = conn_key_hash, - .match = conn_match, - .equal = conn_equal, - .remove_callback = conn_remove + .key_equal = conn_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -534,6 +500,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) { @@ -542,5 +507,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)); @@ -722,14 +687,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) { @@ -751,13 +712,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 @@ -855,6 +812,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); @@ -1134,8 +1090,8 @@ void __async_init(void) { - if (!hash_table_create(&client_hash_table, 0, 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, 0, 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 bc216a07a86e40d74455b7f4d6fb8f65e195443d) +++ uspace/lib/c/include/adt/hash.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -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_table.h =================================================================== --- uspace/lib/c/include/adt/hash_table.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/c/include/adt/hash_table.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -1,4 +1,6 @@ /* * Copyright (c) 2006 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -39,30 +41,25 @@ #include #include +#include +/** Opaque hash table link type. */ +typedef struct ht_link { + link_t link; +} ht_link_t; /** Set of operations for hash table. */ typedef struct { - /** Returns the hash of the key stored in the item. - */ - size_t (*hash)(const link_t *item); + /** Returns the hash of the key stored in the item (ie its lookup key). */ + size_t (*hash)(const ht_link_t *item); - /** Returns the hash of the key. - */ - size_t (*key_hash)(unsigned long key[]); + /** Returns the hash of the key. */ + size_t (*key_hash)(void *key); - /** Hash table item match 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. - * - */ - bool (*match)(unsigned long key[], size_t keys, const link_t *item); + /** True if the items are equal (have the same lookup keys). */ + bool (*equal)(const ht_link_t *item1, const ht_link_t *item2); - /** - */ - bool (*equal)(const link_t *item1, const 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. * @@ -71,29 +68,36 @@ * @param item Item that was removed from the hash table. */ - void (*remove_callback)(link_t *item); + void (*remove_callback)(ht_link_t *item); } hash_table_ops_t; /** Hash table structure. */ typedef struct { + hash_table_ops_t *op; list_t *bucket; size_t bucket_cnt; - size_t max_keys; - size_t items; - hash_table_ops_t *op; + 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 *, 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 *, link_t *); -extern bool hash_table_insert_unique(hash_table_t *, link_t *); -extern link_t *hash_table_find(const hash_table_t *, unsigned long []); -extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t); -extern void hash_table_remove_item(hash_table_t *, link_t *); -extern void hash_table_destroy(hash_table_t *); -extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, 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 *); Index: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/c/include/adt/list.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -105,4 +105,10 @@ 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/nic/include/nic.h =================================================================== --- uspace/lib/nic/include/nic.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/nic/include/nic.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -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/src/nic_addr_db.c =================================================================== --- uspace/lib/nic/src/nic_addr_db.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/nic/src/nic_addr_db.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -36,4 +36,5 @@ */ #include "nic_addr_db.h" +#include "libarch/common.h" #include #include @@ -43,12 +44,6 @@ #include #include - -/* The key count hash table field is not used. Use this dummy value. */ -#define KEY_CNT 1 - -/** - * Maximal length of addresses in the DB (in bytes). - */ -#define NIC_ADDR_MAX_LENGTH 16 +#include + /** @@ -56,6 +51,7 @@ */ typedef struct nic_addr_entry { - link_t link; - uint8_t addr[NIC_ADDR_MAX_LENGTH]; + ht_link_t link; + uint8_t len; + uint8_t addr[1]; } nic_addr_entry_t; @@ -64,21 +60,23 @@ * Hash table helper functions */ - -static bool nic_addr_match(unsigned long *key, size_t key_cnt, - const link_t *item) -{ - uint8_t *addr = (uint8_t*)key; - nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); - - return 0 == bcmp(entry->addr, addr, NIC_ADDR_MAX_LENGTH); -} - -static size_t nic_addr_key_hash(unsigned long *key) -{ - uint8_t *addr = (uint8_t*)key; +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 (int i = NIC_ADDR_MAX_LENGTH - 1; i >= 0; --i) { - hash = (hash << 8) ^ (hash >> 24) ^ addr[i]; + + for (size_t i = 0; i < len; ++i) { + hash = (hash << 5) ^ addr[i]; } @@ -86,13 +84,17 @@ } -static size_t nic_addr_hash(const link_t *item) -{ - nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); - - unsigned long *key = (unsigned long*)entry->addr; - return nic_addr_key_hash(key); -} - -static void nic_addr_removed(link_t *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); @@ -104,5 +106,5 @@ .hash = nic_addr_hash, .key_hash = nic_addr_key_hash, - .match = nic_addr_match, + .key_equal = nic_addr_key_equal, .equal = 0, .remove_callback = nic_addr_removed @@ -122,9 +124,9 @@ { assert(db); - if (addr_len > NIC_ADDR_MAX_LENGTH) { + + if (addr_len > UCHAR_MAX) return EINVAL; - } - - if (!hash_table_create(&db->set, 0, KEY_CNT, &set_ops)) + + if (!hash_table_create(&db->set, 0, 0, &set_ops)) return ENOMEM; @@ -152,5 +154,4 @@ { assert(db); - nic_addr_db_clear(db); hash_table_destroy(&db->set); } @@ -171,17 +172,18 @@ { assert(db && addr); - /* Ugly type-punning hack. */ - unsigned long *key = (unsigned long*)addr; - - if (hash_table_find(&db->set, key)) + + 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)); + nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1); if (entry == NULL) return ENOMEM; - - link_initialize(&entry->link); - - bzero(entry->addr, NIC_ADDR_MAX_LENGTH); + + entry->len = (uint8_t) db->addr_len; memcpy(entry->addr, addr, db->addr_len); @@ -202,14 +204,14 @@ { assert(db && addr); - unsigned long *key = (unsigned long*)addr; - - link_t *item = hash_table_find(&db->set, key); - - if (item) { - hash_table_remove_item(&db->set, item); + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + if (hash_table_remove(&db->set, &key)) return EOK; - } else { + else return ENOENT; - } } @@ -225,7 +227,11 @@ { assert(db && addr); - unsigned long *key = (unsigned long*)addr; - - return 0 != hash_table_find(&db->set, key); + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + return 0 != hash_table_find(&db->set, &key); } @@ -241,5 +247,5 @@ * Helper function for nic_addr_db_foreach */ -static bool 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; Index: uspace/lib/nic/src/nic_wol_virtues.c =================================================================== --- uspace/lib/nic/src/nic_wol_virtues.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/lib/nic/src/nic_wol_virtues.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -37,4 +37,5 @@ #include "nic_wol_virtues.h" +#include "nic.h" #include #include @@ -45,20 +46,19 @@ */ -static size_t nic_wv_key_hash(unsigned long keys[]) -{ - return keys[0]; -} - -static size_t nic_wv_hash(const link_t *item) +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; - unsigned long key = virtue->id; - return nic_wv_key_hash(&key); -} - -static bool nic_wv_match(unsigned long key[], size_t keys, const link_t *item) + 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[0]); + return (virtue->id == *(nic_wv_id_t*) key); } @@ -76,9 +76,9 @@ wvs->table_operations.hash = nic_wv_hash; wvs->table_operations.key_hash = nic_wv_key_hash; - wvs->table_operations.match = nic_wv_match; + 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, 1, &wvs->table_operations)) { + if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) { return ENOMEM; } @@ -168,6 +168,5 @@ do { virtue->id = wvs->next_id++; - } while (NULL != - hash_table_find(&wvs->table, (unsigned long *) &virtue->id)); + } while (NULL != hash_table_find(&wvs->table, &virtue->id)); hash_table_insert(&wvs->table, &virtue->item); virtue->next = wvs->lists[virtue->type]; @@ -188,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; @@ -195,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 */ @@ -232,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; } Index: uspace/srv/devman/devman.c =================================================================== --- uspace/srv/devman/devman.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/devman/devman.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -66,49 +66,53 @@ /* hash table operations */ -static size_t devices_key_hash(unsigned long key[]) -{ - return key[0]; -} - -static size_t devman_devices_hash(const link_t *item) -{ - dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev); - unsigned long key = dev->handle; - return devices_key_hash(&key); -} - -static size_t devman_functions_hash(const link_t *item) -{ - fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun); - unsigned long key = fun->handle; - return devices_key_hash(&key); -} - -static size_t loc_functions_hash(const link_t *item) -{ - fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun); - unsigned long key = fun->service_id; - return devices_key_hash(&key); -} - -static bool devman_devices_match(unsigned long key[], size_t keys, - const link_t *item) -{ - dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev); - return (dev->handle == (devman_handle_t) key[0]); -} - -static bool devman_functions_match(unsigned long key[], size_t keys, - const link_t *item) -{ - fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun); - return (fun->handle == (devman_handle_t) key[0]); -} - -static bool loc_functions_match(unsigned long key[], size_t keys, - const link_t *item) -{ - fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun); - return (fun->service_id == (service_id_t) key[0]); +static inline size_t handle_key_hash(void *key) +{ + devman_handle_t handle = *(devman_handle_t*)key; + return handle; +} + +static size_t devman_devices_hash(const ht_link_t *item) +{ + dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev); + return handle_key_hash(&dev->handle); +} + +static size_t devman_functions_hash(const ht_link_t *item) +{ + fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun); + return handle_key_hash(&fun->handle); +} + +static bool devman_devices_key_equal(void *key, const ht_link_t *item) +{ + devman_handle_t handle = *(devman_handle_t*)key; + dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev); + return dev->handle == handle; +} + +static bool devman_functions_key_equal(void *key, const ht_link_t *item) +{ + devman_handle_t handle = *(devman_handle_t*)key; + fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun); + return fun->handle == handle; +} + +static inline size_t service_id_key_hash(void *key) +{ + service_id_t service_id = *(service_id_t*)key; + return service_id; +} + +static size_t loc_functions_hash(const ht_link_t *item) +{ + fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun); + return service_id_key_hash(&fun->service_id); +} + +static bool loc_functions_key_equal(void *key, const ht_link_t *item) +{ + service_id_t service_id = *(service_id_t*)key; + fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun); + return fun->service_id == service_id; } @@ -116,6 +120,6 @@ static hash_table_ops_t devman_devices_ops = { .hash = devman_devices_hash, - .key_hash = devices_key_hash, - .match = devman_devices_match, + .key_hash = handle_key_hash, + .key_equal = devman_devices_key_equal, .equal = 0, .remove_callback = 0 @@ -124,6 +128,6 @@ static hash_table_ops_t devman_functions_ops = { .hash = devman_functions_hash, - .key_hash = devices_key_hash, - .match = devman_functions_match, + .key_hash = handle_key_hash, + .key_equal = devman_functions_key_equal, .equal = 0, .remove_callback = 0 @@ -132,6 +136,6 @@ static hash_table_ops_t loc_devices_ops = { .hash = loc_functions_hash, - .key_hash = devices_key_hash, - .match = loc_functions_match, + .key_hash = service_id_key_hash, + .key_equal = loc_functions_key_equal, .equal = 0, .remove_callback = 0 @@ -998,7 +1002,7 @@ tree->current_handle = 0; - hash_table_create(&tree->devman_devices, 0, 1, &devman_devices_ops); - hash_table_create(&tree->devman_functions, 0, 1, &devman_functions_ops); - hash_table_create(&tree->loc_functions, 0, 1, &loc_devices_ops); + hash_table_create(&tree->devman_devices, 0, 0, &devman_devices_ops); + hash_table_create(&tree->devman_functions, 0, 0, &devman_functions_ops); + hash_table_create(&tree->loc_functions, 0, 0, &loc_devices_ops); fibril_rwlock_initialize(&tree->rwlock); @@ -1034,5 +1038,4 @@ list_initialize(&dev->functions); link_initialize(&dev->driver_devices); - link_initialize(&dev->devman_dev); return dev; @@ -1082,14 +1085,11 @@ dev_node_t *find_dev_node_no_lock(dev_tree_t *tree, devman_handle_t handle) { - unsigned long key = handle; - link_t *link; - assert(fibril_rwlock_is_locked(&tree->rwlock)); - link = hash_table_find(&tree->devman_devices, &key); + ht_link_t *link = hash_table_find(&tree->devman_devices, &handle); if (link == NULL) return NULL; - return hash_table_get_instance(link, dev_node_t, devman_dev); + return hash_table_get_inst(link, dev_node_t, devman_dev); } @@ -1165,6 +1165,4 @@ link_initialize(&fun->dev_functions); list_initialize(&fun->match_ids.ids); - link_initialize(&fun->devman_fun); - link_initialize(&fun->loc_fun); return fun; @@ -1215,15 +1213,13 @@ fun_node_t *find_fun_node_no_lock(dev_tree_t *tree, devman_handle_t handle) { - unsigned long key = handle; - link_t *link; fun_node_t *fun; assert(fibril_rwlock_is_locked(&tree->rwlock)); - link = hash_table_find(&tree->devman_functions, &key); + ht_link_t *link = hash_table_find(&tree->devman_functions, &handle); if (link == NULL) return NULL; - fun = hash_table_get_instance(link, fun_node_t, devman_fun); + fun = hash_table_get_inst(link, fun_node_t, devman_fun); return fun; @@ -1324,6 +1320,5 @@ /* Remove node from the handle-to-node map. */ - unsigned long key = dev->handle; - hash_table_remove(&tree->devman_devices, &key, 1); + hash_table_remove(&tree->devman_devices, &dev->handle); /* Unlink from parent function. */ @@ -1386,6 +1381,5 @@ /* Remove the node from the handle-to-node map. */ - unsigned long key = fun->handle; - hash_table_remove(&tree->devman_functions, &key, 1); + hash_table_remove(&tree->devman_functions, &fun->handle); /* Remove the node from the list of its parent's children. */ @@ -1500,11 +1494,9 @@ { fun_node_t *fun = NULL; - link_t *link; - unsigned long key = (unsigned long) service_id; fibril_rwlock_read_lock(&tree->rwlock); - link = hash_table_find(&tree->loc_functions, &key); + ht_link_t *link = hash_table_find(&tree->loc_functions, &service_id); if (link != NULL) { - fun = hash_table_get_instance(link, fun_node_t, loc_fun); + fun = hash_table_get_inst(link, fun_node_t, loc_fun); fun_add_ref(fun); } Index: uspace/srv/devman/devman.h =================================================================== --- uspace/srv/devman/devman.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/devman/devman.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -150,5 +150,5 @@ * Used by the hash table of devices indexed by devman device handles. */ - link_t devman_dev; + ht_link_t devman_dev; /** @@ -201,10 +201,10 @@ * Used by the hash table of functions indexed by devman device handles. */ - link_t devman_fun; + ht_link_t devman_fun; /** * Used by the hash table of functions indexed by service IDs. */ - link_t loc_fun; + ht_link_t loc_fun; }; Index: uspace/srv/fs/cdfs/cdfs_ops.c =================================================================== --- uspace/srv/fs/cdfs/cdfs_ops.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/cdfs/cdfs_ops.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -37,6 +37,8 @@ */ +#include "cdfs_ops.h" #include #include +#include #include #include @@ -50,19 +52,9 @@ #include "cdfs.h" #include "cdfs_endian.h" -#include "cdfs_ops.h" /** Standard CD-ROM block size */ #define BLOCK_SIZE 2048 -/** Implicit node cache size - * - * More nodes can be actually cached if the files remain - * opended. - * - */ -#define NODE_CACHE_SIZE 200 - -#define NODES_KEY_SRVC 0 -#define NODES_KEY_INDEX 1 +#define NODE_CACHE_SIZE 200 /** All root nodes have index 0 */ @@ -203,5 +195,5 @@ service_id_t service_id; /**< Service ID of block device */ - link_t nh_link; /**< Nodes hash table link */ + ht_link_t nh_link; /**< Nodes hash table link */ cdfs_dentry_type_t type; /**< Dentry type */ @@ -224,45 +216,36 @@ static hash_table_t nodes; -static size_t nodes_key_hash(unsigned long key[]) -{ - return key[NODES_KEY_INDEX]; -} - -static size_t nodes_hash(const link_t *item) -{ - cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link); - - unsigned long key[] = { - [NODES_KEY_INDEX] = node->index - }; - - return nodes_key_hash(key); -} - -static bool nodes_match(unsigned long key[], size_t keys, const link_t *item) -{ - cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link); - - if (keys == 1) { - return (node->service_id == key[NODES_KEY_SRVC]); - } else { - assert(keys == 2); - return ((node->service_id == key[NODES_KEY_SRVC]) && - (node->index == key[NODES_KEY_INDEX])); - } -} - -static bool nodes_equal(const link_t *item1, const link_t *item2) -{ - cdfs_node_t *node1 = hash_table_get_instance(item1, cdfs_node_t, nh_link); - cdfs_node_t *node2 = hash_table_get_instance(item2, cdfs_node_t, nh_link); - - return node1->service_id == node2->service_id - && node1->index == node2->index; -} - -static void nodes_remove_callback(link_t *item) -{ - cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link); +/* + * Hash table support functions. + */ + +typedef struct { + service_id_t service_id; + fs_index_t index; +} ht_key_t; + +static size_t nodes_key_hash(void *k) +{ + ht_key_t *key = (ht_key_t*)k; + return hash_combine(key->service_id, key->index); +} + +static size_t nodes_hash(const ht_link_t *item) +{ + cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link); + return hash_combine(node->service_id, node->index); +} + +static bool nodes_key_equal(void *k, const ht_link_t *item) +{ + cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link); + ht_key_t *key = (ht_key_t*)k; + + return key->service_id == node->service_id && key->index == node->index; +} + +static void nodes_remove_callback(ht_link_t *item) +{ + cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link); assert(node->type == CDFS_DIRECTORY); @@ -283,6 +266,6 @@ .hash = nodes_hash, .key_hash = nodes_key_hash, - .match = nodes_match, - .equal = nodes_equal, + .key_equal = nodes_key_equal, + .equal = 0, .remove_callback = nodes_remove_callback }; @@ -291,13 +274,13 @@ fs_index_t index) { - unsigned long key[] = { - [NODES_KEY_SRVC] = service_id, - [NODES_KEY_INDEX] = index + ht_key_t key = { + .index = index, + .service_id = service_id }; - link_t *link = hash_table_find(&nodes, key); + ht_link_t *link = hash_table_find(&nodes, &key); if (link) { cdfs_node_t *node = - hash_table_get_instance(link, cdfs_node_t, nh_link); + hash_table_get_inst(link, cdfs_node_t, nh_link); *rfn = FS_NODE(node); @@ -325,5 +308,4 @@ node->opened = 0; - link_initialize(&node->nh_link); list_initialize(&node->cs_list); } @@ -517,13 +499,13 @@ static fs_node_t *get_cached_node(service_id_t service_id, fs_index_t index) { - unsigned long key[] = { - [NODES_KEY_SRVC] = service_id, - [NODES_KEY_INDEX] = index + ht_key_t key = { + .index = index, + .service_id = service_id }; - link_t *link = hash_table_find(&nodes, key); + ht_link_t *link = hash_table_find(&nodes, &key); if (link) { cdfs_node_t *node = - hash_table_get_instance(link, cdfs_node_t, nh_link); + hash_table_get_inst(link, cdfs_node_t, nh_link); return FS_NODE(node); } @@ -811,11 +793,19 @@ } +static bool rm_service_id_nodes(ht_link_t *item, void *arg) +{ + service_id_t service_id = *(service_id_t*)arg; + cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link); + + if (node->service_id == service_id) { + hash_table_remove_item(&nodes, &node->nh_link); + } + + return true; +} + static void cdfs_instance_done(service_id_t service_id) { - unsigned long key[] = { - [NODES_KEY_SRVC] = service_id - }; - - hash_table_remove(&nodes, key, 1); + hash_table_apply(&nodes, rm_service_id_nodes, &service_id); block_cache_fini(service_id); block_fini(service_id); @@ -831,15 +821,15 @@ size_t *rbytes) { - unsigned long key[] = { - [NODES_KEY_SRVC] = service_id, - [NODES_KEY_INDEX] = index + ht_key_t key = { + .index = index, + .service_id = service_id }; - link_t *link = hash_table_find(&nodes, key); + ht_link_t *link = hash_table_find(&nodes, &key); if (link == NULL) return ENOENT; cdfs_node_t *node = - hash_table_get_instance(link, cdfs_node_t, nh_link); + hash_table_get_inst(link, cdfs_node_t, nh_link); if (!node->processed) { @@ -921,5 +911,5 @@ } -static bool cache_remove_closed(link_t *item, void *arg) +static bool cache_remove_closed(ht_link_t *item, void *arg) { size_t *premove_cnt = (size_t*)arg; @@ -927,5 +917,5 @@ /* Some nodes were requested to be removed from the cache. */ if (0 < *premove_cnt) { - cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link); + cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link); if (!node->opened) { @@ -957,15 +947,15 @@ return EOK; - unsigned long key[] = { - [NODES_KEY_SRVC] = service_id, - [NODES_KEY_INDEX] = index + ht_key_t key = { + .index = index, + .service_id = service_id }; - link_t *link = hash_table_find(&nodes, key); + ht_link_t *link = hash_table_find(&nodes, &key); if (link == 0) return ENOENT; cdfs_node_t *node = - hash_table_get_instance(link, cdfs_node_t, nh_link); + hash_table_get_inst(link, cdfs_node_t, nh_link); assert(node->opened > 0); @@ -1013,5 +1003,5 @@ bool cdfs_init(void) { - if (!hash_table_create(&nodes, 0, 2, &nodes_ops)) + if (!hash_table_create(&nodes, 0, 0, &nodes_ops)) return false; Index: uspace/srv/fs/exfat/exfat.h =================================================================== --- uspace/srv/fs/exfat/exfat.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/exfat/exfat.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -106,7 +106,7 @@ typedef struct { /** Used indices (position) hash table link. */ - link_t uph_link; + ht_link_t uph_link; /** Used indices (index) hash table link. */ - link_t uih_link; + ht_link_t uih_link; fibril_mutex_t lock; Index: uspace/srv/fs/exfat/exfat_idx.c =================================================================== --- uspace/srv/fs/exfat/exfat_idx.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/exfat/exfat_idx.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -41,4 +41,5 @@ #include #include +#include #include #include @@ -91,4 +92,5 @@ if (lock) fibril_mutex_lock(&unused_lock); + list_foreach(unused_list, l) { u = list_get_instance(l, unused_t, link); @@ -112,53 +114,40 @@ static hash_table_t up_hash; -#define UPH_SID_KEY 0 -#define UPH_PFC_KEY 1 -#define UPH_PDI_KEY 2 - -static size_t pos_key_hash(unsigned long key[]) -{ - /* Inspired by Effective Java, 2nd edition. */ - size_t hash = 17; - - hash = 31 * hash + key[UPH_PFC_KEY]; - hash = 31 * hash + key[UPH_PDI_KEY]; - hash = 31 * hash + key[UPH_SID_KEY]; - - return hash; -} - -static size_t pos_hash(const link_t *item) -{ - exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link); - - unsigned long pkey[] = { - [UPH_SID_KEY] = fidx->service_id, - [UPH_PFC_KEY] = fidx->pfc, - [UPH_PDI_KEY] = fidx->pdi, - }; - - return pos_key_hash(pkey); -} - -static bool pos_match(unsigned long key[], size_t keys, const link_t *item) -{ - service_id_t service_id = (service_id_t)key[UPH_SID_KEY]; +typedef struct { + service_id_t service_id; exfat_cluster_t pfc; unsigned pdi; - exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link); - - switch (keys) { - case 1: - return (service_id == fidx->service_id); - case 3: - pfc = (exfat_cluster_t) key[UPH_PFC_KEY]; - pdi = (unsigned) key[UPH_PDI_KEY]; - return (service_id == fidx->service_id) && (pfc == fidx->pfc) && - (pdi == fidx->pdi); - default: - assert((keys == 1) || (keys == 3)); - } - - return 0; +} pos_key_t; + +static inline size_t pos_key_hash(void *key) +{ + pos_key_t *pos = (pos_key_t*)key; + + size_t hash = 0; + hash = hash_combine(pos->pfc, pos->pdi); + return hash_combine(hash, pos->service_id); +} + +static size_t pos_hash(const ht_link_t *item) +{ + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link); + + pos_key_t pkey = { + .service_id = fidx->service_id, + .pfc = fidx->pfc, + .pdi = fidx->pdi, + }; + + return pos_key_hash(&pkey); +} + +static bool pos_key_equal(void *key, const ht_link_t *item) +{ + pos_key_t *pos = (pos_key_t*)key; + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link); + + return pos->service_id == fidx->service_id + && pos->pdi == fidx->pdi + && pos->pfc == fidx->pfc; } @@ -166,5 +155,5 @@ .hash = pos_hash, .key_hash = pos_key_hash, - .match = pos_match, + .key_equal = pos_key_equal, .equal = 0, .remove_callback = 0, @@ -177,57 +166,32 @@ static hash_table_t ui_hash; -#define UIH_SID_KEY 0 -#define UIH_INDEX_KEY 1 - -static size_t idx_key_hash(unsigned long key[]) -{ - service_id_t service_id = (service_id_t)key[UIH_SID_KEY]; - fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY]; - - /* - * Compute a simple hash unlimited by specific table size as per: - * Effective Java, 2nd edition. - */ - size_t hash = 17; - hash = 31 * hash + (size_t)service_id; - hash = 31 * hash + (size_t)index; - return hash; -} - -static size_t idx_hash(const link_t *item) -{ - exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link); - - unsigned long ikey[] = { - [UIH_SID_KEY] = fidx->service_id, - [UIH_INDEX_KEY] = fidx->index, - }; - - return idx_key_hash(ikey); -} - -static bool idx_match(unsigned long key[], size_t keys, const link_t *item) -{ - service_id_t service_id = (service_id_t)key[UIH_SID_KEY]; +typedef struct { + service_id_t service_id; fs_index_t index; - exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link); - - switch (keys) { - case 1: - return (service_id == fidx->service_id); - case 2: - index = (fs_index_t) key[UIH_INDEX_KEY]; - return (service_id == fidx->service_id) && - (index == fidx->index); - default: - assert((keys == 1) || (keys == 2)); - } - - return 0; -} - -static void idx_remove_callback(link_t *item) -{ - exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link); +} idx_key_t; + +static size_t idx_key_hash(void *key_arg) +{ + idx_key_t *key = (idx_key_t*)key_arg; + return hash_combine(key->service_id, key->index); +} + +static size_t idx_hash(const ht_link_t *item) +{ + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); + return hash_combine(fidx->service_id, fidx->index); +} + +static bool idx_key_equal(void *key_arg, const ht_link_t *item) +{ + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); + idx_key_t *key = (idx_key_t*)key_arg; + + return key->index == fidx->index && key->service_id == fidx->service_id; +} + +static void idx_remove_callback(ht_link_t *item) +{ + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); free(fidx); @@ -237,5 +201,5 @@ .hash = idx_hash, .key_hash = idx_key_hash, - .match = idx_match, + .key_equal = idx_key_equal, .equal = 0, .remove_callback = idx_remove_callback, @@ -379,6 +343,4 @@ } - link_initialize(&fidx->uph_link); - link_initialize(&fidx->uih_link); fibril_mutex_initialize(&fidx->lock); fidx->service_id = service_id; @@ -415,15 +377,15 @@ { exfat_idx_t *fidx; - link_t *l; - unsigned long pkey[] = { - [UPH_SID_KEY] = service_id, - [UPH_PFC_KEY] = pfc, - [UPH_PDI_KEY] = pdi, + + pos_key_t pos_key = { + .service_id = service_id, + .pfc = pfc, + .pdi = pdi, }; fibril_mutex_lock(&used_lock); - l = hash_table_find(&up_hash, pkey); + ht_link_t *l = hash_table_find(&up_hash, &pos_key); if (l) { - fidx = hash_table_get_instance(l, exfat_idx_t, uph_link); + fidx = hash_table_get_inst(l, exfat_idx_t, uph_link); } else { int rc; @@ -456,12 +418,6 @@ void exfat_idx_hashout(exfat_idx_t *idx) { - unsigned long pkey[] = { - [UPH_SID_KEY] = idx->service_id, - [UPH_PFC_KEY] = idx->pfc, - [UPH_PDI_KEY] = idx->pdi, - }; - - fibril_mutex_lock(&used_lock); - hash_table_remove(&up_hash, pkey, 3); + fibril_mutex_lock(&used_lock); + hash_table_remove_item(&up_hash, &idx->uph_link); fibril_mutex_unlock(&used_lock); } @@ -471,14 +427,14 @@ { exfat_idx_t *fidx = NULL; - link_t *l; - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id, - [UIH_INDEX_KEY] = index, + + idx_key_t idx_key = { + .service_id = service_id, + .index = index, }; fibril_mutex_lock(&used_lock); - l = hash_table_find(&ui_hash, ikey); + ht_link_t *l = hash_table_find(&ui_hash, &idx_key); if (l) { - fidx = hash_table_get_instance(l, exfat_idx_t, uih_link); + fidx = hash_table_get_inst(l, exfat_idx_t, uih_link); fibril_mutex_lock(&fidx->lock); } @@ -494,10 +450,8 @@ void exfat_idx_destroy(exfat_idx_t *idx) { - unsigned long ikey[] = { - [UIH_SID_KEY] = idx->service_id, - [UIH_INDEX_KEY] = idx->index, + idx_key_t idx_key = { + .service_id = idx->service_id, + .index = idx->index, }; - service_id_t service_id = idx->service_id; - fs_index_t index = idx->index; /* TODO: assert(idx->pfc == FAT_CLST_RES0); */ @@ -510,8 +464,8 @@ * the index hash only. */ - hash_table_remove(&ui_hash, ikey, 2); + hash_table_remove(&ui_hash, &idx_key); fibril_mutex_unlock(&used_lock); /* Release the VFS index. */ - exfat_index_free(service_id, index); + exfat_index_free(idx_key.service_id, idx_key.index); /* The index structure itself is freed in idx_remove_callback(). */ } @@ -519,7 +473,7 @@ int exfat_idx_init(void) { - if (!hash_table_create(&up_hash, 0, 3, &uph_ops)) + if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) return ENOMEM; - if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) { + if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) { hash_table_destroy(&up_hash); return ENOMEM; @@ -531,4 +485,5 @@ { /* We assume the hash tables are empty. */ + assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash)); hash_table_destroy(&up_hash); hash_table_destroy(&ui_hash); @@ -555,13 +510,30 @@ } +static bool rm_pos_service_id(ht_link_t *item, void *arg) +{ + service_id_t service_id = *(service_id_t*)arg; + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link); + + if (fidx->service_id == service_id) { + hash_table_remove_item(&up_hash, item); + } + + return true; +} + +static bool rm_idx_service_id(ht_link_t *item, void *arg) +{ + service_id_t service_id = *(service_id_t*)arg; + exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); + + if (fidx->service_id == service_id) { + hash_table_remove_item(&ui_hash, item); + } + + return true; +} + void exfat_idx_fini_by_service_id(service_id_t service_id) { - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id - }; - unsigned long pkey[] = { - [UPH_SID_KEY] = service_id - }; - /* * Remove this instance's index structure from up_hash and ui_hash. @@ -570,6 +542,6 @@ */ fibril_mutex_lock(&used_lock); - hash_table_remove(&up_hash, pkey, 1); - hash_table_remove(&ui_hash, ikey, 1); + hash_table_apply(&up_hash, rm_pos_service_id, &service_id); + hash_table_apply(&ui_hash, rm_idx_service_id, &service_id); fibril_mutex_unlock(&used_lock); Index: uspace/srv/fs/exfat/exfat_ops.c =================================================================== --- uspace/srv/fs/exfat/exfat_ops.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/exfat/exfat_ops.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -54,4 +54,5 @@ #include #include +#include #include #include Index: uspace/srv/fs/ext2fs/ext2fs_ops.c =================================================================== --- uspace/srv/fs/ext2fs/ext2fs_ops.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/ext2fs/ext2fs_ops.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -49,4 +49,5 @@ #include #include +#include #include #include @@ -62,7 +63,4 @@ #define EXT2FS_NODE(node) ((node) ? (ext2fs_node_t *) (node)->data : NULL) #define EXT2FS_DBG(format, ...) {if (false) printf("ext2fs: %s: " format "\n", __FUNCTION__, ##__VA_ARGS__);} -#define OPEN_NODES_KEYS 2 -#define OPEN_NODES_DEV_HANDLE_KEY 0 -#define OPEN_NODES_INODE_KEY 1 typedef struct ext2fs_instance { @@ -77,5 +75,5 @@ ext2_inode_ref_t *inode_ref; fs_node_t *fs_node; - link_t link; + ht_link_t link; unsigned int references; } ext2fs_node_t; @@ -121,43 +119,36 @@ static FIBRIL_MUTEX_INITIALIZE(open_nodes_lock); -/* Hash table interface for open nodes hash table */ -static size_t open_nodes_key_hash(unsigned long key[]) -{ - /* Hash construction recommended in Effective Java, 2nd Edition. */ - size_t hash = 17; - hash = 31 * hash + key[OPEN_NODES_DEV_HANDLE_KEY]; - hash = 31 * hash + key[OPEN_NODES_INODE_KEY]; - return hash; -} - -static size_t open_nodes_hash(const link_t *item) -{ - ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link); +/* + * Hash table interface for open nodes hash table + */ + +typedef struct { + service_id_t service_id; + fs_index_t index; +} node_key_t; + +static size_t open_nodes_key_hash(void *key) +{ + node_key_t *node_key = (node_key_t*)key; + return hash_combine(node_key->service_id, node_key->index); +} + +static size_t open_nodes_hash(const ht_link_t *item) +{ + ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link); assert(enode->instance); assert(enode->inode_ref); - unsigned long key[] = { - [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id, - [OPEN_NODES_INODE_KEY] = enode->inode_ref->index, - }; - - return open_nodes_key_hash(key); -} - -static bool open_nodes_match(unsigned long key[], size_t keys, - const link_t *item) -{ - ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link); - assert(keys > 0); - if (enode->instance->service_id != - ((service_id_t) key[OPEN_NODES_DEV_HANDLE_KEY])) { - return false; - } - if (keys == 1) { - return true; - } - assert(keys == 2); - return (enode->inode_ref->index == key[OPEN_NODES_INODE_KEY]); + return hash_combine(enode->instance->service_id, enode->inode_ref->index); +} + +static bool open_nodes_key_equal(void *key, const ht_link_t *item) +{ + node_key_t *node_key = (node_key_t*)key; + ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link); + + return node_key->service_id == enode->instance->service_id + && node_key->index == enode->inode_ref->index; } @@ -165,5 +156,5 @@ .hash = open_nodes_hash, .key_hash = open_nodes_key_hash, - .match = open_nodes_match, + .key_equal = open_nodes_key_equal, .equal = 0, .remove_callback = 0, @@ -175,5 +166,5 @@ int ext2fs_global_init(void) { - if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) { + if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) { return ENOMEM; } @@ -329,12 +320,12 @@ /* Check if the node is not already open */ - unsigned long key[] = { - [OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id, - [OPEN_NODES_INODE_KEY] = index, + node_key_t key = { + .service_id = inst->service_id, + .index = index }; - link_t *already_open = hash_table_find(&open_nodes, key); + ht_link_t *already_open = hash_table_find(&open_nodes, &key); if (already_open) { - enode = hash_table_get_instance(already_open, ext2fs_node_t, link); + enode = hash_table_get_inst(already_open, ext2fs_node_t, link); *rfn = enode->fs_node; enode->references++; @@ -370,5 +361,4 @@ enode->references = 1; enode->fs_node = node; - link_initialize(&enode->link); node->data = enode; @@ -421,15 +411,15 @@ int ext2fs_node_put_core(ext2fs_node_t *enode) { - int rc; - - unsigned long key[] = { - [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id, - [OPEN_NODES_INODE_KEY] = enode->inode_ref->index, + node_key_t key = { + .service_id = enode->instance->service_id, + .index = enode->inode_ref->index }; - hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS); + + hash_table_remove(&open_nodes, &key); + assert(enode->instance->open_nodes_count > 0); enode->instance->open_nodes_count--; - rc = ext2_filesystem_put_inode_ref(enode->inode_ref); + int rc = ext2_filesystem_put_inode_ref(enode->inode_ref); if (rc != EOK) { EXT2FS_DBG("ext2_filesystem_put_inode_ref failed"); Index: uspace/srv/fs/fat/fat.h =================================================================== --- uspace/srv/fs/fat/fat.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/fat/fat.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -190,7 +190,7 @@ typedef struct { /** Used indices (position) hash table link. */ - link_t uph_link; + ht_link_t uph_link; /** Used indices (index) hash table link. */ - link_t uih_link; + ht_link_t uih_link; fibril_mutex_t lock; Index: uspace/srv/fs/fat/fat_idx.c =================================================================== --- uspace/srv/fs/fat/fat_idx.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/fat/fat_idx.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -41,9 +41,9 @@ #include #include +#include #include #include #include #include - /** Each instance of this type describes one interval of freed VFS indices. */ @@ -59,6 +59,6 @@ */ typedef struct { - link_t link; - service_id_t service_id; + link_t link; + service_id_t service_id; /** Next unassigned index. */ @@ -98,5 +98,5 @@ return u; } - + if (lock) fibril_mutex_unlock(&unused_lock); @@ -114,53 +114,40 @@ static hash_table_t up_hash; -#define UPH_SID_KEY 0 -#define UPH_PFC_KEY 1 -#define UPH_PDI_KEY 2 - -static size_t pos_key_hash(unsigned long key[]) -{ - /* Inspired by Effective Java, 2nd edition. */ - size_t hash = 17; - - hash = 31 * hash + key[UPH_PFC_KEY]; - hash = 31 * hash + key[UPH_PDI_KEY]; - hash = 31 * hash + key[UPH_SID_KEY]; - - return hash; -} - -static size_t pos_hash(const link_t *item) -{ - fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link); - - unsigned long pkey[] = { - [UPH_SID_KEY] = fidx->service_id, - [UPH_PFC_KEY] = fidx->pfc, - [UPH_PDI_KEY] = fidx->pdi, - }; - - return pos_key_hash(pkey); -} - -static bool pos_match(unsigned long key[], size_t keys, const link_t *item) -{ - service_id_t service_id = (service_id_t)key[UPH_SID_KEY]; +typedef struct { + service_id_t service_id; fat_cluster_t pfc; unsigned pdi; - fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link); - - switch (keys) { - case 1: - return (service_id == fidx->service_id); - case 3: - pfc = (fat_cluster_t) key[UPH_PFC_KEY]; - pdi = (unsigned) key[UPH_PDI_KEY]; - return (service_id == fidx->service_id) && (pfc == fidx->pfc) && - (pdi == fidx->pdi); - default: - assert((keys == 1) || (keys == 3)); - } - - return 0; +} pos_key_t; + +static inline size_t pos_key_hash(void *key) +{ + pos_key_t *pos = (pos_key_t*)key; + + size_t hash = 0; + hash = hash_combine(pos->pfc, pos->pdi); + return hash_combine(hash, pos->service_id); +} + +static size_t pos_hash(const ht_link_t *item) +{ + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link); + + pos_key_t pkey = { + .service_id = fidx->service_id, + .pfc = fidx->pfc, + .pdi = fidx->pdi, + }; + + return pos_key_hash(&pkey); +} + +static bool pos_key_equal(void *key, const ht_link_t *item) +{ + pos_key_t *pos = (pos_key_t*)key; + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link); + + return pos->service_id == fidx->service_id + && pos->pdi == fidx->pdi + && pos->pfc == fidx->pfc; } @@ -168,5 +155,5 @@ .hash = pos_hash, .key_hash = pos_key_hash, - .match = pos_match, + .key_equal = pos_key_equal, .equal = 0, .remove_callback = 0, @@ -179,54 +166,32 @@ static hash_table_t ui_hash; -#define UIH_SID_KEY 0 -#define UIH_INDEX_KEY 1 - -static size_t idx_key_hash(unsigned long key[]) -{ - /* - * Compute a simple hash unlimited by specific table size as per: - * Effective Java, 2nd edition. - */ - size_t hash = 17; - hash = 31 * hash + key[UIH_SID_KEY]; - hash = 31 * hash + key[UIH_INDEX_KEY]; - return hash; -} - -static size_t idx_hash(const link_t *item) -{ - fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link); - - unsigned long ikey[] = { - [UIH_SID_KEY] = fidx->service_id, - [UIH_INDEX_KEY] = fidx->index, - }; - - return idx_key_hash(ikey); -} - -static bool idx_match(unsigned long key[], size_t keys, const link_t *item) -{ - service_id_t service_id = (service_id_t)key[UIH_SID_KEY]; +typedef struct { + service_id_t service_id; fs_index_t index; - fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link); - - switch (keys) { - case 1: - return (service_id == fidx->service_id); - case 2: - index = (fs_index_t) key[UIH_INDEX_KEY]; - return (service_id == fidx->service_id) && - (index == fidx->index); - default: - assert((keys == 1) || (keys == 2)); - } - - return 0; -} - -static void idx_remove_callback(link_t *item) -{ - fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link); +} idx_key_t; + +static size_t idx_key_hash(void *key_arg) +{ + idx_key_t *key = (idx_key_t*)key_arg; + return hash_combine(key->service_id, key->index); +} + +static size_t idx_hash(const ht_link_t *item) +{ + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link); + return hash_combine(fidx->service_id, fidx->index); +} + +static bool idx_key_equal(void *key_arg, const ht_link_t *item) +{ + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link); + idx_key_t *key = (idx_key_t*)key_arg; + + return key->index == fidx->index && key->service_id == fidx->service_id; +} + +static void idx_remove_callback(ht_link_t *item) +{ + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link); free(fidx); @@ -236,5 +201,5 @@ .hash = idx_hash, .key_hash = idx_key_hash, - .match = idx_match, + .key_equal = idx_key_equal, .equal = 0, .remove_callback = idx_remove_callback, @@ -378,6 +343,4 @@ } - link_initialize(&fidx->uph_link); - link_initialize(&fidx->uih_link); fibril_mutex_initialize(&fidx->lock); fidx->service_id = service_id; @@ -414,15 +377,15 @@ { fat_idx_t *fidx; - link_t *l; - unsigned long pkey[] = { - [UPH_SID_KEY] = service_id, - [UPH_PFC_KEY] = pfc, - [UPH_PDI_KEY] = pdi, + + pos_key_t pos_key = { + .service_id = service_id, + .pfc = pfc, + .pdi = pdi, }; fibril_mutex_lock(&used_lock); - l = hash_table_find(&up_hash, pkey); + ht_link_t *l = hash_table_find(&up_hash, &pos_key); if (l) { - fidx = hash_table_get_instance(l, fat_idx_t, uph_link); + fidx = hash_table_get_inst(l, fat_idx_t, uph_link); } else { int rc; @@ -464,14 +427,14 @@ { fat_idx_t *fidx = NULL; - link_t *l; - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id, - [UIH_INDEX_KEY] = index, + + idx_key_t idx_key = { + .service_id = service_id, + .index = index, }; fibril_mutex_lock(&used_lock); - l = hash_table_find(&ui_hash, ikey); + ht_link_t *l = hash_table_find(&ui_hash, &idx_key); if (l) { - fidx = hash_table_get_instance(l, fat_idx_t, uih_link); + fidx = hash_table_get_inst(l, fat_idx_t, uih_link); fibril_mutex_lock(&fidx->lock); } @@ -487,10 +450,8 @@ void fat_idx_destroy(fat_idx_t *idx) { - unsigned long ikey[] = { - [UIH_SID_KEY] = idx->service_id, - [UIH_INDEX_KEY] = idx->index, + idx_key_t idx_key = { + .service_id = idx->service_id, + .index = idx->index, }; - service_id_t service_id = idx->service_id; - fs_index_t index = idx->index; assert(idx->pfc == FAT_CLST_RES0); @@ -502,8 +463,8 @@ * the index hash only. */ - hash_table_remove(&ui_hash, ikey, 2); + hash_table_remove(&ui_hash, &idx_key); fibril_mutex_unlock(&used_lock); /* Release the VFS index. */ - fat_index_free(service_id, index); + fat_index_free(idx_key.service_id, idx_key.index); /* The index structure itself is freed in idx_remove_callback(). */ } @@ -511,7 +472,7 @@ int fat_idx_init(void) { - if (!hash_table_create(&up_hash, 0, 3, &uph_ops)) + if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) return ENOMEM; - if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) { + if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) { hash_table_destroy(&up_hash); return ENOMEM; @@ -523,4 +484,5 @@ { /* We assume the hash tables are empty. */ + assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash)); hash_table_destroy(&up_hash); hash_table_destroy(&ui_hash); @@ -547,13 +509,30 @@ } +static bool rm_pos_service_id(ht_link_t *item, void *arg) +{ + service_id_t service_id = *(service_id_t*)arg; + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link); + + if (fidx->service_id == service_id) { + hash_table_remove_item(&up_hash, item); + } + + return true; +} + +static bool rm_idx_service_id(ht_link_t *item, void *arg) +{ + service_id_t service_id = *(service_id_t*)arg; + fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link); + + if (fidx->service_id == service_id) { + hash_table_remove_item(&ui_hash, item); + } + + return true; +} + void fat_idx_fini_by_service_id(service_id_t service_id) { - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id - }; - unsigned long pkey[] = { - [UPH_SID_KEY] = service_id - }; - /* * Remove this instance's index structure from up_hash and ui_hash. @@ -562,6 +541,6 @@ */ fibril_mutex_lock(&used_lock); - hash_table_remove(&up_hash, pkey, 1); - hash_table_remove(&ui_hash, ikey, 1); + hash_table_apply(&up_hash, rm_pos_service_id, &service_id); + hash_table_apply(&ui_hash, rm_idx_service_id, &service_id); fibril_mutex_unlock(&used_lock); Index: uspace/srv/fs/locfs/locfs_ops.c =================================================================== --- uspace/srv/fs/locfs/locfs_ops.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/locfs/locfs_ops.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -61,5 +61,5 @@ async_sess_t *sess; /**< If NULL, the structure is incomplete. */ size_t refcount; - link_t link; + ht_link_t link; fibril_condvar_t cv; /**< Broadcast when completed. */ } service_t; @@ -71,34 +71,26 @@ static FIBRIL_MUTEX_INITIALIZE(services_mutex); -#define SERVICES_KEYS 1 -#define SERVICES_KEY_HANDLE 0 - /* Implementation of hash table interface for the nodes hash table. */ -static size_t services_key_hash(unsigned long key[]) -{ - return key[SERVICES_KEY_HANDLE]; -} - -static size_t services_hash(const link_t *item) -{ - service_t *dev = hash_table_get_instance(item, service_t, link); - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = dev->service_id - }; - - return services_key_hash(key); -} - -static bool services_match(unsigned long key[], size_t keys, const link_t *item) -{ - assert(keys == 1); - service_t *dev = hash_table_get_instance(item, service_t, link); - return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]); -} - -static void services_remove_callback(link_t *item) -{ - free(hash_table_get_instance(item, service_t, link)); +static size_t services_key_hash(void *key) +{ + return *(service_id_t*)key; +} + +static size_t services_hash(const ht_link_t *item) +{ + service_t *dev = hash_table_get_inst(item, service_t, link); + return dev->service_id; +} + +static bool services_key_equal(void *key, const ht_link_t *item) +{ + service_t *dev = hash_table_get_inst(item, service_t, link); + return (dev->service_id == *(service_id_t*)key); +} + +static void services_remove_callback(ht_link_t *item) +{ + free(hash_table_get_inst(item, service_t, link)); } @@ -106,5 +98,5 @@ .hash = services_hash, .key_hash = services_key_hash, - .match = services_match, + .key_equal = services_key_equal, .equal = 0, .remove_callback = services_remove_callback @@ -242,12 +234,8 @@ /* Device node */ - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = (unsigned long) node->service_id - }; - link_t *lnk; - fibril_mutex_lock(&services_mutex); + ht_link_t *lnk; restart: - lnk = hash_table_find(&services, key); + lnk = hash_table_find(&services, &node->service_id); if (lnk == NULL) { service_t *dev = (service_t *) malloc(sizeof(service_t)); @@ -292,5 +280,5 @@ * entry and free the device structure. */ - hash_table_remove(&services, key, SERVICES_KEYS); + hash_table_remove(&services, &node->service_id); fibril_mutex_unlock(&services_mutex); @@ -301,5 +289,5 @@ dev->sess = sess; } else { - service_t *dev = hash_table_get_instance(lnk, service_t, link); + service_t *dev = hash_table_get_inst(lnk, service_t, link); if (!dev->sess) { @@ -463,5 +451,5 @@ bool locfs_init(void) { - if (!hash_table_create(&services, 0, SERVICES_KEYS, &services_ops)) + if (!hash_table_create(&services, 0, 0, &services_ops)) return false; @@ -567,10 +555,6 @@ /* Device node */ - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = (unsigned long) index - }; - fibril_mutex_lock(&services_mutex); - link_t *lnk = hash_table_find(&services, key); + ht_link_t *lnk = hash_table_find(&services, &index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -578,5 +562,5 @@ } - service_t *dev = hash_table_get_instance(lnk, service_t, link); + service_t *dev = hash_table_get_inst(lnk, service_t, link); assert(dev->sess); @@ -633,10 +617,7 @@ if (type == LOC_OBJECT_SERVICE) { /* Device node */ - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = (unsigned long) index - }; fibril_mutex_lock(&services_mutex); - link_t *lnk = hash_table_find(&services, key); + ht_link_t *lnk = hash_table_find(&services, &index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -644,5 +625,5 @@ } - service_t *dev = hash_table_get_instance(lnk, service_t, link); + service_t *dev = hash_table_get_inst(lnk, service_t, link); assert(dev->sess); @@ -703,10 +684,7 @@ if (type == LOC_OBJECT_SERVICE) { - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = (unsigned long) index - }; fibril_mutex_lock(&services_mutex); - link_t *lnk = hash_table_find(&services, key); + ht_link_t *lnk = hash_table_find(&services, &index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -714,5 +692,5 @@ } - service_t *dev = hash_table_get_instance(lnk, service_t, link); + service_t *dev = hash_table_get_inst(lnk, service_t, link); assert(dev->sess); dev->refcount--; @@ -720,5 +698,5 @@ if (dev->refcount == 0) { async_hangup(dev->sess); - hash_table_remove(&services, key, SERVICES_KEYS); + hash_table_remove(&services, &index); } @@ -744,10 +722,7 @@ if (type == LOC_OBJECT_SERVICE) { - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = (unsigned long) index - }; - + fibril_mutex_lock(&services_mutex); - link_t *lnk = hash_table_find(&services, key); + ht_link_t *lnk = hash_table_find(&services, &index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -755,5 +730,5 @@ } - service_t *dev = hash_table_get_instance(lnk, service_t, link); + service_t *dev = hash_table_get_inst(lnk, service_t, link); assert(dev->sess); Index: uspace/srv/fs/mfs/mfs.h =================================================================== --- uspace/srv/fs/mfs/mfs.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/mfs/mfs.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -142,5 +142,5 @@ unsigned refcnt; fs_node_t *fsnode; - link_t link; + ht_link_t link; }; Index: uspace/srv/fs/mfs/mfs_ops.c =================================================================== --- uspace/srv/fs/mfs/mfs_ops.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/mfs/mfs_ops.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -35,9 +35,7 @@ #include #include +#include #include "mfs.h" -#define OPEN_NODES_KEYS 2 -#define OPEN_NODES_SERVICE_KEY 0 -#define OPEN_NODES_INODE_KEY 1 static bool check_magic_number(uint16_t magic, bool *native, @@ -60,8 +58,4 @@ static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name); static int mfs_destroy_node(fs_node_t *fn); -static size_t open_nodes_hash(const link_t *item); -static size_t open_nodes_key_hash(unsigned long key[]); -static bool open_nodes_match(unsigned long key[], size_t keys, - const link_t *item); static int mfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index); @@ -95,44 +89,37 @@ /* Hash table interface for open nodes hash table */ +typedef struct { + service_id_t service_id; + fs_index_t index; +} node_key_t; + static size_t -open_nodes_key_hash(unsigned long key[]) -{ - /* As recommended by Effective Java, 2nd Edition. */ - size_t hash = 17; - hash = 37 * hash + key[OPEN_NODES_SERVICE_KEY]; - hash = 37 * hash + key[OPEN_NODES_INODE_KEY]; - return hash; +open_nodes_key_hash(void *key) +{ + node_key_t *node_key = (node_key_t*)key; + return hash_combine(node_key->service_id, node_key->index); } static size_t -open_nodes_hash(const link_t *item) -{ - struct mfs_node *m = hash_table_get_instance(item, struct mfs_node, link); - - unsigned long key[] = { - [OPEN_NODES_SERVICE_KEY] = m->instance->service_id, - [OPEN_NODES_INODE_KEY] = m->ino_i->index, - }; - - return open_nodes_key_hash(key); +open_nodes_hash(const ht_link_t *item) +{ + struct mfs_node *m = hash_table_get_inst(item, struct mfs_node, link); + return hash_combine(m->instance->service_id, m->ino_i->index); } static bool -open_nodes_match(unsigned long key[], size_t keys, const link_t *item) -{ - assert(keys == 2); - struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link); - - service_id_t service_id = ((service_id_t) key[OPEN_NODES_SERVICE_KEY]); - - return mnode->instance->service_id == service_id - && mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]; -} - +open_nodes_key_equal(void *key, const ht_link_t *item) +{ + node_key_t *node_key = (node_key_t*)key; + struct mfs_node *mnode = hash_table_get_inst(item, struct mfs_node, link); + + return node_key->service_id == mnode->instance->service_id + && node_key->index == mnode->ino_i->index; +} static hash_table_ops_t open_nodes_ops = { .hash = open_nodes_hash, .key_hash = open_nodes_key_hash, - .match = open_nodes_match, + .key_equal = open_nodes_key_equal, .equal = 0, .remove_callback = 0, @@ -142,5 +129,5 @@ mfs_global_init(void) { - if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) { + if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) { return ENOMEM; } @@ -413,6 +400,4 @@ mnode->refcnt = 1; - link_initialize(&mnode->link); - fibril_mutex_lock(&open_nodes_lock); hash_table_insert(&open_nodes, &mnode->link); @@ -515,9 +500,5 @@ mnode->refcnt--; if (mnode->refcnt == 0) { - unsigned long key[] = { - [OPEN_NODES_SERVICE_KEY] = mnode->instance->service_id, - [OPEN_NODES_INODE_KEY] = mnode->ino_i->index - }; - hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS); + hash_table_remove_item(&open_nodes, &mnode->link); assert(mnode->instance->open_nodes_cnt > 0); mnode->instance->open_nodes_cnt--; @@ -578,12 +559,13 @@ /* Check if the node is not already open */ - unsigned long key[] = { - [OPEN_NODES_SERVICE_KEY] = inst->service_id, - [OPEN_NODES_INODE_KEY] = index, + node_key_t key = { + .service_id = inst->service_id, + .index = index }; - link_t *already_open = hash_table_find(&open_nodes, key); + + ht_link_t *already_open = hash_table_find(&open_nodes, &key); if (already_open) { - mnode = hash_table_get_instance(already_open, struct mfs_node, link); + mnode = hash_table_get_inst(already_open, struct mfs_node, link); *rfn = mnode->fsnode; mnode->refcnt++; @@ -616,5 +598,4 @@ mnode->ino_i = ino_i; mnode->refcnt = 1; - link_initialize(&mnode->link); mnode->instance = inst; Index: uspace/srv/fs/tmpfs/tmpfs.h =================================================================== --- uspace/srv/fs/tmpfs/tmpfs.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/tmpfs/tmpfs.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -62,5 +62,5 @@ fs_index_t index; /**< TMPFS node index. */ service_id_t service_id;/**< Service ID of block device. */ - link_t nh_link; /**< Nodes hash table link. */ + ht_link_t nh_link; /**< Nodes hash table link. */ tmpfs_dentry_type_t type; unsigned lnkcnt; /**< Link count. */ Index: uspace/srv/fs/tmpfs/tmpfs_ops.c =================================================================== --- uspace/srv/fs/tmpfs/tmpfs_ops.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/fs/tmpfs/tmpfs_ops.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -50,4 +50,5 @@ #include #include +#include #include #include @@ -140,51 +141,36 @@ hash_table_t nodes; -#define NODES_KEY_DEV 0 -#define NODES_KEY_INDEX 1 - -/* Implementation of hash table interface for the nodes hash table. */ -static size_t nodes_key_hash(unsigned long key[]) -{ - /* Based on Effective Java, 2nd Edition. */ - size_t hash = 17; - hash = 37 * hash + key[NODES_KEY_DEV]; - hash = 37 * hash + key[NODES_KEY_INDEX]; - return hash; -} - -static size_t nodes_hash(const link_t *item) -{ - tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, nh_link); - - unsigned long key[] = { - [NODES_KEY_DEV] = nodep->service_id, - [NODES_KEY_INDEX] = nodep->index - }; - - return nodes_key_hash(key); -} - -static bool nodes_match(unsigned long key[], size_t keys, const link_t *item) -{ - tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, - nh_link); - - switch (keys) { - case 1: - return (nodep->service_id == key[NODES_KEY_DEV]); - case 2: - return ((nodep->service_id == key[NODES_KEY_DEV]) && - (nodep->index == key[NODES_KEY_INDEX])); - default: - assert((keys == 1) || (keys == 2)); - } - - return 0; -} - -static void nodes_remove_callback(link_t *item) -{ - tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, - nh_link); +/* + * Implementation of hash table interface for the nodes hash table. + */ + +typedef struct { + service_id_t service_id; + fs_index_t index; +} node_key_t; + +static size_t nodes_key_hash(void *k) +{ + node_key_t *key = (node_key_t *)k; + return hash_combine(key->service_id, key->index); +} + +static size_t nodes_hash(const ht_link_t *item) +{ + tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link); + return hash_combine(nodep->service_id, nodep->index); +} + +static bool nodes_key_equal(void *key_arg, const ht_link_t *item) +{ + tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link); + node_key_t *key = (node_key_t *)key_arg; + + return key->service_id == node->service_id && key->index == node->index; +} + +static void nodes_remove_callback(ht_link_t *item) +{ + tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link); while (!list_empty(&nodep->cs_list)) { @@ -209,5 +195,5 @@ .hash = nodes_hash, .key_hash = nodes_key_hash, - .match = nodes_match, + .key_equal = nodes_key_equal, .equal = 0, .remove_callback = nodes_remove_callback @@ -223,5 +209,4 @@ nodep->size = 0; nodep->data = NULL; - link_initialize(&nodep->nh_link); list_initialize(&nodep->cs_list); } @@ -236,5 +221,5 @@ bool tmpfs_init(void) { - if (!hash_table_create(&nodes, 0, 2, &nodes_ops)) + if (!hash_table_create(&nodes, 0, 0, &nodes_ops)) return false; @@ -254,17 +239,18 @@ } +static bool rm_service_id_nodes(ht_link_t *item, void *arg) +{ + service_id_t sid = *(service_id_t*)arg; + tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link); + + if (node->service_id == sid) { + hash_table_remove_item(&nodes, &node->nh_link); + } + return true; +} + static void tmpfs_instance_done(service_id_t service_id) -{ - unsigned long key[] = { - [NODES_KEY_DEV] = service_id - }; - /* - * Here we are making use of one special feature of our hash table - * implementation, which allows to remove more items based on a partial - * key match. In the following, we are going to remove all nodes - * matching our device handle. The nodes_remove_callback() function will - * take care of resource deallocation. - */ - hash_table_remove(&nodes, key, 1); +{ + hash_table_apply(&nodes, rm_service_id_nodes, &service_id); } @@ -288,12 +274,14 @@ int tmpfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index) { - unsigned long key[] = { - [NODES_KEY_DEV] = service_id, - [NODES_KEY_INDEX] = index + node_key_t key = { + .service_id = service_id, + .index = index }; - link_t *lnk = hash_table_find(&nodes, key); + + ht_link_t *lnk = hash_table_find(&nodes, &key); + if (lnk) { tmpfs_node_t *nodep; - nodep = hash_table_get_instance(lnk, tmpfs_node_t, nh_link); + nodep = hash_table_get_inst(lnk, tmpfs_node_t, nh_link); *rfn = FS_NODE(nodep); } else { @@ -358,10 +346,6 @@ assert(!nodep->lnkcnt); assert(list_empty(&nodep->cs_list)); - - unsigned long key[] = { - [NODES_KEY_DEV] = nodep->service_id, - [NODES_KEY_INDEX] = nodep->index - }; - hash_table_remove(&nodes, key, 2); + + hash_table_remove_item(&nodes, &nodep->nh_link); /* @@ -488,14 +472,14 @@ * Lookup the respective TMPFS node. */ - link_t *hlp; - unsigned long key[] = { - [NODES_KEY_DEV] = service_id, - [NODES_KEY_INDEX] = index + node_key_t key = { + .service_id = service_id, + .index = index }; - hlp = hash_table_find(&nodes, key); + + ht_link_t *hlp = hash_table_find(&nodes, &key); if (!hlp) return ENOENT; - tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, - nh_link); + + tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link); /* @@ -550,14 +534,15 @@ * Lookup the respective TMPFS node. */ - link_t *hlp; - unsigned long key[] = { - [NODES_KEY_DEV] = service_id, - [NODES_KEY_INDEX] = index + node_key_t key = { + .service_id = service_id, + .index = index }; - hlp = hash_table_find(&nodes, key); + + ht_link_t *hlp = hash_table_find(&nodes, &key); + if (!hlp) return ENOENT; - tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, - nh_link); + + tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link); /* @@ -612,12 +597,14 @@ * Lookup the respective TMPFS node. */ - unsigned long key[] = { - [NODES_KEY_DEV] = service_id, - [NODES_KEY_INDEX] = index + node_key_t key = { + .service_id = service_id, + .index = index }; - link_t *hlp = hash_table_find(&nodes, key); + + ht_link_t *hlp = hash_table_find(&nodes, &key); + if (!hlp) return ENOENT; - tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, nh_link); + tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link); if (size == nodep->size) @@ -648,13 +635,13 @@ static int tmpfs_destroy(service_id_t service_id, fs_index_t index) { - link_t *hlp; - unsigned long key[] = { - [NODES_KEY_DEV] = service_id, - [NODES_KEY_INDEX] = index + node_key_t key = { + .service_id = service_id, + .index = index }; - hlp = hash_table_find(&nodes, key); + + ht_link_t *hlp = hash_table_find(&nodes, &key); if (!hlp) return ENOENT; - tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, + tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link); return tmpfs_destroy_node(FS_NODE(nodep)); Index: uspace/srv/hid/input/generic/gsp.c =================================================================== --- uspace/srv/hid/input/generic/gsp.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/hid/input/generic/gsp.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -51,23 +51,45 @@ #include #include +#include #include #include /* - * Hash table operations for the transition function. - */ - -static size_t trans_op_hash(const link_t *item); -static size_t trans_op_key_hash(unsigned long key[]); -static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item); + * Transition function hash table operations. + */ +typedef struct { + int old_state; + int input; +} trans_key_t; + +static size_t trans_key_hash(void *key) +{ + trans_key_t *trans_key = (trans_key_t *)key; + return hash_combine(trans_key->input, trans_key->old_state); +} + +static size_t trans_hash(const ht_link_t *item) +{ + gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link); + return hash_combine(t->input, t->old_state); +} + +static bool trans_key_equal(void *key, const ht_link_t *item) +{ + trans_key_t *trans_key = (trans_key_t *)key; + gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link); + + return trans_key->input == t->input && trans_key->old_state == t->old_state; +} static hash_table_ops_t trans_ops = { - .hash = trans_op_hash, - .key_hash = trans_op_key_hash, - .match = trans_op_match, + .hash = trans_hash, + .key_hash = trans_key_hash, + .key_equal = trans_key_equal, .equal = 0, .remove_callback = 0 }; + static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input); static void trans_insert(gsp_t *p, gsp_trans_t *t); @@ -78,5 +100,5 @@ { p->states = 1; - hash_table_create(&p->trans, 0, 2, &trans_ops); + hash_table_create(&p->trans, 0, 0, &trans_ops); } @@ -222,14 +244,15 @@ static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input) { - link_t *item; - unsigned long key[2]; - - key[0] = state; - key[1] = input; - - item = hash_table_find(&p->trans, key); + ht_link_t *item; + + trans_key_t key = { + .input = input, + .old_state = state + }; + + item = hash_table_find(&p->trans, &key); if (item == NULL) return NULL; - return hash_table_get_instance(item, gsp_trans_t, link); + return hash_table_get_inst(item, gsp_trans_t, link); } @@ -258,30 +281,4 @@ } -/* - * Transition function hash table operations. - */ - -static size_t trans_op_key_hash(unsigned long key[]) -{ - return (key[0] * 17 + key[1]); -} - -static size_t trans_op_hash(const link_t *item) -{ - gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link); - unsigned long key[] = { - t->old_state, - t->input - }; - - return trans_op_key_hash(key); -} - -static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item) -{ - gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link); - return ((key[0] == (unsigned long) t->old_state) - && (key[1] == (unsigned long) t->input)); -} /** Index: uspace/srv/hid/input/include/gsp.h =================================================================== --- uspace/srv/hid/input/include/gsp.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/hid/input/include/gsp.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -56,5 +56,5 @@ /** Scancode parser transition. */ typedef struct { - link_t link; /**< Link to hash table in @c gsp_t */ + ht_link_t link; /**< Link to hash table in @c gsp_t */ /* Preconditions */ Index: uspace/srv/ns/service.c =================================================================== --- uspace/srv/ns/service.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/ns/service.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -43,5 +43,5 @@ /** Service hash table item. */ typedef struct { - link_t link; + ht_link_t link; sysarg_t service; /**< Service ID. */ sysarg_t phone; /**< Phone registered with the service. */ @@ -49,63 +49,20 @@ } hashed_service_t; -/** Compute hash index into service hash table. - * - * @param key Pointer keys. However, only the first key (i.e. service number) - * is used to compute the hash index. - * - * @return Hash index corresponding to key[0]. - * - */ -static size_t service_key_hash(unsigned long key[]) + +static size_t service_key_hash(void *key) { - assert(key); - return key[0]; + return *(sysarg_t*)key; } -static size_t service_hash(const link_t *item) +static size_t service_hash(const ht_link_t *item) { - hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link); - unsigned long key = hs->service; - return service_key_hash(&key); + hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link); + return hs->service; } -/** Compare a key with hashed item. - * - * This compare function always ignores the third key. - * It exists only to make it possible to remove records - * originating from connection with key[1] in_phone_hash - * value. Note that this is close to being classified - * as a nasty hack. - * - * @param key Array of keys. - * @param keys Must be lesser or equal to 3. - * @param item Pointer to a hash table item. - * - * @return Non-zero if the key matches the item, zero otherwise. - * - */ -static bool service_match(unsigned long key[], size_t keys, const link_t *item) +static bool service_key_equal(void *key, const ht_link_t *item) { - assert(key); - assert(keys <= 3); - assert(item); - - hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link); - - if (keys == 2) - return ((key[0] == hs->service) && (key[1] == hs->in_phone_hash)); - else - return (key[0] == hs->service); -} - -/** Perform actions after removal of item from the hash table. - * - * @param item Item that was removed from the hash table. - * - */ -static void service_remove(link_t *item) -{ - assert(item); - free(hash_table_get_instance(item, hashed_service_t, link)); + hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link); + return hs->service == *(sysarg_t*)key; } @@ -114,7 +71,7 @@ .hash = service_hash, .key_hash = service_key_hash, - .match = service_match, + .key_equal = service_key_equal, .equal = 0, - .remove_callback = service_remove + .remove_callback = 0 }; @@ -135,5 +92,5 @@ int service_init(void) { - if (!hash_table_create(&service_hash_table, 0, 3, &service_hash_table_ops)) { + if (!hash_table_create(&service_hash_table, 0, 0, &service_hash_table_ops)) { printf(NAME ": No memory available for services\n"); return ENOMEM; @@ -152,15 +109,9 @@ pending_conn_t *pr = list_get_instance(cur, pending_conn_t, link); - unsigned long keys[3] = { - pr->service, - 0, - 0 - }; - - link_t *link = hash_table_find(&service_hash_table, keys); + ht_link_t *link = hash_table_find(&service_hash_table, &pr->service); if (!link) continue; - hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link); + hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link); (void) ipc_forward_fast(pr->callid, hs->phone, pr->arg2, pr->arg3, 0, IPC_FF_NONE); @@ -183,11 +134,5 @@ int register_service(sysarg_t service, sysarg_t phone, ipc_call_t *call) { - unsigned long keys[3] = { - service, - call->in_phone_hash, - 0 - }; - - if (hash_table_find(&service_hash_table, keys)) + if (hash_table_find(&service_hash_table, &service)) return EEXISTS; @@ -196,5 +141,4 @@ return ENOMEM; - link_initialize(&hs->link); hs->service = service; hs->phone = phone; @@ -217,11 +161,6 @@ { sysarg_t retval; - unsigned long keys[3] = { - service, - 0, - 0 - }; - link_t *link = hash_table_find(&service_hash_table, keys); + ht_link_t *link = hash_table_find(&service_hash_table, &service); if (!link) { if (IPC_GET_ARG4(*call) & IPC_FLAG_BLOCKING) { @@ -246,5 +185,5 @@ } - hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link); + hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link); (void) ipc_forward_fast(callid, hs->phone, IPC_GET_ARG2(*call), IPC_GET_ARG3(*call), 0, IPC_FF_NONE); Index: uspace/srv/ns/task.c =================================================================== --- uspace/srv/ns/task.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/ns/task.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -53,5 +53,5 @@ /** Task hash table item. */ typedef struct { - link_t link; + ht_link_t link; task_id_t id; /**< Task ID. */ @@ -61,62 +61,26 @@ } hashed_task_t; -/** Compute hash index into task hash table. - * - * @param key Pointer keys. However, only the first key (i.e. truncated task - * number) is used to compute the hash index. - * - * @return Hash index corresponding to key[0]. - * - */ -static size_t task_key_hash(unsigned long key[]) -{ - size_t hash = 17; - hash = 37 * hash + key[1]; - hash = 37 * hash + key[0]; - return hash; -} - -static size_t task_hash(const link_t *item) -{ - hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link); - - unsigned long key[] = { - LOWER32(ht->id), - UPPER32(ht->id) - }; - - return task_key_hash(key); -} - -/** Compare a key with hashed item. - * - * @param key Array of keys. - * @param keys Must be less than or equal to 2. - * @param item Pointer to a hash table item. - * - * @return Non-zero if the key matches the item, zero otherwise. - * - */ -static bool task_match(unsigned long key[], size_t keys, const link_t *item) -{ - assert(key); - assert(keys == 2); - assert(item); - - hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link); - - return (key[0] == LOWER32(ht->id)) - && (key[1] == UPPER32(ht->id)); -} - -/** Perform actions after removal of item from the hash table. - * - * @param item Item that was removed from the hash table. - * - */ -static void task_remove(link_t *item) -{ - assert(item); - free(hash_table_get_instance(item, hashed_task_t, link)); + +static size_t task_key_hash(void *key) +{ + return *(task_id_t*)key; +} + +static size_t task_hash(const ht_link_t *item) +{ + hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link); + return ht->id; +} + +static bool task_key_equal(void *key, const ht_link_t *item) +{ + hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link); + return ht->id == *(task_id_t*)key; +} + +/** Perform actions after removal of item from the hash table. */ +static void task_remove(ht_link_t *item) +{ + free(hash_table_get_inst(item, hashed_task_t, link)); } @@ -125,5 +89,5 @@ .hash = task_hash, .key_hash = task_key_hash, - .match = task_match, + .key_equal = task_key_equal, .equal = 0, .remove_callback = task_remove @@ -134,58 +98,40 @@ typedef struct { - link_t link; + ht_link_t link; sysarg_t in_phone_hash; /**< Incoming phone hash. */ task_id_t id; /**< Task ID. */ } p2i_entry_t; -/** Compute hash index into task hash table. - * - * @param key Array of keys. - * - * @return Hash index corresponding to key[0]. - * - */ -static size_t p2i_key_hash(unsigned long key[]) -{ - assert(key); - return key[0]; -} - -static size_t p2i_hash(const link_t *item) -{ - p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link); - unsigned long key = entry->in_phone_hash; - return p2i_key_hash(&key); -} - -/** Compare a key with hashed item. - * - * @param key Array of keys. - * @param keys Must be less than or equal to 1. - * @param item Pointer to a hash table item. - * - * @return Non-zero if the key matches the item, zero otherwise. - * - */ -static bool p2i_match(unsigned long key[], size_t keys, const link_t *item) -{ - assert(key); - assert(keys == 1); +/* phone-to-id hash table operations */ + +static size_t p2i_key_hash(void *key) +{ + sysarg_t in_phone_hash = *(sysarg_t*)key; + return in_phone_hash; +} + +static size_t p2i_hash(const ht_link_t *item) +{ + p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link); + return entry->in_phone_hash; +} + +static bool p2i_key_equal(void *key, const ht_link_t *item) +{ + sysarg_t in_phone_hash = *(sysarg_t*)key; + p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link); + + return (in_phone_hash == entry->in_phone_hash); +} + +/** Perform actions after removal of item from the hash table. + * + * @param item Item that was removed from the hash table. + * + */ +static void p2i_remove(ht_link_t *item) +{ assert(item); - - p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link); - - return (key[0] == entry->in_phone_hash); -} - -/** Perform actions after removal of item from the hash table. - * - * @param item Item that was removed from the hash table. - * - */ -static void p2i_remove(link_t *item) -{ - assert(item); - free(hash_table_get_instance(item, p2i_entry_t, link)); + free(hash_table_get_inst(item, p2i_entry_t, link)); } @@ -194,5 +140,5 @@ .hash = p2i_hash, .key_hash = p2i_key_hash, - .match = p2i_match, + .key_equal = p2i_key_equal, .equal = 0, .remove_callback = p2i_remove @@ -213,10 +159,10 @@ int task_init(void) { - if (!hash_table_create(&task_hash_table, 0, 2, &task_hash_table_ops)) { + if (!hash_table_create(&task_hash_table, 0, 0, &task_hash_table_ops)) { printf(NAME ": No memory available for tasks\n"); return ENOMEM; } - if (!hash_table_create(&phone_to_id, 0, 1, &p2i_ops)) { + if (!hash_table_create(&phone_to_id, 0, 0, &p2i_ops)) { printf(NAME ": No memory available for tasks\n"); return ENOMEM; @@ -236,14 +182,9 @@ pending_wait_t *pr = list_get_instance(cur, pending_wait_t, link); - unsigned long keys[2] = { - LOWER32(pr->id), - UPPER32(pr->id) - }; - - link_t *link = hash_table_find(&task_hash_table, keys); + ht_link_t *link = hash_table_find(&task_hash_table, &pr->id); if (!link) continue; - hashed_task_t *ht = hash_table_get_instance(link, hashed_task_t, link); + hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link); if (!ht->finished) continue; @@ -256,5 +197,5 @@ } - hash_table_remove(&task_hash_table, keys, 2); + hash_table_remove(&task_hash_table, &pr->id); list_remove(cur); free(pr); @@ -268,12 +209,7 @@ task_exit_t texit; - unsigned long keys[2] = { - LOWER32(id), - UPPER32(id) - }; - - link_t *link = hash_table_find(&task_hash_table, keys); + ht_link_t *link = hash_table_find(&task_hash_table, &id); hashed_task_t *ht = (link != NULL) ? - hash_table_get_instance(link, hashed_task_t, link) : NULL; + hash_table_get_inst(link, hashed_task_t, link) : NULL; if (ht == NULL) { @@ -299,5 +235,5 @@ } - hash_table_remove(&task_hash_table, keys, 2); + hash_table_remove_item(&task_hash_table, link); retval = EOK; @@ -314,7 +250,5 @@ task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call)); - unsigned long keys[] = { call->in_phone_hash }; - - link_t *link = hash_table_find(&phone_to_id, keys); + ht_link_t *link = hash_table_find(&phone_to_id, &call->in_phone_hash); if (link != NULL) return EEXISTS; @@ -332,5 +266,4 @@ */ - link_initialize(&entry->link); entry->in_phone_hash = call->in_phone_hash; entry->id = id; @@ -341,5 +274,4 @@ */ - link_initialize(&ht->link); ht->id = id; ht->finished = false; @@ -353,11 +285,9 @@ static int get_id_by_phone(sysarg_t phone_hash, task_id_t *id) { - unsigned long keys[1] = {phone_hash}; - - link_t *link = hash_table_find(&phone_to_id, keys); + ht_link_t *link = hash_table_find(&phone_to_id, &phone_hash); if (link == NULL) return ENOENT; - p2i_entry_t *entry = hash_table_get_instance(link, p2i_entry_t, link); + p2i_entry_t *entry = hash_table_get_inst(link, p2i_entry_t, link); *id = entry->id; @@ -372,12 +302,7 @@ return rc; - unsigned long keys[2] = { - LOWER32(id), - UPPER32(id) - }; - - link_t *link = hash_table_find(&task_hash_table, keys); + ht_link_t *link = hash_table_find(&task_hash_table, &id); hashed_task_t *ht = (link != NULL) ? - hash_table_get_instance(link, hashed_task_t, link) : NULL; + hash_table_get_inst(link, hashed_task_t, link) : NULL; if ((ht == NULL) || (ht->finished)) @@ -393,6 +318,4 @@ int ns_task_disconnect(ipc_call_t *call) { - unsigned long keys[2]; - task_id_t id; int rc = get_id_by_phone(call->in_phone_hash, &id); @@ -401,17 +324,12 @@ /* Delete from phone-to-id map. */ - keys[0] = call->in_phone_hash; - hash_table_remove(&phone_to_id, keys, 1); + hash_table_remove(&phone_to_id, &call->in_phone_hash); /* Mark task as finished. */ - keys[0] = LOWER32(id); - keys[1] = UPPER32(id); - - link_t *link = hash_table_find(&task_hash_table, keys); + ht_link_t *link = hash_table_find(&task_hash_table, &id); if (link == NULL) return EOK; - hashed_task_t *ht = - hash_table_get_instance(link, hashed_task_t, link); + hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link); ht->finished = true; Index: uspace/srv/vfs/vfs.h =================================================================== --- uspace/srv/vfs/vfs.h (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/vfs/vfs.h (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -36,4 +36,5 @@ #include #include +#include #include #include @@ -112,5 +113,5 @@ unsigned lnkcnt; - link_t nh_link; /**< Node hash-table link. */ + ht_link_t nh_link; /**< Node hash-table link. */ vfs_node_type_t type; /**< Partial info about the node type. */ Index: uspace/srv/vfs/vfs_node.c =================================================================== --- uspace/srv/vfs/vfs_node.c (revision b17518ef2cd636e9ee2a4593e9e3f96130bd854b) +++ uspace/srv/vfs/vfs_node.c (revision bc216a07a86e40d74455b7f4d6fb8f65e195443d) @@ -41,4 +41,5 @@ #include #include +#include #include #include @@ -58,7 +59,8 @@ #define KEY_INDEX 2 -static size_t nodes_key_hash(unsigned long []); -static size_t nodes_hash(const link_t *); -static bool nodes_match(unsigned long [], size_t, const link_t *); +static size_t nodes_key_hash(void *); +static size_t nodes_hash(const ht_link_t *); +static bool nodes_key_equal(void *, const ht_link_t *); +static vfs_triplet_t node_triplet(vfs_node_t *node); /** VFS node hash table operations. */ @@ -66,5 +68,5 @@ .hash = nodes_hash, .key_hash = nodes_key_hash, - .match = nodes_match, + .key_equal = nodes_key_equal, .equal = 0, .remove_callback = 0, @@ -77,5 +79,5 @@ bool vfs_nodes_init(void) { - return hash_table_create(&nodes, 0, 3, &nodes_ops); + return hash_table_create(&nodes, 0, 0, &nodes_ops); } @@ -116,11 +118,5 @@ */ - unsigned long key[] = { - [KEY_FS_HANDLE] = node->fs_handle, - [KEY_DEV_HANDLE] = node->service_id, - [KEY_INDEX] = node->index - }; - - hash_table_remove(&nodes, key, 3); + hash_table_remove_item(&nodes, &node->nh_link); free_vfs_node = true; @@ -160,10 +156,5 @@ { fibril_mutex_lock(&nodes_mutex); - unsigned long key[] = { - [KEY_FS_HANDLE] = node->fs_handle, - [KEY_DEV_HANDLE] = node->service_id, - [KEY_INDEX] = node->index - }; - hash_table_remove(&nodes, key, 3); + hash_table_remove_item(&nodes, &node->nh_link); fibril_mutex_unlock(&nodes_mutex); free(node); @@ -184,14 +175,8 @@ vfs_node_t *vfs_node_get(vfs_lookup_res_t *result) { - unsigned long key[] = { - [KEY_FS_HANDLE] = result->triplet.fs_handle, - [KEY_DEV_HANDLE] = result->triplet.service_id, - [KEY_INDEX] = result->triplet.index - }; - link_t *tmp; vfs_node_t *node; fibril_mutex_lock(&nodes_mutex); - tmp = hash_table_find(&nodes, key); + ht_link_t *tmp = hash_table_find(&nodes, &result->triplet); if (!tmp) { node = (vfs_node_t *) malloc(sizeof(vfs_node_t)); @@ -207,9 +192,8 @@ node->lnkcnt = result->lnkcnt; node->type = result->type; - link_initialize(&node->nh_link); fibril_rwlock_initialize(&node->contents_rwlock); hash_table_insert(&nodes, &node->nh_link); } else { - node = hash_table_get_instance(tmp, vfs_node_t, nh_link); + node = hash_table_get_inst(tmp, vfs_node_t, nh_link); if (node->type == VFS_NODE_UNKNOWN && result->type != VFS_NODE_UNKNOWN) { @@ -242,37 +226,4 @@ } -size_t nodes_key_hash(unsigned long key[]) -{ - /* Combine into a hash like they do in Effective Java, 2nd edition. */ - size_t hash = 17; - hash = 37 * hash + key[KEY_FS_HANDLE]; - hash = 37 * hash + key[KEY_DEV_HANDLE]; - hash = 37 * hash + key[KEY_INDEX]; - return hash; -} - -size_t nodes_hash(const link_t *item) -{ - vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link); - - unsigned long key[] = { - [KEY_FS_HANDLE] = node->fs_handle, - [KEY_DEV_HANDLE] = node->service_id, - [KEY_INDEX] = node->index - }; - - return nodes_key_hash(key); -} - - -bool nodes_match(unsigned long key[], size_t keys, const link_t *item) -{ - vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link); - return (node->fs_handle == (fs_handle_t) key[KEY_FS_HANDLE]) && - (node->service_id == key[KEY_DEV_HANDLE]) && - (node->index == key[KEY_INDEX]); -} - - struct refcnt_data { /** Sum of all reference counts for this file system instance. */ @@ -282,7 +233,7 @@ }; -static bool refcnt_visitor(link_t *item, void *arg) -{ - vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link); +static bool refcnt_visitor(ht_link_t *item, void *arg) +{ + vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link); struct refcnt_data *rd = (void *) arg; @@ -332,4 +283,39 @@ } + +static size_t nodes_key_hash(void *key) +{ + vfs_triplet_t *tri = key; + size_t hash = hash_combine(tri->fs_handle, tri->index); + return hash_combine(hash, tri->service_id); +} + +static size_t nodes_hash(const ht_link_t *item) +{ + vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link); + vfs_triplet_t tri = node_triplet(node); + return nodes_key_hash(&tri); +} + +static bool nodes_key_equal(void *key, const ht_link_t *item) +{ + vfs_triplet_t *tri = key; + vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link); + return node->fs_handle == tri->fs_handle + && node->service_id == tri->service_id + && node->index == tri->index; +} + +static inline vfs_triplet_t node_triplet(vfs_node_t *node) +{ + vfs_triplet_t tri = { + .fs_handle = node->fs_handle, + .service_id = node->service_id, + .index = node->index + }; + + return tri; +} + /** * @}