libisofs  1.5.4
About: libisofs is a library to create an ISO 9660 filesystem, supports extensions like RockRidge or Joliet, makes bootable ISO 9660, and records file attributes which are of interest for data backups.
  Fossies Dox: libisofs-1.5.4.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

util_rbtree.c File Reference
#include "util.h"
#include "libisofs.h"
#include <stdlib.h>
Include dependency graph for util_rbtree.c:

Go to the source code of this file.

Data Structures

struct  iso_rbnode
 
struct  iso_rbtree
 

Functions

int iso_rbtree_new (int(*compare)(const void *, const void *), IsoRBTree **tree)
 Create a new binary tree. More...
 
static void rbtree_destroy_aux (struct iso_rbnode *root, void(*free_data)(void *))
 
void iso_rbtree_destroy (IsoRBTree *tree, void(*free_data)(void *))
 Destroy a given tree. More...
 
static int is_red (struct iso_rbnode *root)
 
static struct iso_rbnodeiso_rbtree_single (struct iso_rbnode *root, int dir)
 
static struct iso_rbnodeiso_rbtree_double (struct iso_rbnode *root, int dir)
 
static struct iso_rbnodeiso_rbnode_new (void *data)
 
int iso_rbtree_insert (IsoRBTree *tree, void *data, void **item)
 Inserts a given element in a Red-Black tree. More...
 
size_t iso_rbtree_get_size (IsoRBTree *tree)
 Get the number of elements in a given tree. More...
 
static size_t rbtree_to_array_aux (struct iso_rbnode *root, void **array, size_t pos, int(*include_item)(void *))
 
void ** iso_rbtree_to_array (IsoRBTree *tree, int(*include_item)(void *), size_t *size)
 Get an array view of the elements of the tree. More...
 
static size_t rbtree_count_array_aux (struct iso_rbnode *root, size_t pos, int(*include_item)(void *))
 
size_t iso_rbtree_count_array (IsoRBTree *tree, size_t initial_count, int(*include_item)(void *))
 Predict the size of the array which gets returned by iso_rbtree_to_array(). More...
 

Function Documentation

◆ is_red()

static int is_red ( struct iso_rbnode root)
inlinestatic

Definition at line 94 of file util_rbtree.c.

95 {
96  return root != NULL && root->red;
97 }
unsigned int red
Definition: util_rbtree.c:28

References iso_rbnode::red.

Referenced by iso_rbtree_insert().

◆ iso_rbnode_new()

static struct iso_rbnode* iso_rbnode_new ( void *  data)
static

Definition at line 120 of file util_rbtree.c.

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 }
void * data
Definition: util_rbtree.c:26
struct iso_rbnode * ch[2]
Definition: util_rbtree.c:27

References iso_rbnode::ch, iso_rbnode::data, and iso_rbnode::red.

Referenced by iso_rbtree_insert().

◆ iso_rbtree_count_array()

size_t iso_rbtree_count_array ( IsoRBTree tree,
size_t  initial_count,
int(*)(void *)  include_item 
)

Predict the size of the array which gets returned by iso_rbtree_to_array().

Definition at line 337 of file util_rbtree.c.

339 {
340  size_t pos;
341 
342  pos = rbtree_count_array_aux(tree->root, initial_count, include_item);
343  return pos;
344 }
struct iso_rbnode * root
Definition: util_rbtree.c:33
static size_t rbtree_count_array_aux(struct iso_rbnode *root, size_t pos, int(*include_item)(void *))
Definition: util_rbtree.c:313

References rbtree_count_array_aux(), and iso_rbtree::root.

Referenced by filesrc_writer_pre_compute().

◆ iso_rbtree_destroy()

void iso_rbtree_destroy ( IsoRBTree tree,
void(*)(void *)  free_data 
)

Destroy a given tree.

Note that only the structure itself is deleted. To delete the elements, you should provide a valid free_data function. It will be called for each element of the tree, so you can use it to free any related data.

Definition at line 84 of file util_rbtree.c.

85 {
86  if (tree == NULL) {
87  return;
88  }
89  rbtree_destroy_aux(tree->root, free_data);
90  free(tree);
91 }
static void rbtree_destroy_aux(struct iso_rbnode *root, void(*free_data)(void *))
Definition: util_rbtree.c:64

References rbtree_destroy_aux(), and iso_rbtree::root.

Referenced by ecma119_image_free().

◆ iso_rbtree_double()

static struct iso_rbnode* iso_rbtree_double ( struct iso_rbnode root,
int  dir 
)
static

Definition at line 113 of file util_rbtree.c.

114 {
115  root->ch[!dir] = iso_rbtree_single(root->ch[!dir], !dir);
116  return iso_rbtree_single(root, dir);
117 }
static struct iso_rbnode * iso_rbtree_single(struct iso_rbnode *root, int dir)
Definition: util_rbtree.c:100

References iso_rbnode::ch, and iso_rbtree_single().

Referenced by iso_rbtree_insert().

◆ iso_rbtree_get_size()

size_t iso_rbtree_get_size ( IsoRBTree tree)

Get the number of elements in a given tree.

Definition at line 250 of file util_rbtree.c.

251 {
252  return tree->size;
253 }
size_t size
Definition: util_rbtree.c:34

References iso_rbtree::size.

◆ iso_rbtree_insert()

int iso_rbtree_insert ( IsoRBTree tree,
void *  data,
void **  item 
)

Inserts a given element in a Red-Black tree.

Parameters
treethe tree where to insert
dataelement to be inserted on the tree. It can't be NULL
itemif not NULL, it will point to a location where the tree element ptr will be stored. If data was inserted, *item == data. If data was already on the tree, *item points to the previously inserted object that is equal to data.
Returns
1 success, 0 element already inserted, < 0 error

Definition at line 149 of file util_rbtree.c.

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 }
#define ISO_OUT_OF_MEM
Memory allocation error (FATAL,HIGH, -6)
Definition: libisofs.h:8745
#define ISO_NULL_POINTER
NULL pointer as value for an arg.
Definition: libisofs.h:8742
int(* compare)(const void *a, const void *b)
Definition: util_rbtree.c:35
static struct iso_rbnode * iso_rbtree_double(struct iso_rbnode *root, int dir)
Definition: util_rbtree.c:113
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

References iso_rbnode::ch, iso_rbtree::compare, iso_rbnode::data, is_red(), ISO_NULL_POINTER, ISO_OUT_OF_MEM, iso_rbnode_new(), iso_rbtree_double(), iso_rbtree_single(), iso_rbnode::red, iso_rbtree::root, and iso_rbtree::size.

Referenced by iso_file_src_add(), and iso_file_src_create().

◆ iso_rbtree_new()

int iso_rbtree_new ( int(*)(const void *, const void *)  compare,
IsoRBTree **  tree 
)

Create a new binary tree.

libisofs binary trees allow you to add any data passing it as a pointer. You must provide a function suitable for compare two elements.

Parameters
compareA function to compare two elements. It takes a pointer to both elements and return 0, -1 or 1 if the first element is equal, less or greater than the second one.
treeLocation where the tree structure will be stored.

Definition at line 50 of file util_rbtree.c.

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 }
#define ISO_SUCCESS
successfully execution
Definition: libisofs.h:8719

References ISO_NULL_POINTER, ISO_OUT_OF_MEM, and ISO_SUCCESS.

Referenced by ecma119_image_new().

◆ iso_rbtree_single()

static struct iso_rbnode* iso_rbtree_single ( struct iso_rbnode root,
int  dir 
)
static

Definition at line 100 of file util_rbtree.c.

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 }

References iso_rbnode::ch, and iso_rbnode::red.

Referenced by iso_rbtree_double(), and iso_rbtree_insert().

◆ iso_rbtree_to_array()

void** iso_rbtree_to_array ( IsoRBTree tree,
int(*)(void *)  include_item,
size_t *  size 
)

Get an array view of the elements of the tree.

Parameters
include_itemFunction to select which elements to include in the array. It that takes a pointer to an element and returns 1 if the element should be included, 0 if not. If you want to add all elements to the array, you can pass a NULL pointer.
Returns
A sorted array with the contents of the tree, or NULL if there is not enough memory to allocate the array. You should free(3) the array when no more needed. Note that the array is NULL-terminated, and thus it has size + 1 length.

Definition at line 284 of file util_rbtree.c.

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 }
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

References rbtree_to_array_aux(), iso_rbtree::root, and iso_rbtree::size.

Referenced by filesrc_writer_pre_compute().

◆ rbtree_count_array_aux()

static size_t rbtree_count_array_aux ( struct iso_rbnode root,
size_t  pos,
int(*)(void *)  include_item 
)
static

Definition at line 313 of file util_rbtree.c.

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 }

References iso_rbnode::ch, and iso_rbnode::data.

Referenced by iso_rbtree_count_array().

◆ rbtree_destroy_aux()

static void rbtree_destroy_aux ( struct iso_rbnode root,
void(*)(void *)  free_data 
)
static

Definition at line 64 of file util_rbtree.c.

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 }

References iso_rbnode::ch, and iso_rbnode::data.

Referenced by iso_rbtree_destroy().

◆ rbtree_to_array_aux()

static size_t rbtree_to_array_aux ( struct iso_rbnode root,
void **  array,
size_t  pos,
int(*)(void *)  include_item 
)
static

Definition at line 256 of file util_rbtree.c.

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 }

References iso_rbnode::ch, and iso_rbnode::data.

Referenced by iso_rbtree_to_array().