[urcu.git] / urcu-rbtree.h

#ifndef URCU_RBTREE_H
#define URCU_RBTREE_H

/*
 * urcu-rbtree.h
 *
 * Userspace RCU library - Red-Black Tree
 *
 * Copyright (c) 2010 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
 *
 * Implementation of RCU-adapted data structures and operations based on the RB
 * tree algorithms found in chapter 12 of:
 *
 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
 * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
 * Press, September 2009.
 */

#include <pthread.h>

#define COLOR_BLACK	0
#define COLOR_RED	1

/*
 * Node key comparison function.
 * < 0 : a lower than b.
 * > 0 : a greater than b.
 * == 0 : a equals b.
 */
typedef int (*rcu_rbtree_comp)(void *a, void *b);

/*
 * Node allocation and deletion functions.
 */
typedef struct rcu_rbtree_node *(*rcu_rbtree_alloc)(void);
typedef void (*rcu_rbtree_free)(struct rcu_rbtree_node *node);

struct rcu_rbtree_node;

struct rcu_rbtree_node {
	/* must be set upon insertion */
	void *key;

	/* internally reserved */
	struct rcu_rbtree_node *p, *left, *right;
	unsigned int color:1;
};

/* nil rbtree node. "root" must initially point to this node. */
struct rcu_rbtree_node rcu_rbtree_nil;

/*
 * Each of the search primitive and "prev"/"next" iteration must be called with
 * the RCU read-side lock held.
 *
 * Insertion and removal must be protected by a mutex. At the moment, insertion
 * and removal use defer_rcu, so calling them with rcu read-lock held is
 * prohibited.
 */

/*
 * Node insertion. Returns 0 on success. May fail with -ENOMEM.
 */
int rcu_rbtree_insert(struct rcu_rbtree_node **root,
		      struct rcu_rbtree_node *node,
		      rcu_rbtree_comp comp,
		      rcu_rbtree_alloc rballoc,
		      rcu_rbtree_free rbfree);

/*
 * Remove node from tree.
 * Must wait for a grace period after removal before performing deletion of the
 * node. Note: it is illegal to re-use the same node pointer passed to "insert"
 * also to "remove", because it may have been copied and garbage-collected since
 * the insertion. A "search" for the key in the tree should be done to get
 * "node".
 * Returns 0 on success. May fail with -ENOMEM.
 *
 * The caller is responsible for freeing the node after a grace period.
 */
int rcu_rbtree_remove(struct rcu_rbtree_node **root,
		      struct rcu_rbtree_node *node,
		      rcu_rbtree_comp comp,
		      rcu_rbtree_alloc rballoc,
		      rcu_rbtree_free rbfree);

/* RCU read-side */

/*
 * Search key starting from node x. Returns NULL if not found.
 */
struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
					  void *key, rcu_rbtree_comp comp);

struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree_node *x,
				       rcu_rbtree_comp comp);

struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree_node *x,
				       rcu_rbtree_comp comp);

struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x,
					rcu_rbtree_comp comp);

struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree_node *x,
					rcu_rbtree_comp comp);

#endif /* URCU_RBTREE_H */
Commit	Line	Data
00131368 MD	1	#ifndef URCU_RBTREE_H
	2	#define URCU_RBTREE_H
	3
	4	/*
	5	* urcu-rbtree.h
	6	*
	7	* Userspace RCU library - Red-Black Tree
	8	*
	9	* Copyright (c) 2010 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	* Implementation of RCU-adapted data structures and operations based on the RB
	26	* tree algorithms found in chapter 12 of:
	27	*
	28	* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
	29	* Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
	30	* Press, September 2009.
	31	*/
	32
	33	#include <pthread.h>
	34
	35	#define COLOR_BLACK 0
	36	#define COLOR_RED 1
	37
	38	/*
	39	* Node key comparison function.
	40	* < 0 : a lower than b.
	41	* > 0 : a greater than b.
	42	* == 0 : a equals b.
	43	*/
	44	typedef int (rcu_rbtree_comp)(void a, void *b);
	45
	46	/*
	47	* Node allocation and deletion functions.
	48	*/
	49	typedef struct rcu_rbtree_node (rcu_rbtree_alloc)(void);
	50	typedef void (rcu_rbtree_free)(struct rcu_rbtree_node node);
	51
	52	struct rcu_rbtree_node;
	53
	54	struct rcu_rbtree_node {
	55	/* must be set upon insertion */
	56	void *key;
	57
	58	/* internally reserved */
	59	struct rcu_rbtree_node p, left, *right;
	60	unsigned int color:1;
	61	};
	62
db5b1669 MD	63	/* nil rbtree node. "root" must initially point to this node. */
	64	struct rcu_rbtree_node rcu_rbtree_nil;
	65
00131368 MD	66	/*
	67	* Each of the search primitive and "prev"/"next" iteration must be called with
	68	* the RCU read-side lock held.
	69	*
	70	* Insertion and removal must be protected by a mutex. At the moment, insertion
	71	* and removal use defer_rcu, so calling them with rcu read-lock held is
	72	* prohibited.
	73	*/
	74
	75	/*
	76	* Node insertion. Returns 0 on success. May fail with -ENOMEM.
	77	*/
	78	int rcu_rbtree_insert(struct rcu_rbtree_node **root,
	79	struct rcu_rbtree_node *node,
	80	rcu_rbtree_comp comp,
	81	rcu_rbtree_alloc rballoc,
	82	rcu_rbtree_free rbfree);
	83
	84	/*
	85	* Remove node from tree.
	86	* Must wait for a grace period after removal before performing deletion of the
3bc7f395 MD	87	* node. Note: it is illegal to re-use the same node pointer passed to "insert"
	88	* also to "remove", because it may have been copied and garbage-collected since
	89	* the insertion. A "search" for the key in the tree should be done to get
	90	* "node".
00131368	91	* Returns 0 on success. May fail with -ENOMEM.
3bc7f395 MD	92	*
3bc7f395 MD	93	* The caller is responsible for freeing the node after a grace period.
00131368 MD	94	*/
	95	int rcu_rbtree_remove(struct rcu_rbtree_node **root,
	96	struct rcu_rbtree_node *node,
	97	rcu_rbtree_comp comp,
	98	rcu_rbtree_alloc rballoc,
	99	rcu_rbtree_free rbfree);
	100
	101	/* RCU read-side */
	102
	103	/*
	104	* Search key starting from node x. Returns NULL if not found.
	105	*/
	106	struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
	107	void *key, rcu_rbtree_comp comp);
	108
	109	struct rcu_rbtree_node rcu_rbtree_min(struct rcu_rbtree_node x,
	110	rcu_rbtree_comp comp);
	111
	112	struct rcu_rbtree_node rcu_rbtree_max(struct rcu_rbtree_node x,
	113	rcu_rbtree_comp comp);
	114
	115	struct rcu_rbtree_node rcu_rbtree_next(struct rcu_rbtree_node x,
	116	rcu_rbtree_comp comp);
	117
	118	struct rcu_rbtree_node rcu_rbtree_prev(struct rcu_rbtree_node x,
	119	rcu_rbtree_comp comp);
	120
	121	#endif /* URCU_RBTREE_H */