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

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