LXR uboot/fs/btrfs/common/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 <linux/errno.h>
  20#include "rbtree-utils.h"
  21
  22int rb_insert(struct rb_root *root, struct rb_node *node,
  23              rb_compare_nodes comp)
  24{
  25        struct rb_node **p = &root->rb_node;
  26        struct rb_node *parent = NULL;
  27        int ret;
  28
  29        while(*p) {
  30                parent = *p;
  31
  32                ret = comp(parent, node);
  33                if (ret < 0)
  34                        p = &(*p)->rb_left;
  35                else if (ret > 0)
  36                        p = &(*p)->rb_right;
  37                else
  38                        return -EEXIST;
  39        }
  40
  41        rb_link_node(node, parent, p);
  42        rb_insert_color(node, root);
  43        return 0;
  44}
  45
  46struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
  47                          struct rb_node **next_ret)
  48{
  49        struct rb_node *n = root->rb_node;
  50        struct rb_node *parent = NULL;
  51        int ret = 0;
  52
  53        while(n) {
  54                parent = n;
  55
  56                ret = comp(n, key);
  57                if (ret < 0)
  58                        n = n->rb_left;
  59                else if (ret > 0)
  60                        n = n->rb_right;
  61                else
  62                        return n;
  63        }
  64
  65        if (!next_ret)
  66                return NULL;
  67
  68        if (parent && ret > 0)
  69                parent = rb_next(parent);
  70
  71        *next_ret = parent;
  72        return NULL;
  73}
  74
  75void rb_free_nodes(struct rb_root *root, rb_free_node free_node)
  76{
  77        struct rb_node *node;
  78
  79        while ((node = rb_first(root))) {
  80                rb_erase(node, root);
  81                free_node(node);
  82        }
  83}
  84