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__delete(struct rblist *rblist) 105 { 106 if (rblist != NULL) { 107 struct rb_node *pos, *next = rb_first(&rblist->entries); 108 109 while (next) { 110 pos = next; 111 next = rb_next(pos); 112 rblist__remove_node(rblist, pos); 113 } 114 free(rblist); 115 } 116 } 117 118 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx) 119 { 120 struct rb_node *node; 121 122 for (node = rb_first(&rblist->entries); node; node = rb_next(node)) { 123 if (!idx--) 124 return node; 125 } 126 127 return NULL; 128 } 129