GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
tree.h
Go to the documentation of this file.
1 /* LIBDGL -- a Directed Graph Library implementation
2  * Copyright (C) 2002 Roberto Micarelli
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /* best view tabstop=4
20  */
21 
22 #ifndef _DGL_TREE_H_
23 #define _DGL_TREE_H_
24 
25 #include "avl.h"
26 #include "tavl.h"
27 
28 
29 #define USE_THREADED_AVL
30 
31 #if defined(USE_THREADED_AVL)
32 #define avl_table tavl_table
33 #define avl_traverser tavl_traverser
34 #define avl_create tavl_create
35 #define avl_copy tavl_copy
36 #define avl_destroy tavl_destroy
37 #define avl_probe tavl_probe
38 #define avl_insert tavl_insert
39 #define avl_replace tavl_replace
40 #define avl_delete tavl_delete
41 #define avl_find tavl_find
42 #define avl_assert_insert tavl_assert_insert
43 #define avl_assert_delete tavl_assert_delete
44 #define avl_t_init tavl_t_init
45 #define avl_t_first tavl_t_first
46 #define avl_t_last tavl_t_last
47 #define avl_t_find tavl_t_find
48 #define avl_t_insert tavl_t_insert
49 #define avl_t_copy tavl_t_copy
50 #define avl_t_next tavl_t_next
51 #define avl_t_prev tavl_t_prev
52 #define avl_t_cur tavl_t_cur
53 #define avl_t_replace tavl_t_replace
54 #endif
55 
56 
57 extern void *dglTreeGetAllocator();
58 
59 /*
60  * Define a node as it is hosted in pNodeTree
61  */
62 typedef struct _dglTreeNode
63 {
64  long nKey;
65  void *pv;
66  void *pv2;
69 extern void dglTreeNodeCancel(void *pvNode, void *pvParam);
70 extern int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB,
71  void *pvParam);
72 extern dglTreeNode_s *dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey);
73 
74 
75 /*
76  * Define a version-2 node as it is hosted in pNodeTree
77  */
78 typedef struct _dglTreeNode2
79 {
80  long nKey;
81  void *pv;
82  void *pv2;
83  void *pv3;
86 extern void dglTreeNode2Cancel(void *pvNode, void *pvParam);
87 extern int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB,
88  void *pvParam);
89 extern dglTreeNode2_s *dglTreeNode2Add(void *pvAVL, dglInt32_t nKey);
90 
91 
92 /*
93  * Define a edge as it is hosted in pEdgeTree
94  */
95 typedef struct _dglTreeEdge
96 {
98  void *pv;
101 extern void dglTreeEdgeCancel(void *pvEdge, void *pvParam);
102 extern int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB,
103  void *pvParam);
104 extern dglTreeEdge_s *dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey);
105 
106 
107 /*
108  * Define a dummy entry to 'touch' selected item with a dglInt32_t key
109  * i.e. used to mark visited nodes in a greedy or tree-growing algorithm
110  */
111 typedef struct _dglTreeTouchI32
112 {
116 extern void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam);
117 extern int dglTreeTouchI32Compare(const void *pvTouchI32A,
118  const void *pvTouchI32B, void *pvParam);
119 extern dglTreeTouchI32_s *dglTreeTouchI32Add(void *pvAVL, dglInt32_t nKey);
120 
121 
122 /*
123  * Define a entry to mantain a predecessor/distance network in shortest-path computation
124  */
125 typedef struct _dglTreePredist
126 {
135 extern void dglTreePredistCancel(void *pvPredist, void *pvParam);
136 extern int dglTreePredistCompare(const void *pvPredistA,
137  const void *pvPredistB, void *pvParam);
138 extern dglTreePredist_s *dglTreePredistAdd(void *pvAVL, dglInt32_t nKey);
139 
140 
141 /*
142  * 32bit-key Node Prioritizer
143  */
144 typedef struct _dglTreeNodePri32
145 {
151 extern void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam);
152 extern int dglTreeNodePri32Compare(const void *pvNodePri32A,
153  const void *pvNodePri32B, void *pvParam);
154 extern dglTreeNodePri32_s *dglTreeNodePri32Add(void *pvAVL, dglInt32_t nKey);
155 
156 
157 /*
158  * 32bit-key Edge Prioritizer
159  */
160 typedef struct _dglTreeEdgePri32
161 {
167 extern void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam);
168 extern int dglTreeEdgePri32Compare(const void *pvEdgePri32A,
169  const void *pvEdgePri32B, void *pvParam);
170 extern dglTreeEdgePri32_s *dglTreeEdgePri32Add(void *pvAVL, dglInt32_t nKey);
171 
172 
173 #endif
int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, void *pvParam)
Definition: tree.c:162
struct _dglTreePredist dglTreePredist_s
dglByte_t bFlags
Definition: tree.h:132
void dglTreeNode2Cancel(void *pvNode2, void *pvParam)
Definition: tree.c:98
struct _dglTreeNodePri32 dglTreeNodePri32_s
dglInt32_t * pnData
Definition: tree.h:164
void dglTreeNodeCancel(void *pvNode, void *pvParam)
Definition: tree.c:44
unsigned char dglByte_t
Definition: type.h:36
void dglTreeEdgeCancel(void *pvEdge, void *pvParam)
Definition: tree.c:155
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:225
dglInt32_t * pnVal
Definition: tree.h:148
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam)
Definition: tree.c:264
dglTreePredist_s * dglTreePredistAlloc()
Definition: tree.c:250
dglTreeEdge_s * dglTreeEdgeAlloc()
Definition: tree.c:146
void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam)
Definition: tree.c:364
long nKey
Definition: tree.h:64
void * pv3
Definition: tree.h:83
void * pv
Definition: tree.h:81
struct _dglTreeEdgePri32 dglTreeEdgePri32_s
dglInt32_t * pnEdge
Definition: tree.h:131
void * pv2
Definition: tree.h:66
dglTreeNode_s * dglTreeNodeAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:65
dglInt32_t nKey
Definition: tree.h:127
dglInt32_t cnVal
Definition: tree.h:147
void * pv2
Definition: tree.h:82
dglTreeNode_s * dglTreeNodeAlloc()
Definition: tree.c:35
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam)
Definition: tree.c:53
long nKey
Definition: tree.h:80
dglInt32_t nKey
Definition: tree.h:146
int dglTreeNode2Compare(const void *pvNode2A, const void *pvNode2B, void *pvParam)
Definition: tree.c:109
dglInt32_t nDistance
Definition: tree.h:129
struct _dglTreeEdge dglTreeEdge_s
dglTreeEdgePri32_s * dglTreeEdgePri32Alloc()
Definition: tree.c:355
dglInt32_t nFrom
Definition: tree.h:128
long dglInt32_t
Definition: type.h:37
void * dglTreeGetAllocator()
Definition: tree.c:422
struct _dglTreeNode2 dglTreeNode2_s
dglTreeEdge_s * dglTreeEdgeAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:174
void * pv
Definition: tree.h:98
dglInt32_t cnData
Definition: tree.h:163
struct _dglTreeTouchI32 dglTreeTouchI32_s
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam)
Definition: tree.c:207
dglTreeEdgePri32_s * dglTreeEdgePri32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:385
void dglTreePredistCancel(void *pvPredist, void *pvParam)
Definition: tree.c:259
dglTreeNode2_s * dglTreeNode2Alloc()
Definition: tree.c:89
dglInt32_t nKey
Definition: tree.h:97
int dglTreeEdgePri32Compare(const void *pvEdgePri32A, const void *pvEdgePri32B, void *pvParam)
Definition: tree.c:372
void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam)
Definition: tree.c:312
dglTreeNode2_s * dglTreeNode2Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:122
dglTreeNodePri32_s * dglTreeNodePri32Alloc()
Definition: tree.c:303
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam)
Definition: tree.c:212
int dglTreeNodePri32Compare(const void *pvNodePri32A, const void *pvNodePri32B, void *pvParam)
Definition: tree.c:317
dglInt32_t nKey
Definition: tree.h:162
dglTreePredist_s * dglTreePredistAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:277
dglInt32_t nKey
Definition: tree.h:113
dglTreeNodePri32_s * dglTreeNodePri32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:330
void * pv
Definition: tree.h:65
struct _dglTreeNode dglTreeNode_s
dglInt32_t nCost
Definition: tree.h:130
dglTreeTouchI32_s * dglTreeTouchI32Alloc()
Definition: tree.c:199