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 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) 52 { 53 struct rb_node **p = &rblist->entries.rb_node; 54 struct rb_node *parent = NULL; 55 56 while (*p != NULL) { 57 int rc; 58 59 parent = *p; 60 61 rc = rblist->node_cmp(parent, entry); 62 if (rc > 0) 63 p = &(*p)->rb_left; 64 else if (rc < 0) 65 p = &(*p)->rb_right; 66 else 67 return parent; 68 } 69 70 return NULL; 71 } 72 73 void rblist__init(struct rblist *rblist) 74 { 75 if (rblist != NULL) { 76 rblist->entries = RB_ROOT; 77 rblist->nr_entries = 0; 78 } 79 80 return; 81 } 82 83 void rblist__delete(struct rblist *rblist) 84 { 85 if (rblist != NULL) { 86 struct rb_node *pos, *next = rb_first(&rblist->entries); 87 88 while (next) { 89 pos = next; 90 next = rb_next(pos); 91 rblist__remove_node(rblist, pos); 92 } 93 free(rblist); 94 } 95 } 96 97 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx) 98 { 99 struct rb_node *node; 100 101 for (node = rb_first(&rblist->entries); node; node = rb_next(node)) { 102 if (!idx--) 103 return node; 104 } 105 106 return NULL; 107 } 108