File: AVLTree.h

package info (click to toggle)
debfoster 2.7-2.1
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid, stretch
  • size: 1,188 kB
  • sloc: sh: 4,243; ansic: 2,397; perl: 39; makefile: 26; sed: 16
file content (160 lines) | stat: -rw-r--r-- 5,456 bytes parent folder | download | duplicates (5)
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
#ifndef _AVLTREE_H
#define _AVLTREE_H

/*
 * AVLTree.c: Source code for the AVLTree library.
 * Copyright (C) 1998  Michael H. Buselli
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * The author of this library can be reached at the following address:
 * Michael H. Buselli
 * 4334 N. Hazel St. #515
 * Chicago, IL  60613-1456
 * Or you can send email to <cosine@cosine.org>.
 * The original web page for this product is:
 * http://www.cosine.org/project/AVLTree/
 *
 * Augmented AVL tree. Original by Michael H. Buselli <cosine@cosine.org>.
 * Modified 2000-11-28 by Wessel Dankers <wsl@nl.linux.org> to use counts 
 * instead of depths, to add the ->next and ->prev and to generally obfuscate   
 * the code. Mail me if you found a bug.
 */

/* We need either depths or counts (or both) */
#if !defined(AVL_DEPTH) && !defined(AVL_COUNT)
#define AVL_DEPTH
#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 (*AVLCompare)(const void *, const void *);

typedef struct AVLNode {
	struct AVLNode *next;
	struct AVLNode *prev;
	struct AVLNode *parent;
	struct AVLNode *left;
	struct AVLNode *right;
	void *item;
#ifdef AVL_COUNT
	unsigned int count;
#endif
#ifdef AVL_DEPTH
	unsigned char depth;
#endif
} AVLNode;

typedef struct AVLTree {
	AVLNode *head;
	AVLNode *tail;
	AVLNode *top;
	AVLCompare cmp;
} AVLTree;

/* 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 AVLTree *AVLInitTree(AVLTree *avltree, AVLCompare);

/* Allocates and initializes a new tree for elements that will be
 * ordered using the supplied strcmp()-like function.
 * Returns NULL if memory could not be allocated.
 * O(1) */
extern AVLTree *AVLAllocTree(AVLCompare);

/* Free()s all nodes in the tree but leaves the tree itself.
 * O(1) */
extern void AVLFreeNodes(AVLTree *);

/* Initializes memory for use as a node. Returns NULL if avlnode is NULL.
 * O(1) */
extern AVLNode *AVLInitNode(AVLNode *avlnode, void *item);

/* Insert an item into the tree and return the new node.
 * Returns NULL and sets errno if memory for the new node could not be
 * allocated or if the node is already in the tree (EEXIST).
 * O(lg n) */
extern AVLNode *AVLInsert(AVLTree *, 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 AVLNode *AVLInsertNode(AVLTree *, AVLNode *);

/* 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 AVLNode *AVLInsertTopNode(AVLTree *, AVLNode *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 AVLNode *AVLInsertNodeBefore(AVLTree *, AVLNode *old, AVLNode *new);

/* 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 AVLNode *AVLInsertNodeAfter(AVLTree *, AVLNode *old, AVLNode *new);

/* Deletes a node from the tree. Returns immediately if the node is NULL.
 * This function comes in handy if you need to update the search key.
 * O(lg n) */
extern void AVLUnlinkNode(AVLTree *, AVLNode *);

/* Deletes a node from the tree. Returns immediately if the node is NULL.
 * O(lg n) */
extern void AVLDeleteNode(AVLTree *, AVLNode *);

/* Searches for an item in the tree and deletes it if found.
 * O(lg n) */
extern void AVLDelete(AVLTree *, const void *item);

/* 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 AVLCloseSearch(const AVLTree *, const void *item, AVLNode **avlnode);

/* Searches for the item in the tree and returns a matching node if found
 * or NULL if not.
 * O(lg n) */
extern AVLNode *AVLSearch(const AVLTree *, const void *item);

#ifdef AVL_COUNT
/* Returns the number of nodes in the tree.
 * O(1) */
extern unsigned int AVLCount(const AVLTree *);

/* 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 AVLNode *AVLAtIndex(const AVLTree *, unsigned int);

/* Returns the rank of a node in the list. Counting starts at 0.
 * O(lg n) */
extern unsigned int AVLIndexOf(const AVLNode *);
#endif

#endif