[urcu.git] / urcu / rculfhash.h

#ifndef _URCU_RCULFHASH_H
#define _URCU_RCULFHASH_H

/*
 * urcu/rculfhash.h
 *
 * Userspace RCU library - Lock-Free RCU Hash Table
 *
 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <stdint.h>
#include <urcu-call-rcu.h>

#ifdef __cplusplus
extern "C" {
#endif

/*
 * struct cds_lfht_node and struct _cds_lfht_node should be aligned on
 * 4-bytes boundaries because the two lower bits are used as flags.
 */

struct _cds_lfht_node {
	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
	unsigned long reverse_hash;
};

struct cds_lfht_node {
	/* cache-hot for iteration */
	struct _cds_lfht_node p;          /* needs to be first field */
	void *key;
	unsigned int key_len;
	/* cache-cold for iteration */
	struct rcu_head head;
};

struct cds_lfht;

/*
 * Caution !
 * 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 unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
					void *key2, size_t key2_len);

/*
 * cds_lfht_node_init - initialize a hash table node
 */
static inline
void cds_lfht_node_init(struct cds_lfht_node *node, void *key,
			size_t key_len)
{
	node->key = key;
	node->key_len = key_len;
}

/*
 * cds_lfht_new - allocate a hash table.
 *
 * init_size must be power of two.
 * Return NULL on error.
 */
struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
			cds_lfht_compare_fct compare_fct,
			unsigned long hash_seed,
			unsigned long init_size,
			void (*cds_lfht_call_rcu)(struct rcu_head *head,
				void (*func)(struct rcu_head *head)));

/*
 * cds_lfht_destroy - destroy a hash table.
 *
 * Return 0 on success, negative error value on error.
 */
int cds_lfht_destroy(struct cds_lfht *ht);

/*
 * cds_lfht_count_nodes - count the number of nodes in the hash table.
 *
 * Call with rcu_read_lock held.
 */
void cds_lfht_count_nodes(struct cds_lfht *ht,
			unsigned long *count,
			unsigned long *removed);

/*
 * cds_lfht_lookup - lookup a node by key.
 *
 * Return NULL if not found.
 * Call with rcu_read_lock held.
 */
struct cds_lfht_node *cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len);

/*
 * cds_lfht_next - get the next item with same key (after a lookup).
 *
 * Return NULL if no following node exists with same key.
 * RCU read-side lock must be held across cds_lfht_lookup and cds_lfht_next calls, and also
 * between cds_lfht_next calls using the node returned by a previous cds_lfht_next.
 * Call with rcu_read_lock held.
 */
struct cds_lfht_node *cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_node *node);

/*
 * cds_lfht_add - add a node to the hash table.
 *
 * Call with rcu_read_lock held.
 */
void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);

/*
 * cds_lfht_add_unique - add a node to hash table, if key is not present.
 *
 * Return the node added upon success.
 * Return the unique node already present upon failure. If cds_lfht_add_unique fails,
 * the node passed as parameter should be freed by the caller.
 * Call with rcu_read_lock held.
 */
struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, struct cds_lfht_node *node);

/*
 * cds_lfht_remove - remove node from hash table.
 *
 * Node can be looked up with cds_lfht_lookup. RCU read-side lock must be held between
 * lookup and removal.
 * Call with rcu_read_lock held.
 */
int cds_lfht_remove(struct cds_lfht *ht, struct cds_lfht_node *node);

/*
 * cds_lfht_resize - Force a hash table resize
 * @growth: growth order (current size is multiplied by 2^growth)
 *
 * Currently, only expand operation is supported (growth >= 0).
 */
void cds_lfht_resize(struct cds_lfht *ht, int growth);

#ifdef __cplusplus
}
#endif

#endif /* _URCU_RCULFHASH_H */
Commit	Line	Data
	1	#ifndef _URCU_RCULFHASH_H
	2	#define _URCU_RCULFHASH_H
	3
	4	/*
	5	* urcu/rculfhash.h
	6	*
	7	* Userspace RCU library - Lock-Free RCU Hash Table
	8	*
	9	* Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	10	*
	11	* This library is free software; you can redistribute it and/or
	12	* modify it under the terms of the GNU Lesser General Public
	13	* License as published by the Free Software Foundation; either
	14	* version 2.1 of the License, or (at your option) any later version.
	15	*
	16	* This library is distributed in the hope that it will be useful,
	17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	19	* Lesser General Public License for more details.
	20	*
	21	* You should have received a copy of the GNU Lesser General Public
	22	* License along with this library; if not, write to the Free Software
	23	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	24	*/
	25
	26	#include <stdint.h>
	27	#include <urcu-call-rcu.h>
	28
	29	#ifdef __cplusplus
	30	extern "C" {
	31	#endif
	32
	33	/*
	34	* struct cds_lfht_node and struct _cds_lfht_node should be aligned on
	35	* 4-bytes boundaries because the two lower bits are used as flags.
	36	*/
	37
	38	struct _cds_lfht_node {
	39	struct cds_lfht_node next; / ptr \| DUMMY_FLAG \| REMOVED_FLAG */
	40	unsigned long reverse_hash;
	41	};
	42
	43	struct cds_lfht_node {
	44	/* cache-hot for iteration */
	45	struct _cds_lfht_node p; /* needs to be first field */
	46	void *key;
	47	unsigned int key_len;
	48	/* cache-cold for iteration */
	49	struct rcu_head head;
	50	};
	51
	52	struct cds_lfht;
	53
	54	/*
	55	* Caution !
	56	* Ensure reader and writer threads are registered as urcu readers.
	57	*/
	58
	59	typedef unsigned long (cds_lfht_hash_fct)(void key, size_t length,
	60	unsigned long seed);
	61	typedef unsigned long (cds_lfht_compare_fct)(void key1, size_t key1_len,
	62	void *key2, size_t key2_len);
	63
	64	/*
	65	* cds_lfht_node_init - initialize a hash table node
	66	*/
	67	static inline
	68	void cds_lfht_node_init(struct cds_lfht_node node, void key,
	69	size_t key_len)
	70	{
	71	node->key = key;
	72	node->key_len = key_len;
	73	}
	74
	75	/*
	76	* cds_lfht_new - allocate a hash table.
	77	*
	78	* init_size must be power of two.
	79	* Return NULL on error.
	80	*/
	81	struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
	82	cds_lfht_compare_fct compare_fct,
	83	unsigned long hash_seed,
	84	unsigned long init_size,
	85	void (cds_lfht_call_rcu)(struct rcu_head head,
	86	void (func)(struct rcu_head head)));
	87
	88	/*
	89	* cds_lfht_destroy - destroy a hash table.
	90	*
	91	* Return 0 on success, negative error value on error.
	92	*/
	93	int cds_lfht_destroy(struct cds_lfht *ht);
	94
	95	/*
	96	* cds_lfht_count_nodes - count the number of nodes in the hash table.
	97	*
	98	* Call with rcu_read_lock held.
	99	*/
	100	void cds_lfht_count_nodes(struct cds_lfht *ht,
	101	unsigned long *count,
	102	unsigned long *removed);
	103
	104	/*
	105	* cds_lfht_lookup - lookup a node by key.
	106	*
	107	* Return NULL if not found.
	108	* Call with rcu_read_lock held.
	109	*/
	110	struct cds_lfht_node cds_lfht_lookup(struct cds_lfht ht, void *key, size_t key_len);
	111
	112	/*
	113	* cds_lfht_next - get the next item with same key (after a lookup).
	114	*
	115	* Return NULL if no following node exists with same key.
	116	* RCU read-side lock must be held across cds_lfht_lookup and cds_lfht_next calls, and also
	117	* between cds_lfht_next calls using the node returned by a previous cds_lfht_next.
	118	* Call with rcu_read_lock held.
	119	*/
	120	struct cds_lfht_node cds_lfht_next(struct cds_lfht ht, struct cds_lfht_node *node);
	121
	122	/*
	123	* cds_lfht_add - add a node to the hash table.
	124	*
	125	* Call with rcu_read_lock held.
	126	*/
	127	void cds_lfht_add(struct cds_lfht ht, struct cds_lfht_node node);
	128
	129	/*
	130	* cds_lfht_add_unique - add a node to hash table, if key is not present.
	131	*
	132	* Return the node added upon success.
	133	* Return the unique node already present upon failure. If cds_lfht_add_unique fails,
	134	* the node passed as parameter should be freed by the caller.
	135	* Call with rcu_read_lock held.
	136	*/
	137	struct cds_lfht_node cds_lfht_add_unique(struct cds_lfht ht, struct cds_lfht_node *node);
	138
	139	/*
	140	* cds_lfht_remove - remove node from hash table.
	141	*
	142	* Node can be looked up with cds_lfht_lookup. RCU read-side lock must be held between
	143	* lookup and removal.
	144	* Call with rcu_read_lock held.
	145	*/
	146	int cds_lfht_remove(struct cds_lfht ht, struct cds_lfht_node node);
	147
	148	/*
	149	* cds_lfht_resize - Force a hash table resize
	150	* @growth: growth order (current size is multiplied by 2^growth)
	151	*
	152	* Currently, only expand operation is supported (growth >= 0).
	153	*/
	154	void cds_lfht_resize(struct cds_lfht *ht, int growth);
	155
	156	#ifdef __cplusplus
	157	}
	158	#endif
	159
	160	#endif /* _URCU_RCULFHASH_H */