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
51struct 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
73void 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
83void 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
97struct 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