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->node_delete(rblist, rb_node); 48 } 49 50 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) 51 { 52 struct rb_node **p = &rblist->entries.rb_node; 53 struct rb_node *parent = NULL; 54 55 while (*p != NULL) { 56 int rc; 57 58 parent = *p; 59 60 rc = rblist->node_cmp(parent, entry); 61 if (rc > 0) 62 p = &(*p)->rb_left; 63 else if (rc < 0) 64 p = &(*p)->rb_right; 65 else 66 return parent; 67 } 68 69 return NULL; 70 } 71 72 void rblist__init(struct rblist *rblist) 73 { 74 if (rblist != NULL) { 75 rblist->entries = RB_ROOT; 76 rblist->nr_entries = 0; 77 } 78 79 return; 80 } 81 82 void rblist__delete(struct rblist *rblist) 83 { 84 if (rblist != NULL) { 85 struct rb_node *pos, *next = rb_first(&rblist->entries); 86 87 while (next) { 88 pos = next; 89 next = rb_next(pos); 90 rb_erase(pos, &rblist->entries); 91 rblist->node_delete(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