xorriso  1.5.4.pl02
About: GNU xorriso creates, loads, manipulates and writes ISO 9660 filesystem images with Rock Ridge extensions. It is suitable for incremental data backup and for production of bootable ISO 9660 images. GNU xorriso is a statical compilation of the libraries libburn, libisofs, libisoburn, and libjte.
  Fossies Dox: xorriso-1.5.4.pl02.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

util_rbtree.c
Go to the documentation of this file.
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
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  */
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 
#define ISO_SUCCESS
Definition: libisofs.h:8719
#define ISO_OUT_OF_MEM
Definition: libisofs.h:8745
#define ISO_NULL_POINTER
Definition: libisofs.h:8742
void * data
Definition: util_rbtree.c:26
struct iso_rbnode * ch[2]
Definition: util_rbtree.c:27
unsigned int red
Definition: util_rbtree.c:28
int(* compare)(const void *a, const void *b)
Definition: util_rbtree.c:35
struct iso_rbnode * root
Definition: util_rbtree.c:33
size_t size
Definition: util_rbtree.c:34
static struct iso_rbnode * iso_rbtree_double(struct iso_rbnode *root, int dir)
Definition: util_rbtree.c:113
size_t iso_rbtree_count_array(IsoRBTree *tree, size_t initial_count, int(*include_item)(void *))
Definition: util_rbtree.c:337
static void rbtree_destroy_aux(struct iso_rbnode *root, void(*free_data)(void *))
Definition: util_rbtree.c:64
size_t iso_rbtree_get_size(IsoRBTree *tree)
Definition: util_rbtree.c:250
static size_t rbtree_to_array_aux(struct iso_rbnode *root, void **array, size_t pos, int(*include_item)(void *))
Definition: util_rbtree.c:256
void iso_rbtree_destroy(IsoRBTree *tree, void(*free_data)(void *))
Definition: util_rbtree.c:84
int iso_rbtree_new(int(*compare)(const void *, const void *), IsoRBTree **tree)
Definition: util_rbtree.c:50
static struct iso_rbnode * iso_rbnode_new(void *data)
Definition: util_rbtree.c:120
static int is_red(struct iso_rbnode *root)
Definition: util_rbtree.c:94
static struct iso_rbnode * iso_rbtree_single(struct iso_rbnode *root, int dir)
Definition: util_rbtree.c:100
static size_t rbtree_count_array_aux(struct iso_rbnode *root, size_t pos, int(*include_item)(void *))
Definition: util_rbtree.c:313
int iso_rbtree_insert(IsoRBTree *tree, void *data, void **item)
Definition: util_rbtree.c:149
void ** iso_rbtree_to_array(IsoRBTree *tree, int(*include_item)(void *), size_t *size)
Definition: util_rbtree.c:284