urcu-rbtree.h

   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
  63 /*
  64  * Each of the search primitive and "prev"/"next" iteration must be called with
  65  * the RCU read-side lock held.
  66  *
  67  * Insertion and removal must be protected by a mutex. At the moment, insertion
  68  * and removal use defer_rcu, so calling them with rcu read-lock held is
  69  * prohibited.
  70  */
  71
  72 /*
  73  * Node insertion. Returns 0 on success. May fail with -ENOMEM.
  74  */
  75 int rcu_rbtree_insert(struct rcu_rbtree_node **root,
  76                       struct rcu_rbtree_node *node,
  77                       rcu_rbtree_comp comp,
  78                       rcu_rbtree_alloc rballoc,
  79                       rcu_rbtree_free rbfree);
  80
  81 /*
  82  * Remove node from tree.
  83  * Must wait for a grace period after removal before performing deletion of the
  84  * node.
  85  * Returns 0 on success. May fail with -ENOMEM.
  86  */
  87 int rcu_rbtree_remove(struct rcu_rbtree_node **root,
  88                       struct rcu_rbtree_node *node,
  89                       rcu_rbtree_comp comp,
  90                       rcu_rbtree_alloc rballoc,
  91                       rcu_rbtree_free rbfree);
  92
  93 /* RCU read-side */
  94
  95 /*
  96  * Search key starting from node x. Returns NULL if not found.
  97  */
  98 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
  99                                           void *key, rcu_rbtree_comp comp);
 100
 101 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree_node *x,
 102                                        rcu_rbtree_comp comp);
 103
 104 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree_node *x,
 105                                        rcu_rbtree_comp comp);
 106
 107 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x,
 108                                         rcu_rbtree_comp comp);
 109
 110 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree_node *x,
 111                                         rcu_rbtree_comp comp);
 112
 113 #endif /* URCU_RBTREE_H */