LXR linux/tools/perf/util/rblist.c

   1/*
   2 * Based on strlist.c by:
   3 * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com>
   4 *
   5 * Licensed under the GPLv2.
   6 */
   7
   8#include <errno.h>
   9#include <stdio.h>
  10#include <stdlib.h>
  11
  12#include "rblist.h"
  13
  14int rblist__add_node(struct rblist *rblist, const void *new_entry)
  15{
  16        struct rb_node **p = &rblist->entries.rb_root.rb_node;
  17        struct rb_node *parent = NULL, *new_node;
  18        bool leftmost = true;
  19
  20        while (*p != NULL) {
  21                int rc;
  22
  23                parent = *p;
  24
  25                rc = rblist->node_cmp(parent, new_entry);
  26                if (rc > 0)
  27                        p = &(*p)->rb_left;
  28                else if (rc < 0) {
  29                        p = &(*p)->rb_right;
  30                        leftmost = false;
  31                }
  32                else
  33                        return -EEXIST;
  34        }
  35
  36        new_node = rblist->node_new(rblist, new_entry);
  37        if (new_node == NULL)
  38                return -ENOMEM;
  39
  40        rb_link_node(new_node, parent, p);
  41        rb_insert_color_cached(new_node, &rblist->entries, leftmost);
  42        ++rblist->nr_entries;
  43
  44        return 0;
  45}
  46
  47void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
  48{
  49        rb_erase_cached(rb_node, &rblist->entries);
  50        --rblist->nr_entries;
  51        rblist->node_delete(rblist, rb_node);
  52}
  53
  54static struct rb_node *__rblist__findnew(struct rblist *rblist,
  55                                         const void *entry,
  56                                         bool create)
  57{
  58        struct rb_node **p = &rblist->entries.rb_root.rb_node;
  59        struct rb_node *parent = NULL, *new_node = NULL;
  60        bool leftmost = true;
  61
  62        while (*p != NULL) {
  63                int rc;
  64
  65                parent = *p;
  66
  67                rc = rblist->node_cmp(parent, entry);
  68                if (rc > 0)
  69                        p = &(*p)->rb_left;
  70                else if (rc < 0) {
  71                        p = &(*p)->rb_right;
  72                        leftmost = false;
  73                }
  74                else
  75                        return parent;
  76        }
  77
  78        if (create) {
  79                new_node = rblist->node_new(rblist, entry);
  80                if (new_node) {
  81                        rb_link_node(new_node, parent, p);
  82                        rb_insert_color_cached(new_node,
  83                                               &rblist->entries, leftmost);
  84                        ++rblist->nr_entries;
  85                }
  86        }
  87
  88        return new_node;
  89}
  90
  91struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
  92{
  93        return __rblist__findnew(rblist, entry, false);
  94}
  95
  96struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry)
  97{
  98        return __rblist__findnew(rblist, entry, true);
  99}
 100
 101void rblist__init(struct rblist *rblist)
 102{
 103        if (rblist != NULL) {
 104                rblist->entries  = RB_ROOT_CACHED;
 105                rblist->nr_entries = 0;
 106        }
 107
 108        return;
 109}
 110
 111void rblist__exit(struct rblist *rblist)
 112{
 113        struct rb_node *pos, *next = rb_first_cached(&rblist->entries);
 114
 115        while (next) {
 116                pos = next;
 117                next = rb_next(pos);
 118                rblist__remove_node(rblist, pos);
 119        }
 120}
 121
 122void rblist__delete(struct rblist *rblist)
 123{
 124        if (rblist != NULL) {
 125                rblist__exit(rblist);
 126                free(rblist);
 127        }
 128}
 129
 130struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
 131{
 132        struct rb_node *node;
 133
 134        for (node = rb_first_cached(&rblist->entries); node;
 135             node = rb_next(node)) {
 136                if (!idx--)
 137                        return node;
 138        }
 139
 140        return NULL;
 141}
 142