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; +} + /** * @}