GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-9aacb948ba
tree.c
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 #include <stdio.h>
22 #include <string.h>
23 #include <stdlib.h>
24 
25 #include <grass/gis.h>
26 #include "type.h"
27 #include "tree.h"
28 
29 /*
30  * AVL Support for data type dglTreeNode_s
31  * alloc
32  * cancel
33  * compare
34  * add
35  */
37 {
38  dglTreeNode_s *pNode = (dglTreeNode_s *)malloc(sizeof(dglTreeNode_s));
39 
40  if (pNode)
41  memset(pNode, 0, sizeof(dglTreeNode_s));
42  return pNode;
43 }
44 
45 void dglTreeNodeCancel(void *pvNode, void *pvParam UNUSED)
46 {
47  if (((dglTreeNode_s *)pvNode)->pv)
48  free(((dglTreeNode_s *)pvNode)->pv);
49  if (((dglTreeNode_s *)pvNode)->pv2)
50  free(((dglTreeNode_s *)pvNode)->pv2);
51  free(pvNode);
52 }
53 
54 int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB,
55  void *pvParam UNUSED)
56 {
57  if (((dglTreeNode_s *)pvNodeA)->nKey < ((dglTreeNode_s *)pvNodeB)->nKey)
58  return -1;
59  else if (((dglTreeNode_s *)pvNodeA)->nKey >
60  ((dglTreeNode_s *)pvNodeB)->nKey)
61  return 1;
62  else
63  return 0;
64 }
65 
67 {
68  dglTreeNode_s *pnode;
69  void **ppvret;
70 
71  if ((pnode = dglTreeNodeAlloc()) == NULL)
72  return NULL;
73  pnode->nKey = nKey;
74  ppvret = avl_probe(pavl, pnode);
75  if (*ppvret != pnode) {
76  free(pnode);
77  pnode = *ppvret;
78  }
79  return pnode;
80 }
81 
82 /*
83  * AVL Support for data type dglTreeNode2_s
84  * alloc
85  * cancel
86  * compare
87  * add
88  */
90 {
91  dglTreeNode2_s *pNode2 = (dglTreeNode2_s *)malloc(sizeof(dglTreeNode2_s));
92  if (pNode2)
93  memset(pNode2, 0, sizeof(dglTreeNode2_s));
94  return pNode2;
95 }
96 
97 void dglTreeNode2Cancel(void *pvNode2, void *pvParam UNUSED)
98 {
99  if (((dglTreeNode2_s *)pvNode2)->pv)
100  free(((dglTreeNode2_s *)pvNode2)->pv);
101  if (((dglTreeNode2_s *)pvNode2)->pv2)
102  free(((dglTreeNode2_s *)pvNode2)->pv2);
103  if (((dglTreeNode2_s *)pvNode2)->pv3)
104  free(((dglTreeNode2_s *)pvNode2)->pv3);
105  free(pvNode2);
106 }
107 
108 int dglTreeNode2Compare(const void *pvNode2A, const void *pvNode2B,
109  void *pvParam UNUSED)
110 {
111  if (((dglTreeNode2_s *)pvNode2A)->nKey < ((dglTreeNode2_s *)pvNode2B)->nKey)
112  return -1;
113  else if (((dglTreeNode2_s *)pvNode2A)->nKey >
114  ((dglTreeNode2_s *)pvNode2B)->nKey)
115  return 1;
116  else
117  return 0;
118 }
119 
121 {
122  dglTreeNode2_s *pnode;
123  void **ppvret;
124 
125  if ((pnode = dglTreeNode2Alloc()) == NULL)
126  return NULL;
127  pnode->nKey = nKey;
128  ppvret = avl_probe(pavl, pnode);
129  if (*ppvret != pnode) {
130  free(pnode);
131  pnode = *ppvret;
132  }
133  return pnode;
134 }
135 
136 /*
137  * AVL Support for data type dglTreeEdge_s
138  * alloc
139  * cancel
140  * compare
141  * add
142  */
144 {
145  dglTreeEdge_s *pEdge = (dglTreeEdge_s *)malloc(sizeof(dglTreeEdge_s));
146 
147  if (pEdge)
148  memset(pEdge, 0, sizeof(dglTreeEdge_s));
149  return pEdge;
150 }
151 
152 void dglTreeEdgeCancel(void *pvEdge, void *pvParam UNUSED)
153 {
154  if (((dglTreeEdge_s *)pvEdge)->pv)
155  free(((dglTreeEdge_s *)pvEdge)->pv);
156  free(pvEdge);
157 }
158 
159 int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB,
160  void *pvParam UNUSED)
161 {
162  if (((dglTreeEdge_s *)pvEdgeA)->nKey < ((dglTreeEdge_s *)pvEdgeB)->nKey)
163  return -1;
164  else if (((dglTreeEdge_s *)pvEdgeA)->nKey >
165  ((dglTreeEdge_s *)pvEdgeB)->nKey)
166  return 1;
167  else
168  return 0;
169 }
170 
172 {
173  dglTreeEdge_s *pedge;
174  void **ppvret;
175 
176  if ((pedge = dglTreeEdgeAlloc()) == NULL)
177  return NULL;
178  pedge->nKey = nKey;
179  ppvret = avl_probe(pavl, pedge);
180  if (*ppvret != pedge) {
181  free(pedge);
182  pedge = *ppvret;
183  }
184  return pedge;
185 }
186 
187 /*
188  * AVL Support for data type dglTreeTouchI32_s
189  * alloc
190  * cancel
191  * compare
192  * add
193  */
195 {
196  dglTreeTouchI32_s *pTouchI32 =
198  pTouchI32->nKey = 0;
199  return pTouchI32;
200 }
201 
202 void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam UNUSED)
203 {
204  free(pvTouchI32);
205 }
206 
207 int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B,
208  void *pvParam UNUSED)
209 {
210  if (((dglTreeTouchI32_s *)pvTouchI32A)->nKey <
211  ((dglTreeTouchI32_s *)pvTouchI32B)->nKey)
212  return -1;
213  else if (((dglTreeTouchI32_s *)pvTouchI32A)->nKey >
214  ((dglTreeTouchI32_s *)pvTouchI32B)->nKey)
215  return 1;
216  else
217  return 0;
218 }
219 
221 {
222  dglTreeTouchI32_s *pnode;
223  void **ppvret;
224 
225  if ((pnode = dglTreeTouchI32Alloc()) == NULL)
226  return NULL;
227  pnode->nKey = nKey;
228  ppvret = avl_probe(pavl, pnode);
229  if (*ppvret != pnode) {
230  free(pnode);
231  pnode = *ppvret;
232  }
233  return pnode;
234 }
235 
236 /*
237  * AVL Support for data type dglTreePredist_s
238  * alloc
239  * cancel
240  * compare
241  * add
242  */
244 {
245  dglTreePredist_s *pPredist =
247  if (pPredist)
248  memset(pPredist, 0, sizeof(dglTreePredist_s));
249  return pPredist;
250 }
251 
252 void dglTreePredistCancel(void *pvPredist, void *pvParam UNUSED)
253 {
254  free(pvPredist);
255 }
256 
257 int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB,
258  void *pvParam UNUSED)
259 {
260  if (((dglTreePredist_s *)pvPredistA)->nKey <
261  ((dglTreePredist_s *)pvPredistB)->nKey)
262  return -1;
263  else if (((dglTreePredist_s *)pvPredistA)->nKey >
264  ((dglTreePredist_s *)pvPredistB)->nKey)
265  return 1;
266  else
267  return 0;
268 }
269 
271 {
272  dglTreePredist_s *pnode;
273  void **ppvret;
274 
275  if ((pnode = dglTreePredistAlloc()) == NULL)
276  return NULL;
277  pnode->nKey = nKey;
278  ppvret = avl_probe(pavl, pnode);
279  if (*ppvret != pnode) {
280  free(pnode);
281  pnode = *ppvret;
282  }
283  return pnode;
284 }
285 
286 /*
287  * AVL Support for data type dglTreeNodePri32_s
288  * alloc
289  * cancel
290  * compare
291  * add
292  */
294 {
295  dglTreeNodePri32_s *pNodePri32 =
297  if (pNodePri32)
298  memset(pNodePri32, 0, sizeof(dglTreeNodePri32_s));
299  return pNodePri32;
300 }
301 
302 void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam UNUSED)
303 {
304  free(pvNodePri32);
305 }
306 
307 int dglTreeNodePri32Compare(const void *pvNodePri32A, const void *pvNodePri32B,
308  void *pvParam UNUSED)
309 {
310  if (((dglTreeNodePri32_s *)pvNodePri32A)->nKey <
311  ((dglTreeNodePri32_s *)pvNodePri32B)->nKey)
312  return -1;
313  else if (((dglTreeNodePri32_s *)pvNodePri32A)->nKey >
314  ((dglTreeNodePri32_s *)pvNodePri32B)->nKey)
315  return 1;
316  else
317  return 0;
318 }
319 
321 {
322  dglTreeNodePri32_s *pnode;
323  void **ppvret;
324 
325  if ((pnode = dglTreeNodePri32Alloc()) == NULL)
326  return NULL;
327  pnode->nKey = nKey;
328  ppvret = avl_probe(pavl, pnode);
329  if (*ppvret != pnode) {
330  free(pnode);
331  pnode = *ppvret;
332  }
333  return pnode;
334 }
335 
336 /*
337  * AVL Support for data type dglTreeEdgePri32_s
338  * alloc
339  * cancel
340  * compare
341  * add
342  */
344 {
345  dglTreeEdgePri32_s *pEdgePri32 =
347  if (pEdgePri32)
348  memset(pEdgePri32, 0, sizeof(dglTreeEdgePri32_s));
349  return pEdgePri32;
350 }
351 
352 void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam UNUSED)
353 {
354  if (((dglTreeEdgePri32_s *)pvEdgePri32)->pnData) {
355  free(((dglTreeEdgePri32_s *)pvEdgePri32)->pnData);
356  }
357  free(pvEdgePri32);
358 }
359 
360 int dglTreeEdgePri32Compare(const void *pvEdgePri32A, const void *pvEdgePri32B,
361  void *pvParam UNUSED)
362 {
363  if (((dglTreeEdgePri32_s *)pvEdgePri32A)->nKey <
364  ((dglTreeEdgePri32_s *)pvEdgePri32B)->nKey)
365  return -1;
366  else if (((dglTreeEdgePri32_s *)pvEdgePri32A)->nKey >
367  ((dglTreeEdgePri32_s *)pvEdgePri32B)->nKey)
368  return 1;
369  else
370  return 0;
371 }
372 
374 {
375  dglTreeEdgePri32_s *pnode;
376  void **ppvret;
377 
378  if ((pnode = dglTreeEdgePri32Alloc()) == NULL)
379  return NULL;
380  pnode->nKey = nKey;
381  ppvret = avl_probe(pavl, pnode);
382  if (*ppvret != pnode) {
383  free(pnode);
384  pnode = *ppvret;
385  }
386  return pnode;
387 }
388 
389 /*
390  * Our AVL allocator
391  */
392 static void *_tree_malloc(struct libavl_allocator *allocator UNUSED,
393  size_t libavl_size)
394 {
395  return malloc(libavl_size);
396 }
397 
398 static void _tree_free(struct libavl_allocator *allocator UNUSED,
399  void *libavl_block)
400 {
401  free(libavl_block);
402 }
403 
404 static struct libavl_allocator _tree_allocator = {_tree_malloc, _tree_free};
405 
407 {
408  return &_tree_allocator;
409 }
#define NULL
Definition: ccmath.h:32
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
void * malloc(YYSIZE_T)
void free(void *)
dglInt32_t nKey
Definition: tree.h:148
dglInt32_t nKey
Definition: tree.h:90
long nKey
Definition: tree.h:75
dglInt32_t nKey
Definition: tree.h:134
long nKey
Definition: tree.h:61
dglInt32_t nKey
Definition: tree.h:117
dglInt32_t nKey
Definition: tree.h:104
void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam UNUSED)
Definition: tree.c:352
dglTreeNode_s * dglTreeNodeAlloc(void)
Definition: tree.c:36
dglTreeEdgePri32_s * dglTreeEdgePri32Alloc(void)
Definition: tree.c:343
dglTreeNodePri32_s * dglTreeNodePri32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:320
dglTreeEdgePri32_s * dglTreeEdgePri32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:373
dglTreeEdge_s * dglTreeEdgeAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:171
int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, void *pvParam UNUSED)
Definition: tree.c:159
void dglTreeNode2Cancel(void *pvNode2, void *pvParam UNUSED)
Definition: tree.c:97
int dglTreeNodePri32Compare(const void *pvNodePri32A, const void *pvNodePri32B, void *pvParam UNUSED)
Definition: tree.c:307
dglTreePredist_s * dglTreePredistAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:270
dglTreePredist_s * dglTreePredistAlloc(void)
Definition: tree.c:243
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam UNUSED)
Definition: tree.c:257
void dglTreeNodeCancel(void *pvNode, void *pvParam UNUSED)
Definition: tree.c:45
int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, void *pvParam UNUSED)
Definition: tree.c:54
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam UNUSED)
Definition: tree.c:202
dglTreeNodePri32_s * dglTreeNodePri32Alloc(void)
Definition: tree.c:293
int dglTreeNode2Compare(const void *pvNode2A, const void *pvNode2B, void *pvParam UNUSED)
Definition: tree.c:108
void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam UNUSED)
Definition: tree.c:302
void * dglTreeGetAllocator(void)
Definition: tree.c:406
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:220
void dglTreeEdgeCancel(void *pvEdge, void *pvParam UNUSED)
Definition: tree.c:152
int dglTreeEdgePri32Compare(const void *pvEdgePri32A, const void *pvEdgePri32B, void *pvParam UNUSED)
Definition: tree.c:360
dglTreeTouchI32_s * dglTreeTouchI32Alloc(void)
Definition: tree.c:194
dglTreeNode2_s * dglTreeNode2Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:120
dglTreeEdge_s * dglTreeEdgeAlloc(void)
Definition: tree.c:143
void dglTreePredistCancel(void *pvPredist, void *pvParam UNUSED)
Definition: tree.c:252
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam UNUSED)
Definition: tree.c:207
dglTreeNode_s * dglTreeNodeAdd(void *pavl, dglInt32_t nKey)
Definition: tree.c:66
dglTreeNode2_s * dglTreeNode2Alloc(void)
Definition: tree.c:89
#define avl_probe
Definition: tree.h:34
long dglInt32_t
Definition: type.h:36