X-Git-Url: http://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Frculfhash.h;h=6953ad12499b515819b73e56808106fdf55926e1;hp=a1ae0f5a8fef9e80e39d8f21750005b565810cd7;hb=747d725c1dd45d5072e0e411642c4d5c6403b4be;hpb=04db56f85e2cd2abb05e4ef14990e99a1058d0df diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index a1ae0f5..6953ad1 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -7,6 +7,7 @@ * Userspace RCU library - Lock-Free RCU Hash Table * * Copyright 2011 - Mathieu Desnoyers + * Copyright 2011 - Lai Jiangshan * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -26,13 +27,13 @@ */ #include +#include #include #ifdef __cplusplus extern "C" { #endif - /* * cds_lfht_node: Contains the next pointers and reverse-hash * value required for lookup and traversal of the hash table. @@ -49,7 +50,7 @@ extern "C" { * of the hash value for cds_lfht APIs. */ struct cds_lfht_node { - struct cds_lfht_node *next; /* ptr | DUMMY_FLAG | REMOVED_FLAG */ + struct cds_lfht_node *next; /* ptr | BUCKET_FLAG | REMOVED_FLAG */ unsigned long reverse_hash; } __attribute__((aligned(4))); @@ -71,9 +72,7 @@ struct cds_lfht; * Ensure reader and writer threads are registered as urcu readers. */ -typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length, - unsigned long seed); -typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, void *key); +typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, const void *key); /* * cds_lfht_node_init - initialize a hash table node @@ -99,7 +98,8 @@ enum { * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly. */ struct cds_lfht *_cds_lfht_new(unsigned long init_size, - unsigned long min_alloc_size, + unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets, int flags, void (*cds_lfht_call_rcu)(struct rcu_head *head, void (*func)(struct rcu_head *head)), @@ -114,11 +114,16 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size, /* * cds_lfht_new - allocate a hash table. - * @init_size: number of nodes to allocate initially. Must be power of two. - * @min_alloc_size: the smallest allocation size to use. Must be power of two. + * @init_size: number of buckets to allocate initially. Must be power of two. + * @min_nr_alloc_buckets: the minimum number of allocated buckets. + * (must be power of two) + * @max_nr_buckets: the maximum number of hash table buckets allowed. + * (must be power of two) * @flags: hash table creation flags (can be combined with bitwise or: '|'). * 0: no flags. * CDS_LFHT_AUTO_RESIZE: automatically resize hash table. + * CDS_LFHT_ACCOUNTING: count the number of node addition + * and removal in the table * @attr: optional resize worker thread attributes. NULL for default. * * Return NULL on error. @@ -131,15 +136,17 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size, * this priority level. Having lower priority for call_rcu and resize threads * does not pose any correctness issue, but the resize operations could be * starved by updates, thus leading to long hash table bucket chains. - * Threads calling this API need to be registered RCU read-side threads. + * Threads calling this API are NOT required to be registered RCU read-side + * threads. It can be called very early.(before rcu is initialized ...etc.) */ static inline struct cds_lfht *cds_lfht_new(unsigned long init_size, - unsigned long min_alloc_size, + unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets, int flags, pthread_attr_t *attr) { - return _cds_lfht_new(init_size, min_alloc_size, flags, + return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags, call_rcu, synchronize_rcu, rcu_read_lock, rcu_read_unlock, rcu_thread_offline, rcu_thread_online, rcu_register_thread, @@ -179,15 +186,17 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, /* * cds_lfht_lookup - lookup a node by key. * @ht: the hash table. - * @match: the key match function. * @hash: the key hash. + * @match: the key match function. + * @key: the current node key. * @iter: Node, if found (output). *iter->node set to NULL if not found. * * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ -void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match, - unsigned long hash, void *key, struct cds_lfht_iter *iter); +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash, + cds_lfht_match_fct match, const void *key, + struct cds_lfht_iter *iter); /* * cds_lfht_next_duplicate - get the next item with same key (after a lookup). @@ -206,7 +215,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match, * Threads calling this API need to be registered RCU read-side threads. */ void cds_lfht_next_duplicate(struct cds_lfht *ht, - cds_lfht_match_fct match, void *key, + cds_lfht_match_fct match, const void *key, struct cds_lfht_iter *iter); /* @@ -248,9 +257,9 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, /* * cds_lfht_add_unique - add a node to hash table, if key is not present. * @ht: the hash table. + * @hash: the node's hash. * @match: the key match function. * @key: the node's key. - * @hash: the node's hash. * @node: the node to try adding. * * Return the node added upon success. @@ -266,17 +275,17 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, * add_unique and add_replace (see below). */ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, - cds_lfht_match_fct match, - void *key, unsigned long hash, + cds_lfht_match_fct match, + const void *key, struct cds_lfht_node *node); /* * cds_lfht_add_replace - replace or add a node within hash table. * @ht: the hash table. + * @hash: the node's hash. * @match: the key match function. * @key: the node's key. - * @hash: the node's hash. * @node: the node to add. * * Return the node replaced upon success. If no node matching the key @@ -298,9 +307,9 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, * will never generate duplicated keys. */ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, - cds_lfht_match_fct match, - void *key, unsigned long hash, + cds_lfht_match_fct match, + const void *key, struct cds_lfht_node *node); /* @@ -362,6 +371,43 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter); */ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size); +/* + * Note: cds_lfht_for_each are safe for element removal during + * iteration. + */ +#define cds_lfht_for_each(ht, iter, node) \ + for (cds_lfht_first(ht, iter), \ + node = cds_lfht_iter_get_node(iter); \ + node != NULL; \ + cds_lfht_next(ht, iter), \ + node = cds_lfht_iter_get_node(iter)) + +#define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node) \ + for (cds_lfht_lookup(ht, hash, match, key, iter), \ + node = cds_lfht_iter_get_node(iter); \ + node != NULL; \ + cds_lfht_next_duplicate(ht, match, key, iter), \ + node = cds_lfht_iter_get_node(iter)) + +#define cds_lfht_for_each_entry(ht, iter, pos, member) \ + for (cds_lfht_first(ht, iter), \ + pos = caa_container_of(cds_lfht_iter_get_node(iter), \ + typeof(*(pos)), member); \ + &(pos)->member != NULL; \ + cds_lfht_next(ht, iter), \ + pos = caa_container_of(cds_lfht_iter_get_node(iter), \ + typeof(*(pos)), member)) + +#define cds_lfht_for_each_entry_duplicate(ht, hash, match, key, \ + iter, pos, member) \ + for (cds_lfht_lookup(ht, hash, match, key, iter), \ + pos = caa_container_of(cds_lfht_iter_get_node(iter), \ + typeof(*(pos)), member); \ + &(pos)->member != NULL; \ + cds_lfht_next_duplicate(ht, match, key, iter), \ + pos = caa_container_of(cds_lfht_iter_get_node(iter), \ + typeof(*(pos)), member)) + #ifdef __cplusplus } #endif