src/include/utils/avltree.h

   1 /*
   2  * SysDB - src/include/utils/avltree.h
   3  * Copyright (C) 2014 Sebastian 'tokkee' Harl <sh@tokkee.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  16  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  17  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  18  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
  19  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  20  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #ifndef SDB_UTILS_AVLTREE_H
  29 #define SDB_UTILS_AVLTREE_H 1
  30
  31 #include "core/object.h"
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 /*
  38  * An AVL tree implements Adelson-Velskii and Landis' self-balancing search
  39  * tree. It supports search, insert, and delete operations in average and
  40  * worst-case time-complexity O(log n).
  41  */
  42 struct sdb_avltree;
  43 typedef struct sdb_avltree sdb_avltree_t;
  44
  45 struct sdb_avltree_iter;
  46 typedef struct sdb_avltree_iter sdb_avltree_iter_t;
  47
  48 /*
  49  * sdb_avltree_create:
  50  * Creates an AVL tree. Insert and lookup operations will use the specified
  51  * compare function to determine the location of an object in the tree. If no
  52  * function has been specified, it defaults to sdb_object_cmp_by_name, that
  53  * is, objects will be compared by their names.
  54  */
  55 sdb_avltree_t *
  56 sdb_avltree_create(sdb_object_cmp_cb cmp);
  57
  58 /*
  59  * sdb_avltree_destroy:
  60  * Destroy the specified AVL tree and release all included objects (decrement
  61  * the ref-count).
  62  */
  63 void
  64 sdb_avltree_destroy(sdb_avltree_t *tree);
  65
  66 /*
  67  * sdb_avltree_clear:
  68  * Remove all nodes from the tree, releasing the included objects (decrement
  69  * the ref-count).
  70  */
  71 void
  72 sdb_avltree_clear(sdb_avltree_t *tree);
  73
  74 /*
  75  * sdb_avltree_insert:
  76  * Insert a new node into the tree (using the tree's compare function to find
  77  * the right location). Each object must be unique (based on the compare
  78  * function). This operation may change the structure of the tree by
  79  * rebalancing subtrees which no longer comply with the rules of AVL.
  80  *
  81  * Returns:
  82  *  - 0 on success
  83  *  - a negative value else
  84  */
  85 int
  86 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj);
  87
  88 /*
  89  * sdb_avltree_lookup:
  90  * Lookup an object from a tree. The object matching the specified reference
  91  * object (using the tree's compare function) will be returned.
  92  *
  93  * Returns:
  94  *  - the requested object
  95  *  - NULL if no such object exists
  96  */
  97 sdb_object_t *
  98 sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref);
  99
 100 /*
 101  * sdb_avltree_get_iter, sdb_avltree_iter_has_next, sdb_avltree_iter_get_next,
 102  * sdb_avltree_iter_destroy:
 103  * Iterate through all nodes of the tree. The iterator will start at the
 104  * smallest element (based on the tree's compare function) and then iterate
 105  * through the sorted sequence of all nodes.
 106  *
 107  * sdb_avltree_iter_get_next returns NULL if there is no next element.
 108  */
 109 sdb_avltree_iter_t *
 110 sdb_avltree_get_iter(sdb_avltree_t *tree);
 111 void
 112 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter);
 113
 114 _Bool
 115 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter);
 116 sdb_object_t *
 117 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter);
 118
 119 /*
 120  * sdb_avltree_size:
 121  * Returns the number of nodes in the tree.
 122  */
 123 size_t
 124 sdb_avltree_size(sdb_avltree_t *tree);
 125
 126 /*
 127  * sdb_avltree_valid:
 128  * Validate a tree, checking if all rules of AVL are met. All errors will be
 129  * reported through the logging sub-system. This function is mainly intended
 130  * for debugging and (unit) testing.
 131  *
 132  * Returns:
 133  *  - true if the tree is valid
 134  *  - false else
 135  */
 136 _Bool
 137 sdb_avltree_valid(sdb_avltree_t *tree);
 138
 139 #ifdef __cplusplus
 140 } /* extern "C" */
 141 #endif
 142
 143 #endif /* ! SDB_UTILS_AVLTREE_H */
 144
 145 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 146