"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