/usr/include/sc_avl.h is in libp4est-dev 1.1-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 | /* *INDENT-OFF* */
/*****************************************************************************
avl.h - Source code for the AVL-tree library.
Copyright (C) 1998 Michael H. Buselli <cosine@cosine.org>
Copyright (C) 2000-2002 Wessel Dankers <wsl@nl.linux.org>
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Augmented AVL-tree. Original by Michael H. Buselli <cosine@cosine.org>.
Modified by Wessel Dankers <wsl@nl.linux.org> to add a bunch of bloat to
the sourcecode, change the interface and squash a few bugs.
Mail him if you find new bugs.
*****************************************************************************/
/* renamed from avl.h to sc_avl.h for the SC Library and modified */
#ifndef _AVL_H
#define _AVL_H
#include <sc_containers.h>
SC_EXTERN_C_BEGIN;
/* modification to use count only */
#define AVL_COUNT
/* We need either depths, counts or both (the latter being the default) */
#if !defined(AVL_DEPTH) && !defined(AVL_COUNT)
#define AVL_DEPTH
#define AVL_COUNT
#endif
/* User supplied function to compare two items like strcmp() does.
* For example: cmp(a,b) will return:
* -1 if a < b
* 0 if a = b
* 1 if a > b
*/
typedef int (*avl_compare_t)(const void *, const void *);
/* User supplied function to delete an item when a node is free()d.
* If NULL, the item is not free()d.
*/
typedef void (*avl_freeitem_t)(void *);
/* User supplied function to call on an item in foreach().
*/
typedef void (*avl_foreach_t)(void *, void *);
typedef struct avl_node_t {
struct avl_node_t *next;
struct avl_node_t *prev;
struct avl_node_t *parent;
struct avl_node_t *left;
struct avl_node_t *right;
void *item;
#ifdef AVL_COUNT
unsigned int count;
#endif
#ifdef AVL_DEPTH
unsigned char depth;
#endif
} avl_node_t;
typedef struct avl_tree_t {
avl_node_t *head;
avl_node_t *tail;
avl_node_t *top;
avl_compare_t cmp;
avl_freeitem_t freeitem;
} avl_tree_t;
/* Initializes a new tree for elements that will be ordered using
* the supplied strcmp()-like function.
* Returns the value of avltree (even if it's NULL).
* O(1) */
extern avl_tree_t *avl_init_tree(avl_tree_t *avltree, avl_compare_t, avl_freeitem_t);
/* Allocates and initializes a new tree for elements that will be
* ordered using the supplied strcmp()-like function.
* Aborts if memory could not be allocated.
* O(1) */
extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_freeitem_t);
/* Frees the entire tree efficiently. Nodes will be free()d.
* If the tree's freeitem is not NULL it will be invoked on every item.
* O(n) */
extern void avl_free_tree(avl_tree_t *);
/* Reinitializes the tree structure for reuse. Nothing is free()d.
* Compare and freeitem functions are left alone.
* O(1) */
extern void avl_clear_tree(avl_tree_t *);
/* Free()s all nodes in the tree but leaves the tree itself.
* If the tree's freeitem is not NULL it will be invoked on every item.
* O(n) */
extern void avl_free_nodes(avl_tree_t *);
/* Initializes memory for use as a node. Returns NULL if avlnode is NULL.
* O(1) */
extern avl_node_t *avl_init_node(avl_node_t *avlnode, void *item);
/* Insert an item into the tree and return the new node.
* Aborts if memory for the new node could not be allocated.
* Returns NULL if the node is already in the tree, or the new node.
* O(lg n) */
extern avl_node_t *avl_insert(avl_tree_t *, void *item);
/* Insert a node into the tree and return it.
* Returns NULL if the node is already in the tree.
* O(lg n) */
extern avl_node_t *avl_insert_node(avl_tree_t *, avl_node_t *);
/* Insert a node in an empty tree. If avlnode is NULL, the tree will be
* cleared and ready for re-use.
* If the tree is not empty, the old nodes are left dangling.
* O(1) */
extern avl_node_t *avl_insert_top(avl_tree_t *, avl_node_t *avlnode);
/* Insert a node before another node. Returns the new node.
* If old is NULL, the item is appended to the tree.
* O(lg n) */
extern avl_node_t *avl_insert_before(avl_tree_t *, avl_node_t *old, avl_node_t *nw);
/* Insert a node after another node. Returns the new node.
* If old is NULL, the item is prepended to the tree.
* O(lg n) */
extern avl_node_t *avl_insert_after(avl_tree_t *, avl_node_t *old, avl_node_t *nw);
/* Deletes a node from the tree. Returns immediately if the node is NULL.
* The item will not be free()d regardless of the tree's freeitem handler.
* This function comes in handy if you need to update the search key.
* O(lg n) */
extern void avl_unlink_node(avl_tree_t *, avl_node_t *);
/* Deletes a node from the tree. Returns immediately if the node is NULL.
* If the tree's freeitem is not NULL, it is invoked on the item.
* If it is, returns the item.
* O(lg n) */
extern void *avl_delete_node(avl_tree_t *, avl_node_t *);
/* Searches for an item in the tree and deletes it if found.
* If the tree's freeitem is not NULL, it is invoked on the item.
* If it is, returns the item.
* O(lg n) */
extern void *avl_delete(avl_tree_t *, const void *item);
/* If exactly one node is moved in memory, this will fix the pointers
* in the tree that refer to it. It must be an exact shallow copy.
* Returns the pointer to the old position.
* O(1) */
extern avl_node_t *avl_fixup_node(avl_tree_t *, avl_node_t *nw);
/* Searches for a node with the key closest (or equal) to the given item.
* If avlnode is not NULL, *avlnode will be set to the node found or NULL
* if the tree is empty. Return values:
* -1 if the returned node is smaller
* 0 if the returned node is equal or if the tree is empty
* 1 if the returned node is greater
* O(lg n) */
extern int avl_search_closest(const avl_tree_t *, const void *item, avl_node_t **avlnode);
/* Searches for the item in the tree and returns a matching node if found
* or NULL if not.
* O(lg n) */
extern avl_node_t *avl_search(const avl_tree_t *, const void *item);
/* Calls the callback function for every item in the tree in order.
* O(n) */
extern void avl_foreach(avl_tree_t *, avl_foreach_t, void *);
#ifdef AVL_COUNT
/* Returns the number of nodes in the tree.
* O(1) */
extern unsigned int avl_count(const avl_tree_t *);
/* Searches a node by its rank in the list. Counting starts at 0.
* Returns NULL if the index exceeds the number of nodes in the tree.
* O(lg n) */
extern avl_node_t *avl_at(const avl_tree_t *, unsigned int);
/* Returns the rank of a node in the list. Counting starts at 0.
* O(lg n) */
extern unsigned int avl_index(const avl_node_t *);
/* Copies all items into an array of void *.
* O(n) */
extern void avl_to_array (avl_tree_t *, sc_array_t *);
#endif /* AVL_COUNT */
SC_EXTERN_C_END;
#endif /* !_AVL_H */
|