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
 14int 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
 44void 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
 51static 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
 84struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
 85{
 86	return __rblist__findnew(rblist, entry, false);
 87}
 88
 89struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry)
 90{
 91	return __rblist__findnew(rblist, entry, true);
 92}
 93
 94void 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
104void 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
118struct 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}