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_node;
  17        struct rb_node *parent = NULL, *new_node;
  18
  19        while (*p != NULL) {
  20                int rc;
  21
  22                parent = *p;
  23
  24                rc = rblist->node_cmp(parent, new_entry);
  25                if (rc > 0)
  26                        p = &(*p)->rb_left;
  27                else if (rc < 0)
  28                        p = &(*p)->rb_right;
  29                else
  30                        return -EEXIST;
  31        }
  32
  33        new_node = rblist->node_new(rblist, new_entry);
  34        if (new_node == NULL)
  35                return -ENOMEM;
  36
  37        rb_link_node(new_node, parent, p);
  38        rb_insert_color(new_node, &rblist->entries);
  39        ++rblist->nr_entries;
  40
  41        return 0;
  42}
  43
  44void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
  45{
  46        rb_erase(rb_node, &rblist->entries);
  47        --rblist->nr_entries;
  48        rblist->node_delete(rblist, rb_node);
  49}
  50
  51struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
  52{
  53        struct rb_node **p = &rblist->entries.rb_node;
  54        struct rb_node *parent = NULL;
  55
  56        while (*p != NULL) {
  57                int rc;
  58
  59                parent = *p;
  60
  61                rc = rblist->node_cmp(parent, entry);
  62                if (rc > 0)
  63                        p = &(*p)->rb_left;
  64                else if (rc < 0)
  65                        p = &(*p)->rb_right;
  66                else
  67                        return parent;
  68        }
  69
  70        return NULL;
  71}
  72
  73void rblist__init(struct rblist *rblist)
  74{
  75        if (rblist != NULL) {
  76                rblist->entries  = RB_ROOT;
  77                rblist->nr_entries = 0;
  78        }
  79
  80        return;
  81}
  82
  83void rblist__delete(struct rblist *rblist)
  84{
  85        if (rblist != NULL) {
  86                struct rb_node *pos, *next = rb_first(&rblist->entries);
  87
  88                while (next) {
  89                        pos = next;
  90                        next = rb_next(pos);
  91                        rblist__remove_node(rblist, pos);
  92                }
  93                free(rblist);
  94        }
  95}
  96
  97struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
  98{
  99        struct rb_node *node;
 100
 101        for (node = rb_first(&rblist->entries); node; node = rb_next(node)) {
 102                if (!idx--)
 103                        return node;
 104        }
 105
 106        return NULL;
 107}
 108