"Fossies" - the Fresh Open Source Software Archive 
Member "libisofs-1.5.4/libisofs/util_rbtree.c" (8 Jul 2020, 8715 Bytes) of package /linux/misc/libisofs-1.5.4.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "util_rbtree.c" see the
Fossies "Dox" file reference documentation and the latest
Fossies "Diffs" side-by-side code changes report:
1.5.2_vs_1.5.4.
1 /*
2 * Copyright (c) 2007 Vreixo Formoso
3 *
4 * This file is part of the libisofs project; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License version 2
6 * or later as published by the Free Software Foundation.
7 * See COPYING file for details.
8 */
9
10 #ifdef HAVE_CONFIG_H
11 #include "../config.h"
12 #endif
13
14 #include "util.h"
15 #include "libisofs.h"
16
17 #include <stdlib.h>
18
19 /*
20 * This implementation of Red-Black tree is based on the public domain
21 * implementation of Julienne Walker.
22 */
23
24 struct iso_rbnode
25 {
26 void *data;
27 struct iso_rbnode *ch[2];
28 unsigned int red :1;
29 };
30
31 struct iso_rbtree
32 {
33 struct iso_rbnode *root;
34 size_t size;
35 int (*compare)(const void *a, const void *b);
36 };
37
38 /**
39 * Create a new binary tree. libisofs binary trees allow you to add any data
40 * passing it as a pointer. You must provide a function suitable for compare
41 * two elements.
42 *
43 * @param compare
44 * A function to compare two elements. It takes a pointer to both elements
45 * and return 0, -1 or 1 if the first element is equal, less or greater
46 * than the second one.
47 * @param tree
48 * Location where the tree structure will be stored.
49 */
50 int iso_rbtree_new(int (*compare)(const void*, const void*), IsoRBTree **tree)
51 {
52 if (compare == NULL || tree == NULL) {
53 return ISO_NULL_POINTER;
54 }
55 *tree = calloc(1, sizeof(IsoRBTree));
56 if (*tree == NULL) {
57 return ISO_OUT_OF_MEM;
58 }
59 (*tree)->compare = compare;
60 return ISO_SUCCESS;
61 }
62
63 static
64 void rbtree_destroy_aux(struct iso_rbnode *root, void (*free_data)(void *))
65 {
66 if (root == NULL) {
67 return;
68 }
69 if (free_data != NULL) {
70 free_data(root->data);
71 }
72 rbtree_destroy_aux(root->ch[0], free_data);
73 rbtree_destroy_aux(root->ch[1], free_data);
74 free(root);
75 }
76
77 /**
78 * Destroy a given tree.
79 *
80 * Note that only the structure itself is deleted. To delete the elements, you
81 * should provide a valid free_data function. It will be called for each
82 * element of the tree, so you can use it to free any related data.
83 */
84 void iso_rbtree_destroy(IsoRBTree *tree, void (*free_data)(void *))
85 {
86 if (tree == NULL) {
87 return;
88 }
89 rbtree_destroy_aux(tree->root, free_data);
90 free(tree);
91 }
92
93 static inline
94 int is_red(struct iso_rbnode *root)
95 {
96 return root != NULL && root->red;
97 }
98
99 static
100 struct iso_rbnode *iso_rbtree_single(struct iso_rbnode *root, int dir)
101 {
102 struct iso_rbnode *save = root->ch[!dir];
103
104 root->ch[!dir] = save->ch[dir];
105 save->ch[dir] = root;
106
107 root->red = 1;
108 save->red = 0;
109 return save;
110 }
111
112 static
113 struct iso_rbnode *iso_rbtree_double(struct iso_rbnode *root, int dir)
114 {
115 root->ch[!dir] = iso_rbtree_single(root->ch[!dir], !dir);
116 return iso_rbtree_single(root, dir);
117 }
118
119 static
120 struct iso_rbnode *iso_rbnode_new(void *data)
121 {
122 struct iso_rbnode *rn = malloc(sizeof(struct iso_rbnode));
123
124 if (rn != NULL) {
125 rn->data = data;
126 rn->red = 1;
127 rn->ch[0] = NULL;
128 rn->ch[1] = NULL;
129 }
130
131 return rn;
132 }
133
134 /**
135 * Inserts a given element in a Red-Black tree.
136 *
137 * @param tree
138 * the tree where to insert
139 * @param data
140 * element to be inserted on the tree. It can't be NULL
141 * @param item
142 * if not NULL, it will point to a location where the tree element ptr
143 * will be stored. If data was inserted, *item == data. If data was
144 * already on the tree, *item points to the previously inserted object
145 * that is equal to data.
146 * @return
147 * 1 success, 0 element already inserted, < 0 error
148 */
149 int iso_rbtree_insert(IsoRBTree *tree, void *data, void **item)
150 {
151 struct iso_rbnode *new;
152 int added = 0; /* has a new node been added? */
153
154 if (tree == NULL || data == NULL) {
155 return ISO_NULL_POINTER;
156 }
157
158 if (tree->root == NULL) {
159 /* Empty tree case */
160 tree->root = iso_rbnode_new(data);
161 if (tree->root == NULL) {
162 return ISO_OUT_OF_MEM;
163 }
164 new = data;
165 added = 1;
166 } else {
167 struct iso_rbnode head = { 0, {NULL, NULL}, 0 }; /* False tree root */
168
169 struct iso_rbnode *g, *t; /* Grandparent & parent */
170 struct iso_rbnode *p, *q; /* Iterator & parent */
171 int dir = 0, last = 0;
172 int comp;
173
174 /* Set up helpers */
175 t = &head;
176 g = p = NULL;
177 q = t->ch[1] = tree->root;
178
179 /* Search down the tree */
180 while (1) {
181 if (q == NULL) {
182 /* Insert new node at the bottom */
183 p->ch[dir] = q = iso_rbnode_new(data);
184 if (q == NULL) {
185 return ISO_OUT_OF_MEM;
186 }
187 added = 1;
188 } else if (is_red(q->ch[0]) && is_red(q->ch[1])) {
189 /* Color flip */
190 q->red = 1;
191 q->ch[0]->red = 0;
192 q->ch[1]->red = 0;
193 }
194
195 /* Fix red violation */
196 if (is_red(q) && is_red(p)) {
197 int dir2 = (t->ch[1] == g);
198
199 if (q == p->ch[last]) {
200 t->ch[dir2] = iso_rbtree_single(g, !last);
201 } else {
202 t->ch[dir2] = iso_rbtree_double(g, !last);
203 }
204 }
205
206 if (q->data == data) {
207 comp = 0;
208 } else {
209 comp = tree->compare(q->data, data);
210 }
211
212 /* Stop if found */
213 if (comp == 0) {
214 new = q->data;
215 break;
216 }
217
218 last = dir;
219 dir = (comp < 0);
220
221 /* Update helpers */
222 if (g != NULL)
223 t = g;
224 g = p, p = q;
225 q = q->ch[dir];
226 }
227
228 /* Update root */
229 tree->root = head.ch[1];
230 }
231
232 /* Make root black */
233 tree->root->red = 0;
234
235 if (item != NULL) {
236 *item = new;
237 }
238 if (added) {
239 /* a new element has been added */
240 tree->size++;
241 return 1;
242 } else {
243 return 0;
244 }
245 }
246
247 /**
248 * Get the number of elements in a given tree.
249 */
250 size_t iso_rbtree_get_size(IsoRBTree *tree)
251 {
252 return tree->size;
253 }
254
255 static
256 size_t rbtree_to_array_aux(struct iso_rbnode *root, void **array, size_t pos,
257 int (*include_item)(void *))
258 {
259 if (root == NULL) {
260 return pos;
261 }
262 pos = rbtree_to_array_aux(root->ch[0], array, pos, include_item);
263 if (include_item == NULL || include_item(root->data)) {
264 array[pos++] = root->data;
265 }
266 pos = rbtree_to_array_aux(root->ch[1], array, pos, include_item);
267 return pos;
268 }
269
270 /**
271 * Get an array view of the elements of the tree.
272 *
273 * @param include_item
274 * Function to select which elements to include in the array. It that takes
275 * a pointer to an element and returns 1 if the element should be included,
276 * 0 if not. If you want to add all elements to the array, you can pass a
277 * NULL pointer.
278 * @return
279 * A sorted array with the contents of the tree, or NULL if there is not
280 * enough memory to allocate the array. You should free(3) the array when
281 * no more needed. Note that the array is NULL-terminated, and thus it
282 * has size + 1 length.
283 */
284 void ** iso_rbtree_to_array(IsoRBTree *tree, int (*include_item)(void *),
285 size_t *size)
286 {
287 size_t pos;
288 void **array, **new_array;
289
290 array = malloc((tree->size + 1) * sizeof(void*));
291 if (array == NULL) {
292 return NULL;
293 }
294
295 /* fill array */
296 pos = rbtree_to_array_aux(tree->root, array, 0, include_item);
297 array[pos] = NULL;
298
299 new_array = realloc(array, (pos + 1) * sizeof(void*));
300 if (new_array == NULL) {
301 free((char *) array);
302 return NULL;
303 }
304 array= new_array;
305 if (size) {
306 *size = pos;
307 }
308 return array;
309 }
310
311
312 static
313 size_t rbtree_count_array_aux(struct iso_rbnode *root, size_t pos,
314 int (*include_item)(void *))
315 {
316 if (root == NULL) {
317 return pos;
318 }
319 pos = rbtree_count_array_aux(root->ch[0], pos, include_item);
320 if (include_item == NULL || include_item(root->data)) {
321
322 /*
323 {
324 IsoFileSrc* src = (IsoFileSrc*) root->data;
325 fprintf(stderr, "libisofs_DEBUG: rbtree_count_array_aux : not taken : '%s'\n",
326 iso_stream_get_source_path(src->stream, 0));
327 }
328 */
329
330 pos++;
331 }
332 pos = rbtree_count_array_aux(root->ch[1], pos, include_item);
333 return pos;
334 }
335
336
337 size_t iso_rbtree_count_array(IsoRBTree *tree, size_t initial_count,
338 int (*include_item)(void *))
339 {
340 size_t pos;
341
342 pos = rbtree_count_array_aux(tree->root, initial_count, include_item);
343 return pos;
344 }
345