[urcu.git] / urcu / rculfhash.h

#ifndef _URCU_RCULFHASH_H
#define _URCU_RCULFHASH_H

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

#ifdef __cplusplus
extern "C" {
#endif

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

struct _rcu_ht_node {
	struct rcu_ht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
	unsigned long reverse_hash;
};

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

struct rcu_ht;

/*
 * Caution !
 * Ensure reader and writer threads are registered as urcu readers.
 */

typedef unsigned long (*ht_hash_fct)(void *key, size_t length,
				     unsigned long seed);
typedef unsigned long (*ht_compare_fct)(void *key1, size_t key1_len,
				        void *key2, size_t key2_len);

static inline
void ht_node_init(struct rcu_ht_node *node, void *key,
		  size_t key_len)
{
	node->key = key;
	node->key_len = key_len;
}

/*
 * init_size must be power of two.
 */
struct rcu_ht *ht_new(ht_hash_fct hash_fct,
		      ht_compare_fct compare_fct,
		      unsigned long hash_seed,
		      unsigned long init_size,
		      void (*ht_call_rcu)(struct rcu_head *head,
				void (*func)(struct rcu_head *head)));

int ht_destroy(struct rcu_ht *ht);
/* Count the number of nodes in the hash table. Call with rcu_read_lock held. */
void ht_count_nodes(struct rcu_ht *ht,
		unsigned long *count,
		unsigned long *removed);

/* Call with rcu_read_lock held. */
struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len);

/* Call with rcu_read_lock held. */
void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node);

/*
 * Call with rcu_read_lock held.
 * Returns the node added upon success.
 * Returns the unique node already present upon failure. If ht_add_unique fails,
 * the node passed as parameter should be freed by the caller.
 */
struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node);

/* Call with rcu_read_lock held. */
int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node);

void ht_resize(struct rcu_ht *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	#include <stdint.h>
	5	#include <urcu-call-rcu.h>
	6
	7	#ifdef __cplusplus
	8	extern "C" {
	9	#endif
	10
	11	/*
	12	* struct rcu_ht_node and struct _rcu_ht_node should be aligned on
	13	* 4-bytes boundaries because the two lower bits are used as flags.
	14	*/
	15
	16	struct _rcu_ht_node {
	17	struct rcu_ht_node next; / ptr \| DUMMY_FLAG \| REMOVED_FLAG */
	18	unsigned long reverse_hash;
	19	};
	20
	21	struct rcu_ht_node {
	22	/* cache-hot for iteration */
	23	struct _rcu_ht_node p; /* needs to be first field */
	24	void *key;
	25	unsigned int key_len;
	26	/* cache-cold for iteration */
	27	struct rcu_head head;
	28	};
	29
	30	struct rcu_ht;
	31
	32	/*
	33	* Caution !
	34	* Ensure reader and writer threads are registered as urcu readers.
	35	*/
	36
	37	typedef unsigned long (ht_hash_fct)(void key, size_t length,
	38	unsigned long seed);
	39	typedef unsigned long (ht_compare_fct)(void key1, size_t key1_len,
	40	void *key2, size_t key2_len);
	41
	42	static inline
	43	void ht_node_init(struct rcu_ht_node node, void key,
	44	size_t key_len)
	45	{
	46	node->key = key;
	47	node->key_len = key_len;
	48	}
	49
	50	/*
	51	* init_size must be power of two.
	52	*/
	53	struct rcu_ht *ht_new(ht_hash_fct hash_fct,
	54	ht_compare_fct compare_fct,
	55	unsigned long hash_seed,
	56	unsigned long init_size,
	57	void (ht_call_rcu)(struct rcu_head head,
	58	void (func)(struct rcu_head head)));
	59
	60	int ht_destroy(struct rcu_ht *ht);
	61	/* Count the number of nodes in the hash table. Call with rcu_read_lock held. */
	62	void ht_count_nodes(struct rcu_ht *ht,
	63	unsigned long *count,
	64	unsigned long *removed);
	65
	66	/* Call with rcu_read_lock held. */
	67	struct rcu_ht_node ht_lookup(struct rcu_ht ht, void *key, size_t key_len);
	68
	69	/* Call with rcu_read_lock held. */
	70	void ht_add(struct rcu_ht ht, struct rcu_ht_node node);
	71
	72	/*
	73	* Call with rcu_read_lock held.
	74	* Returns the node added upon success.
	75	* Returns the unique node already present upon failure. If ht_add_unique fails,
	76	* the node passed as parameter should be freed by the caller.
	77	*/
	78	struct rcu_ht_node ht_add_unique(struct rcu_ht ht, struct rcu_ht_node *node);
	79
	80	/* Call with rcu_read_lock held. */
	81	int ht_remove(struct rcu_ht ht, struct rcu_ht_node node);
	82
	83	void ht_resize(struct rcu_ht *ht, int growth);
	84
	85	#ifdef __cplusplus
	86	}
	87	#endif
	88
	89	#endif /* _URCU_RCULFHASH_H */