GRASS Programmer's Manual
6.4.2(2012)
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Pages
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
*/
35
dglTreeNode_s
*
dglTreeNodeAlloc
()
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
65
dglTreeNode_s
*
dglTreeNodeAdd
(
void
*pavl,
dglInt32_t
nKey)
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
*/
89
dglTreeNode2_s
*
dglTreeNode2Alloc
()
90
{
91
dglTreeNode2_s
*pNode2 =
92
(
dglTreeNode2_s
*) malloc(
sizeof
(
dglTreeNode2_s
));
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
122
dglTreeNode2_s
*
dglTreeNode2Add
(
void
*pavl,
dglInt32_t
nKey)
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
*/
146
dglTreeEdge_s
*
dglTreeEdgeAlloc
()
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
174
dglTreeEdge_s
*
dglTreeEdgeAdd
(
void
*pavl,
dglInt32_t
nKey)
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
*/
199
dglTreeTouchI32_s
*
dglTreeTouchI32Alloc
()
200
{
201
dglTreeTouchI32_s
*pTouchI32 =
202
(
dglTreeTouchI32_s
*) malloc(
sizeof
(
dglTreeTouchI32_s
));
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
225
dglTreeTouchI32_s
*
dglTreeTouchI32Add
(
void
*pavl,
dglInt32_t
nKey)
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
*/
250
dglTreePredist_s
*
dglTreePredistAlloc
()
251
{
252
dglTreePredist_s
*pPredist =
253
(
dglTreePredist_s
*) malloc(
sizeof
(
dglTreePredist_s
));
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
277
dglTreePredist_s
*
dglTreePredistAdd
(
void
*pavl,
dglInt32_t
nKey)
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
*/
303
dglTreeNodePri32_s
*
dglTreeNodePri32Alloc
()
304
{
305
dglTreeNodePri32_s
*pNodePri32 =
306
(
dglTreeNodePri32_s
*) malloc(
sizeof
(
dglTreeNodePri32_s
));
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
330
dglTreeNodePri32_s
*
dglTreeNodePri32Add
(
void
*pavl,
dglInt32_t
nKey)
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
*/
355
dglTreeEdgePri32_s
*
dglTreeEdgePri32Alloc
()
356
{
357
dglTreeEdgePri32_s
*pEdgePri32 =
358
(
dglTreeEdgePri32_s
*) malloc(
sizeof
(
dglTreeEdgePri32_s
));
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
385
dglTreeEdgePri32_s
*
dglTreeEdgePri32Add
(
void
*pavl,
dglInt32_t
nKey)
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
422
void
*
dglTreeGetAllocator
()
423
{
424
return
&_tree_allocator;
425
}
lib
vector
dglib
tree.c
Generated on Sun Mar 16 2014 05:07:49 for GRASS Programmer's Manual by
1.8.1.2