[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.
 */
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.
 */
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.
 *
 * Returns 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).
 *
 * Returns 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.
 *
 * Returns the node added upon success.
 * Returns 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	*/
	80	struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
	81	cds_lfht_compare_fct compare_fct,
	82	unsigned long hash_seed,
	83	unsigned long init_size,
	84	void (cds_lfht_call_rcu)(struct rcu_head head,
	85	void (func)(struct rcu_head head)));
	86
	87	/*
	88	* cds_lfht_destroy - destroy a hash table.
	89	*/
	90	int cds_lfht_destroy(struct cds_lfht *ht);
	91
	92	/*
	93	* cds_lfht_count_nodes - count the number of nodes in the hash table.
	94	*
	95	* Call with rcu_read_lock held.
	96	*/
	97	void cds_lfht_count_nodes(struct cds_lfht *ht,
	98	unsigned long *count,
	99	unsigned long *removed);
	100
	101	/*
	102	* cds_lfht_lookup - lookup a node by key.
	103	*
	104	* Returns NULL if not found.
	105	* Call with rcu_read_lock held.
	106	*/
	107	struct cds_lfht_node cds_lfht_lookup(struct cds_lfht ht, void *key, size_t key_len);
	108
	109	/*
	110	* cds_lfht_next - get the next item with same key (after a lookup).
	111	*
	112	* Returns NULL if no following node exists with same key.
	113	* RCU read-side lock must be held across cds_lfht_lookup and cds_lfht_next calls, and also
	114	* between cds_lfht_next calls using the node returned by a previous cds_lfht_next.
	115	* Call with rcu_read_lock held.
	116	*/
	117	struct cds_lfht_node cds_lfht_next(struct cds_lfht ht, struct cds_lfht_node *node);
	118
	119	/*
	120	* cds_lfht_add - add a node to the hash table.
	121	*
	122	* Call with rcu_read_lock held.
	123	*/
	124	void cds_lfht_add(struct cds_lfht ht, struct cds_lfht_node node);
	125
	126	/*
	127	* cds_lfht_add_unique - add a node to hash table, if key is not present.
	128	*
	129	* Returns the node added upon success.
	130	* Returns the unique node already present upon failure. If cds_lfht_add_unique fails,
	131	* the node passed as parameter should be freed by the caller.
	132	* Call with rcu_read_lock held.
	133	*/
	134	struct cds_lfht_node cds_lfht_add_unique(struct cds_lfht ht, struct cds_lfht_node *node);
	135
	136	/*
	137	* cds_lfht_remove - remove node from hash table.
	138	*
	139	* Node can be looked up with cds_lfht_lookup. RCU read-side lock must be held between
	140	* lookup and removal.
	141	* Call with rcu_read_lock held.
	142	*/
	143	int cds_lfht_remove(struct cds_lfht ht, struct cds_lfht_node node);
	144
	145	/*
	146	* cds_lfht_resize - Force a hash table resize
	147	* @growth: growth order (current size is multiplied by 2^growth)
	148	*
	149	* Currently, only expand operation is supported (growth >= 0).
	150	*/
	151	void cds_lfht_resize(struct cds_lfht *ht, int growth);
	152
	153	#ifdef __cplusplus
	154	}
	155	#endif
	156
	157	#endif /* _URCU_RCULFHASH_H */