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