Index: uspace/app/mkexfat/mkexfat.c =================================================================== --- uspace/app/mkexfat/mkexfat.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/app/mkexfat/mkexfat.c (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/app/trace/ipcp.c (revision 062d9000625057300f609429080872d6492b542e) @@ -38,4 +38,5 @@ #include #include +#include #include "ipc_desc.h" #include "proto.h" @@ -52,5 +53,5 @@ ipc_callid_t call_hash; - link_t link; + ht_link_t link; } pending_call_t; @@ -64,6 +65,5 @@ int have_conn[MAX_PHONE]; -#define PCALL_TABLE_CHAINS 32 -hash_table_t pending_calls; +static hash_table_t pending_calls; /* @@ -73,38 +73,32 @@ proto_t *proto_unknown; /**< Protocol with no known methods. */ -static hash_index_t pending_call_hash(unsigned long key[]); -static int pending_call_compare(unsigned long key[], hash_count_t keys, - link_t *item); -static void pending_call_remove_callback(link_t *item); - -hash_table_operations_t pending_call_ops = { + +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, - .compare = pending_call_compare, - .remove_callback = pending_call_remove_callback + .key_hash = pending_call_key_hash, + .key_equal = pending_call_key_equal, + .equal = 0, + .remove_callback = 0 }; - - -static hash_index_t pending_call_hash(unsigned long key[]) -{ -// printf("pending_call_hash\n"); - return key[0] % PCALL_TABLE_CHAINS; -} - -static int pending_call_compare(unsigned long key[], hash_count_t keys, - link_t *item) -{ - pending_call_t *hs; - -// printf("pending_call_compare\n"); - hs = hash_table_get_instance(item, pending_call_t, link); - - // FIXME: this will fail if sizeof(long) < sizeof(void *). - return key[0] == hs->call_hash; -} - -static void pending_call_remove_callback(link_t *item) -{ -// printf("pending_call_remove_callback\n"); -} @@ -177,5 +171,6 @@ } - hash_table_create(&pending_calls, PCALL_TABLE_CHAINS, 1, &pending_call_ops); + bool ok = hash_table_create(&pending_calls, 0, 0, &pending_call_ops); + assert(ok); } @@ -190,5 +185,4 @@ pending_call_t *pcall; proto_t *proto; - unsigned long key[1]; oper_t *oper; sysarg_t *args; @@ -254,7 +248,5 @@ pcall->oper = oper; - key[0] = hash; - - hash_table_insert(&pending_calls, key, &pcall->link); + hash_table_insert(&pending_calls, &pcall->link); } @@ -334,7 +326,6 @@ void ipcp_call_in(ipc_call_t *call, ipc_callid_t hash) { - link_t *item; + ht_link_t *item; pending_call_t *pcall; - unsigned long key[1]; if ((hash & IPC_CALLID_ANSWERED) == 0 && hash != IPCP_CALLID_SYNC) { @@ -347,7 +338,6 @@ hash = hash & ~IPC_CALLID_ANSWERED; - key[0] = hash; - - item = hash_table_find(&pending_calls, key); + + item = hash_table_find(&pending_calls, &hash); if (item == NULL) return; /* No matching question found */ @@ -357,6 +347,6 @@ */ - pcall = hash_table_get_instance(item, pending_call_t, link); - hash_table_remove(&pending_calls, key, 1); + 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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/app/trace/proto.c (revision 062d9000625057300f609429080872d6492b542e) @@ -40,117 +40,103 @@ #include "proto.h" -#define SRV_PROTO_TABLE_CHAINS 32 -#define METHOD_OPER_TABLE_CHAINS 32 - -hash_table_t srv_proto; + +/* Maps service number to protocol */ +static hash_table_t srv_proto; 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 hash_index_t srv_proto_hash(unsigned long key[]); -static int srv_proto_compare(unsigned long key[], hash_count_t keys, - link_t *item); -static void srv_proto_remove_callback(link_t *item); - -hash_table_operations_t srv_proto_ops = { +/* 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; +} + +static hash_table_ops_t srv_proto_ops = { .hash = srv_proto_hash, - .compare = srv_proto_compare, - .remove_callback = srv_proto_remove_callback + .key_hash = srv_proto_key_hash, + .key_equal = srv_proto_key_equal, + .equal = 0, + .remove_callback = 0 }; -static hash_index_t method_oper_hash(unsigned long key[]); -static int method_oper_compare(unsigned long key[], hash_count_t keys, - link_t *item); -static void method_oper_remove_callback(link_t *item); - -hash_table_operations_t method_oper_ops = { + +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; +} + +static hash_table_ops_t method_oper_ops = { .hash = method_oper_hash, - .compare = method_oper_compare, - .remove_callback = method_oper_remove_callback + .key_hash = method_oper_key_hash, + .key_equal = method_oper_key_equal, + .equal = 0, + .remove_callback = 0 }; -static hash_index_t srv_proto_hash(unsigned long key[]) -{ - return key[0] % SRV_PROTO_TABLE_CHAINS; -} - -static int srv_proto_compare(unsigned long key[], hash_count_t keys, - link_t *item) + +void proto_init(void) +{ + /* todo: check return value. */ + bool ok = hash_table_create(&srv_proto, 0, 0, &srv_proto_ops); + assert(ok); +} + +void proto_cleanup(void) +{ + hash_table_destroy(&srv_proto); +} + +void proto_register(int srv, proto_t *proto) { srv_proto_t *sp; - - sp = hash_table_get_instance(item, srv_proto_t, link); - - return key[0] == sp->srv; -} - -static void srv_proto_remove_callback(link_t *item) -{ -} - -static hash_index_t method_oper_hash(unsigned long key[]) -{ - return key[0] % METHOD_OPER_TABLE_CHAINS; -} - -static int method_oper_compare(unsigned long key[], hash_count_t keys, - link_t *item) -{ - method_oper_t *mo; - - mo = hash_table_get_instance(item, method_oper_t, link); - - return key[0] == mo->method; -} - -static void method_oper_remove_callback(link_t *item) -{ -} - - -void proto_init(void) -{ - hash_table_create(&srv_proto, SRV_PROTO_TABLE_CHAINS, 1, - &srv_proto_ops); -} - -void proto_cleanup(void) -{ - hash_table_destroy(&srv_proto); -} - -void proto_register(int srv, proto_t *proto) -{ - srv_proto_t *sp; - unsigned long key; sp = malloc(sizeof(srv_proto_t)); sp->srv = srv; sp->proto = proto; - key = srv; - - hash_table_insert(&srv_proto, &key, &sp->link); + + hash_table_insert(&srv_proto, &sp->link); } proto_t *proto_get_by_srv(int srv) { - unsigned long key; - link_t *item; - srv_proto_t *sp; - - 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; } @@ -159,6 +145,7 @@ { proto->name = name; - hash_table_create(&proto->method_oper, SRV_PROTO_TABLE_CHAINS, 1, - &method_oper_ops); + /* todo: check return value. */ + bool ok = hash_table_create(&proto->method_oper, 0, 0, &method_oper_ops); + assert(ok); } @@ -181,25 +168,18 @@ { method_oper_t *mo; - unsigned long key; mo = malloc(sizeof(method_oper_t)); mo->method = method; mo->oper = oper; - key = method; - - hash_table_insert(&proto->method_oper, &key, &mo->link); + + hash_table_insert(&proto->method_oper, &mo->link); } 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/app/trace/proto.h =================================================================== --- uspace/app/trace/proto.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/app/trace/proto.h (revision 062d9000625057300f609429080872d6492b542e) @@ -62,6 +62,4 @@ } proto_t; -/* Maps service number to protocol */ -extern hash_table_t srv_proto; extern void proto_init(void); Index: uspace/lib/block/block.c =================================================================== --- uspace/lib/block/block.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/block/block.c (revision 062d9000625057300f609429080872d6492b542e) @@ -62,6 +62,4 @@ static LIST_INITIALIZE(dcl); -#define CACHE_BUCKETS_LOG2 10 -#define CACHE_BUCKETS (1 << CACHE_BUCKETS_LOG2) typedef struct { @@ -233,23 +231,30 @@ } -static hash_index_t cache_hash(unsigned long *key) -{ - return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1); -} - -static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item) -{ - block_t *b = hash_table_get_instance(item, block_t, hash_link); - return b->lba == MERGE_LOUP32(key[0], key[1]); -} - -static void cache_remove_callback(link_t *item) -{ -} - -static hash_table_operations_t cache_ops = { +static size_t cache_key_hash(void *key) +{ + aoff64_t *lba = (aoff64_t*)key; + return *lba; +} + +static size_t cache_hash(const ht_link_t *item) +{ + block_t *b = hash_table_get_inst(item, block_t, hash_link); + return b->lba; +} + +static bool cache_key_equal(void *key, const ht_link_t *item) +{ + aoff64_t *lba = (aoff64_t*)key; + block_t *b = hash_table_get_inst(item, block_t, hash_link); + return b->lba == *lba; +} + + +static hash_table_ops_t cache_ops = { .hash = cache_hash, - .compare = cache_compare, - .remove_callback = cache_remove_callback + .key_hash = cache_key_hash, + .key_equal = cache_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -282,6 +287,5 @@ cache->blocks_cluster = cache->lblock_size / devcon->pblock_size; - if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2, - &cache_ops)) { + if (!hash_table_create(&cache->block_hash, 0, 0, &cache_ops)) { free(cache); return ENOMEM; @@ -321,9 +325,5 @@ } - unsigned long key[2] = { - LOWER32(b->lba), - UPPER32(b->lba) - }; - hash_table_remove(&cache->block_hash, key, 2); + hash_table_remove_item(&cache->block_hash, &b->hash_link); free(b->data); @@ -357,5 +357,4 @@ fibril_rwlock_initialize(&b->contents_lock); link_initialize(&b->free_link); - link_initialize(&b->hash_link); } @@ -377,9 +376,5 @@ cache_t *cache; block_t *b; - link_t *l; - unsigned long key[2] = { - LOWER32(ba), - UPPER32(ba) - }; + link_t *link; int rc; @@ -397,11 +392,11 @@ fibril_mutex_lock(&cache->lock); - l = hash_table_find(&cache->block_hash, key); - if (l) { + ht_link_t *hlink = hash_table_find(&cache->block_hash, &ba); + if (hlink) { found: /* * We found the block in the cache. */ - b = hash_table_get_instance(l, block_t, hash_link); + b = hash_table_get_inst(hlink, block_t, hash_link); fibril_mutex_lock(&b->lock); if (b->refcnt++ == 0) @@ -441,6 +436,6 @@ goto out; } - l = list_first(&cache->free_list); - b = list_get_instance(l, block_t, free_link); + link = list_first(&cache->free_list); + b = list_get_instance(link, block_t, free_link); fibril_mutex_lock(&b->lock); @@ -479,6 +474,6 @@ goto retry; } - l = hash_table_find(&cache->block_hash, key); - if (l) { + hlink = hash_table_find(&cache->block_hash, &ba); + if (hlink) { /* * Someone else must have already @@ -502,9 +497,5 @@ */ list_remove(&b->free_link); - unsigned long temp_key[2] = { - LOWER32(b->lba), - UPPER32(b->lba) - }; - hash_table_remove(&cache->block_hash, temp_key, 2); + hash_table_remove_item(&cache->block_hash, &b->hash_link); } @@ -514,5 +505,5 @@ b->lba = ba; b->pba = ba_ltop(devcon, b->lba); - hash_table_insert(&cache->block_hash, key, &b->hash_link); + hash_table_insert(&cache->block_hash, &b->hash_link); /* @@ -622,9 +613,5 @@ * Take the block out of the cache and free it. */ - unsigned long key[2] = { - LOWER32(block->lba), - UPPER32(block->lba) - }; - hash_table_remove(&cache->block_hash, key, 2); + hash_table_remove_item(&cache->block_hash, &block->hash_link); fibril_mutex_unlock(&block->lock); free(block->data); Index: uspace/lib/block/block.h =================================================================== --- uspace/lib/block/block.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/block/block.h (revision 062d9000625057300f609429080872d6492b542e) @@ -84,5 +84,5 @@ link_t free_link; /** Link for placing the block into the block hash table. */ - link_t hash_link; + ht_link_t hash_link; /** Buffer with the block data. */ void *data; Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/c/Makefile (revision 062d9000625057300f609429080872d6492b542e) @@ -124,5 +124,4 @@ generic/adt/list.c \ generic/adt/hash_table.c \ - generic/adt/hash_set.c \ generic/adt/dynamic_fifo.c \ generic/adt/char_map.c \ Index: uspace/lib/c/generic/adt/hash_set.c =================================================================== --- uspace/lib/c/generic/adt/hash_set.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ (revision ) @@ -1,382 +1,0 @@ -/* - * Copyright (c) 2008 Jakub Jermar - * Copyright (c) 2011 Radim Vansa - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup libc - * @{ - */ -/** @file - */ - -#include -#include -#include -#include -#include -#include - -/** Create chained hash set - * - * @param h Hash set structure to be initialized. - * @param[in] hash Hash function - * @param[in] equals Equals function - * @param[in] init_size Initial hash set size - * - * @return True on success - * - */ -int hash_set_init(hash_set_t *h, hash_set_hash hash, hash_set_equals equals, - size_t init_size) -{ - assert(h); - assert(hash); - assert(equals); - - if (init_size < HASH_SET_MIN_SIZE) - init_size = HASH_SET_MIN_SIZE; - - h->table = malloc(init_size * sizeof(link_t)); - if (!h->table) - return false; - - for (size_t i = 0; i < init_size; i++) - list_initialize(&h->table[i]); - - h->size = init_size; - h->count = 0; - h->hash = hash; - h->equals = equals; - - return true; -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - * - */ -void hash_set_destroy(hash_set_t *h) -{ - assert(h); - free(h->table); -} - -/** Rehash the internal table to new table - * - * @param h Original hash set - * @param new_table Memory for the new table - * @param new_size Size of the new table - */ -static void hash_set_rehash(hash_set_t *h, list_t *new_table, - size_t new_size) -{ - assert(new_size >= HASH_SET_MIN_SIZE); - - for (size_t bucket = 0; bucket < new_size; bucket++) - list_initialize(&new_table[bucket]); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - next = cur->next; - list_append(cur, &new_table[h->hash(cur) % new_size]); - } - } - - list_t *old_table = h->table; - h->table = new_table; - free(old_table); - h->size = new_size; -} - -/** Insert item into the set. - * - * If the set already contains equivalent object, - * the function fails. - * - * @param h Hash table. - * @param key Array of all keys necessary to compute hash index. - * @param item Item to be inserted into the hash table. - * - * @return True if the object was inserted - * @return Ffalse if the set already contained equivalent object. - * - */ -int hash_set_insert(hash_set_t *h, link_t *item) -{ - assert(item); - assert(h); - assert(h->hash); - assert(h->equals); - - unsigned long hash = h->hash(item); - unsigned long chain = hash % h->size; - - list_foreach(h->table[chain], cur) { - if (h->equals(cur, item)) - return false; - } - - if (h->count + 1 > h->size) { - size_t new_size = h->size * 2; - list_t *temp = malloc(new_size * sizeof(list_t)); - if (temp != NULL) - hash_set_rehash(h, temp, new_size); - - /* - * If the allocation fails, just use the same - * old table and try to rehash next time. - */ - chain = hash % h->size; - } - - h->count++; - list_append(item, &h->table[chain]); - - return true; -} - -/** Search the hash set for a matching object and return it - * - * @param h Hash set - * @param item The item that should equal to the matched object - * - * @return Matching item on success, NULL if there is no such item. - * - */ -link_t *hash_set_find(hash_set_t *h, const link_t *item) -{ - assert(h); - assert(h->hash); - assert(h->equals); - - unsigned long chain = h->hash(item) % h->size; - - list_foreach(h->table[chain], cur) { - if (h->equals(cur, item)) - return cur; - } - - return NULL; -} - -/** Remove first matching object from the hash set and return it - * - * @param h Hash set. - * @param item The item that should be equal to the matched object - * - * @return The removed item or NULL if this is not found. - * - */ -link_t *hash_set_remove(hash_set_t *h, const link_t *item) -{ - assert(h); - assert(h->hash); - assert(h->equals); - - link_t *cur = hash_set_find(h, item); - if (cur) { - list_remove(cur); - - h->count--; - if (4 * h->count < h->size && h->size > HASH_SET_MIN_SIZE) { - size_t new_size = h->size / 2; - if (new_size < HASH_SET_MIN_SIZE) - /* possible e.g. if init_size == HASH_SET_MIN_SIZE + 1 */ - new_size = HASH_SET_MIN_SIZE; - - list_t *temp = malloc(new_size * sizeof (list_t)); - if (temp != NULL) - hash_set_rehash(h, temp, new_size); - } - } - - return cur; -} - -/** Remove all elements for which the function returned non-zero - * - * The function can also destroy the element. - * - * @param h Hash set. - * @param f Function to be applied. - * @param arg Argument to be passed to the function. - * - */ -void hash_set_remove_selected(hash_set_t *h, int (*f)(link_t *, void *), - void *arg) -{ - assert(h); - assert(h->table); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *prev = &h->table[bucket].head; - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - next = cur->next; - if (f(cur, arg)) { - prev->next = next; - next->prev = prev; - h->count--; - } else - prev = cur; - } - } - - if (4 * h->count < h->size && h->size > HASH_SET_MIN_SIZE) { - size_t new_size = h->size / 2; - if (new_size < HASH_SET_MIN_SIZE) - /* possible e.g. if init_size == HASH_SET_MIN_SIZE + 1 */ - new_size = HASH_SET_MIN_SIZE; - - list_t *temp = malloc(new_size * sizeof (list_t)); - if (temp != NULL) - hash_set_rehash(h, temp, new_size); - } -} - -/** Apply function to all items in hash set - * - * @param h Hash set. - * @param f Function to be applied. - * @param arg Argument to be passed to the function. - * - */ -void hash_set_apply(hash_set_t *h, void (*f)(link_t *, void *), void *arg) -{ - assert(h); - assert(h->table); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - - /* - * The next pointer must be stored prior to the functor - * call to allow using destructor as the functor (the - * free function could overwrite the cur->next pointer). - */ - next = cur->next; - f(cur, arg); - } - } -} - -/** Remove all elements from the set. - * - * The table is reallocated to the minimum size. - * - * @param h Hash set - * @param f Function (destructor?) applied to all element. Can be NULL. - * @param arg Argument to the destructor. - * - */ -void hash_set_clear(hash_set_t *h, void (*f)(link_t *, void *), void *arg) -{ - assert(h); - assert(h->table); - - for (size_t bucket = 0; bucket < h->size; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->table[bucket].head.next; - cur != &h->table[bucket].head; - cur = next) { - next = cur->next; - list_remove(cur); - if (f != NULL) - f(cur, arg); - } - } - - assert(h->size >= HASH_SET_MIN_SIZE); - list_t *new_table = - realloc(h->table, HASH_SET_MIN_SIZE * sizeof(list_t)); - - /* We are shrinking, therefore we shouldn't get NULL */ - assert(new_table); - - if (h->table != new_table) { - /* Init the lists, pointers to itself are used in them */ - for (size_t bucket = 0; bucket < HASH_SET_MIN_SIZE; ++bucket) - list_initialize(&new_table[bucket]); - - h->table = new_table; - } - - h->count = 0; - h->size = HASH_SET_MIN_SIZE; -} - -/** Get hash set size - * - * @param hHash set - * - * @return Number of elements in the set. - * - */ -size_t hash_set_count(const hash_set_t *h) -{ - assert(h); - return h->count; -} - -/** Check whether element is contained in the hash set - * - * @param h Hash set - * @param item Item that should be equal to the matched object - * - * @return True if the hash set contains equal object - * @return False otherwise - * - */ -int hash_set_contains(const hash_set_t *h, const link_t *item) -{ - /* - * The hash_set_find cannot accept constant hash set, - * because we can modify the returned element. But in - * this case we are using it safely. - */ - return hash_set_find((hash_set_t *) h, item) != NULL; -} - -/** @} - */ Index: uspace/lib/c/generic/adt/hash_table.c =================================================================== --- uspace/lib/c/generic/adt/hash_table.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/c/generic/adt/hash_table.c (revision 062d9000625057300f609429080872d6492b542e) @@ -1,4 +1,6 @@ /* * Copyright (c) 2008 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -34,5 +36,15 @@ /* - * This is an implementation of generic chained hash table. + * This is an implementation of a generic resizable chained hash table. + * + * The table grows to 2*n+1 buckets each time, starting at n == 89, + * per Thomas Wang's recommendation: + * http://www.concentric.net/~Ttwang/tech/hashsize.htm + * + * This policy produces prime table sizes for the first five resizes + * and generally produces table sizes which are either prime or + * have fairly large (prime/odd) divisors. Having a prime table size + * mitigates the use of suboptimal hash functions and distributes + * items over the whole table. */ @@ -44,38 +56,99 @@ #include +/* Optimal initial bucket count. See comment above. */ +#define HT_MIN_BUCKETS 89 +/* The table is resized when the average load per bucket exceeds this number. */ +#define HT_MAX_LOAD 2 + + +static size_t round_up_size(size_t size); +static bool alloc_table(size_t bucket_cnt, list_t **pbuckets); +static void clear_items(hash_table_t *h); +static void resize(hash_table_t *h, size_t new_bucket_cnt); +static void grow_if_needed(hash_table_t *h); +static void shrink_if_needed(hash_table_t *h); + +/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */ +static void nop_remove_callback(ht_link_t *item) +{ + /* no-op */ +} + + /** Create chained hash table. * * @param h Hash table structure. Will be initialized by this call. - * @param m Number of hash table buckets. + * @param init_size Initial desired number of hash table buckets. Pass zero + * if you want the default initial size. * @param max_keys Maximal number of keys needed to identify an item. - * @param op Hash table operations structure. + * @param op Hash table operations structure. remove_callback() + * is optional and can be NULL if no action is to be taken + * upon removal. equal() is optional if and only if + * hash_table_insert_unique() will never be invoked. + * All other operations are mandatory. * * @return True on success * */ -bool hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, - hash_table_operations_t *op) +bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load, + hash_table_ops_t *op) { assert(h); - assert(op && op->hash && op->compare); - assert(max_keys > 0); - - h->entry = malloc(m * sizeof(list_t)); - if (!h->entry) + assert(op && op->hash && op->key_hash && op->key_equal); + + /* Check for compulsory ops. */ + if (!op || !op->hash || !op->key_hash || !op->key_equal) return false; - memset((void *) h->entry, 0, m * sizeof(list_t)); - - hash_count_t i; - for (i = 0; i < m; i++) - list_initialize(&h->entry[i]); - - h->entries = m; - h->max_keys = max_keys; + h->bucket_cnt = round_up_size(init_size); + + if (!alloc_table(h->bucket_cnt, &h->bucket)) + return false; + + h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load; + h->item_cnt = 0; h->op = op; + h->full_item_cnt = h->max_load * h->bucket_cnt; + h->apply_ongoing = false; + + if (h->op->remove_callback == 0) { + h->op->remove_callback = nop_remove_callback; + } return true; } +/** Destroy a hash table instance. + * + * @param h Hash table to be destroyed. + * + */ +void hash_table_destroy(hash_table_t *h) +{ + assert(h && h->bucket); + assert(!h->apply_ongoing); + + clear_items(h); + + free(h->bucket); + + h->bucket = 0; + h->bucket_cnt = 0; +} + +/** Returns true if there are no items in the table. */ +bool hash_table_empty(hash_table_t *h) +{ + assert(h && h->bucket); + return h->item_cnt == 0; +} + +/** Returns the number of items in the table. */ +size_t hash_table_size(hash_table_t *h) +{ + assert(h && h->bucket); + return h->item_cnt; +} + /** Remove all elements from the hash table * @@ -84,29 +157,32 @@ void hash_table_clear(hash_table_t *h) { - for (hash_count_t chain = 0; chain < h->entries; ++chain) { - link_t *cur; - link_t *next; - - for (cur = h->entry[chain].head.next; - cur != &h->entry[chain].head; - cur = next) { - next = cur->next; + assert(h && h->bucket); + assert(!h->apply_ongoing); + + clear_items(h); + + /* Shrink the table to its minimum size if possible. */ + if (HT_MIN_BUCKETS < h->bucket_cnt) { + resize(h, HT_MIN_BUCKETS); + } +} + +/** Unlinks and removes all items but does not resize. */ +static void clear_items(hash_table_t *h) +{ + if (h->item_cnt == 0) + return; + + for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { + list_foreach_safe(h->bucket[idx], cur, next) { + assert(cur); + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + list_remove(cur); - h->op->remove_callback(cur); - } - } -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - * - */ -void hash_table_destroy(hash_table_t *h) -{ - assert(h); - assert(h->entry); - - free(h->entry); + h->op->remove_callback(cur_link); + } + } + + h->item_cnt = 0; } @@ -117,13 +193,52 @@ * @param item Item to be inserted into the hash table. */ -void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item) +void hash_table_insert(hash_table_t *h, ht_link_t *item) { assert(item); - assert(h && h->op && h->op->hash && h->op->compare); - - hash_index_t chain = h->op->hash(key); - assert(chain < h->entries); - - list_append(item, &h->entry[chain]); + assert(h && h->bucket); + assert(!h->apply_ongoing); + + size_t idx = h->op->hash(item) % h->bucket_cnt; + + list_append(&item->link, &h->bucket[idx]); + ++h->item_cnt; + grow_if_needed(h); +} + + +/** Insert item into a hash table if not already present. + * + * @param h Hash table. + * @param key Array of all keys necessary to compute hash index. + * @param item Item to be inserted into the hash table. + * + * @return False if such an item had already been inserted. + * @return True if the inserted item was the only item with such a lookup key. + */ +bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item) +{ + assert(item); + assert(h && h->bucket && h->bucket_cnt); + assert(h->op && h->op->hash && h->op->equal); + assert(!h->apply_ongoing); + + size_t idx = h->op->hash(item) % h->bucket_cnt; + + /* Check for duplicates. */ + list_foreach(h->bucket[idx], cur) { + /* + * We could filter out items using their hashes first, but + * calling equal() might very well be just as fast. + */ + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + if (h->op->equal(cur_link, item)) + return false; + } + + list_append(&item->link, &h->bucket[idx]); + ++h->item_cnt; + grow_if_needed(h); + + return true; } @@ -136,20 +251,45 @@ * */ -link_t *hash_table_find(hash_table_t *h, unsigned long key[]) -{ - assert(h && h->op && h->op->hash && h->op->compare); - - hash_index_t chain = h->op->hash(key); - assert(chain < h->entries); - - list_foreach(h->entry[chain], cur) { - if (h->op->compare(key, h->max_keys, cur)) { - /* - * The entry is there. - */ - return cur; - } - } - +ht_link_t *hash_table_find(const hash_table_t *h, void *key) +{ + assert(h && h->bucket); + + size_t idx = h->op->key_hash(key) % h->bucket_cnt; + + list_foreach(h->bucket[idx], cur) { + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + /* + * Is this is the item we are looking for? We could have first + * checked if the hashes match but op->key_equal() may very well be + * just as fast as op->hash(). + */ + if (h->op->key_equal(key, cur_link)) { + return cur_link; + } + } + + return NULL; +} + +/** Find the next item equal to item. */ +ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item) +{ + assert(item); + assert(h && h->bucket); + + /* Traverse the circular list until we reach the starting item again. */ + for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) { + assert(cur); + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + /* + * Is this is the item we are looking for? We could have first + * checked if the hashes match but op->equal() may very well be + * just as fast as op->hash(). + */ + if (h->op->equal(cur_link, item)) { + return cur_link; + } + } + return NULL; } @@ -163,76 +303,170 @@ * the hash table. * @param keys Number of keys in the 'key' array. - * - */ -void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys) -{ - assert(h && h->op && h->op->hash && h->op->compare && - h->op->remove_callback); - assert(keys <= h->max_keys); - - if (keys == h->max_keys) { - /* - * All keys are known, hash_table_find() can be used to find the - * entry. + * + * @return Returns the number of removed items. + */ +size_t hash_table_remove(hash_table_t *h, void *key) +{ + assert(h && h->bucket); + assert(!h->apply_ongoing); + + size_t idx = h->op->key_hash(key) % h->bucket_cnt; + + size_t removed = 0; + + list_foreach_safe(h->bucket[idx], cur, next) { + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + + if (h->op->key_equal(key, cur_link)) { + ++removed; + list_remove(cur); + h->op->remove_callback(cur_link); + } + } + + h->item_cnt -= removed; + shrink_if_needed(h); + + return removed; +} + +/** Removes an item already present in the table. The item must be in the table.*/ +void hash_table_remove_item(hash_table_t *h, ht_link_t *item) +{ + assert(item); + assert(h && h->bucket); + assert(link_in_use(&item->link)); + + list_remove(&item->link); + --h->item_cnt; + h->op->remove_callback(item); + shrink_if_needed(h); +} + +/** Apply function to all items in hash table. + * + * @param h Hash table. + * @param f Function to be applied. Return false if no more items + * should be visited. The functor may only delete the supplied + * item. It must not delete the successor of the item passed + * in the first argument. + * @param arg Argument to be passed to the function. + */ +void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg) +{ + assert(f); + assert(h && h->bucket); + + if (h->item_cnt == 0) + return; + + h->apply_ongoing = true; + + for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { + list_foreach_safe(h->bucket[idx], cur, next) { + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + /* + * The next pointer had already been saved. f() may safely + * delete cur (but not next!). + */ + if (!f(cur_link, arg)) + return; + } + } + + h->apply_ongoing = false; + + shrink_if_needed(h); + grow_if_needed(h); +} + +/** Rounds up size to the nearest suitable table size. */ +static size_t round_up_size(size_t size) +{ + size_t rounded_size = HT_MIN_BUCKETS; + + while (rounded_size < size) { + rounded_size = 2 * rounded_size + 1; + } + + return rounded_size; +} + +/** Allocates and initializes the desired number of buckets. True if successful.*/ +static bool alloc_table(size_t bucket_cnt, list_t **pbuckets) +{ + assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt); + + list_t *buckets = malloc(bucket_cnt * sizeof(list_t)); + if (!buckets) + return false; + + for (size_t i = 0; i < bucket_cnt; i++) + list_initialize(&buckets[i]); + + *pbuckets = buckets; + return true; +} + + +/** Shrinks the table if the table is only sparely populated. */ +static inline void shrink_if_needed(hash_table_t *h) +{ + if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) { + /* + * Keep the bucket_cnt odd (possibly also prime). + * Shrink from 2n + 1 to n. Integer division discards the +1. */ - - link_t *cur = hash_table_find(h, key); - if (cur) { - list_remove(cur); - h->op->remove_callback(cur); - } - + size_t new_bucket_cnt = h->bucket_cnt / 2; + resize(h, new_bucket_cnt); + } +} + +/** Grows the table if table load exceeds the maximum allowed. */ +static inline void grow_if_needed(hash_table_t *h) +{ + /* Grow the table if the average bucket load exceeds the maximum. */ + if (h->full_item_cnt < h->item_cnt) { + /* Keep the bucket_cnt odd (possibly also prime). */ + size_t new_bucket_cnt = 2 * h->bucket_cnt + 1; + resize(h, new_bucket_cnt); + } +} + +/** Allocates and rehashes items to a new table. Frees the old table. */ +static void resize(hash_table_t *h, size_t new_bucket_cnt) +{ + assert(h && h->bucket); + assert(HT_MIN_BUCKETS <= new_bucket_cnt); + + /* We are traversing the table and resizing would mess up the buckets. */ + if (h->apply_ongoing) return; - } - - /* - * Fewer keys were passed. - * Any partially matching entries are to be removed. - */ - hash_index_t chain; - for (chain = 0; chain < h->entries; chain++) { - for (link_t *cur = h->entry[chain].head.next; - cur != &h->entry[chain].head; - cur = cur->next) { - if (h->op->compare(key, keys, cur)) { - link_t *hlp; - - hlp = cur; - cur = cur->prev; - - list_remove(hlp); - h->op->remove_callback(hlp); - - continue; + + list_t *new_buckets; + + /* Leave the table as is if we cannot resize. */ + if (!alloc_table(new_bucket_cnt, &new_buckets)) + return; + + if (0 < h->item_cnt) { + /* Rehash all the items to the new table. */ + for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) { + list_foreach_safe(h->bucket[old_idx], cur, next) { + ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); + + size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt; + list_remove(cur); + list_append(cur, &new_buckets[new_idx]); } } } -} - -/** Apply function to all items in hash table. - * - * @param h Hash table. - * @param f Function to be applied. - * @param arg Argument to be passed to the function. - * - */ -void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg) -{ - for (hash_index_t bucket = 0; bucket < h->entries; bucket++) { - link_t *cur; - link_t *next; - - for (cur = h->entry[bucket].head.next; cur != &h->entry[bucket].head; - cur = next) { - /* - * The next pointer must be stored prior to the functor - * call to allow using destructor as the functor (the - * free function could overwrite the cur->next pointer). - */ - next = cur->next; - f(cur, arg); - } - } -} + + free(h->bucket); + h->bucket = new_buckets; + h->bucket_cnt = new_bucket_cnt; + h->full_item_cnt = h->max_load * h->bucket_cnt; +} + /** @} Index: uspace/lib/c/generic/async.c =================================================================== --- uspace/lib/c/generic/async.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/c/generic/async.c (revision 062d9000625057300f609429080872d6492b542e) @@ -116,6 +116,4 @@ #include "private/libc.h" -#define CLIENT_HASH_TABLE_BUCKETS 32 -#define CONN_HASH_TABLE_BUCKETS 32 /** Session data */ @@ -205,5 +203,5 @@ /* Client connection data */ typedef struct { - link_t link; + ht_link_t link; task_id_t in_task_id; @@ -217,5 +215,5 @@ /** Hash table link. */ - link_t link; + ht_link_t link; /** Incoming client task ID. */ @@ -393,31 +391,31 @@ static LIST_INITIALIZE(timeout_list); -static hash_index_t client_hash(unsigned long key[]) -{ - assert(key); - - return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS); -} - -static int client_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - assert(key); - assert(keys == 2); - assert(item); - - client_t *client = hash_table_get_instance(item, client_t, link); - return (key[0] == LOWER32(client->in_task_id) && - (key[1] == UPPER32(client->in_task_id))); -} - -static void client_remove(link_t *item) -{ -} +static size_t client_key_hash(void *k) +{ + task_id_t key = *(task_id_t*)k; + return key; +} + +static size_t client_hash(const ht_link_t *item) +{ + client_t *client = hash_table_get_inst(item, client_t, link); + return client_key_hash(&client->in_task_id); +} + +static bool client_key_equal(void *k, const ht_link_t *item) +{ + task_id_t key = *(task_id_t*)k; + client_t *client = hash_table_get_inst(item, client_t, link); + return key == client->in_task_id; +} + /** Operations for the client hash table. */ -static hash_table_operations_t client_hash_table_ops = { +static hash_table_ops_t client_hash_table_ops = { .hash = client_hash, - .compare = client_compare, - .remove_callback = client_remove + .key_hash = client_key_hash, + .key_equal = client_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -429,38 +427,31 @@ * */ -static hash_index_t conn_hash(unsigned long key[]) -{ - assert(key); - - return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS); -} - -/** Compare hash table item with a key. - * - * @param key Array containing the source phone hash as the only item. - * @param keys Expected 1 but ignored. - * @param item Connection hash table item. - * - * @return True on match, false otherwise. - * - */ -static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - assert(key); - assert(item); - - connection_t *conn = hash_table_get_instance(item, connection_t, link); - return (key[0] == conn->in_phone_hash); -} - -static void conn_remove(link_t *item) -{ -} +static size_t conn_key_hash(void *key) +{ + sysarg_t in_phone_hash = *(sysarg_t*)key; + return in_phone_hash ; +} + +static size_t conn_hash(const ht_link_t *item) +{ + connection_t *conn = hash_table_get_inst(item, connection_t, link); + return conn_key_hash(&conn->in_phone_hash); +} + +static bool conn_key_equal(void *key, const ht_link_t *item) +{ + sysarg_t in_phone_hash = *(sysarg_t*)key; + connection_t *conn = hash_table_get_inst(item, connection_t, link); + return (in_phone_hash == conn->in_phone_hash); +} + /** Operations for the connection hash table. */ -static hash_table_operations_t conn_hash_table_ops = { +static hash_table_ops_t conn_hash_table_ops = { .hash = conn_hash, - .compare = conn_compare, - .remove_callback = conn_remove + .key_hash = conn_key_hash, + .key_equal = conn_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -510,6 +501,5 @@ futex_down(&async_futex); - unsigned long key = call->in_phone_hash; - link_t *hlp = hash_table_find(&conn_hash_table, &key); + ht_link_t *hlp = hash_table_find(&conn_hash_table, &call->in_phone_hash); if (!hlp) { @@ -518,5 +508,5 @@ } - connection_t *conn = hash_table_get_instance(hlp, connection_t, link); + connection_t *conn = hash_table_get_inst(hlp, connection_t, link); msg_t *msg = malloc(sizeof(*msg)); @@ -698,14 +688,10 @@ static client_t *async_client_get(task_id_t client_id, bool create) { - unsigned long key[2] = { - LOWER32(client_id), - UPPER32(client_id), - }; client_t *client = NULL; futex_down(&async_futex); - link_t *lnk = hash_table_find(&client_hash_table, key); + ht_link_t *lnk = hash_table_find(&client_hash_table, &client_id); if (lnk) { - client = hash_table_get_instance(lnk, client_t, link); + client = hash_table_get_inst(lnk, client_t, link); atomic_inc(&client->refcnt); } else if (create) { @@ -716,5 +702,5 @@ atomic_set(&client->refcnt, 1); - hash_table_insert(&client_hash_table, key, &client->link); + hash_table_insert(&client_hash_table, &client->link); } } @@ -727,13 +713,9 @@ { bool destroy; - unsigned long key[2] = { - LOWER32(client->in_task_id), - UPPER32(client->in_task_id) - }; - + futex_down(&async_futex); if (atomic_predec(&client->refcnt) == 0) { - hash_table_remove(&client_hash_table, key, 2); + hash_table_remove(&client_hash_table, &client->in_task_id); destroy = true; } else @@ -831,6 +813,5 @@ */ futex_down(&async_futex); - unsigned long key = fibril_connection->in_phone_hash; - hash_table_remove(&conn_hash_table, &key, 1); + hash_table_remove(&conn_hash_table, &fibril_connection->in_phone_hash); futex_up(&async_futex); @@ -916,8 +897,7 @@ /* Add connection to the connection hash table */ - unsigned long key = conn->in_phone_hash; futex_down(&async_futex); - hash_table_insert(&conn_hash_table, &key, &conn->link); + hash_table_insert(&conn_hash_table, &conn->link); futex_up(&async_futex); @@ -1111,10 +1091,8 @@ void __async_init(void) { - if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS, - 2, &client_hash_table_ops)) + if (!hash_table_create(&client_hash_table, 0, 0, &client_hash_table_ops)) abort(); - if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS, - 1, &conn_hash_table_ops)) + if (!hash_table_create(&conn_hash_table, 0, 0, &conn_hash_table_ops)) abort(); Index: uspace/lib/c/include/adt/hash.h =================================================================== --- uspace/lib/c/include/adt/hash.h (revision 062d9000625057300f609429080872d6492b542e) +++ uspace/lib/c/include/adt/hash.h (revision 062d9000625057300f609429080872d6492b542e) @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup genericadt + * @{ + */ +/** @file + */ +#ifndef KERN_HASH_H_ +#define KERN_HASH_H_ + +#include + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint32_t hash_mix32(uint32_t hash) +{ + /* + * Thomas Wang's modification of Bob Jenkin's hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * Public domain. + */ + hash = ~hash + (hash << 15); + hash = hash ^ (hash >> 12); + hash = hash + (hash << 2); + hash = hash ^ (hash >> 4); + hash = hash * 2057; + hash = hash ^ (hash >> 16); + return hash; +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint64_t hash_mix64(uint64_t hash) +{ + /* + * Thomas Wang's public domain 64-bit hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + */ + hash = (hash ^ 61) ^ (hash >> 16); + hash = hash + (hash << 3); + hash = hash ^ (hash >> 4); + hash = hash * 0x27d4eb2d; + hash = hash ^ (hash >> 15); + /* + * Lower order bits are mixed more thoroughly. Swap them with + * the higher order bits and make the resulting higher order bits + * more usable. + */ + return (hash << 32) | (hash >> 32); +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline size_t hash_mix(size_t hash) +{ +#ifdef __32_BITS__ + return hash_mix32(hash); +#elif defined(__64_BITS__) + return hash_mix64(hash); +#else +#error Unknown size_t size - cannot select proper hash mix function. +#endif +} + +/** Use to create a hash from multiple values. + * + * Typical usage: + * @code + * int car_id; + * bool car_convertible; + * // .. + * size_t hash = 0; + * hash = hash_combine(hash, car_id); + * hash = hash_combine(hash, car_convertible); + * // Now use hash as a hash of both car_id and car_convertible. + * @endcode + */ +static inline size_t hash_combine(size_t seed, size_t hash) +{ + /* + * todo: use Bob Jenkin's proper mixing hash pass: + * http://burtleburtle.net/bob/c/lookup3.c + */ + seed ^= hash + 0x9e3779b9 + + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5))); + return seed; +} + +#endif Index: uspace/lib/c/include/adt/hash_set.h =================================================================== --- uspace/lib/c/include/adt/hash_set.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ (revision ) @@ -1,84 +1,0 @@ -/* - * Copyright (c) 2006 Jakub Jermar - * Copyright (c) 2011 Radim Vansa - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup libc - * @{ - */ -/** @file - */ - -#ifndef LIBC_HASH_SET_H_ -#define LIBC_HASH_SET_H_ - -#include -#include - -#define HASH_SET_MIN_SIZE 8 - -typedef unsigned long (*hash_set_hash)(const link_t *); -typedef int (*hash_set_equals)(const link_t *, const link_t *); - -/** Hash table structure. */ -typedef struct { - list_t *table; - - /** Current table size */ - size_t size; - - /** - * Current number of entries. If count > size, - * the table is rehashed into table with double - * size. If (4 * count < size) && (size > min_size), - * the table is rehashed into table with half the size. - */ - size_t count; - - /** Hash function */ - hash_set_hash hash; - - /** Hash table item equals function */ - hash_set_equals equals; -} hash_set_t; - -extern int hash_set_init(hash_set_t *, hash_set_hash, hash_set_equals, size_t); -extern int hash_set_insert(hash_set_t *, link_t *); -extern link_t *hash_set_find(hash_set_t *, const link_t *); -extern int hash_set_contains(const hash_set_t *, const link_t *); -extern size_t hash_set_count(const hash_set_t *); -extern link_t *hash_set_remove(hash_set_t *, const link_t *); -extern void hash_set_remove_selected(hash_set_t *, - int (*)(link_t *, void *), void *); -extern void hash_set_destroy(hash_set_t *); -extern void hash_set_apply(hash_set_t *, void (*)(link_t *, void *), void *); -extern void hash_set_clear(hash_set_t *, void (*)(link_t *, void *), void *); - -#endif - -/** @} - */ Index: uspace/lib/c/include/adt/hash_table.h =================================================================== --- uspace/lib/c/include/adt/hash_table.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/c/include/adt/hash_table.h (revision 062d9000625057300f609429080872d6492b542e) @@ -1,4 +1,6 @@ /* * Copyright (c) 2006 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -39,58 +41,65 @@ #include #include +#include -typedef unsigned long hash_count_t; -typedef unsigned long hash_index_t; +/** Opaque hash table link type. */ +typedef struct ht_link { + link_t link; +} ht_link_t; /** Set of operations for hash table. */ typedef struct { - /** Hash function. - * - * @param key Array of keys needed to compute hash index. - * All keys must be passed. - * - * @return Index into hash table. - * - */ - hash_index_t (*hash)(unsigned long key[]); + /** Returns the hash of the key stored in the item (ie its lookup key). */ + size_t (*hash)(const ht_link_t *item); - /** Hash table item comparison function. - * - * @param key Array of keys that will be compared with item. It is - * not necessary to pass all keys. - * - * @return True if the keys match, false otherwise. - * - */ - int (*compare)(unsigned long key[], hash_count_t keys, link_t *item); + /** Returns the hash of the key. */ + size_t (*key_hash)(void *key); + /** True if the items are equal (have the same lookup keys). */ + bool (*equal)(const ht_link_t *item1, const ht_link_t *item2); + + /** Returns true if the key is equal to the item's lookup key. */ + bool (*key_equal)(void *key, const ht_link_t *item); + /** Hash table item removal callback. + * + * Must not invoke any mutating functions of the hash table. * * @param item Item that was removed from the hash table. - * */ - void (*remove_callback)(link_t *item); -} hash_table_operations_t; + void (*remove_callback)(ht_link_t *item); +} hash_table_ops_t; /** Hash table structure. */ typedef struct { - list_t *entry; - hash_count_t entries; - hash_count_t max_keys; - hash_table_operations_t *op; + hash_table_ops_t *op; + list_t *bucket; + size_t bucket_cnt; + size_t full_item_cnt; + size_t item_cnt; + size_t max_load; + bool apply_ongoing; } hash_table_t; -#define hash_table_get_instance(item, type, member) \ - list_get_instance((item), type, member) +#define hash_table_get_inst(item, type, member) \ + member_to_inst((item), type, member) -extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t, - hash_table_operations_t *); +extern bool hash_table_create(hash_table_t *, size_t, size_t, + hash_table_ops_t *); +extern void hash_table_destroy(hash_table_t *); + +extern bool hash_table_empty(hash_table_t *); +extern size_t hash_table_size(hash_table_t *); + extern void hash_table_clear(hash_table_t *); -extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *); -extern link_t *hash_table_find(hash_table_t *, unsigned long []); -extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t); -extern void hash_table_destroy(hash_table_t *); -extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *), - void *); +extern void hash_table_insert(hash_table_t *, ht_link_t *); +extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *); +extern ht_link_t *hash_table_find(const hash_table_t *, void *); +extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *); +extern size_t hash_table_remove(hash_table_t *, void *); +extern void hash_table_remove_item(hash_table_t *, ht_link_t *); +extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *), + void *); + #endif Index: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/c/include/adt/list.h (revision 062d9000625057300f609429080872d6492b542e) @@ -71,6 +71,43 @@ iterator != &(list).head; iterator = iterator->next) +/** Unlike list_foreach(), allows removing items while traversing a list. + * + * @code + * list_t mylist; + * typedef struct item { + * int value; + * link_t item_link; + * } item_t; + * + * //.. + * + * // Print each list element's value and remove the element from the list. + * list_foreach_safe(mylist, cur_link, next_link) { + * item_t *cur_item = list_get_instance(cur_link, item_t, item_link); + * printf("%d\n", cur_item->value); + * list_remove(cur_link); + * } + * @endcode + * + * @param list List to traverse. + * @param iterator Iterator to the current element of the list. + * The item this iterator points may be safely removed + * from the list. + * @param next_iter Iterator to the next element of the list. + */ +#define list_foreach_safe(list, iterator, next_iter) \ + for (link_t *iterator = (list).head.next, \ + *next_iter = iterator->next; \ + iterator != &(list).head; \ + iterator = next_iter, next_iter = iterator->next) + #define assert_link_not_used(link) \ assert(((link)->prev == NULL) && ((link)->next == NULL)) + +/** Returns true if the link is definitely part of a list. False if not sure. */ +static inline int link_in_use(link_t *link) +{ + return link->prev != NULL && link->next != NULL; +} /** Initialize doubly-linked circular list link Index: uspace/lib/c/include/macros.h =================================================================== --- uspace/lib/c/include/macros.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/c/include/macros.h (revision 062d9000625057300f609429080872d6492b542e) @@ -52,4 +52,10 @@ | ((((uint64_t) (up)) & 0xffffffff) << 32)) +#ifndef member_to_inst +#define member_to_inst(ptr_member, type, member_identif) \ + ((type*) (((void*)(ptr_member)) - ((void*)&(((type*)0)->member_identif)))) +#endif + + #endif Index: uspace/lib/nic/include/nic.h =================================================================== --- uspace/lib/nic/include/nic.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/nic/include/nic.h (revision 062d9000625057300f609429080872d6492b542e) @@ -40,4 +40,5 @@ #include +#include #include #include @@ -53,5 +54,5 @@ */ typedef struct nic_wol_virtue { - link_t item; + ht_link_t item; nic_wv_id_t id; nic_wv_type_t type; Index: uspace/lib/nic/include/nic_addr_db.h =================================================================== --- uspace/lib/nic/include/nic_addr_db.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/nic/include/nic_addr_db.h (revision 062d9000625057300f609429080872d6492b542e) @@ -43,14 +43,5 @@ #endif -#include - -/** - * Initial size of DB's hash set - */ -#define NIC_ADDR_DB_INIT_SIZE 8 -/** - * Maximal length of addresses in the DB (in bytes). - */ -#define NIC_ADDR_MAX_LENGTH 16 +#include /** @@ -58,25 +49,14 @@ */ typedef struct nic_addr_db { - hash_set_t set; + hash_table_t set; size_t addr_len; } nic_addr_db_t; -/** - * Helper structure for keeping the address in the hash set. - */ -typedef struct nic_addr_entry { - link_t item; - size_t addr_len; - uint8_t addr[NIC_ADDR_MAX_LENGTH]; -} nic_addr_entry_t; extern int nic_addr_db_init(nic_addr_db_t *db, size_t addr_len); extern void nic_addr_db_clear(nic_addr_db_t *db); extern void nic_addr_db_destroy(nic_addr_db_t *db); -extern size_t nic_addr_db_count(const nic_addr_db_t *db); extern int nic_addr_db_insert(nic_addr_db_t *db, const uint8_t *addr); extern int nic_addr_db_remove(nic_addr_db_t *db, const uint8_t *addr); -extern void nic_addr_db_remove_selected(nic_addr_db_t *db, - int (*func)(const uint8_t *, void *), void *arg); extern int nic_addr_db_contains(const nic_addr_db_t *db, const uint8_t *addr); extern void nic_addr_db_foreach(const nic_addr_db_t *db, Index: uspace/lib/nic/include/nic_wol_virtues.h =================================================================== --- uspace/lib/nic/include/nic_wol_virtues.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/nic/include/nic_wol_virtues.h (revision 062d9000625057300f609429080872d6492b542e) @@ -51,5 +51,5 @@ * Operations for table */ - hash_table_operations_t table_operations; + hash_table_ops_t table_operations; /** * WOL virtues hashed by their ID's. Index: uspace/lib/nic/src/nic_addr_db.c =================================================================== --- uspace/lib/nic/src/nic_addr_db.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/nic/src/nic_addr_db.c (revision 062d9000625057300f609429080872d6492b542e) @@ -35,4 +35,6 @@ * @brief Generic hash-set based database of addresses */ +#include "nic_addr_db.h" +#include "libarch/common.h" #include #include @@ -40,49 +42,72 @@ #include #include - -#include "nic_addr_db.h" - -/** - * Hash set helper function - */ -static int nic_addr_equals(const link_t *item1, const link_t *item2) -{ - assert(item1 && item2); - size_t addr_len = ((const nic_addr_entry_t *) item1)->addr_len; - - assert(addr_len == ((const nic_addr_entry_t *) item2)->addr_len); - - size_t i; - for (i = 0; i < addr_len; ++i) { - if (((nic_addr_entry_t *) item1)->addr[i] != - ((nic_addr_entry_t *) item2)->addr[i]) - return false; +#include +#include +#include + + +/** + * Helper structure for keeping the address in the hash set. + */ +typedef struct nic_addr_entry { + ht_link_t link; + uint8_t len; + uint8_t addr[1]; +} nic_addr_entry_t; + + +/* + * Hash table helper functions + */ +typedef struct { + size_t len; + const uint8_t *addr; +} addr_key_t; + +static bool nic_addr_key_equal(void *key_arg, const ht_link_t *item) +{ + addr_key_t *key = (addr_key_t*)key_arg; + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + + return 0 == bcmp(entry->addr, key->addr, entry->len); +} + +static size_t addr_hash(size_t len, const uint8_t *addr) +{ + size_t hash = 0; + + for (size_t i = 0; i < len; ++i) { + hash = (hash << 5) ^ addr[i]; } - return true; -} - -/** - * Hash set helper function - */ -static unsigned long nic_addr_hash(const link_t *item) -{ - assert(item); - const nic_addr_entry_t *entry = (const nic_addr_entry_t *) item; - unsigned long hash = 0; - - size_t i; - for (i = 0; i < entry->addr_len; ++i) { - hash = (hash << 8) ^ (hash >> 24) ^ entry->addr[i]; - } + return hash; } -/** - * Helper wrapper - */ -static void nic_addr_destroy(link_t *item, void *unused) -{ - free(item); -} +static size_t nic_addr_key_hash(void *k) +{ + addr_key_t *key = (addr_key_t*)k; + return addr_hash(key->len, key->addr); +} + +static size_t nic_addr_hash(const ht_link_t *item) +{ + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + return addr_hash(entry->len, entry->addr); +} + +static void nic_addr_removed(ht_link_t *item) +{ + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + + free(entry); +} + +static hash_table_ops_t set_ops = { + .hash = nic_addr_hash, + .key_hash = nic_addr_key_hash, + .key_equal = nic_addr_key_equal, + .equal = 0, + .remove_callback = nic_addr_removed +}; /** @@ -99,11 +124,11 @@ { assert(db); - if (addr_len > NIC_ADDR_MAX_LENGTH) { + + if (addr_len > UCHAR_MAX) return EINVAL; - } - if (!hash_set_init(&db->set, nic_addr_hash, nic_addr_equals, - NIC_ADDR_DB_INIT_SIZE)) { + + if (!hash_table_create(&db->set, 0, 0, &set_ops)) return ENOMEM; - } + db->addr_len = addr_len; return EOK; @@ -118,5 +143,5 @@ { assert(db); - hash_set_clear(&db->set, nic_addr_destroy, NULL); + hash_table_clear(&db->set); } @@ -129,20 +154,7 @@ { assert(db); - hash_set_apply(&db->set, nic_addr_destroy, NULL); - hash_set_destroy(&db->set); -} - -/** - * Get number of addresses in the db - * - * @param db - * - * @return Number of adresses - */ -size_t nic_addr_db_count(const nic_addr_db_t *db) -{ - assert(db); - return hash_set_count(&db->set); -} + hash_table_destroy(&db->set); +} + /** @@ -160,12 +172,22 @@ { assert(db && addr); - nic_addr_entry_t *entry = malloc(sizeof (nic_addr_entry_t)); - if (entry == NULL) { + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + if (hash_table_find(&db->set, &key)) + return EEXIST; + + nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1); + if (entry == NULL) return ENOMEM; - } - entry->addr_len = db->addr_len; + + entry->len = (uint8_t) db->addr_len; memcpy(entry->addr, addr, db->addr_len); - - return hash_set_insert(&db->set, &entry->item) ? EOK : EEXIST; + + hash_table_insert(&db->set, &entry->link); + return EOK; } @@ -182,11 +204,14 @@ { assert(db && addr); - nic_addr_entry_t entry; - entry.addr_len = db->addr_len; - memcpy(entry.addr, addr, db->addr_len); - - link_t *removed = hash_set_remove(&db->set, &entry.item); - free(removed); - return removed != NULL ? EOK : ENOENT; + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + if (hash_table_remove(&db->set, &key)) + return EOK; + else + return ENOENT; } @@ -202,9 +227,11 @@ { assert(db && addr); - nic_addr_entry_t entry; - entry.addr_len = db->addr_len; - memcpy(entry.addr, addr, db->addr_len); - - return hash_set_contains(&db->set, &entry.item); + + addr_key_t key = { + .len = db->addr_len, + .addr = addr + }; + + return 0 != hash_table_find(&db->set, &key); } @@ -220,7 +247,10 @@ * Helper function for nic_addr_db_foreach */ -static void nic_addr_db_fe_helper(link_t *item, void *arg) { +static bool nic_addr_db_fe_helper(ht_link_t *item, void *arg) +{ nic_addr_db_fe_arg_t *hs = (nic_addr_db_fe_arg_t *) arg; - hs->func(((nic_addr_entry_t *) item)->addr, hs->arg); + nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link); + hs->func(entry->addr, hs->arg); + return true; } @@ -237,39 +267,5 @@ { nic_addr_db_fe_arg_t hs = { .func = func, .arg = arg }; - hash_set_apply((hash_set_t *) &db->set, nic_addr_db_fe_helper, &hs); -} - -/** - * Helper structure for nic_addr_db_remove_selected - */ -typedef struct { - int (*func)(const uint8_t *, void *); - void *arg; -} nic_addr_db_rs_arg_t; - -/** - * Helper function for nic_addr_db_foreach - */ -static int nic_addr_db_rs_helper(link_t *item, void *arg) { - nic_addr_db_rs_arg_t *hs = (nic_addr_db_rs_arg_t *) arg; - int retval = hs->func(((nic_addr_entry_t *) item)->addr, hs->arg); - if (retval) { - free(item); - } - return retval; -} - -/** - * Removes all addresses for which the function returns non-zero. - * - * @param db - * @param func User-defined function - * @param arg Custom argument passed to the function - */ -void nic_addr_db_remove_selected(nic_addr_db_t *db, - int (*func)(const uint8_t *, void *), void *arg) -{ - nic_addr_db_rs_arg_t hs = { .func = func, .arg = arg }; - hash_set_remove_selected(&db->set, nic_addr_db_rs_helper, &hs); + hash_table_apply((hash_table_t*)&db->set, nic_addr_db_fe_helper, &hs); } Index: uspace/lib/nic/src/nic_wol_virtues.c =================================================================== --- uspace/lib/nic/src/nic_wol_virtues.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/lib/nic/src/nic_wol_virtues.c (revision 062d9000625057300f609429080872d6492b542e) @@ -37,32 +37,28 @@ #include "nic_wol_virtues.h" +#include "nic.h" #include #include -#define NIC_WV_HASH_COUNT 32 - -/** - * Hash table helper function - */ -static int nic_wv_compare(unsigned long key[], hash_count_t keys, - link_t *item) + +/* + * Hash table helper functions + */ + +static size_t nic_wv_key_hash(void *key) +{ + return *(nic_wv_id_t*) key; +} + +static size_t nic_wv_hash(const ht_link_t *item) { nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item; - return (virtue->id == (nic_wv_id_t) key[0]); -} - -/** - * Hash table helper function - */ -static void nic_wv_rc(link_t *item) -{ -} - -/** - * Hash table helper function - */ -static hash_index_t nic_wv_hash(unsigned long keys[]) -{ - return keys[0] % NIC_WV_HASH_COUNT; + return virtue->id; +} + +static bool nic_wv_key_equal(void *key, const ht_link_t *item) +{ + nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item; + return (virtue->id == *(nic_wv_id_t*) key); } @@ -77,10 +73,12 @@ int nic_wol_virtues_init(nic_wol_virtues_t *wvs) { - bzero(wvs, sizeof (nic_wol_virtues_t)); - wvs->table_operations.compare = nic_wv_compare; + bzero(wvs, sizeof(nic_wol_virtues_t)); wvs->table_operations.hash = nic_wv_hash; - wvs->table_operations.remove_callback = nic_wv_rc; - if (!hash_table_create(&wvs->table, NIC_WV_HASH_COUNT, 1, - &wvs->table_operations)) { + wvs->table_operations.key_hash = nic_wv_key_hash; + wvs->table_operations.key_equal = nic_wv_key_equal; + wvs->table_operations.equal = 0; + wvs->table_operations.remove_callback = 0; + + if (!hash_table_create(&wvs->table, 0, 0, &wvs->table_operations)) { return ENOMEM; } @@ -170,8 +168,6 @@ do { virtue->id = wvs->next_id++; - } while (NULL != - hash_table_find(&wvs->table, (unsigned long *) &virtue->id)); - hash_table_insert(&wvs->table, - (unsigned long *) &virtue->id, &virtue->item); + } while (NULL != hash_table_find(&wvs->table, &virtue->id)); + hash_table_insert(&wvs->table, &virtue->item); virtue->next = wvs->lists[virtue->type]; wvs->lists[virtue->type] = virtue; @@ -191,6 +187,6 @@ nic_wol_virtue_t *nic_wol_virtues_remove(nic_wol_virtues_t *wvs, nic_wv_id_t id) { - nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) - hash_table_find(&wvs->table, (unsigned long *) &id); + nic_wol_virtue_t *virtue = + (nic_wol_virtue_t *) hash_table_find(&wvs->table, &id); if (virtue == NULL) { return NULL; @@ -198,5 +194,5 @@ /* Remove from filter_table */ - hash_table_remove(&wvs->table, (unsigned long *) &id, 1); + hash_table_remove_item(&wvs->table, &virtue->item); /* Remove from filter_types */ @@ -235,6 +231,5 @@ * constant virtue the retyping is correct. */ - link_t *virtue = hash_table_find( - &((nic_wol_virtues_t *) wvs)->table, (unsigned long *) &id); + ht_link_t *virtue = hash_table_find(&((nic_wol_virtues_t *) wvs)->table, &id); return (const nic_wol_virtue_t *) virtue; } Index: uspace/srv/devman/devman.c =================================================================== --- uspace/srv/devman/devman.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/devman/devman.c (revision 062d9000625057300f609429080872d6492b542e) @@ -66,50 +66,78 @@ /* hash table operations */ -static hash_index_t devices_hash(unsigned long key[]) -{ - return key[0] % DEVICE_BUCKETS; -} - -static int devman_devices_compare(unsigned long key[], hash_count_t keys, - 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 int devman_functions_compare(unsigned long key[], hash_count_t keys, - 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 int loc_functions_compare(unsigned long key[], hash_count_t keys, - 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 void devices_remove_callback(link_t *item) -{ -} - -static hash_table_operations_t devman_devices_ops = { - .hash = devices_hash, - .compare = devman_devices_compare, - .remove_callback = devices_remove_callback +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; +} + + +static hash_table_ops_t devman_devices_ops = { + .hash = devman_devices_hash, + .key_hash = handle_key_hash, + .key_equal = devman_devices_key_equal, + .equal = 0, + .remove_callback = 0 }; -static hash_table_operations_t devman_functions_ops = { - .hash = devices_hash, - .compare = devman_functions_compare, - .remove_callback = devices_remove_callback +static hash_table_ops_t devman_functions_ops = { + .hash = devman_functions_hash, + .key_hash = handle_key_hash, + .key_equal = devman_functions_key_equal, + .equal = 0, + .remove_callback = 0 }; -static hash_table_operations_t loc_devices_ops = { - .hash = devices_hash, - .compare = loc_functions_compare, - .remove_callback = devices_remove_callback +static hash_table_ops_t loc_devices_ops = { + .hash = loc_functions_hash, + .key_hash = service_id_key_hash, + .key_equal = loc_functions_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -974,10 +1002,7 @@ tree->current_handle = 0; - hash_table_create(&tree->devman_devices, DEVICE_BUCKETS, 1, - &devman_devices_ops); - hash_table_create(&tree->devman_functions, DEVICE_BUCKETS, 1, - &devman_functions_ops); - hash_table_create(&tree->loc_functions, DEVICE_BUCKETS, 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); @@ -1013,5 +1038,4 @@ list_initialize(&dev->functions); link_initialize(&dev->driver_devices); - link_initialize(&dev->devman_dev); return dev; @@ -1060,14 +1084,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); } @@ -1144,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; @@ -1206,15 +1225,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; @@ -1294,6 +1311,5 @@ /* Add the node to the handle-to-node map. */ dev->handle = ++tree->current_handle; - unsigned long key = dev->handle; - hash_table_insert(&tree->devman_devices, &key, &dev->devman_dev); + hash_table_insert(&tree->devman_devices, &dev->devman_dev); /* Add the node to the list of its parent's children. */ @@ -1316,6 +1332,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. */ @@ -1358,6 +1373,5 @@ /* Add the node to the handle-to-node map. */ fun->handle = ++tree->current_handle; - unsigned long key = fun->handle; - hash_table_insert(&tree->devman_functions, &key, &fun->devman_fun); + hash_table_insert(&tree->devman_functions, &fun->devman_fun); /* Add the node to the list of its parent's children. */ @@ -1379,6 +1393,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. */ @@ -1493,11 +1506,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); } @@ -1511,6 +1522,5 @@ assert(fibril_rwlock_is_write_locked(&tree->rwlock)); - unsigned long key = (unsigned long) fun->service_id; - hash_table_insert(&tree->loc_functions, &key, &fun->loc_fun); + hash_table_insert(&tree->loc_functions, &fun->loc_fun); } Index: uspace/srv/devman/devman.h =================================================================== --- uspace/srv/devman/devman.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/devman/devman.h (revision 062d9000625057300f609429080872d6492b542e) @@ -52,5 +52,4 @@ #define MATCH_EXT ".ma" -#define DEVICE_BUCKETS 256 #define LOC_DEVICE_NAMESPACE "devices" @@ -151,5 +150,5 @@ * Used by the hash table of devices indexed by devman device handles. */ - link_t devman_dev; + ht_link_t devman_dev; /** @@ -204,10 +203,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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/cdfs/cdfs_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -37,6 +37,8 @@ */ +#include "cdfs_ops.h" #include #include +#include #include #include @@ -50,21 +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_BUCKETS 256 - -#define NODES_KEY_SRVC 0 -#define NODES_KEY_INDEX 1 +#define NODE_CACHE_SIZE 200 /** All root nodes have index 0 */ @@ -205,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 */ @@ -226,31 +216,36 @@ static hash_table_t nodes; -static hash_index_t nodes_hash(unsigned long key[]) -{ - return key[NODES_KEY_INDEX] % NODES_BUCKETS; -} - -static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - cdfs_node_t *node = - hash_table_get_instance(item, cdfs_node_t, nh_link); - - switch (keys) { - case 1: - return (node->service_id == key[NODES_KEY_SRVC]); - case 2: - return ((node->service_id == key[NODES_KEY_SRVC]) && - (node->index == key[NODES_KEY_INDEX])); - default: - assert((keys == 1) || (keys == 2)); - } - - return 0; -} - -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); @@ -268,7 +263,9 @@ /** Nodes hash table operations */ -static hash_table_operations_t nodes_ops = { +static hash_table_ops_t nodes_ops = { .hash = nodes_hash, - .compare = nodes_compare, + .key_hash = nodes_key_hash, + .key_equal = nodes_key_equal, + .equal = 0, .remove_callback = nodes_remove_callback }; @@ -277,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); @@ -311,5 +308,4 @@ node->opened = 0; - link_initialize(&node->nh_link); list_initialize(&node->cs_list); } @@ -353,10 +349,5 @@ /* Insert the new node into the nodes hash table. */ - unsigned long key[] = { - [NODES_KEY_SRVC] = node->service_id, - [NODES_KEY_INDEX] = node->index - }; - - hash_table_insert(&nodes, key, &node->nh_link); + hash_table_insert(&nodes, &node->nh_link); *rfn = FS_NODE(node); @@ -508,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); } @@ -802,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); @@ -822,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) { @@ -912,34 +911,31 @@ } +static bool cache_remove_closed(ht_link_t *item, void *arg) +{ + size_t *premove_cnt = (size_t*)arg; + + /* Some nodes were requested to be removed from the cache. */ + if (0 < *premove_cnt) { + cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link); + + if (!node->opened) { + hash_table_remove_item(&nodes, item); + + --nodes_cached; + --*premove_cnt; + } + } + + /* Only continue if more nodes were requested to be removed. */ + return 0 < *premove_cnt; +} + static void cleanup_cache(service_id_t service_id) { if (nodes_cached > NODE_CACHE_SIZE) { - size_t remove = nodes_cached - NODE_CACHE_SIZE; - - // FIXME: this accesses the internals of the hash table - // and should be rewritten in a clean way - - for (hash_index_t chain = 0; chain < nodes.entries; chain++) { - for (link_t *link = nodes.entry[chain].head.next; - link != &nodes.entry[chain].head; - link = link->next) { - if (remove == 0) - return; - - cdfs_node_t *node = - hash_table_get_instance(link, cdfs_node_t, nh_link); - if (node->opened == 0) { - link_t *tmp = link; - link = link->prev; - - list_remove(tmp); - nodes.op->remove_callback(tmp); - nodes_cached--; - remove--; - - continue; - } - } - } + size_t remove_cnt = nodes_cached - NODE_CACHE_SIZE; + + if (0 < remove_cnt) + hash_table_apply(&nodes, cache_remove_closed, &remove_cnt); } } @@ -951,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); @@ -1007,5 +1003,5 @@ bool cdfs_init(void) { - if (!hash_table_create(&nodes, NODES_BUCKETS, 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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/exfat/exfat.h (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/exfat/exfat_idx.c (revision 062d9000625057300f609429080872d6492b542e) @@ -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,70 +114,48 @@ static hash_table_t up_hash; -#define UPH_BUCKETS_LOG 12 -#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG) - -#define UPH_SID_KEY 0 -#define UPH_PFC_KEY 1 -#define UPH_PDI_KEY 2 - -static hash_index_t pos_hash(unsigned long key[]) -{ - service_id_t service_id = (service_id_t)key[UPH_SID_KEY]; - exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY]; - unsigned pdi = (unsigned)key[UPH_PDI_KEY]; - - hash_index_t h; - - /* - * The least significant half of all bits are the least significant bits - * of the parent node's first cluster. - * - * The least significant half of the most significant half of all bits - * are the least significant bits of the node's dentry index within the - * parent directory node. - * - * The most significant half of the most significant half of all bits - * are the least significant bits of the device handle. - */ - h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1); - h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << - (UPH_BUCKETS_LOG / 2); - h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << - (3 * (UPH_BUCKETS_LOG / 4)); - - return h; -} - -static int pos_compare(unsigned long key[], hash_count_t keys, 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; -} - -static void pos_remove_callback(link_t *item) -{ - /* nothing to do */ -} - -static hash_table_operations_t uph_ops = { +} 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; +} + +static hash_table_ops_t uph_ops = { .hash = pos_hash, - .compare = pos_compare, - .remove_callback = pos_remove_callback, + .key_hash = pos_key_hash, + .key_equal = pos_key_equal, + .equal = 0, + .remove_callback = 0, }; @@ -186,54 +166,41 @@ static hash_table_t ui_hash; -#define UIH_BUCKETS_LOG 12 -#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG) - -#define UIH_SID_KEY 0 -#define UIH_INDEX_KEY 1 - -static hash_index_t idx_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]; - - hash_index_t h; - - h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1); - h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) << - (UIH_BUCKETS_LOG / 2); - - return h; -} - -static int idx_compare(unsigned long key[], hash_count_t keys, 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); } -static hash_table_operations_t uih_ops = { +static hash_table_ops_t uih_ops = { .hash = idx_hash, - .compare = idx_compare, + .key_hash = idx_key_hash, + .key_equal = idx_key_equal, + .equal = 0, .remove_callback = idx_remove_callback, }; @@ -376,6 +343,4 @@ } - link_initialize(&fidx->uph_link); - link_initialize(&fidx->uih_link); fibril_mutex_initialize(&fidx->lock); fidx->service_id = service_id; @@ -400,10 +365,5 @@ } - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id, - [UIH_INDEX_KEY] = fidx->index, - }; - - hash_table_insert(&ui_hash, ikey, &fidx->uih_link); + hash_table_insert(&ui_hash, &fidx->uih_link); fibril_mutex_lock(&fidx->lock); fibril_mutex_unlock(&used_lock); @@ -417,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; @@ -437,14 +397,9 @@ } - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id, - [UIH_INDEX_KEY] = fidx->index, - }; - fidx->pfc = pfc; fidx->pdi = pdi; - hash_table_insert(&up_hash, pkey, &fidx->uph_link); - hash_table_insert(&ui_hash, ikey, &fidx->uih_link); + hash_table_insert(&up_hash, &fidx->uph_link); + hash_table_insert(&ui_hash, &fidx->uih_link); } fibril_mutex_lock(&fidx->lock); @@ -456,12 +411,6 @@ void exfat_idx_hashin(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_insert(&up_hash, pkey, &idx->uph_link); + fibril_mutex_lock(&used_lock); + hash_table_insert(&up_hash, &idx->uph_link); fibril_mutex_unlock(&used_lock); } @@ -469,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); } @@ -484,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); } @@ -507,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); */ @@ -523,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(). */ } @@ -532,7 +473,7 @@ int exfat_idx_init(void) { - if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops)) + if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) return ENOMEM; - if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) { + if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) { hash_table_destroy(&up_hash); return ENOMEM; @@ -544,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); @@ -568,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. @@ -583,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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/exfat/exfat_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/ext2fs/ext2fs_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -49,4 +49,5 @@ #include #include +#include #include #include @@ -62,8 +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 -#define OPEN_NODES_BUCKETS 256 typedef struct ext2fs_instance { @@ -78,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; @@ -122,36 +119,44 @@ static FIBRIL_MUTEX_INITIALIZE(open_nodes_lock); -/* Hash table interface for open nodes hash table */ -static hash_index_t open_nodes_hash(unsigned long key[]) -{ - /* TODO: This is very simple and probably can be improved */ - return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS; -} - -static int open_nodes_compare(unsigned long key[], hash_count_t keys, - 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]); -} - -static void open_nodes_remove_cb(link_t *link) -{ - /* We don't use remove callback for this hash table */ -} - -static hash_table_operations_t open_nodes_ops = { +/* + * 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); + + 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; +} + +static hash_table_ops_t open_nodes_ops = { .hash = open_nodes_hash, - .compare = open_nodes_compare, - .remove_callback = open_nodes_remove_cb, + .key_hash = open_nodes_key_hash, + .key_equal = open_nodes_key_equal, + .equal = 0, + .remove_callback = 0, }; @@ -161,6 +166,5 @@ int ext2fs_global_init(void) { - if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS, - OPEN_NODES_KEYS, &open_nodes_ops)) { + if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) { return ENOMEM; } @@ -316,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++; @@ -357,10 +361,9 @@ enode->references = 1; enode->fs_node = node; - link_initialize(&enode->link); node->data = enode; *rfn = node; - hash_table_insert(&open_nodes, key, &enode->link); + hash_table_insert(&open_nodes, &enode->link); inst->open_nodes_count++; @@ -408,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/ext4fs/ext4fs_ops.c =================================================================== --- uspace/srv/fs/ext4fs/ext4fs_ops.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/ext4fs/ext4fs_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -42,4 +42,5 @@ #include #include +#include #include #include "ext4fs.h" @@ -48,11 +49,4 @@ #define EXT4FS_NODE(node) \ ((node) ? (ext4fs_node_t *) (node)->data : NULL) - -#define OPEN_NODES_KEYS 2 - -#define OPEN_NODES_DEV_HANDLE_KEY 0 -#define OPEN_NODES_INODE_KEY 1 - -#define OPEN_NODES_BUCKETS 256 /** @@ -73,5 +67,5 @@ ext4_inode_ref_t *inode_ref; fs_node_t *fs_node; - link_t link; + ht_link_t link; unsigned int references; } ext4fs_node_t; @@ -115,45 +109,37 @@ /* Hash table interface for open nodes hash table */ -static hash_index_t open_nodes_hash(unsigned long key[]) -{ - /* TODO: This is very simple and probably can be improved */ - return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS; -} - -/** Compare given item with values in hash table. - * - */ -static int open_nodes_compare(unsigned long key[], hash_count_t keys, - link_t *item) -{ - assert(keys > 0); - - ext4fs_node_t *enode = - hash_table_get_instance(item, ext4fs_node_t, link); - - 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]); -} - -/** Empty callback to correct hash table initialization. - * - */ -static void open_nodes_remove_cb(link_t *link) -{ - /* We don't use remove callback for this hash table */ -} - -static hash_table_operations_t open_nodes_ops = { + +typedef struct { + service_id_t service_id; + fs_index_t index; +} node_key_t; + +static size_t open_nodes_key_hash(void *key_arg) +{ + node_key_t *key = (node_key_t *)key_arg; + return hash_combine(key->service_id, key->index); +} + +static size_t open_nodes_hash(const ht_link_t *item) +{ + ext4fs_node_t *enode = hash_table_get_inst(item, ext4fs_node_t, link); + return hash_combine(enode->instance->service_id, enode->inode_ref->index); +} + +static bool open_nodes_key_equal(void *key_arg, const ht_link_t *item) +{ + node_key_t *key = (node_key_t *)key_arg; + ext4fs_node_t *enode = hash_table_get_inst(item, ext4fs_node_t, link); + + return key->service_id == enode->instance->service_id + && key->index == enode->inode_ref->index; +} + +static hash_table_ops_t open_nodes_ops = { .hash = open_nodes_hash, - .compare = open_nodes_compare, - .remove_callback = open_nodes_remove_cb, + .key_hash = open_nodes_key_hash, + .key_equal = open_nodes_key_equal, + .equal = NULL, + .remove_callback = NULL, }; @@ -168,6 +154,5 @@ int ext4fs_global_init(void) { - if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS, - OPEN_NODES_KEYS, &open_nodes_ops)) + if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) return ENOMEM; @@ -315,13 +300,13 @@ /* 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); ext4fs_node_t *enode = NULL; if (already_open) { - enode = hash_table_get_instance(already_open, ext4fs_node_t, link); + enode = hash_table_get_inst(already_open, ext4fs_node_t, link); *rfn = enode->fs_node; enode->references++; @@ -364,10 +349,9 @@ enode->references = 1; enode->fs_node = fs_node; - link_initialize(&enode->link); fs_node->data = enode; *rfn = fs_node; - hash_table_insert(&open_nodes, key, &enode->link); + hash_table_insert(&open_nodes, &enode->link); inst->open_nodes_count++; @@ -386,10 +370,5 @@ int ext4fs_node_put_core(ext4fs_node_t *enode) { - unsigned long key[] = { - [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id, - [OPEN_NODES_INODE_KEY] = enode->inode_ref->index - }; - - hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS); + hash_table_remove_item(&open_nodes, &enode->link); assert(enode->instance->open_nodes_count > 0); enode->instance->open_nodes_count--; @@ -498,13 +477,6 @@ enode->references = 1; - link_initialize(&enode->link); - - unsigned long key[] = { - [OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id, - [OPEN_NODES_INODE_KEY] = inode_ref->index - }; - fibril_mutex_lock(&open_nodes_lock); - hash_table_insert(&open_nodes, key, &enode->link); + hash_table_insert(&open_nodes, &enode->link); fibril_mutex_unlock(&open_nodes_lock); inst->open_nodes_count++; Index: uspace/srv/fs/fat/fat.h =================================================================== --- uspace/srv/fs/fat/fat.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/fat/fat.h (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/fat/fat_idx.c (revision 062d9000625057300f609429080872d6492b542e) @@ -41,4 +41,5 @@ #include #include +#include #include #include @@ -58,6 +59,6 @@ */ typedef struct { - link_t link; - service_id_t service_id; + link_t link; + service_id_t service_id; /** Next unassigned index. */ @@ -97,5 +98,5 @@ return u; } - + if (lock) fibril_mutex_unlock(&unused_lock); @@ -113,70 +114,48 @@ static hash_table_t up_hash; -#define UPH_BUCKETS_LOG 12 -#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG) - -#define UPH_SID_KEY 0 -#define UPH_PFC_KEY 1 -#define UPH_PDI_KEY 2 - -static hash_index_t pos_hash(unsigned long key[]) -{ - service_id_t service_id = (service_id_t)key[UPH_SID_KEY]; - fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY]; - unsigned pdi = (unsigned)key[UPH_PDI_KEY]; - - hash_index_t h; - - /* - * The least significant half of all bits are the least significant bits - * of the parent node's first cluster. - * - * The least significant half of the most significant half of all bits - * are the least significant bits of the node's dentry index within the - * parent directory node. - * - * The most significant half of the most significant half of all bits - * are the least significant bits of the device handle. - */ - h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1); - h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << - (UPH_BUCKETS_LOG / 2); - h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << - (3 * (UPH_BUCKETS_LOG / 4)); - - return h; -} - -static int pos_compare(unsigned long key[], hash_count_t keys, 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; -} - -static void pos_remove_callback(link_t *item) -{ - /* nothing to do */ -} - -static hash_table_operations_t uph_ops = { +} 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; +} + +static hash_table_ops_t uph_ops = { .hash = pos_hash, - .compare = pos_compare, - .remove_callback = pos_remove_callback, + .key_hash = pos_key_hash, + .key_equal = pos_key_equal, + .equal = 0, + .remove_callback = 0, }; @@ -187,54 +166,41 @@ static hash_table_t ui_hash; -#define UIH_BUCKETS_LOG 12 -#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG) - -#define UIH_SID_KEY 0 -#define UIH_INDEX_KEY 1 - -static hash_index_t idx_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]; - - hash_index_t h; - - h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1); - h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) << - (UIH_BUCKETS_LOG / 2); - - return h; -} - -static int idx_compare(unsigned long key[], hash_count_t keys, 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); } -static hash_table_operations_t uih_ops = { +static hash_table_ops_t uih_ops = { .hash = idx_hash, - .compare = idx_compare, + .key_hash = idx_key_hash, + .key_equal = idx_key_equal, + .equal = 0, .remove_callback = idx_remove_callback, }; @@ -377,6 +343,4 @@ } - link_initialize(&fidx->uph_link); - link_initialize(&fidx->uih_link); fibril_mutex_initialize(&fidx->lock); fidx->service_id = service_id; @@ -401,10 +365,5 @@ } - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id, - [UIH_INDEX_KEY] = fidx->index, - }; - - hash_table_insert(&ui_hash, ikey, &fidx->uih_link); + hash_table_insert(&ui_hash, &fidx->uih_link); fibril_mutex_lock(&fidx->lock); fibril_mutex_unlock(&used_lock); @@ -418,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; @@ -438,14 +397,9 @@ } - unsigned long ikey[] = { - [UIH_SID_KEY] = service_id, - [UIH_INDEX_KEY] = fidx->index, - }; - fidx->pfc = pfc; fidx->pdi = pdi; - hash_table_insert(&up_hash, pkey, &fidx->uph_link); - hash_table_insert(&ui_hash, ikey, &fidx->uih_link); + hash_table_insert(&up_hash, &fidx->uph_link); + hash_table_insert(&ui_hash, &fidx->uih_link); } fibril_mutex_lock(&fidx->lock); @@ -457,12 +411,6 @@ void fat_idx_hashin(fat_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_insert(&up_hash, pkey, &idx->uph_link); + fibril_mutex_lock(&used_lock); + hash_table_insert(&up_hash, &idx->uph_link); fibril_mutex_unlock(&used_lock); } @@ -470,12 +418,6 @@ void fat_idx_hashout(fat_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); } @@ -485,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); } @@ -508,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); @@ -523,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(). */ } @@ -532,7 +472,7 @@ int fat_idx_init(void) { - if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops)) + if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) return ENOMEM; - if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) { + if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) { hash_table_destroy(&up_hash); return ENOMEM; @@ -544,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); @@ -568,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. @@ -583,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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/locfs/locfs_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -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,28 +71,33 @@ static FIBRIL_MUTEX_INITIALIZE(services_mutex); -#define SERVICES_KEYS 1 -#define SERVICES_KEY_HANDLE 0 -#define SERVICES_BUCKETS 256 - /* Implementation of hash table interface for the nodes hash table. */ -static hash_index_t services_hash(unsigned long key[]) -{ - return key[SERVICES_KEY_HANDLE] % SERVICES_BUCKETS; -} - -static int services_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - 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 hash_table_operations_t services_ops = { + +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)); +} + +static hash_table_ops_t services_ops = { .hash = services_hash, - .compare = services_compare, + .key_hash = services_key_hash, + .key_equal = services_key_equal, + .equal = 0, .remove_callback = services_remove_callback }; @@ -229,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)); @@ -256,5 +257,5 @@ * below. */ - hash_table_insert(&services, key, &dev->link); + hash_table_insert(&services, &dev->link); /* @@ -279,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); @@ -288,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) { @@ -450,6 +451,5 @@ bool locfs_init(void) { - if (!hash_table_create(&services, SERVICES_BUCKETS, - SERVICES_KEYS, &services_ops)) + if (!hash_table_create(&services, 0, 0, &services_ops)) return false; @@ -555,10 +555,7 @@ /* Device node */ - unsigned long key[] = { - [SERVICES_KEY_HANDLE] = (unsigned long) index - }; - fibril_mutex_lock(&services_mutex); - link_t *lnk = hash_table_find(&services, key); + service_id_t service_index = index; + ht_link_t *lnk = hash_table_find(&services, &service_index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -566,5 +563,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); @@ -621,10 +618,8 @@ 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); + service_id_t service_index = index; + ht_link_t *lnk = hash_table_find(&services, &service_index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -632,5 +627,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); @@ -691,10 +686,8 @@ 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); + service_id_t service_index = index; + ht_link_t *lnk = hash_table_find(&services, &service_index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -702,5 +695,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--; @@ -708,5 +701,6 @@ if (dev->refcount == 0) { async_hangup(dev->sess); - hash_table_remove(&services, key, SERVICES_KEYS); + service_id_t service_index = index; + hash_table_remove(&services, &service_index); } @@ -732,10 +726,8 @@ 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); + service_id_t service_index = index; + ht_link_t *lnk = hash_table_find(&services, &service_index); if (lnk == NULL) { fibril_mutex_unlock(&services_mutex); @@ -743,5 +735,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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/mfs/mfs.h (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/mfs/mfs_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -35,10 +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 -#define OPEN_NODES_BUCKETS 256 static bool check_magic_number(uint16_t magic, bool *native, @@ -61,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 hash_index_t open_nodes_hash(unsigned long key[]); -static int open_nodes_compare(unsigned long key[], hash_count_t keys, - link_t *item); -static void open_nodes_remove_cb(link_t *link); static int mfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index); @@ -95,38 +88,40 @@ /* Hash table interface for open nodes hash table */ -static hash_index_t -open_nodes_hash(unsigned long key[]) -{ - /* TODO: This is very simple and probably can be improved */ - return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS; -} - -static int -open_nodes_compare(unsigned long key[], hash_count_t keys, - link_t *item) -{ - struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link); - assert(keys > 0); - if (mnode->instance->service_id != - ((service_id_t) key[OPEN_NODES_SERVICE_KEY])) { - return false; - } - if (keys == 1) { - return true; - } - assert(keys == 2); - return (mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]); -} - -static void -open_nodes_remove_cb(link_t *link) -{ - /* We don't use remove callback for this hash table */ -} - -static hash_table_operations_t open_nodes_ops = { + +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) +{ + 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_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, - .compare = open_nodes_compare, - .remove_callback = open_nodes_remove_cb, + .key_hash = open_nodes_key_hash, + .key_equal = open_nodes_key_equal, + .equal = 0, + .remove_callback = 0, }; @@ -134,6 +129,5 @@ mfs_global_init(void) { - if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS, - OPEN_NODES_KEYS, &open_nodes_ops)) { + if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) { return ENOMEM; } @@ -406,13 +400,6 @@ mnode->refcnt = 1; - link_initialize(&mnode->link); - - unsigned long key[] = { - [OPEN_NODES_SERVICE_KEY] = inst->service_id, - [OPEN_NODES_INODE_KEY] = inum, - }; - fibril_mutex_lock(&open_nodes_lock); - hash_table_insert(&open_nodes, key, &mnode->link); + hash_table_insert(&open_nodes, &mnode->link); fibril_mutex_unlock(&open_nodes_lock); inst->open_nodes_cnt++; @@ -513,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--; @@ -576,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++; @@ -614,5 +598,4 @@ mnode->ino_i = ino_i; mnode->refcnt = 1; - link_initialize(&mnode->link); mnode->instance = inst; @@ -621,5 +604,5 @@ *rfn = node; - hash_table_insert(&open_nodes, key, &mnode->link); + hash_table_insert(&open_nodes, &mnode->link); inst->open_nodes_cnt++; Index: uspace/srv/fs/tmpfs/tmpfs.h =================================================================== --- uspace/srv/fs/tmpfs/tmpfs.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/tmpfs/tmpfs.h (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/fs/tmpfs/tmpfs_ops.c (revision 062d9000625057300f609429080872d6492b542e) @@ -50,4 +50,5 @@ #include #include +#include #include #include @@ -55,6 +56,4 @@ #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b)) - -#define NODES_BUCKETS 256 /** All root nodes have index 0. */ @@ -142,35 +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 hash_index_t nodes_hash(unsigned long key[]) -{ - return key[NODES_KEY_INDEX] % NODES_BUCKETS; -} - -static int nodes_compare(unsigned long key[], hash_count_t keys, 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)) { @@ -192,7 +192,9 @@ /** TMPFS nodes hash table operations. */ -hash_table_operations_t nodes_ops = { +hash_table_ops_t nodes_ops = { .hash = nodes_hash, - .compare = nodes_compare, + .key_hash = nodes_key_hash, + .key_equal = nodes_key_equal, + .equal = 0, .remove_callback = nodes_remove_callback }; @@ -207,5 +209,4 @@ nodep->size = 0; nodep->data = NULL; - link_initialize(&nodep->nh_link); list_initialize(&nodep->cs_list); } @@ -220,5 +221,5 @@ bool tmpfs_init(void) { - if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops)) + if (!hash_table_create(&nodes, 0, 0, &nodes_ops)) return false; @@ -238,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); } @@ -272,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 { @@ -331,9 +335,5 @@ /* Insert the new node into the nodes hash table. */ - unsigned long key[] = { - [NODES_KEY_DEV] = nodep->service_id, - [NODES_KEY_INDEX] = nodep->index - }; - hash_table_insert(&nodes, key, &nodep->nh_link); + hash_table_insert(&nodes, &nodep->nh_link); *rfn = FS_NODE(nodep); return EOK; @@ -346,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); /* @@ -476,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); /* @@ -538,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); /* @@ -600,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) @@ -636,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/gsp.c =================================================================== --- uspace/srv/hid/input/gsp.c (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/hid/input/gsp.c (revision 062d9000625057300f609429080872d6492b542e) @@ -50,24 +50,45 @@ #include +#include #include #include #include "gsp.h" -#define TRANS_TABLE_CHAINS 256 - /* - * Hash table operations for the transition function. - */ - -static hash_index_t trans_op_hash(unsigned long key[]); -static int trans_op_compare(unsigned long key[], hash_count_t keys, - link_t *item); -static void trans_op_remove_callback(link_t *item); - -static hash_table_operations_t trans_ops = { - .hash = trans_op_hash, - .compare = trans_op_compare, - .remove_callback = trans_op_remove_callback + * 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_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); @@ -75,9 +96,9 @@ static gsp_trans_t *trans_new(void); -/** Initialise scancode parser. */ +/** Initialize scancode parser. */ void gsp_init(gsp_t *p) { p->states = 1; - hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops); + hash_table_create(&p->trans, 0, 0, &trans_ops); } @@ -223,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); } @@ -242,10 +264,5 @@ static void trans_insert(gsp_t *p, gsp_trans_t *t) { - unsigned long key[2]; - - key[0] = t->old_state; - key[1] = t->input; - - hash_table_insert(&p->trans, key, &t->link); + hash_table_insert(&p->trans, &t->link); } @@ -264,26 +281,4 @@ } -/* - * Transition function hash table operations. - */ - -static hash_index_t trans_op_hash(unsigned long key[]) -{ - return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS; -} - -static int trans_op_compare(unsigned long key[], hash_count_t keys, - link_t *item) -{ - gsp_trans_t *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)); -} - -static void trans_op_remove_callback(link_t *item) -{ -} /** Index: uspace/srv/hid/input/gsp.h =================================================================== --- uspace/srv/hid/input/gsp.h (revision 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/hid/input/gsp.h (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/ns/service.c (revision 062d9000625057300f609429080872d6492b542e) @@ -40,9 +40,8 @@ #include "ns.h" -#define SERVICE_HASH_TABLE_CHAINS 20 /** 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. */ @@ -50,63 +49,29 @@ } 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 hash_index_t service_hash(unsigned long key[]) + +static size_t service_key_hash(void *key) { - assert(key); - return (key[0] % SERVICE_HASH_TABLE_CHAINS); + return *(sysarg_t*)key; } -/** 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 int service_compare(unsigned long key[], hash_count_t keys, link_t *item) +static size_t service_hash(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); + hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link); + return 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) +static bool service_key_equal(void *key, const ht_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; } /** Operations for service hash table. */ -static hash_table_operations_t service_hash_table_ops = { +static hash_table_ops_t service_hash_table_ops = { .hash = service_hash, - .compare = service_compare, - .remove_callback = service_remove + .key_hash = service_key_hash, + .key_equal = service_key_equal, + .equal = 0, + .remove_callback = 0 }; @@ -127,6 +92,5 @@ int service_init(void) { - if (!hash_table_create(&service_hash_table, SERVICE_HASH_TABLE_CHAINS, - 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; @@ -145,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); @@ -176,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; @@ -189,9 +141,8 @@ return ENOMEM; - link_initialize(&hs->link); hs->service = service; hs->phone = phone; hs->in_phone_hash = call->in_phone_hash; - hash_table_insert(&service_hash_table, keys, &hs->link); + hash_table_insert(&service_hash_table, &hs->link); return EOK; @@ -210,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) { @@ -239,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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/ns/task.c (revision 062d9000625057300f609429080872d6492b542e) @@ -43,6 +43,4 @@ #include "ns.h" -#define TASK_HASH_TABLE_CHAINS 256 -#define P2I_HASH_TABLE_CHAINS 256 /* TODO: @@ -55,5 +53,5 @@ /** Task hash table item. */ typedef struct { - link_t link; + ht_link_t link; task_id_t id; /**< Task ID. */ @@ -63,57 +61,34 @@ } 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 hash_index_t task_hash(unsigned long key[]) -{ - assert(key); - return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS); -} - -/** 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 int task_compare(unsigned long key[], hash_count_t keys, link_t *item) -{ - assert(key); - assert(keys <= 2); - assert(item); - - hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link); - - if (keys == 2) - return ((LOWER32(key[1]) == UPPER32(ht->id)) - && (LOWER32(key[0]) == LOWER32(ht->id))); - else - return (LOWER32(key[0]) == LOWER32(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)); } /** Operations for task hash table. */ -static hash_table_operations_t task_hash_table_ops = { +static hash_table_ops_t task_hash_table_ops = { .hash = task_hash, - .compare = task_compare, + .key_hash = task_key_hash, + .key_equal = task_key_equal, + .equal = 0, .remove_callback = task_remove }; @@ -123,57 +98,48 @@ 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 hash_index_t p2i_hash(unsigned long key[]) -{ - assert(key); - return (key[0] % TASK_HASH_TABLE_CHAINS); -} - -/** 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 int p2i_compare(unsigned long key[], hash_count_t keys, 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)); } /** Operations for task hash table. */ -static hash_table_operations_t p2i_ops = { +static hash_table_ops_t p2i_ops = { .hash = p2i_hash, - .compare = p2i_compare, + .key_hash = p2i_key_hash, + .key_equal = p2i_key_equal, + .equal = 0, .remove_callback = p2i_remove }; @@ -193,12 +159,10 @@ int task_init(void) { - if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS, - 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, P2I_HASH_TABLE_CHAINS, - 1, &p2i_ops)) { + if (!hash_table_create(&phone_to_id, 0, 0, &p2i_ops)) { printf(NAME ": No memory available for tasks\n"); return ENOMEM; @@ -218,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; @@ -238,5 +197,5 @@ } - hash_table_remove(&task_hash_table, keys, 2); + hash_table_remove(&task_hash_table, &pr->id); list_remove(cur); free(pr); @@ -250,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) { @@ -281,5 +235,5 @@ } - hash_table_remove(&task_hash_table, keys, 2); + hash_table_remove_item(&task_hash_table, link); retval = EOK; @@ -293,10 +247,8 @@ int ns_task_id_intro(ipc_call_t *call) { - unsigned long keys[2]; task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call)); - keys[0] = 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; @@ -314,8 +266,7 @@ */ - link_initialize(&entry->link); entry->in_phone_hash = call->in_phone_hash; entry->id = id; - hash_table_insert(&phone_to_id, keys, &entry->link); + hash_table_insert(&phone_to_id, &entry->link); /* @@ -323,13 +274,9 @@ */ - keys[0] = LOWER32(id); - keys[1] = UPPER32(id); - - link_initialize(&ht->link); ht->id = id; ht->finished = false; ht->have_rval = false; ht->retval = -1; - hash_table_insert(&task_hash_table, keys, &ht->link); + hash_table_insert(&task_hash_table, &ht->link); return EOK; @@ -338,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; @@ -357,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)) @@ -378,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); @@ -386,16 +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); - hashed_task_t *ht = - hash_table_get_instance(link, hashed_task_t, link); - if (ht == NULL) + ht_link_t *link = hash_table_find(&task_hash_table, &id); + if (link == NULL) return EOK; + + 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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/vfs/vfs.h (revision 062d9000625057300f609429080872d6492b542e) @@ -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 87e93921044e3d8ca9b62feaa3b112e35abbaa13) +++ uspace/srv/vfs/vfs_node.c (revision 062d9000625057300f609429080872d6492b542e) @@ -41,4 +41,5 @@ #include #include +#include #include #include @@ -58,13 +59,16 @@ #define KEY_INDEX 2 -static hash_index_t nodes_hash(unsigned long []); -static int nodes_compare(unsigned long [], hash_count_t, link_t *); -static void nodes_remove_callback(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. */ -hash_table_operations_t nodes_ops = { +hash_table_ops_t nodes_ops = { .hash = nodes_hash, - .compare = nodes_compare, - .remove_callback = nodes_remove_callback + .key_hash = nodes_key_hash, + .key_equal = nodes_key_equal, + .equal = 0, + .remove_callback = 0, }; @@ -75,5 +79,5 @@ bool vfs_nodes_init(void) { - return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops); + return hash_table_create(&nodes, 0, 0, &nodes_ops); } @@ -114,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; @@ -158,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); @@ -182,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)); @@ -205,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, key, &node->nh_link); + 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) { @@ -240,24 +226,4 @@ } -hash_index_t nodes_hash(unsigned long key[]) -{ - hash_index_t a = key[KEY_FS_HANDLE] << (NODES_BUCKETS_LOG / 4); - hash_index_t b = (a | key[KEY_DEV_HANDLE]) << (NODES_BUCKETS_LOG / 2); - - return (b | key[KEY_INDEX]) & (NODES_BUCKETS - 1); -} - -int nodes_compare(unsigned long key[], hash_count_t keys, 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]); -} - -void nodes_remove_callback(link_t *item) -{ -} - struct refcnt_data { /** Sum of all reference counts for this file system instance. */ @@ -267,7 +233,7 @@ }; -static void 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; @@ -275,4 +241,6 @@ (node->service_id == rd->service_id)) rd->refcnt += node->refcnt; + + return true; } @@ -315,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; +} + /** * @}