← Back to branch summary

~ubuntu-branches/ubuntu/vivid/sflphone/vivid

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Mark Purcell
  • Date: 2013-06-30 11:40:56 UTC
  • mfrom: (4.1.18 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130630114056-0np50jkyqo6vnmii
Tags: 1.2.3-2
* changeset_r92d62cfc54732bbbcfff2b1d36c096b120b981a5.diff 
  - fixes automatic endian detection 
* Update Vcs: fixes vcs-field-not-canonical

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject/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