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
  51static struct rb_node *__rblist__findnew(struct rblist *rblist,
  52                                         const void *entry,
  53                                         bool create)
  54{
  55        struct rb_node **p = &rblist->entries.rb_node;
  56        struct rb_node *parent = NULL, *new_node = NULL;
  57
  58        while (*p != NULL) {
  59                int rc;
  60
  61                parent = *p;
  62
  63                rc = rblist->node_cmp(parent, entry);
  64                if (rc > 0)
  65                        p = &(*p)->rb_left;
  66                else if (rc < 0)
  67                        p = &(*p)->rb_right;
  68                else
  69                        return parent;
  70        }
  71
  72        if (create) {
  73                new_node = rblist->node_new(rblist, entry);
  74                if (new_node) {
  75                        rb_link_node(new_node, parent, p);
  76                        rb_insert_color(new_node, &rblist->entries);
  77                        ++rblist->nr_entries;
  78                }
  79        }
  80
  81        return new_node;
  82}
  83
  84struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
  85{
  86        return __rblist__findnew(rblist, entry, false);
  87}
  88
  89struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry)
  90{
  91        return __rblist__findnew(rblist, entry, true);
  92}
  93
  94void rblist__init(struct rblist *rblist)
  95{
  96        if (rblist != NULL) {
  97                rblist->entries  = RB_ROOT;
  98                rblist->nr_entries = 0;
  99        }
 100
 101        return;
 102}
 103
 104void rblist__delete(struct rblist *rblist)
 105{
 106        if (rblist != NULL) {
 107                struct rb_node *pos, *next = rb_first(&rblist->entries);
 108
 109                while (next) {
 110                        pos = next;
 111                        next = rb_next(pos);
 112                        rblist__remove_node(rblist, pos);
 113                }
 114                free(rblist);
 115        }
 116}
 117
 118struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
 119{
 120        struct rb_node *node;
 121
 122        for (node = rb_first(&rblist->entries); node; node = rb_next(node)) {
 123                if (!idx--)
 124                        return node;
 125        }
 126
 127        return NULL;
 128}
 129