141 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*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 else32 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 else74 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