GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
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 #define USE_THREADED_AVL
26 
27 #if defined(USE_THREADED_AVL)
28 #include "tavl.h"
29 #define avl_table tavl_table
30 #define avl_traverser tavl_traverser
31 #define avl_create tavl_create
32 #define avl_copy tavl_copy
33 #define avl_destroy tavl_destroy
34 #define avl_probe tavl_probe
35 #define avl_insert tavl_insert
36 #define avl_replace tavl_replace
37 #define avl_delete tavl_delete
38 #define avl_find tavl_find
39 #define avl_assert_insert tavl_assert_insert
40 #define avl_assert_delete tavl_assert_delete
41 #define avl_t_init tavl_t_init
42 #define avl_t_first tavl_t_first
43 #define avl_t_last tavl_t_last
44 #define avl_t_find tavl_t_find
45 #define avl_t_insert tavl_t_insert
46 #define avl_t_copy tavl_t_copy
47 #define avl_t_next tavl_t_next
48 #define avl_t_prev tavl_t_prev
49 #define avl_t_cur tavl_t_cur
50 #define avl_t_replace tavl_t_replace
51 #else
52 #include "avl.h"
53 #endif
54 
55 
56 extern void *dglTreeGetAllocator();
57 
58 /*
59  * Define a node as it is hosted in pNodeTree
60  */
61 typedef struct _dglTreeNode
62 {
63  long nKey;
64  void *pv;
65  void *pv2;
68 extern void dglTreeNodeCancel(void *pvNode, void *pvParam);
69 extern int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB,
70  void *pvParam);
71 extern dglTreeNode_s *dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey);
72 
73 
74 /*
75  * Define a version-2 node as it is hosted in pNodeTree
76  */
77 typedef struct _dglTreeNode2
78 {
79  long nKey;
80  void *pv;
81  void *pv2;
82  void *pv3;
85 extern void dglTreeNode2Cancel(void *pvNode, void *pvParam);
86 extern int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB,
87  void *pvParam);
88 extern dglTreeNode2_s *dglTreeNode2Add(void *pvAVL, dglInt32_t nKey);
89 
90 
91 /*
92  * Define a edge as it is hosted in pEdgeTree
93  */
94 typedef struct _dglTreeEdge
95 {
97  void *pv;
100 extern void dglTreeEdgeCancel(void *pvEdge, void *pvParam);
101 extern int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB,
102  void *pvParam);
103 extern dglTreeEdge_s *dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey);
104 
105 
106 /*
107  * Define a dummy entry to 'touch' selected item with a dglInt32_t key
108  * i.e. used to mark visited nodes in a greedy or tree-growing algorithm
109  */
110 typedef struct _dglTreeTouchI32
111 {
115 extern void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam);
116 extern int dglTreeTouchI32Compare(const void *pvTouchI32A,
117  const void *pvTouchI32B, void *pvParam);
119 
120 
121 /*
122  * Define a entry to maintain a predecessor/distance network in shortest-path computation
123  */
124 typedef struct _dglTreePredist
125 {
134 extern void dglTreePredistCancel(void *pvPredist, void *pvParam);
135 extern int dglTreePredistCompare(const void *pvPredistA,
136  const void *pvPredistB, void *pvParam);
137 extern dglTreePredist_s *dglTreePredistAdd(void *pvAVL, dglInt32_t nKey);
138 
139 
140 /*
141  * 32bit-key Node Prioritizer
142  */
143 typedef struct _dglTreeNodePri32
144 {
150 extern void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam);
151 extern int dglTreeNodePri32Compare(const void *pvNodePri32A,
152  const void *pvNodePri32B, void *pvParam);
154 
155 
156 /*
157  * 32bit-key Edge Prioritizer
158  */
159 typedef struct _dglTreeEdgePri32
160 {
166 extern void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam);
167 extern int dglTreeEdgePri32Compare(const void *pvEdgePri32A,
168  const void *pvEdgePri32B, void *pvParam);
170 
171 
172 #endif
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:225
struct _dglTreePredist dglTreePredist_s
dglByte_t bFlags
Definition: tree.h:131
int dglTreeNodePri32Compare(const void *pvNodePri32A, const void *pvNodePri32B, void *pvParam)
Definition: tree.c:317
struct _dglTreeNodePri32 dglTreeNodePri32_s
dglInt32_t * pnData
Definition: tree.h:163
unsigned char dglByte_t
Definition: type.h:36
void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam)
Definition: tree.c:312
dglTreeNodePri32_s * dglTreeNodePri32Alloc()
Definition: tree.c:303
dglInt32_t * pnVal
Definition: tree.h:147
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam)
Definition: tree.c:212
dglTreeTouchI32_s * dglTreeTouchI32Alloc()
Definition: tree.c:199
void dglTreePredistCancel(void *pvPredist, void *pvParam)
Definition: tree.c:259
long nKey
Definition: tree.h:63
void * pv3
Definition: tree.h:82
dglTreeEdgePri32_s * dglTreeEdgePri32Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:385
void * pv
Definition: tree.h:80
struct _dglTreeEdgePri32 dglTreeEdgePri32_s
int dglTreeEdgePri32Compare(const void *pvEdgePri32A, const void *pvEdgePri32B, void *pvParam)
Definition: tree.c:372
dglInt32_t * pnEdge
Definition: tree.h:130
void * pv2
Definition: tree.h:65
dglTreeNode2_s * dglTreeNode2Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:122
void dglTreeNodeCancel(void *pvNode, void *pvParam)
Definition: tree.c:44
dglInt32_t nKey
Definition: tree.h:126
dglInt32_t cnVal
Definition: tree.h:146
void * pv2
Definition: tree.h:81
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam)
Definition: tree.c:264
long nKey
Definition: tree.h:79
dglInt32_t nKey
Definition: tree.h:145
int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB, void *pvParam)
Definition: tree.c:109
dglTreeEdge_s * dglTreeEdgeAlloc()
Definition: tree.c:146
dglInt32_t nDistance
Definition: tree.h:128
void dglTreeEdgeCancel(void *pvEdge, void *pvParam)
Definition: tree.c:155
struct _dglTreeEdge dglTreeEdge_s
dglInt32_t nFrom
Definition: tree.h:127
long dglInt32_t
Definition: type.h:37
struct _dglTreeNode2 dglTreeNode2_s
void * pv
Definition: tree.h:97
dglInt32_t cnData
Definition: tree.h:162
struct _dglTreeTouchI32 dglTreeTouchI32_s
dglTreePredist_s * dglTreePredistAdd(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:277
void dglTreeNode2Cancel(void *pvNode, void *pvParam)
Definition: tree.c:98
dglInt32_t nKey
Definition: tree.h:96
dglTreeNode_s * dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:65
int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, void *pvParam)
Definition: tree.c:162
dglTreeEdgePri32_s * dglTreeEdgePri32Alloc()
Definition: tree.c:355
dglTreeNodePri32_s * dglTreeNodePri32Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:330
void * dglTreeGetAllocator()
Definition: tree.c:422
dglInt32_t nKey
Definition: tree.h:161
void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam)
Definition: tree.c:364
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam)
Definition: tree.c:207
dglTreeEdge_s * dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:174
dglInt32_t nKey
Definition: tree.h:112
dglTreeNode2_s * dglTreeNode2Alloc()
Definition: tree.c:89
void * pv
Definition: tree.h:64
struct _dglTreeNode dglTreeNode_s
dglTreePredist_s * dglTreePredistAlloc()
Definition: tree.c:250
dglInt32_t nCost
Definition: tree.h:129
dglTreeNode_s * dglTreeNodeAlloc()
Definition: tree.c:35
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam)
Definition: tree.c:53