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_rbnode *	iso_rbtree_single (struct iso_rbnode *root, int dir)
static struct iso_rbnode *	iso_rbtree_double (struct iso_rbnode *root, int dir)
static struct iso_rbnode *	iso_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.

{
    return root != NULL && root->red;
}

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.

{
    struct iso_rbnode *rn = malloc(sizeof(struct iso_rbnode));
 
    if (rn != NULL) {
        rn->data = data;
        rn->red = 1;
        rn->ch[0] = NULL;
        rn->ch[1] = NULL;
    }
 
    return rn;
}

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.

{
    size_t pos;
 
    pos = rbtree_count_array_aux(tree->root, initial_count, include_item);
    return pos;
}

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.

{
    if (tree == NULL) {
        return;
    }
    rbtree_destroy_aux(tree->root, free_data);
    free(tree);
}

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.

{
    root->ch[!dir] = iso_rbtree_single(root->ch[!dir], !dir);
    return iso_rbtree_single(root, dir);
}

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.

{
    return tree->size;
}

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

tree	the tree where to insert
data	element to be inserted on the tree. It can't be NULL
item	if 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.

{
    struct iso_rbnode *new;
    int added = 0; /* has a new node been added? */
 
    if (tree == NULL || data == NULL) {
        return ISO_NULL_POINTER;
    }
 
    if (tree->root == NULL) {
        /* Empty tree case */
        tree->root = iso_rbnode_new(data);
        if (tree->root == NULL) {
            return ISO_OUT_OF_MEM;
        }
        new = data;
        added = 1;
    } else {
        struct iso_rbnode head = { 0, {NULL, NULL}, 0 }; /* False tree root */
 
        struct iso_rbnode *g, *t; /* Grandparent & parent */
        struct iso_rbnode *p, *q; /* Iterator & parent */
        int dir = 0, last = 0;
        int comp;
 
        /* Set up helpers */
        t = &head;
        g = p = NULL;
        q = t->ch[1] = tree->root;
 
        /* Search down the tree */
        while (1) {
            if (q == NULL) {
                /* Insert new node at the bottom */
                p->ch[dir] = q = iso_rbnode_new(data);
                if (q == NULL) {
                    return ISO_OUT_OF_MEM;
                }
                added = 1;
            } else if (is_red(q->ch[0]) && is_red(q->ch[1])) {
                /* Color flip */
                q->red = 1;
                q->ch[0]->red = 0;
                q->ch[1]->red = 0;
            }
 
            /* Fix red violation */
            if (is_red(q) && is_red(p)) {
                int dir2 = (t->ch[1] == g);
 
                if (q == p->ch[last]) {
                    t->ch[dir2] = iso_rbtree_single(g, !last);
                } else {
                    t->ch[dir2] = iso_rbtree_double(g, !last);
                }
            }
 
            if (q->data == data) {
                comp = 0;
            } else {
                comp = tree->compare(q->data, data);
            }
 
            /* Stop if found */
            if (comp == 0) {
                new = q->data;
                break;
            }
 
            last = dir;
            dir = (comp < 0);
 
            /* Update helpers */
            if (g != NULL)
                t = g;
            g = p, p = q;
            q = q->ch[dir];
        }
 
        /* Update root */
        tree->root = head.ch[1];
    }
 
    /* Make root black */
    tree->root->red = 0;
 
    if (item != NULL) {
        *item = new;
    }
    if (added) {
        /* a new element has been added */
        tree->size++;
        return 1;
    } else {
        return 0;
    }
}

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

compare	A 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.
tree	Location where the tree structure will be stored.

Definition at line 50 of file util_rbtree.c.

{
    if (compare == NULL || tree == NULL) {
        return ISO_NULL_POINTER;
    }
    *tree = calloc(1, sizeof(IsoRBTree));
    if (*tree == NULL) {
        return ISO_OUT_OF_MEM;
    }
    (*tree)->compare = compare;
    return ISO_SUCCESS;
}

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.

{
    struct iso_rbnode *save = root->ch[!dir];
 
    root->ch[!dir] = save->ch[dir];
    save->ch[dir] = root;
 
    root->red = 1;
    save->red = 0;
    return save;
}

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_item

Function 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.

{
    size_t pos;
    void **array, **new_array;
 
    array = malloc((tree->size + 1) * sizeof(void*));
    if (array == NULL) {
        return NULL;
    }
 
    /* fill array */
    pos = rbtree_to_array_aux(tree->root, array, 0, include_item);
    array[pos] = NULL;
 
    new_array = realloc(array, (pos + 1) * sizeof(void*));
    if (new_array == NULL) {
        free((char *) array);
        return NULL;
    }
    array= new_array;
    if (size) {
        *size = pos;
    }
    return array;
}

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.

{
    if (root == NULL) {
        return pos;
    }
    pos = rbtree_count_array_aux(root->ch[0], pos, include_item);
    if (include_item == NULL || include_item(root->data)) {
 
/*
{
IsoFileSrc* src = (IsoFileSrc*) root->data;
fprintf(stderr, "libisofs_DEBUG: rbtree_count_array_aux : not taken : '%s'\n",
                iso_stream_get_source_path(src->stream, 0));
}       
*/
 
        pos++;
    }
    pos = rbtree_count_array_aux(root->ch[1], pos, include_item);
    return pos;
}

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.

{
    if (root == NULL) {
        return;
    }
    if (free_data != NULL) {
        free_data(root->data);
    }
    rbtree_destroy_aux(root->ch[0], free_data);
    rbtree_destroy_aux(root->ch[1], free_data);
    free(root);
}

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.

{
    if (root == NULL) {
        return pos;
    }
    pos = rbtree_to_array_aux(root->ch[0], array, pos, include_item);
    if (include_item == NULL || include_item(root->data)) {
        array[pos++] = root->data;
    }
    pos = rbtree_to_array_aux(root->ch[1], array, pos, include_item);
    return pos;
}

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

Referenced by iso_rbtree_to_array().