perf/util/rblist.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * Based on strlist.c by:
0004  * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com>
0005  */
0006
0007 #include <errno.h>
0008 #include <stdio.h>
0009 #include <stdlib.h>
0010
0011 #include "rblist.h"
0012
0013 int rblist__add_node(struct rblist *rblist, const void *new_entry)
0014 {
0015     struct rb_node **p = &rblist->entries.rb_root.rb_node;
0016     struct rb_node *parent = NULL, *new_node;
0017     bool leftmost = true;
0018
0019     while (*p != NULL) {
0020         int rc;
0021
0022         parent = *p;
0023
0024         rc = rblist->node_cmp(parent, new_entry);
0025         if (rc > 0)
0026             p = &(*p)->rb_left;
0027         else if (rc < 0) {
0028             p = &(*p)->rb_right;
0029             leftmost = false;
0030         }
0031         else
0032             return -EEXIST;
0033     }
0034
0035     new_node = rblist->node_new(rblist, new_entry);
0036     if (new_node == NULL)
0037         return -ENOMEM;
0038
0039     rb_link_node(new_node, parent, p);
0040     rb_insert_color_cached(new_node, &rblist->entries, leftmost);
0041     ++rblist->nr_entries;
0042
0043     return 0;
0044 }
0045
0046 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
0047 {
0048     rb_erase_cached(rb_node, &rblist->entries);
0049     --rblist->nr_entries;
0050     rblist->node_delete(rblist, rb_node);
0051 }
0052
0053 static struct rb_node *__rblist__findnew(struct rblist *rblist,
0054                      const void *entry,
0055                      bool create)
0056 {
0057     struct rb_node **p = &rblist->entries.rb_root.rb_node;
0058     struct rb_node *parent = NULL, *new_node = NULL;
0059     bool leftmost = true;
0060
0061     while (*p != NULL) {
0062         int rc;
0063
0064         parent = *p;
0065
0066         rc = rblist->node_cmp(parent, entry);
0067         if (rc > 0)
0068             p = &(*p)->rb_left;
0069         else if (rc < 0) {
0070             p = &(*p)->rb_right;
0071             leftmost = false;
0072         }
0073         else
0074             return parent;
0075     }
0076
0077     if (create) {
0078         new_node = rblist->node_new(rblist, entry);
0079         if (new_node) {
0080             rb_link_node(new_node, parent, p);
0081             rb_insert_color_cached(new_node,
0082                            &rblist->entries, leftmost);
0083             ++rblist->nr_entries;
0084         }
0085     }
0086
0087     return new_node;
0088 }
0089
0090 struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
0091 {
0092     return __rblist__findnew(rblist, entry, false);
0093 }
0094
0095 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry)
0096 {
0097     return __rblist__findnew(rblist, entry, true);
0098 }
0099
0100 void rblist__init(struct rblist *rblist)
0101 {
0102     if (rblist != NULL) {
0103         rblist->entries  = RB_ROOT_CACHED;
0104         rblist->nr_entries = 0;
0105     }
0106
0107     return;
0108 }
0109
0110 void rblist__exit(struct rblist *rblist)
0111 {
0112     struct rb_node *pos, *next = rb_first_cached(&rblist->entries);
0113
0114     while (next) {
0115         pos = next;
0116         next = rb_next(pos);
0117         rblist__remove_node(rblist, pos);
0118     }
0119 }
0120
0121 void rblist__delete(struct rblist *rblist)
0122 {
0123     if (rblist != NULL) {
0124         rblist__exit(rblist);
0125         free(rblist);
0126     }
0127 }
0128
0129 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
0130 {
0131     struct rb_node *node;
0132
0133     for (node = rb_first_cached(&rblist->entries); node;
0134          node = rb_next(node)) {
0135         if (!idx--)
0136             return node;
0137     }
0138
0139     return NULL;
0140 }