137bbd3ffSDavid Ahern /* 237bbd3ffSDavid Ahern * Based on strlist.c by: 337bbd3ffSDavid Ahern * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com> 437bbd3ffSDavid Ahern * 537bbd3ffSDavid Ahern * Licensed under the GPLv2. 637bbd3ffSDavid Ahern */ 737bbd3ffSDavid Ahern 837bbd3ffSDavid Ahern #include <errno.h> 937bbd3ffSDavid Ahern #include <stdio.h> 1037bbd3ffSDavid Ahern #include <stdlib.h> 1137bbd3ffSDavid Ahern 1237bbd3ffSDavid Ahern #include "rblist.h" 1337bbd3ffSDavid Ahern 1437bbd3ffSDavid Ahern int rblist__add_node(struct rblist *rblist, const void *new_entry) 1537bbd3ffSDavid Ahern { 1637bbd3ffSDavid Ahern struct rb_node **p = &rblist->entries.rb_node; 1737bbd3ffSDavid Ahern struct rb_node *parent = NULL, *new_node; 1837bbd3ffSDavid Ahern 1937bbd3ffSDavid Ahern while (*p != NULL) { 2037bbd3ffSDavid Ahern int rc; 2137bbd3ffSDavid Ahern 2237bbd3ffSDavid Ahern parent = *p; 2337bbd3ffSDavid Ahern 2437bbd3ffSDavid Ahern rc = rblist->node_cmp(parent, new_entry); 2537bbd3ffSDavid Ahern if (rc > 0) 2637bbd3ffSDavid Ahern p = &(*p)->rb_left; 2737bbd3ffSDavid Ahern else if (rc < 0) 2837bbd3ffSDavid Ahern p = &(*p)->rb_right; 2937bbd3ffSDavid Ahern else 3037bbd3ffSDavid Ahern return -EEXIST; 3137bbd3ffSDavid Ahern } 3237bbd3ffSDavid Ahern 3337bbd3ffSDavid Ahern new_node = rblist->node_new(rblist, new_entry); 3437bbd3ffSDavid Ahern if (new_node == NULL) 3537bbd3ffSDavid Ahern return -ENOMEM; 3637bbd3ffSDavid Ahern 3737bbd3ffSDavid Ahern rb_link_node(new_node, parent, p); 3837bbd3ffSDavid Ahern rb_insert_color(new_node, &rblist->entries); 3937bbd3ffSDavid Ahern ++rblist->nr_entries; 4037bbd3ffSDavid Ahern 4137bbd3ffSDavid Ahern return 0; 4237bbd3ffSDavid Ahern } 4337bbd3ffSDavid Ahern 4437bbd3ffSDavid Ahern void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) 4537bbd3ffSDavid Ahern { 4637bbd3ffSDavid Ahern rb_erase(rb_node, &rblist->entries); 4737bbd3ffSDavid Ahern rblist->node_delete(rblist, rb_node); 4837bbd3ffSDavid Ahern } 4937bbd3ffSDavid Ahern 5037bbd3ffSDavid Ahern struct rb_node *rblist__find(struct rblist *rblist, const void *entry) 5137bbd3ffSDavid Ahern { 5237bbd3ffSDavid Ahern struct rb_node **p = &rblist->entries.rb_node; 5337bbd3ffSDavid Ahern struct rb_node *parent = NULL; 5437bbd3ffSDavid Ahern 5537bbd3ffSDavid Ahern while (*p != NULL) { 5637bbd3ffSDavid Ahern int rc; 5737bbd3ffSDavid Ahern 5837bbd3ffSDavid Ahern parent = *p; 5937bbd3ffSDavid Ahern 6037bbd3ffSDavid Ahern rc = rblist->node_cmp(parent, entry); 6137bbd3ffSDavid Ahern if (rc > 0) 6237bbd3ffSDavid Ahern p = &(*p)->rb_left; 6337bbd3ffSDavid Ahern else if (rc < 0) 6437bbd3ffSDavid Ahern p = &(*p)->rb_right; 6537bbd3ffSDavid Ahern else 6637bbd3ffSDavid Ahern return parent; 6737bbd3ffSDavid Ahern } 6837bbd3ffSDavid Ahern 6937bbd3ffSDavid Ahern return NULL; 7037bbd3ffSDavid Ahern } 7137bbd3ffSDavid Ahern 7237bbd3ffSDavid Ahern void rblist__init(struct rblist *rblist) 7337bbd3ffSDavid Ahern { 7437bbd3ffSDavid Ahern if (rblist != NULL) { 7537bbd3ffSDavid Ahern rblist->entries = RB_ROOT; 7637bbd3ffSDavid Ahern rblist->nr_entries = 0; 7737bbd3ffSDavid Ahern } 7837bbd3ffSDavid Ahern 7937bbd3ffSDavid Ahern return; 8037bbd3ffSDavid Ahern } 8137bbd3ffSDavid Ahern 8237bbd3ffSDavid Ahern void rblist__delete(struct rblist *rblist) 8337bbd3ffSDavid Ahern { 8437bbd3ffSDavid Ahern if (rblist != NULL) { 8537bbd3ffSDavid Ahern struct rb_node *pos, *next = rb_first(&rblist->entries); 8637bbd3ffSDavid Ahern 8737bbd3ffSDavid Ahern while (next) { 8837bbd3ffSDavid Ahern pos = next; 8937bbd3ffSDavid Ahern next = rb_next(pos); 9037bbd3ffSDavid Ahern rb_erase(pos, &rblist->entries); 9137bbd3ffSDavid Ahern rblist->node_delete(rblist, pos); 9237bbd3ffSDavid Ahern } 9337bbd3ffSDavid Ahern free(rblist); 9437bbd3ffSDavid Ahern } 9537bbd3ffSDavid Ahern } 9637bbd3ffSDavid Ahern 9737bbd3ffSDavid Ahern struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx) 9837bbd3ffSDavid Ahern { 9937bbd3ffSDavid Ahern struct rb_node *node; 10037bbd3ffSDavid Ahern 10137bbd3ffSDavid Ahern for (node = rb_first(&rblist->entries); node; node = rb_next(node)) { 10237bbd3ffSDavid Ahern if (!idx--) 10337bbd3ffSDavid Ahern return node; 10437bbd3ffSDavid Ahern } 10537bbd3ffSDavid Ahern 10637bbd3ffSDavid Ahern return NULL; 10737bbd3ffSDavid Ahern } 108