rbtree-utils.c

   1 /*
   2  * Copyright (C) 2014 Facebook.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include "rbtree-utils.h"
  20
  21 int rb_insert(struct rb_root *root, struct rb_node *node,
  22               rb_compare_nodes comp)
  23 {
  24         struct rb_node **p = &root->rb_node;
  25         struct rb_node *parent = NULL;
  26         int ret;
  27
  28         while(*p) {
  29                 parent = *p;
  30
  31                 ret = comp(parent, node);
  32                 if (ret < 0)
  33                         p = &(*p)->rb_left;
  34                 else if (ret > 0)
  35                         p = &(*p)->rb_right;
  36                 else
  37                         return -EEXIST;
  38         }
  39
  40         rb_link_node(node, parent, p);
  41         rb_insert_color(node, root);
  42         return 0;
  43 }
  44
  45 struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
  46                           struct rb_node **next_ret)
  47 {
  48         struct rb_node *n = root->rb_node;
  49         struct rb_node *parent = NULL;
  50         int ret = 0;
  51
  52         while(n) {
  53                 parent = n;
  54
  55                 ret = comp(n, key);
  56                 if (ret < 0)
  57                         n = n->rb_left;
  58                 else if (ret > 0)
  59                         n = n->rb_right;
  60                 else
  61                         return n;
  62         }
  63
  64         if (!next_ret)
  65                 return NULL;
  66
  67         if (parent && ret > 0)
  68                 parent = rb_next(parent);
  69
  70         *next_ret = parent;
  71         return NULL;
  72 }
  73
  74 void rb_free_nodes(struct rb_root *root, rb_free_node free_node)
  75 {
  76         struct rb_node *node;
  77
  78         while ((node = rb_first(root))) {
  79                 rb_erase(node, root);
  80                 free_node(node);
  81         }
  82 }