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