Commit | Line | Data |
---|---|---|
37bbd3ff DA |
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); | |
03f2f93a | 47 | --rblist->nr_entries; |
37bbd3ff DA |
48 | rblist->node_delete(rblist, rb_node); |
49 | } | |
50 | ||
813335b8 DA |
51 | static struct rb_node *__rblist__findnew(struct rblist *rblist, |
52 | const void *entry, | |
53 | bool create) | |
37bbd3ff DA |
54 | { |
55 | struct rb_node **p = &rblist->entries.rb_node; | |
813335b8 | 56 | struct rb_node *parent = NULL, *new_node = NULL; |
37bbd3ff DA |
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 | ||
813335b8 DA |
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 | ||
84 | struct rb_node *rblist__find(struct rblist *rblist, const void *entry) | |
85 | { | |
86 | return __rblist__findnew(rblist, entry, false); | |
87 | } | |
88 | ||
89 | struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) | |
90 | { | |
91 | return __rblist__findnew(rblist, entry, true); | |
37bbd3ff DA |
92 | } |
93 | ||
94 | void 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 | ||
104 | void 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); | |
03f2f93a | 112 | rblist__remove_node(rblist, pos); |
37bbd3ff DA |
113 | } |
114 | free(rblist); | |
115 | } | |
116 | } | |
117 | ||
118 | struct 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 | } |