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 13 int 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 46 void 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 53 static 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 90 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) 91 { 92 return __rblist__findnew(rblist, entry, false); 93 } 94 95 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) 96 { 97 return __rblist__findnew(rblist, entry, true); 98 } 99 100 void 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 110 void 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 121 void rblist__delete(struct rblist *rblist) 122 { 123 if (rblist != NULL) { 124 rblist__exit(rblist); 125 free(rblist); 126 } 127 } 128 129 struct 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