GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-87d2d42d3b
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 extern void *dglTreeGetAllocator(void);
56 
57 /*
58  * Define a node as it is hosted in pNodeTree
59  */
60 typedef struct _dglTreeNode {
61  long nKey;
62  void *pv;
63  void *pv2;
65 extern dglTreeNode_s *dglTreeNodeAlloc(void);
66 extern void dglTreeNodeCancel(void *pvNode, void *pvParam);
67 extern int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB,
68  void *pvParam);
69 extern dglTreeNode_s *dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey);
70 
71 /*
72  * Define a version-2 node as it is hosted in pNodeTree
73  */
74 typedef struct _dglTreeNode2 {
75  long nKey;
76  void *pv;
77  void *pv2;
78  void *pv3;
80 extern dglTreeNode2_s *dglTreeNode2Alloc(void);
81 extern void dglTreeNode2Cancel(void *pvNode, void *pvParam);
82 extern int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB,
83  void *pvParam);
84 extern dglTreeNode2_s *dglTreeNode2Add(void *pvAVL, dglInt32_t nKey);
85 
86 /*
87  * Define a edge as it is hosted in pEdgeTree
88  */
89 typedef struct _dglTreeEdge {
91  void *pv;
93 extern dglTreeEdge_s *dglTreeEdgeAlloc(void);
94 extern void dglTreeEdgeCancel(void *pvEdge, void *pvParam);
95 extern int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB,
96  void *pvParam);
97 extern dglTreeEdge_s *dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey);
98 
99 /*
100  * Define a dummy entry to 'touch' selected item with a dglInt32_t key
101  * i.e. used to mark visited nodes in a greedy or tree-growing algorithm
102  */
103 typedef struct _dglTreeTouchI32 {
107 extern void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam);
108 extern int dglTreeTouchI32Compare(const void *pvTouchI32A,
109  const void *pvTouchI32B, void *pvParam);
110 extern dglTreeTouchI32_s *dglTreeTouchI32Add(void *pvAVL, dglInt32_t nKey);
111 
112 /*
113  * Define a entry to maintain a predecessor/distance network in shortest-path
114  * computation
115  */
116 typedef struct _dglTreePredist {
125 extern void dglTreePredistCancel(void *pvPredist, void *pvParam);
126 extern int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB,
127  void *pvParam);
128 extern dglTreePredist_s *dglTreePredistAdd(void *pvAVL, dglInt32_t nKey);
129 
130 /*
131  * 32bit-key Node Prioritizer
132  */
133 typedef struct _dglTreeNodePri32 {
139 extern void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam);
140 extern int dglTreeNodePri32Compare(const void *pvNodePri32A,
141  const void *pvNodePri32B, void *pvParam);
142 extern dglTreeNodePri32_s *dglTreeNodePri32Add(void *pvAVL, dglInt32_t nKey);
143 
144 /*
145  * 32bit-key Edge Prioritizer
146  */
147 typedef struct _dglTreeEdgePri32 {
153 extern void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam);
154 extern int dglTreeEdgePri32Compare(const void *pvEdgePri32A,
155  const void *pvEdgePri32B, void *pvParam);
156 extern dglTreeEdgePri32_s *dglTreeEdgePri32Add(void *pvAVL, dglInt32_t nKey);
157 
158 #endif
dglInt32_t * pnData
Definition: tree.h:150
dglInt32_t nKey
Definition: tree.h:148
dglInt32_t cnData
Definition: tree.h:149
dglInt32_t nKey
Definition: tree.h:90
void * pv
Definition: tree.h:91
void * pv
Definition: tree.h:76
void * pv3
Definition: tree.h:78
void * pv2
Definition: tree.h:77
long nKey
Definition: tree.h:75
dglInt32_t cnVal
Definition: tree.h:135
dglInt32_t * pnVal
Definition: tree.h:136
dglInt32_t nKey
Definition: tree.h:134
void * pv2
Definition: tree.h:63
long nKey
Definition: tree.h:61
void * pv
Definition: tree.h:62
dglByte_t bFlags
Definition: tree.h:122
dglInt32_t nKey
Definition: tree.h:117
dglInt32_t nDistance
Definition: tree.h:119
dglInt32_t nCost
Definition: tree.h:120
dglInt32_t nFrom
Definition: tree.h:118
dglInt32_t * pnEdge
Definition: tree.h:121
dglInt32_t nKey
Definition: tree.h:104
int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB, void *pvParam)
dglTreeNode_s * dglTreeNodeAlloc(void)
Definition: tree.c:36
void dglTreePredistCancel(void *pvPredist, void *pvParam)
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam)
dglTreeEdgePri32_s * dglTreeEdgePri32Alloc(void)
Definition: tree.c:343
dglTreeNode_s * dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:66
void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam)
struct _dglTreeNode dglTreeNode_s
void dglTreeEdgeCancel(void *pvEdge, void *pvParam)
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam)
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam)
struct _dglTreeEdgePri32 dglTreeEdgePri32_s
dglTreeEdgePri32_s * dglTreeEdgePri32Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:373
struct _dglTreeNode2 dglTreeNode2_s
dglTreePredist_s * dglTreePredistAdd(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:270
dglTreePredist_s * dglTreePredistAlloc(void)
Definition: tree.c:243
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:220
void dglTreeNode2Cancel(void *pvNode, void *pvParam)
struct _dglTreeNodePri32 dglTreeNodePri32_s
dglTreeNodePri32_s * dglTreeNodePri32Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:320
dglTreeNodePri32_s * dglTreeNodePri32Alloc(void)
Definition: tree.c:293
void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam)
struct _dglTreeTouchI32 dglTreeTouchI32_s
void dglTreeNodeCancel(void *pvNode, void *pvParam)
void * dglTreeGetAllocator(void)
Definition: tree.c:406
dglTreeNode2_s * dglTreeNode2Add(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:120
int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, void *pvParam)
dglTreeTouchI32_s * dglTreeTouchI32Alloc(void)
Definition: tree.c:194
struct _dglTreePredist dglTreePredist_s
dglTreeEdge_s * dglTreeEdgeAlloc(void)
Definition: tree.c:143
int dglTreeEdgePri32Compare(const void *pvEdgePri32A, const void *pvEdgePri32B, void *pvParam)
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam)
struct _dglTreeEdge dglTreeEdge_s
dglTreeEdge_s * dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey)
Definition: tree.c:171
dglTreeNode2_s * dglTreeNode2Alloc(void)
Definition: tree.c:89
int dglTreeNodePri32Compare(const void *pvNodePri32A, const void *pvNodePri32B, void *pvParam)
unsigned char dglByte_t
Definition: type.h:35
long dglInt32_t
Definition: type.h:36