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 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)
 
static void rbtree_destroy_aux (struct iso_rbnode *root, void(*free_data)(void *))
 
void iso_rbtree_destroy (IsoRBTree *tree, void(*free_data)(void *))
 
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)
 
size_t iso_rbtree_get_size (IsoRBTree *tree)
 
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)
 
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 *))
 

Function Documentation

◆ is_red()

static int is_red ( struct iso_rbnode root)
inlinestatic

Definition at line 94 of file util_rbtree.c.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

Referenced by iso_rbtree_to_array().