← Back to branch summary

~ubuntu-branches/ubuntu/wily/sflphone/wily

« back to all changes in this revision

Viewing changes to daemon/libs/pjproject-2.2.1/pjlib/include/pj/rbtree.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2015-01-07 14:51:16 UTC
  • mfrom: (4.3.5 sid)
  • Revision ID: package-import@ubuntu.com-20150107145116-yxnafinf4lrdvrmx
Tags: 1.4.1-0.1ubuntu1
* Merge with Debian, remaining changes:
 - Drop soprano, nepomuk build-dep
* Drop ubuntu patches, now upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject-2.2.1/pjlib/include/pj/rbtree.h
 
1
/* $Id: rbtree.h 3553 2011-05-05 06:14:19Z nanang $ */
 
2
/* 
 
3
 * Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com)
 
4
 * Copyright (C) 2003-2008 Benny Prijono <benny@prijono.org>
 
5
 *
 
6
 * This program is free software; you can redistribute it and/or modify
 
7
 * it under the terms of the GNU General Public License as published by
 
8
 * the Free Software Foundation; either version 2 of the License, or
 
9
 * (at your option) any later version.
 
10
 *
 
11
 * This program is distributed in the hope that it will be useful,
 
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 * GNU General Public License for more details.
 
15
 *
 
16
 * You should have received a copy of the GNU General Public License
 
17
 * along with this program; if not, write to the Free Software
 
18
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 
19
 */
 
20
#ifndef __PJ_RBTREE_H__
 
21
#define __PJ_RBTREE_H__
 
22
 
 
23
/**
 
24
 * @file rbtree.h
 
25
 * @brief Red/Black Tree
 
26
 */
 
27
 
 
28
#include <pj/types.h>
 
29
 
 
30
PJ_BEGIN_DECL
 
31
 
 
32
/**
 
33
 * @defgroup PJ_RBTREE Red/Black Balanced Tree
 
34
 * @ingroup PJ_DS
 
35
 * @brief
 
36
 * Red/Black tree is the variant of balanced tree, where the search, insert, 
 
37
 * and delete operation is \b guaranteed to take at most \a O( lg(n) ).
 
38
 * @{
 
39
 */
 
40
/**
 
41
 * Color type for Red-Black tree.
 
42
 */ 
 
43
typedef enum pj_rbcolor_t
 
44
{
 
45
    PJ_RBCOLOR_BLACK,
 
46
    PJ_RBCOLOR_RED
 
47
} pj_rbcolor_t;
 
48
 
 
49
/**
 
50
 * The type of the node of the R/B Tree.
 
51
 */
 
52
typedef struct pj_rbtree_node 
 
53
{
 
54
    /** Pointers to the node's parent, and left and right siblings. */
 
55
    struct pj_rbtree_node *parent, *left, *right;
 
56
 
 
57
    /** Key associated with the node. */
 
58
    const void *key;
 
59
 
 
60
    /** User data associated with the node. */
 
61
    void *user_data;
 
62
 
 
63
    /** The R/B Tree node color. */
 
64
    pj_rbcolor_t color;
 
65
 
 
66
} pj_rbtree_node;
 
67
 
 
68
 
 
69
/**
 
70
 * The type of function use to compare key value of tree node.
 
71
 * @return
 
72
 *  0 if the keys are equal
 
73
 * <0 if key1 is lower than key2
 
74
 * >0 if key1 is greater than key2.
 
75
 */
 
76
typedef int pj_rbtree_comp(const void *key1, const void *key2);
 
77
 
 
78
 
 
79
/**
 
80
 * Declaration of a red-black tree. All elements in the tree must have UNIQUE
 
81
 * key.
 
82
 * A red black tree always maintains the balance of the tree, so that the
 
83
 * tree height will not be greater than lg(N). Insert, search, and delete
 
84
 * operation will take lg(N) on the worst case. But for insert and delete,
 
85
 * there is additional time needed to maintain the balance of the tree.
 
86
 */
 
87
typedef struct pj_rbtree
 
88
{
 
89
    pj_rbtree_node null_node;   /**< Constant to indicate NULL node.    */
 
90
    pj_rbtree_node *null;       /**< Constant to indicate NULL node.    */
 
91
    pj_rbtree_node *root;       /**< Root tree node.                    */
 
92
    unsigned size;              /**< Number of elements in the tree.    */
 
93
    pj_rbtree_comp *comp;       /**< Key comparison function.           */
 
94
} pj_rbtree;
 
95
 
 
96
 
 
97
/**
 
98
 * Guidance on how much memory required for each of the node.
 
99
 */
 
100
#define PJ_RBTREE_NODE_SIZE         (sizeof(pj_rbtree_node))
 
101
 
 
102
 
 
103
/**
 
104
 * Guidance on memory required for the tree.
 
105
 */
 
106
#define PJ_RBTREE_SIZE              (sizeof(pj_rbtree))
 
107
 
 
108
 
 
109
/**
 
110
 * Initialize the tree.
 
111
 * @param tree the tree to be initialized.
 
112
 * @param comp key comparison function to be used for this tree.
 
113
 */
 
114
PJ_DECL(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp);
 
115
 
 
116
/**
 
117
 * Get the first element in the tree.
 
118
 * The first element always has the least value for the key, according to
 
119
 * the comparison function.
 
120
 * @param tree the tree.
 
121
 * @return the tree node, or NULL if the tree has no element.
 
122
 */
 
123
PJ_DECL(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree );
 
124
 
 
125
/**
 
126
 * Get the last element in the tree.
 
127
 * The last element always has the greatest key value, according to the
 
128
 * comparison function defined for the tree.
 
129
 * @param tree the tree.
 
130
 * @return the tree node, or NULL if the tree has no element.
 
131
 */
 
132
PJ_DECL(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree );
 
133
 
 
134
/**
 
135
 * Get the successive element for the specified node.
 
136
 * The successive element is an element with greater key value.
 
137
 * @param tree the tree.
 
138
 * @param node the node.
 
139
 * @return the successive node, or NULL if the node has no successor.
 
140
 */
 
141
PJ_DECL(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree, 
 
142
                                         pj_rbtree_node *node );
 
143
 
 
144
/**
 
145
 * The the previous node for the specified node.
 
146
 * The previous node is an element with less key value.
 
147
 * @param tree the tree.
 
148
 * @param node the node.
 
149
 * @return the previous node, or NULL if the node has no previous node.
 
150
 */
 
151
PJ_DECL(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree, 
 
152
                                         pj_rbtree_node *node );
 
153
 
 
154
/**
 
155
 * Insert a new node. 
 
156
 * The node will be inserted at sorted location. The key of the node must 
 
157
 * be UNIQUE, i.e. it hasn't existed in the tree.
 
158
 * @param tree the tree.
 
159
 * @param node the node to be inserted.
 
160
 * @return zero on success, or -1 if the key already exist.
 
161
 */
 
162
PJ_DECL(int) pj_rbtree_insert( pj_rbtree *tree, 
 
163
                               pj_rbtree_node *node );
 
164
 
 
165
/**
 
166
 * Find a node which has the specified key.
 
167
 * @param tree the tree.
 
168
 * @param key the key to search.
 
169
 * @return the tree node with the specified key, or NULL if the key can not
 
170
 *         be found.
 
171
 */
 
172
PJ_DECL(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree,
 
173
                                         const void *key );
 
174
 
 
175
/**
 
176
 * Erase a node from the tree.
 
177
 * @param tree the tree.
 
178
 * @param node the node to be erased.
 
179
 * @return the tree node itself.
 
180
 */
 
181
PJ_DECL(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree,
 
182
                                          pj_rbtree_node *node );
 
183
 
 
184
/**
 
185
 * Get the maximum tree height from the specified node.
 
186
 * @param tree the tree.
 
187
 * @param node the node, or NULL to get the root of the tree.
 
188
 * @return the maximum height, which should be at most lg(N)
 
189
 */
 
190
PJ_DECL(unsigned) pj_rbtree_max_height( pj_rbtree *tree,
 
191
                                        pj_rbtree_node *node );
 
192
 
 
193
/**
 
194
 * Get the minumum tree height from the specified node.
 
195
 * @param tree the tree.
 
196
 * @param node the node, or NULL to get the root of the tree.
 
197
 * @return the height
 
198
 */
 
199
PJ_DECL(unsigned) pj_rbtree_min_height( pj_rbtree *tree,
 
200
                                        pj_rbtree_node *node );
 
201
 
 
202
 
 
203
/**
 
204
 * @}
 
205
 */
 
206
 
 
207
PJ_END_DECL
 
208
 
 
209
#endif  /* __PJ_RBTREE_H__ */
 
210