BLOG | DOCUMENTATION | TRAC

Home --> Documentations --> PJLIB Reference

rbtree.h
Go to the documentation of this file.
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 
28 #include <pj/types.h>
29 
31 
43 typedef enum pj_rbcolor_t
44 {
45  PJ_RBCOLOR_BLACK,
46  PJ_RBCOLOR_RED
47 } pj_rbcolor_t;
48 
52 typedef struct pj_rbtree_node
53 {
55  struct pj_rbtree_node *parent, *left, *right;
56 
58  const void *key;
59 
61  void *user_data;
62 
65 
67 
68 
76 typedef int pj_rbtree_comp(const void *key1, const void *key2);
77 
78 
87 typedef struct pj_rbtree
88 {
92  unsigned size;
94 } pj_rbtree;
95 
96 
100 #define PJ_RBTREE_NODE_SIZE (sizeof(pj_rbtree_node))
101 
102 
106 #define PJ_RBTREE_SIZE (sizeof(pj_rbtree))
107 
108 
114 PJ_DECL(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp);
115 
123 PJ_DECL(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree );
124 
132 PJ_DECL(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree );
133 
141 PJ_DECL(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree,
142  pj_rbtree_node *node );
143 
151 PJ_DECL(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree,
152  pj_rbtree_node *node );
153 
162 PJ_DECL(int) pj_rbtree_insert( pj_rbtree *tree,
163  pj_rbtree_node *node );
164 
172 PJ_DECL(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree,
173  const void *key );
174 
181 PJ_DECL(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree,
182  pj_rbtree_node *node );
183 
190 PJ_DECL(unsigned) pj_rbtree_max_height( pj_rbtree *tree,
191  pj_rbtree_node *node );
192 
199 PJ_DECL(unsigned) pj_rbtree_min_height( pj_rbtree *tree,
200  pj_rbtree_node *node );
201 
202 
208 
209 #endif /* __PJ_RBTREE_H__ */
210 
pj_rbtree_comp * comp
Definition: rbtree.h:93
struct pj_rbtree_node * parent
Definition: rbtree.h:55
pj_rbtree_node * pj_rbtree_find(pj_rbtree *tree, const void *key)
int pj_rbtree_comp(const void *key1, const void *key2)
Definition: rbtree.h:76
pj_rbtree_node null_node
Definition: rbtree.h:89
pj_rbtree_node * pj_rbtree_first(pj_rbtree *tree)
unsigned pj_rbtree_max_height(pj_rbtree *tree, pj_rbtree_node *node)
const void * key
Definition: rbtree.h:58
Declaration of basic types and utility.
pj_rbtree_node * pj_rbtree_erase(pj_rbtree *tree, pj_rbtree_node *node)
void * user_data
Definition: rbtree.h:61
void pj_rbtree_init(pj_rbtree *tree, pj_rbtree_comp *comp)
unsigned size
Definition: rbtree.h:92
pj_rbtree_node * root
Definition: rbtree.h:91
#define PJ_END_DECL
Definition: config.h:1067
int pj_rbtree_insert(pj_rbtree *tree, pj_rbtree_node *node)
pj_rbcolor_t color
Definition: rbtree.h:64
Definition: rbtree.h:87
#define PJ_BEGIN_DECL
Definition: config.h:1066
pj_rbtree_node * pj_rbtree_next(pj_rbtree *tree, pj_rbtree_node *node)
unsigned pj_rbtree_min_height(pj_rbtree *tree, pj_rbtree_node *node)
pj_rbcolor_t
Definition: rbtree.h:43
pj_rbtree_node * null
Definition: rbtree.h:90
pj_rbtree_node * pj_rbtree_last(pj_rbtree *tree)
pj_rbtree_node * pj_rbtree_prev(pj_rbtree *tree, pj_rbtree_node *node)
Definition: rbtree.h:52

 


PJLIB Open Source, high performance, small footprint, and very very portable framework
Copyright (C) 2006-2009 Teluu Inc.