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 14 int rblist__add_node(struct rblist *rblist, const void *new_entry) 15 { 16 struct rb_node **p = &rblist->entries.rb_root.rb_node; 17 struct rb_node *parent = NULL, *new_node; 18 bool leftmost = true; 19 20 while (*p != NULL) { 21 int rc; 22 23 parent = *p; 24 25 rc = rblist->node_cmp(parent, new_entry); 26 if (rc > 0) 27 p = &(*p)->rb_left; 28 else if (rc < 0) { 29 p = &(*p)->rb_right; 30 leftmost = false; 31 } 32 else 33 return -EEXIST; 34 } 35 36 new_node = rblist->node_new(rblist, new_entry); 37 if (new_node == NULL) 38 return -ENOMEM; 39 40 rb_link_node(new_node, parent, p); 41 rb_insert_color_cached(new_node, &rblist->entries, leftmost); 42 ++rblist->nr_entries; 43 44 return 0; 45 } 46 47 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) 48 { 49 rb_erase_cached(rb_node, &rblist->entries); 50 --rblist->nr_entries; 51 rblist->node_delete(rblist, rb_node); 52 } 53 54 static struct rb_node *__rblist__findnew(struct rblist *rblist, 55 const void *entry, 56 bool create) 57 { 58 struct rb_node **p = &rblist->entries.rb_root.rb_node; 59 struct rb_node *parent = NULL, *new_node = NULL; 60 bool leftmost = true; 61 62 while (*p != NULL) { 63 int rc; 64 65 parent = *p; 66 67 rc = rblist->node_cmp(parent, entry); 68 if (rc > 0) 69 p = &(*p)->rb_left; 70 else if (rc < 0) { 71 p = &(*p)->rb_right; 72 leftmost = false; 73 } 74 else 75 return parent; 76 } 77 78 if (create) { 79 new_node = rblist->node_new(rblist, entry); 80 if (new_node) { 81 rb_link_node(new_node, parent, p); 82 rb_insert_color_cached(new_node, 83 &rblist->entries, leftmost); 84 ++rblist->nr_entries; 85 } 86 } 87 88 return new_node; 89 } 90 91 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) 92 { 93 return __rblist__findnew(rblist, entry, false); 94 } 95 96 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) 97 { 98 return __rblist__findnew(rblist, entry, true); 99 } 100 101 void rblist__init(struct rblist *rblist) 102 { 103 if (rblist != NULL) { 104 rblist->entries = RB_ROOT_CACHED; 105 rblist->nr_entries = 0; 106 } 107 108 return; 109 } 110 111 void rblist__exit(struct rblist *rblist) 112 { 113 struct rb_node *pos, *next = rb_first_cached(&rblist->entries); 114 115 while (next) { 116 pos = next; 117 next = rb_next(pos); 118 rblist__remove_node(rblist, pos); 119 } 120 } 121 122 void rblist__delete(struct rblist *rblist) 123 { 124 if (rblist != NULL) { 125 rblist__exit(rblist); 126 free(rblist); 127 } 128 } 129 130 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx) 131 { 132 struct rb_node *node; 133 134 for (node = rb_first_cached(&rblist->entries); node; 135 node = rb_next(node)) { 136 if (!idx--) 137 return node; 138 } 139 140 return NULL; 141 } 142