X-Git-Url: http://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Frculfhash.h;h=004c20817b8585e1cecc21f37068b8725b8a5d43;hp=d242ff6485addffd97d05a8bfbba803681656944;hb=1f67ba508705ff89b0048c9091e94efa938cac71;hpb=0722081a05550337b04be8217208214d30e3c3bf diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index d242ff6..004c208 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -29,6 +29,7 @@ #include #include #include +#include #ifdef __cplusplus extern "C" { @@ -38,8 +39,15 @@ extern "C" { * cds_lfht_node: Contains the next pointers and reverse-hash * value required for lookup and traversal of the hash table. * - * struct cds_lfht_node should be aligned on 4-bytes boundaries because - * the two lower bits are used as flags. + * struct cds_lfht_node should be aligned on 8-bytes boundaries because + * the three lower bits are used as flags. It is worth noting that the + * information contained within these three bits could be represented on + * two bits by re-using the same bit for REMOVAL_OWNER_FLAG and + * BUCKET_FLAG. This can be done if we ensure that no iterator nor + * updater check the BUCKET_FLAG after it detects that the REMOVED_FLAG + * is set. Given the minimum size of struct cds_lfht_node is 8 bytes on + * 32-bit architectures, we choose to go for simplicity and reserve + * three bits. * * struct cds_lfht_node can be embedded into a structure (as a field). * caa_container_of() can be used to get the structure from the struct @@ -50,9 +58,9 @@ extern "C" { * of the hash value for cds_lfht APIs. */ struct cds_lfht_node { - struct cds_lfht_node *next; /* ptr | BUCKET_FLAG | REMOVED_FLAG */ + struct cds_lfht_node *next; /* ptr | REMOVAL_OWNER_FLAG | BUCKET_FLAG | REMOVED_FLAG */ unsigned long reverse_hash; -} __attribute__((aligned(4))); +} __attribute__((aligned(8))); /* cds_lfht_iter: Used to track state while traversing a hash chain. */ struct cds_lfht_iter { @@ -94,27 +102,37 @@ enum { CDS_LFHT_ACCOUNTING = (1U << 1), }; +struct cds_lfht_mm_type { + struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets); + void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order); + void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order); + struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, + unsigned long index); +}; + +extern const struct cds_lfht_mm_type cds_lfht_mm_order; +extern const struct cds_lfht_mm_type cds_lfht_mm_chunk; +extern const struct cds_lfht_mm_type cds_lfht_mm_mmap; + /* * _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_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)), - void (*cds_lfht_synchronize_rcu)(void), - void (*cds_lfht_rcu_read_lock)(void), - void (*cds_lfht_rcu_read_unlock)(void), - void (*cds_lfht_rcu_thread_offline)(void), - void (*cds_lfht_rcu_thread_online)(void), - void (*cds_lfht_rcu_register_thread)(void), - void (*cds_lfht_rcu_unregister_thread)(void), + const struct cds_lfht_mm_type *mm, + const struct rcu_flavor_struct *flavor, pthread_attr_t *attr); /* * cds_lfht_new - allocate a hash table. - * @init_size: number of nodes to allocate initially. Must be power of two. - * @min_nr_alloc_buckets: 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. @@ -138,14 +156,12 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size, static inline struct cds_lfht *cds_lfht_new(unsigned long init_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_nr_alloc_buckets, flags, - call_rcu, synchronize_rcu, rcu_read_lock, - rcu_read_unlock, rcu_thread_offline, - rcu_thread_online, rcu_register_thread, - rcu_unregister_thread, attr); + return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, + flags, NULL, &rcu_flavor, attr); } /* @@ -166,7 +182,6 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr); * @ht: the hash table. * @split_count_before: Sample the node count split-counter before traversal. * @count: Traverse the hash table, count the number of nodes observed. - * @removed: Number of logically removed nodes observed during traversal. * @split_count_after: Sample the node count split-counter after traversal. * * Call with rcu_read_lock held. @@ -175,7 +190,6 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr); void cds_lfht_count_nodes(struct cds_lfht *ht, long *split_count_before, unsigned long *count, - unsigned long *removed, long *split_count_after); /* @@ -200,7 +214,8 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash, * @key: the current node key. * @iter: Node, if found (output). *iter->node set to NULL if not found. * - * Uses an iterator initialized by a lookup. + * Uses an iterator initialized by a lookup. Important: the iterator + * _needs_ to be initialized before calling cds_lfht_next_duplicate. * Sets *iter-node to the following node with same key. * Sets *iter->node to NULL if no following node exists with same key. * RCU read-side lock must be held across cds_lfht_lookup and @@ -308,14 +323,19 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, struct cds_lfht_node *node); /* - * cds_lfht_replace - replace a node pointer to by iter within hash table. + * cds_lfht_replace - replace a node pointed to by iter within hash table. * @ht: the hash table. * @old_iter: the iterator position of the node to replace. - * @now_node: the new node to try using for replacement. + * @hash: the node's hash. + * @match: the key match function. + * @key: the node's key. + * @new_node: the new node to use as replacement. * * Return 0 if replacement is successful, negative value otherwise. - * Replacing a NULL old node or an already removed node will fail with a - * negative value. + * Replacing a NULL old node or an already removed node will fail with + * -ENOENT. + * If the hash or value of the node to replace and the new node differ, + * this function returns -EINVAL without proceeding to the replacement. * Old node can be looked up with cds_lfht_lookup and cds_lfht_next. * RCU read-side lock must be held between lookup and replacement. * Call with rcu_read_lock held. @@ -334,20 +354,24 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, * guarantee that a combination of add_replace and add_unique updates * will never generate duplicated keys. */ -int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter, +int cds_lfht_replace(struct cds_lfht *ht, + struct cds_lfht_iter *old_iter, + unsigned long hash, + cds_lfht_match_fct match, + const void *key, struct cds_lfht_node *new_node); /* * cds_lfht_del - remove node pointed to by iterator from hash table. * @ht: the hash table. - * @iter: the iterator position of the node to delete. + * @node: the node to delete. * * Return 0 if the node is successfully removed, negative value * otherwise. - * Replacing a NULL node or an already removed node will fail with a + * Deleting a NULL node or an already removed node will fail with a * negative value. - * Node can be looked up with cds_lfht_lookup and cds_lfht_next. - * cds_lfht_iter_get_node. + * Node can be looked up with cds_lfht_lookup and cds_lfht_next, + * followed by use of cds_lfht_iter_get_node. * RCU read-side lock must be held between lookup and removal. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. @@ -355,7 +379,21 @@ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter, * freeing the memory reserved for old node (which can be accessed with * cds_lfht_iter_get_node). */ -int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter); +int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node); + +/* + * cds_lfht_is_node_deleted - query if a node is removed from hash table. + * + * Return non-zero if the node is deleted from the hash table, 0 + * otherwise. + * Node can be looked up with cds_lfht_lookup and cds_lfht_next, + * followed by use of cds_lfht_iter_get_node. + * RCU read-side lock must be held between lookup and call to this + * function. + * Call with rcu_read_lock held. + * Threads calling this API need to be registered RCU read-side threads. + */ +int cds_lfht_is_node_deleted(struct cds_lfht_node *node); /* * cds_lfht_resize - Force a hash table resize