[userspace-rcu.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

#define IS_LEFT		0
#define IS_RIGHT	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;
	unsigned int pos: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 &rcu_rbtree_nil 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
8c91bac8 MD	38	#define IS_LEFT 0
	39	#define IS_RIGHT 1
	40
00131368 MD	41	/*
	42	* Node key comparison function.
	43	* < 0 : a lower than b.
	44	* > 0 : a greater than b.
	45	* == 0 : a equals b.
	46	*/
	47	typedef int (rcu_rbtree_comp)(void a, void *b);
	48
	49	/*
	50	* Node allocation and deletion functions.
	51	*/
	52	typedef struct rcu_rbtree_node (rcu_rbtree_alloc)(void);
	53	typedef void (rcu_rbtree_free)(struct rcu_rbtree_node node);
	54
	55	struct rcu_rbtree_node;
	56
	57	struct rcu_rbtree_node {
	58	/* must be set upon insertion */
	59	void *key;
	60
	61	/* internally reserved */
8c91bac8	62	struct rcu_rbtree_node p, left, *right;
00131368	63	unsigned int color:1;
8c91bac8	64	unsigned int pos:1;
00131368 MD	65	};
00131368 MD	66
db5b1669 MD	67	/* nil rbtree node. "root" must initially point to this node. */
	68	struct rcu_rbtree_node rcu_rbtree_nil;
	69
00131368 MD	70	/*
	71	* Each of the search primitive and "prev"/"next" iteration must be called with
	72	* the RCU read-side lock held.
	73	*
	74	* Insertion and removal must be protected by a mutex. At the moment, insertion
	75	* and removal use defer_rcu, so calling them with rcu read-lock held is
	76	* prohibited.
	77	*/
	78
	79	/*
	80	* Node insertion. Returns 0 on success. May fail with -ENOMEM.
	81	*/
	82	int rcu_rbtree_insert(struct rcu_rbtree_node **root,
	83	struct rcu_rbtree_node *node,
	84	rcu_rbtree_comp comp,
	85	rcu_rbtree_alloc rballoc,
	86	rcu_rbtree_free rbfree);
	87
	88	/*
	89	* Remove node from tree.
	90	* Must wait for a grace period after removal before performing deletion of the
3bc7f395 MD	91	* node. Note: it is illegal to re-use the same node pointer passed to "insert"
	92	* also to "remove", because it may have been copied and garbage-collected since
	93	* the insertion. A "search" for the key in the tree should be done to get
	94	* "node".
00131368	95	* Returns 0 on success. May fail with -ENOMEM.
3bc7f395 MD	96	*
3bc7f395 MD	97	* The caller is responsible for freeing the node after a grace period.
00131368 MD	98	*/
	99	int rcu_rbtree_remove(struct rcu_rbtree_node **root,
	100	struct rcu_rbtree_node *node,
	101	rcu_rbtree_comp comp,
	102	rcu_rbtree_alloc rballoc,
	103	rcu_rbtree_free rbfree);
	104
	105	/* RCU read-side */
	106
	107	/*
f6e888c5	108	* Search key starting from node x. Returns &rcu_rbtree_nil if not found.
00131368 MD	109	*/
	110	struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
	111	void *key, rcu_rbtree_comp comp);
	112
	113	struct rcu_rbtree_node rcu_rbtree_min(struct rcu_rbtree_node x,
	114	rcu_rbtree_comp comp);
	115
	116	struct rcu_rbtree_node rcu_rbtree_max(struct rcu_rbtree_node x,
	117	rcu_rbtree_comp comp);
	118
	119	struct rcu_rbtree_node rcu_rbtree_next(struct rcu_rbtree_node x,
	120	rcu_rbtree_comp comp);
	121
	122	struct rcu_rbtree_node rcu_rbtree_prev(struct rcu_rbtree_node x,
	123	rcu_rbtree_comp comp);
	124
	125	#endif /* URCU_RBTREE_H */