urcu/rcurbtree.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 #include <urcu-call-rcu.h>
  35
  36 #define COLOR_BLACK     0
  37 #define COLOR_RED       1
  38
  39 #define IS_LEFT         0
  40 #define IS_RIGHT        1
  41
  42 /*
  43  * Node key comparison function.
  44  * < 0 : a lower than b.
  45  * > 0 : a greater than b.
  46  * == 0 : a equals b.
  47  */
  48 typedef int (*rcu_rbtree_comp)(void *a, void *b);
  49
  50 /*
  51  * Allocation and deletion functions.
  52  */
  53 typedef void *(*rcu_rbtree_alloc)(size_t size);
  54 typedef void (*rcu_rbtree_free)(void *ptr);
  55
  56 /*
  57  * struct rcu_rbtree_node must be aligned at least on 2 bytes.
  58  * Lowest bit reserved for position (left/right) in pointer to parent.
  59  *
  60  * Set "high" to key + 1 to insert single-value nodes.
  61  */
  62 struct rcu_rbtree_node {
  63         /* useful node information returned by search */
  64         void *begin;            /* Start of range (inclusive) */
  65         void *end;              /* range end (exclusive) */
  66         /* internally reserved */
  67         void *max_end;          /* max range end of node and children */
  68         /* parent uses low bit for "0 -> is left, 1 -> is right" */
  69         unsigned long parent;
  70         /* _left and _right must be updated with set_left(), set_right() */
  71         struct rcu_rbtree_node *_left, *_right;
  72         struct rcu_rbtree_node *decay_next;
  73         struct rcu_rbtree *rbtree;
  74         struct rcu_head head;           /* For delayed free */
  75         unsigned int color:1;
  76 };
  77
  78 struct rcu_rbtree {
  79         struct rcu_rbtree_node *root;
  80         struct rcu_rbtree_node nil_node;
  81         rcu_rbtree_comp comp;
  82         rcu_rbtree_alloc rballoc;
  83         rcu_rbtree_free rbfree;
  84         void (*call_rcu)(struct rcu_head *head,
  85                          void (*func)(struct rcu_head *head));
  86 };
  87
  88 #define DEFINE_RCU_RBTREE(x, _comp, _rballoc, _rbfree, _call_rcu) \
  89         struct rcu_rbtree x =                           \
  90                 {                                       \
  91                         .comp = _comp,                  \
  92                         .rballoc = _rballoc,            \
  93                         .rbfree = _rbfree,              \
  94                         .call_rcu = _call_rcu,          \
  95                         .nil_node = {                   \
  96                                 .color = COLOR_BLACK,   \
  97                         },                              \
  98                         .root = &(x).nil_node,          \
  99                 };
 100
 101 /*
 102  * Each of the search primitive and "prev"/"next" iteration must be called with
 103  * the RCU read-side lock held.
 104  *
 105  * Insertion and removal must be protected by a mutex. At the moment, insertion
 106  * and removal use defer_rcu, so calling them with rcu read-lock held is
 107  * prohibited.
 108  */
 109
 110 /*
 111  * Node insertion. Returns 0 on success. May fail with -ENOMEM.
 112  * Caller must have exclusive write access and hold RCU read-side lock.
 113  */
 114 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 115                       void *begin, void *end);
 116
 117 /*
 118  * Remove node from tree.
 119  * Must wait for a grace period after removal before performing deletion of the
 120  * node. Note: it is illegal to re-use the same node pointer passed to "insert"
 121  * also to "remove", because it may have been copied and garbage-collected since
 122  * the insertion. A "search" for the key in the tree should be done to get
 123  * "node".
 124  * Returns 0 on success. May fail with -ENOMEM.
 125  *
 126  * Caller must have exclusive write access and hold RCU read-side lock
 127  * across "search" and "remove".
 128  */
 129 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 130                       struct rcu_rbtree_node *node);
 131
 132 /* RCU read-side */
 133
 134 /*
 135  * For all these read-side privimitives, RCU read-side lock must be held
 136  * across the duration for which the search is done and the returned
 137  * rbtree node is expected to be valid.
 138  */
 139
 140 /*
 141  * Search point in range starting from node x (node x is typically the
 142  * rbtree root node). Returns nil node if not found.
 143  */
 144 struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree,
 145                                           struct rcu_rbtree_node *x,
 146                                           void *point);
 147
 148 /*
 149  * Search range starting from node x (typically the rbtree root node).
 150  * Returns the first range containing the range specified as parameters.
 151  * Returns nil node if not found.
 152  *
 153  * Note: ranges in the rbtree should not partially overlap when this search
 154  * range function is used. Otherwise, a range matching the low value (but not
 155  * containing the high value) could hide a range that would match this query.
 156  * It is OK for the ranges to overlap entirely though.
 157  */
 158 struct rcu_rbtree_node *rcu_rbtree_search_range(struct rcu_rbtree *rbtree,
 159                                           struct rcu_rbtree_node *x,
 160                                           void *begin, void *end);
 161
 162 /*
 163  * Search exact range begin value starting from node x (typically rbtree
 164  * root node). Returns nil node if not found.
 165  * This function is only useful if you do not use the range feature at
 166  * all and only care about range begin values.
 167  */
 168 struct rcu_rbtree_node *rcu_rbtree_search_begin_key(struct rcu_rbtree *rbtree,
 169                                           struct rcu_rbtree_node *x,
 170                                           void *key);
 171
 172 /*
 173  * Search for minimum node of the tree under node x.
 174  */
 175 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 176                                        struct rcu_rbtree_node *x);
 177
 178 /*
 179  * Search for maximum node of the tree under node x.
 180  */
 181 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 182                                        struct rcu_rbtree_node *x);
 183
 184 /*
 185  * Get next node after node x.
 186  */
 187 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 188                                         struct rcu_rbtree_node *x);
 189
 190 /*
 191  * Get previous node before node x.
 192  */
 193 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 194                                         struct rcu_rbtree_node *x);
 195
 196 /*
 197  * Sentinel (bottom nodes).
 198  * Don't care about p, left, right, pos and key values.
 199  */
 200 static
 201 int rcu_rbtree_is_nil(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node)
 202 {
 203         return node == &rbtree->nil_node;
 204 }
 205
 206 #endif /* URCU_RBTREE_H */