1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>Open SCAP Library: /home/pvrabec/project/openscap/openscap-0.5.12/src/OVAL/probes/SEAP/generic/redblack.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.1 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul>
</div>
<h1>/home/pvrabec/project/openscap/openscap-0.5.12/src/OVAL/probes/SEAP/generic/redblack.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> * Copyright 2009 Red Hat Inc., Durham, North Carolina.</span>
<a name="l00003"></a>00003 <span class="comment"> * All Rights Reserved.</span>
<a name="l00004"></a>00004 <span class="comment"> *</span>
<a name="l00005"></a>00005 <span class="comment"> * This library is free software; you can redistribute it and/or</span>
<a name="l00006"></a>00006 <span class="comment"> * modify it under the terms of the GNU Lesser General Public</span>
<a name="l00007"></a>00007 <span class="comment"> * License as published by the Free Software Foundation; either</span>
<a name="l00008"></a>00008 <span class="comment"> * version 2.1 of the License, or (at your option) any later version.</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * This library is distributed in the hope that it will be useful,</span>
<a name="l00011"></a>00011 <span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00012"></a>00012 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</span>
<a name="l00013"></a>00013 <span class="comment"> * Lesser General Public License for more details.</span>
<a name="l00014"></a>00014 <span class="comment"> *</span>
<a name="l00015"></a>00015 <span class="comment"> * You should have received a copy of the GNU Lesser General Public</span>
<a name="l00016"></a>00016 <span class="comment"> * License along with this library; if not, write to the Free Software</span>
<a name="l00017"></a>00017 <span class="comment"> * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA</span>
<a name="l00018"></a>00018 <span class="comment"> *</span>
<a name="l00019"></a>00019 <span class="comment"> * Authors:</span>
<a name="l00020"></a>00020 <span class="comment"> * "Daniel Kopecek" <dkopecek@redhat.com></span>
<a name="l00021"></a>00021 <span class="comment"> */</span>
<a name="l00022"></a>00022
<a name="l00023"></a>00023 <span class="preprocessor">#pragma once</span>
<a name="l00024"></a>00024 <span class="preprocessor"></span><span class="preprocessor">#ifndef REDBLACK_H</span>
<a name="l00025"></a>00025 <span class="preprocessor"></span><span class="preprocessor">#define REDBLACK_H</span>
<a name="l00026"></a>00026 <span class="preprocessor"></span>
<a name="l00027"></a>00027 <span class="preprocessor">#include <stdint.h></span>
<a name="l00028"></a>00028 <span class="preprocessor">#include <stdlib.h></span>
<a name="l00029"></a>00029 <span class="preprocessor">#include <assert.h></span>
<a name="l00030"></a>00030 <span class="preprocessor">#include "../../../../common/util.h"</span>
<a name="l00031"></a>00031
<a name="l00032"></a>00032 OSCAP_HIDDEN_START;
<a name="l00033"></a>00033
<a name="l00034"></a>00034 <span class="preprocessor">#ifndef NDEBUG</span>
<a name="l00035"></a>00035 <span class="preprocessor"></span><span class="preprocessor"># define _E(exp) exp</span>
<a name="l00036"></a>00036 <span class="preprocessor"></span><span class="preprocessor">#else</span>
<a name="l00037"></a>00037 <span class="preprocessor"></span><span class="preprocessor"># define _E(exp) while(0)</span>
<a name="l00038"></a>00038 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00039"></a>00039 <span class="preprocessor"></span>
<a name="l00040"></a>00040 <span class="preprocessor">#define XMALLOC malloc</span>
<a name="l00041"></a>00041 <span class="preprocessor"></span><span class="preprocessor">#define XREALLOC realloc</span>
<a name="l00042"></a>00042 <span class="preprocessor"></span><span class="preprocessor">#define XCALLOC calloc</span>
<a name="l00043"></a>00043 <span class="preprocessor"></span><span class="preprocessor">#define XFREE free</span>
<a name="l00044"></a>00044 <span class="preprocessor"></span>
<a name="l00045"></a>00045 <span class="preprocessor">#define SIDE_LEFT ((side_t)0)</span>
<a name="l00046"></a>00046 <span class="preprocessor"></span><span class="preprocessor">#define SIDE_RGHT ((side_t)1)</span>
<a name="l00047"></a>00047 <span class="preprocessor"></span>
<a name="l00048"></a>00048 <span class="preprocessor">#define COLOR_BLK 0</span>
<a name="l00049"></a>00049 <span class="preprocessor"></span><span class="preprocessor">#define COLOR_RED 1</span>
<a name="l00050"></a>00050 <span class="preprocessor"></span>
<a name="l00051"></a>00051 <span class="preprocessor">#define PREORDER 0</span>
<a name="l00052"></a>00052 <span class="preprocessor"></span><span class="preprocessor">#define INORDER 1</span>
<a name="l00053"></a>00053 <span class="preprocessor"></span><span class="preprocessor">#define POSTORDER 2</span>
<a name="l00054"></a>00054 <span class="preprocessor"></span><span class="preprocessor">#define LRTDLAYER 3</span>
<a name="l00055"></a>00055 <span class="preprocessor"></span><span class="preprocessor">#define RLTDLAYER 4</span>
<a name="l00056"></a>00056 <span class="preprocessor"></span>
<a name="l00057"></a>00057 <span class="preprocessor">#if !defined (E_OK)</span>
<a name="l00058"></a>00058 <span class="preprocessor"></span><span class="preprocessor"># define E_OK 0</span>
<a name="l00059"></a>00059 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00060"></a>00060 <span class="preprocessor"></span><span class="preprocessor">#if !defined (E_FAIL)</span>
<a name="l00061"></a>00061 <span class="preprocessor"></span><span class="preprocessor"># define E_FAIL 1</span>
<a name="l00062"></a>00062 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00063"></a>00063 <span class="preprocessor"></span><span class="preprocessor">#if !defined (E_COLL)</span>
<a name="l00064"></a>00064 <span class="preprocessor"></span><span class="preprocessor"># define E_COLL 2</span>
<a name="l00065"></a>00065 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00066"></a>00066 <span class="preprocessor"></span>
<a name="l00067"></a>00067 <span class="preprocessor">#define __NAME_PREFIX__ ___rb_</span>
<a name="l00068"></a>00068 <span class="preprocessor"></span><span class="preprocessor">#define __TREETYPE_PREFIX rbtree_</span>
<a name="l00069"></a>00069 <span class="preprocessor"></span><span class="preprocessor">#define __NODETYPE_PREFIX rbnode_</span>
<a name="l00070"></a>00070 <span class="preprocessor"></span><span class="preprocessor">#define __NODETYPE_ATTRS__ __attribute__ ((packed))</span>
<a name="l00071"></a>00071 <span class="preprocessor"></span><span class="preprocessor">#define __TREETYPE_ATTRS__ __attribute__ ((packed))</span>
<a name="l00072"></a>00072 <span class="preprocessor"></span>
<a name="l00073"></a>00073 <span class="keyword">typedef</span> uint8_t side_t;
<a name="l00074"></a>00074 <span class="keyword">typedef</span> uint8_t color_t;
<a name="l00075"></a>00075
<a name="l00076"></a>00076 <span class="preprocessor">#define __MYCONCAT2(a, b) a ## b</span>
<a name="l00077"></a>00077 <span class="preprocessor"></span><span class="preprocessor">#define __MYCONCAT3(a, b, c) a ## b ## c</span>
<a name="l00078"></a>00078 <span class="preprocessor"></span><span class="preprocessor">#define CONCAT2(a, b) __MYCONCAT2(a, b)</span>
<a name="l00079"></a>00079 <span class="preprocessor"></span><span class="preprocessor">#define CONCAT3(a, b, c) __MYCONCAT3(a, b, c)</span>
<a name="l00080"></a>00080 <span class="preprocessor"></span><span class="preprocessor">#define EXPAND(a) a</span>
<a name="l00081"></a>00081 <span class="preprocessor"></span>
<a name="l00082"></a>00082 <span class="preprocessor">#define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name)</span>
<a name="l00083"></a>00083 <span class="preprocessor"></span><span class="preprocessor">#define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name)</span>
<a name="l00084"></a>00084 <span class="preprocessor"></span>
<a name="l00085"></a>00085 <span class="comment">/* Definition templates */</span>
<a name="l00086"></a>00086 <span class="preprocessor">#define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree)</span>
<a name="l00087"></a>00087 <span class="preprocessor"></span>
<a name="l00088"></a>00088 <span class="preprocessor">#define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create)</span>
<a name="l00089"></a>00089 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void)</span>
<a name="l00090"></a>00090 <span class="preprocessor"></span><span class="preprocessor">#define RB_CREATE RBN_CREATE_NAME</span>
<a name="l00091"></a>00091 <span class="preprocessor"></span>
<a name="l00092"></a>00092 <span class="preprocessor">#define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode)</span>
<a name="l00093"></a>00093 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void)</span>
<a name="l00094"></a>00094 <span class="preprocessor"></span><span class="preprocessor">#define RB_NEWNODE RBN_NEWNODE_NAME</span>
<a name="l00095"></a>00095 <span class="preprocessor"></span>
<a name="l00096"></a>00096 <span class="preprocessor">#define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert)</span>
<a name="l00097"></a>00097 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node)</span>
<a name="l00098"></a>00098 <span class="preprocessor"></span><span class="preprocessor">#define RB_INSERT RBN_INSERT_NAME</span>
<a name="l00099"></a>00099 <span class="preprocessor"></span>
<a name="l00100"></a>00100 <span class="preprocessor">#define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search)</span>
<a name="l00101"></a>00101 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)</span>
<a name="l00102"></a>00102 <span class="preprocessor"></span><span class="preprocessor">#define RB_SEARCH RBN_SEARCH_NAME</span>
<a name="l00103"></a>00103 <span class="preprocessor"></span>
<a name="l00104"></a>00104 <span class="preprocessor">#define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)</span>
<a name="l00105"></a>00105 <span class="preprocessor"></span>
<a name="l00106"></a>00106 <span class="preprocessor">#define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name)</span>
<a name="l00107"></a>00107 <span class="preprocessor"></span>
<a name="l00108"></a>00108 <span class="preprocessor">#define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node)</span>
<a name="l00109"></a>00109 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node)</span>
<a name="l00110"></a>00110 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name)</span>
<a name="l00111"></a>00111 <span class="preprocessor"></span>
<a name="l00112"></a>00112 <span class="preprocessor">#define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node)</span>
<a name="l00113"></a>00113 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node)</span>
<a name="l00114"></a>00114 <span class="preprocessor"></span>
<a name="l00115"></a>00115 <span class="preprocessor">#define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r)</span>
<a name="l00116"></a>00116 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r)</span>
<a name="l00117"></a>00117 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r)</span>
<a name="l00118"></a>00118 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r)</span>
<a name="l00119"></a>00119 <span class="preprocessor"></span>
<a name="l00120"></a>00120 <span class="preprocessor">#define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate)</span>
<a name="l00121"></a>00121 <span class="preprocessor"></span>
<a name="l00122"></a>00122 <span class="preprocessor">#define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp)</span>
<a name="l00123"></a>00123 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b)</span>
<a name="l00124"></a>00124 <span class="preprocessor"></span><span class="preprocessor">#define RBNODECMP DEF_RBN_NODECMP</span>
<a name="l00125"></a>00125 <span class="preprocessor"></span>
<a name="l00126"></a>00126 <span class="preprocessor">#define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin)</span>
<a name="l00127"></a>00127 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b)</span>
<a name="l00128"></a>00128 <span class="preprocessor"></span><span class="preprocessor">#define RBNODEJOIN DEF_RBN_NODEJOIN</span>
<a name="l00129"></a>00129 <span class="preprocessor"></span>
<a name="l00130"></a>00130 <span class="preprocessor">#define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk)</span>
<a name="l00131"></a>00131 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_WALK(__t_name) void RBN_WALK_NAME(__t_name) (TREETYPE(__t_name) *tree, uint8_t order, void (*callback)(NODETYPE(__t_name) *, void *), void *cbarg)</span>
<a name="l00132"></a>00132 <span class="preprocessor"></span><span class="preprocessor">#define RB_WALK RBN_WALK_NAME</span>
<a name="l00133"></a>00133 <span class="preprocessor"></span>
<a name="l00134"></a>00134 <span class="preprocessor">#define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname)</span>
<a name="l00135"></a>00135 <span class="preprocessor"></span><span class="preprocessor">#define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg)</span>
<a name="l00136"></a>00136 <span class="preprocessor"></span><span class="preprocessor">#define RBCBNAME RBN_CALLBACK_NAME</span>
<a name="l00137"></a>00137 <span class="preprocessor"></span><span class="preprocessor">#define RBCALLBACK DEF_RBN_CALLBACK</span>
<a name="l00138"></a>00138 <span class="preprocessor"></span>
<a name="l00139"></a>00139 <span class="preprocessor">#define NOARG 0</span>
<a name="l00140"></a>00140 <span class="preprocessor"></span>
<a name="l00141"></a>00141 <span class="comment">/* Main template */</span>
<a name="l00142"></a>00142 <span class="preprocessor">#define DEFRBTREE(__t_name, __u_nitem) \</span>
<a name="l00143"></a>00143 <span class="preprocessor"> NODETYPE(__t_name) { \</span>
<a name="l00144"></a>00144 <span class="preprocessor"> </span><span class="comment">/* META data */</span> \
<a name="l00145"></a>00145 NODETYPE(__t_name) *___child[2]; \
<a name="l00146"></a>00146 color_t ___c: 1; <span class="comment">/* Node color */</span> \
<a name="l00147"></a>00147 side_t ___s: 1; <span class="comment">/* Node side relative to parent */</span> \
<a name="l00148"></a>00148 <span class="comment">/* USER data */</span> \
<a name="l00149"></a>00149 __u_nitem; \
<a name="l00150"></a>00150 } __NODETYPE_ATTRS__; \
<a name="l00151"></a>00151 \
<a name="l00152"></a>00152 TREETYPE(__t_name) { \
<a name="l00153"></a>00153 NODETYPE(__t_name) *root; \
<a name="l00154"></a>00154 size_t size; \
<a name="l00155"></a>00155 } __TREETYPE_ATTRS__; \
<a name="l00156"></a>00156 \
<a name="l00157"></a>00157 DEF_RBN_NODEJOIN(__t_name); \
<a name="l00158"></a>00158 DEF_RBN_NODECMP(__t_name); \
<a name="l00159"></a>00159 DEF_RBN_CREATE(__t_name); \
<a name="l00160"></a>00160 DEF_RBN_NEWNODE(__t_name); \
<a name="l00161"></a>00161 DEF_RBN_WALK(__t_name); \
<a name="l00162"></a>00162 DEF_RBN_INSERT(__t_name); \
<a name="l00163"></a>00163 DEF_RBN_SEARCH(__t_name)
<a name="l00164"></a>00164 <span class="comment">/*</span>
<a name="l00165"></a>00165 <span class="comment"> DEF_RBN_INITST(__t_name); \</span>
<a name="l00166"></a>00166 <span class="comment"> DEF_RBN_SEARCH(__t_name, __keytype); \</span>
<a name="l00167"></a>00167 <span class="comment"> DEF_RBN_DELETE(__t_name, __keytype); \</span>
<a name="l00168"></a>00168 <span class="comment"> DEF_RBN_NODE_LEFT(__t_name); \</span>
<a name="l00169"></a>00169 <span class="comment"> DEF_RBN_NODE_RGHT(__t_name); \</span>
<a name="l00170"></a>00170 <span class="comment"> DEF_RBN_NODE_COLOR(__t_name); \</span>
<a name="l00171"></a>00171 <span class="comment"> DEF_RBN_NODE_SIDE(__t_name)</span>
<a name="l00172"></a>00172 <span class="comment">*/</span>
<a name="l00173"></a>00173
<a name="l00174"></a>00174 <span class="preprocessor">#define __isRED(n) ((n)->___c == COLOR_RED)</span>
<a name="l00175"></a>00175 <span class="preprocessor"></span><span class="preprocessor">#define isRED(n) (((n) == NULL) ? 0 : __isRED(n))</span>
<a name="l00176"></a>00176 <span class="preprocessor"></span><span class="preprocessor">#define PTRMOVE(next) { \</span>
<a name="l00177"></a>00177 <span class="preprocessor"> ggp = grp; \</span>
<a name="l00178"></a>00178 <span class="preprocessor"> grp = par; \</span>
<a name="l00179"></a>00179 <span class="preprocessor"> par = cur; \</span>
<a name="l00180"></a>00180 <span class="preprocessor"> cur = next; }</span>
<a name="l00181"></a>00181 <span class="preprocessor"></span>
<a name="l00182"></a>00182 <span class="preprocessor">#define lch (cur->___child[SIDE_LEFT])</span>
<a name="l00183"></a>00183 <span class="preprocessor"></span><span class="preprocessor">#define rch (cur->___child[SIDE_RGHT])</span>
<a name="l00184"></a>00184 <span class="preprocessor"></span>
<a name="l00185"></a>00185 <span class="comment">/* Code templates */</span>
<a name="l00186"></a>00186 <span class="comment">//#define RBN_INITST()</span>
<a name="l00187"></a>00187
<a name="l00188"></a>00188 <span class="preprocessor">#define RBN_NEWNODE_CODE(__t_name) \</span>
<a name="l00189"></a>00189 <span class="preprocessor"> DEF_RBN_NEWNODE(__t_name) { \</span>
<a name="l00190"></a>00190 <span class="preprocessor"> NODETYPE(__t_name) *new; \</span>
<a name="l00191"></a>00191 <span class="preprocessor"> new = XMALLOC(sizeof(NODETYPE(__t_name))); \</span>
<a name="l00192"></a>00192 <span class="preprocessor"> new->___s = 0; \</span>
<a name="l00193"></a>00193 <span class="preprocessor"> new->___c = 0; \</span>
<a name="l00194"></a>00194 <span class="preprocessor"> new->___child[0] = NULL; \</span>
<a name="l00195"></a>00195 <span class="preprocessor"> new->___child[1] = NULL; \</span>
<a name="l00196"></a>00196 <span class="preprocessor"> return (new); \</span>
<a name="l00197"></a>00197 <span class="preprocessor"> }</span>
<a name="l00198"></a>00198 <span class="preprocessor"></span>
<a name="l00199"></a>00199 <span class="preprocessor">#define RBN_ROTATE_CODE(__t_name) \</span>
<a name="l00200"></a>00200 <span class="preprocessor"> static DEF_RBN_ROT_L(__t_name) { \</span>
<a name="l00201"></a>00201 <span class="preprocessor"> register NODETYPE(__t_name) *nr; \</span>
<a name="l00202"></a>00202 <span class="preprocessor"> \</span>
<a name="l00203"></a>00203 <span class="preprocessor"> nr = r->___child[SIDE_RGHT]; \</span>
<a name="l00204"></a>00204 <span class="preprocessor"> r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \</span>
<a name="l00205"></a>00205 <span class="preprocessor"> nr->___child[SIDE_LEFT] = r; \</span>
<a name="l00206"></a>00206 <span class="preprocessor"> \</span>
<a name="l00207"></a>00207 <span class="preprocessor"> nr->___s = r->___s; \</span>
<a name="l00208"></a>00208 <span class="preprocessor"> r->___s = SIDE_LEFT; \</span>
<a name="l00209"></a>00209 <span class="preprocessor"> \</span>
<a name="l00210"></a>00210 <span class="preprocessor"> if (r->___child[SIDE_RGHT] != NULL) \</span>
<a name="l00211"></a>00211 <span class="preprocessor"> r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \</span>
<a name="l00212"></a>00212 <span class="preprocessor"> \</span>
<a name="l00213"></a>00213 <span class="preprocessor"> if (nr->___child[SIDE_RGHT] != NULL) \</span>
<a name="l00214"></a>00214 <span class="preprocessor"> nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \</span>
<a name="l00215"></a>00215 <span class="preprocessor"> \</span>
<a name="l00216"></a>00216 <span class="preprocessor"> return (nr); \</span>
<a name="l00217"></a>00217 <span class="preprocessor"> } \</span>
<a name="l00218"></a>00218 <span class="preprocessor"> \</span>
<a name="l00219"></a>00219 <span class="preprocessor"> static DEF_RBN_ROT_R(__t_name) { \</span>
<a name="l00220"></a>00220 <span class="preprocessor"> register NODETYPE(__t_name) *nr; \</span>
<a name="l00221"></a>00221 <span class="preprocessor"> \</span>
<a name="l00222"></a>00222 <span class="preprocessor"> nr = r->___child[SIDE_LEFT]; \</span>
<a name="l00223"></a>00223 <span class="preprocessor"> r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \</span>
<a name="l00224"></a>00224 <span class="preprocessor"> nr->___child[SIDE_RGHT] = r; \</span>
<a name="l00225"></a>00225 <span class="preprocessor"> \</span>
<a name="l00226"></a>00226 <span class="preprocessor"> nr->___s = r->___s; \</span>
<a name="l00227"></a>00227 <span class="preprocessor"> r->___s = SIDE_RGHT; \</span>
<a name="l00228"></a>00228 <span class="preprocessor"> \</span>
<a name="l00229"></a>00229 <span class="preprocessor"> if (r->___child[SIDE_LEFT] != NULL) \</span>
<a name="l00230"></a>00230 <span class="preprocessor"> r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \</span>
<a name="l00231"></a>00231 <span class="preprocessor"> \</span>
<a name="l00232"></a>00232 <span class="preprocessor"> if (nr->___child[SIDE_LEFT] != NULL) \</span>
<a name="l00233"></a>00233 <span class="preprocessor"> nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \</span>
<a name="l00234"></a>00234 <span class="preprocessor"> \</span>
<a name="l00235"></a>00235 <span class="preprocessor"> return (nr); \</span>
<a name="l00236"></a>00236 <span class="preprocessor"> } \</span>
<a name="l00237"></a>00237 <span class="preprocessor"> \</span>
<a name="l00238"></a>00238 <span class="preprocessor"> static DEF_RBN_ROT_LR(__t_name) { \</span>
<a name="l00239"></a>00239 <span class="preprocessor"> register NODETYPE(__t_name) *nr; \</span>
<a name="l00240"></a>00240 <span class="preprocessor"> \</span>
<a name="l00241"></a>00241 <span class="preprocessor"> nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \</span>
<a name="l00242"></a>00242 <span class="preprocessor"> nr->___s = r->___s; \</span>
<a name="l00243"></a>00243 <span class="preprocessor"> r->___s = SIDE_LEFT; \</span>
<a name="l00244"></a>00244 <span class="preprocessor"> r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \</span>
<a name="l00245"></a>00245 <span class="preprocessor"> \</span>
<a name="l00246"></a>00246 <span class="preprocessor"> if (nr->___child[SIDE_RGHT] != NULL) \</span>
<a name="l00247"></a>00247 <span class="preprocessor"> nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \</span>
<a name="l00248"></a>00248 <span class="preprocessor"> \</span>
<a name="l00249"></a>00249 <span class="preprocessor"> nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \</span>
<a name="l00250"></a>00250 <span class="preprocessor"> r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \</span>
<a name="l00251"></a>00251 <span class="preprocessor"> \</span>
<a name="l00252"></a>00252 <span class="preprocessor"> if (nr->___child[SIDE_LEFT] != NULL) \</span>
<a name="l00253"></a>00253 <span class="preprocessor"> nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \</span>
<a name="l00254"></a>00254 <span class="preprocessor"> \</span>
<a name="l00255"></a>00255 <span class="preprocessor"> nr->___child[SIDE_LEFT] = r; \</span>
<a name="l00256"></a>00256 <span class="preprocessor"> nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \</span>
<a name="l00257"></a>00257 <span class="preprocessor"> \</span>
<a name="l00258"></a>00258 <span class="preprocessor"> return (nr); \</span>
<a name="l00259"></a>00259 <span class="preprocessor"> } \</span>
<a name="l00260"></a>00260 <span class="preprocessor"> \</span>
<a name="l00261"></a>00261 <span class="preprocessor"> static DEF_RBN_ROT_RL(__t_name) { \</span>
<a name="l00262"></a>00262 <span class="preprocessor"> register NODETYPE(__t_name) *nr; \</span>
<a name="l00263"></a>00263 <span class="preprocessor"> \</span>
<a name="l00264"></a>00264 <span class="preprocessor"> nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \</span>
<a name="l00265"></a>00265 <span class="preprocessor"> nr->___s = r->___s; \</span>
<a name="l00266"></a>00266 <span class="preprocessor"> r->___s = SIDE_RGHT; \</span>
<a name="l00267"></a>00267 <span class="preprocessor"> r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \</span>
<a name="l00268"></a>00268 <span class="preprocessor"> \</span>
<a name="l00269"></a>00269 <span class="preprocessor"> if (nr->___child[SIDE_LEFT] != NULL) \</span>
<a name="l00270"></a>00270 <span class="preprocessor"> nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \</span>
<a name="l00271"></a>00271 <span class="preprocessor"> \</span>
<a name="l00272"></a>00272 <span class="preprocessor"> nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \</span>
<a name="l00273"></a>00273 <span class="preprocessor"> r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \</span>
<a name="l00274"></a>00274 <span class="preprocessor"> \</span>
<a name="l00275"></a>00275 <span class="preprocessor"> if (nr->___child[SIDE_RGHT] != NULL) \</span>
<a name="l00276"></a>00276 <span class="preprocessor"> nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \</span>
<a name="l00277"></a>00277 <span class="preprocessor"> \</span>
<a name="l00278"></a>00278 <span class="preprocessor"> nr->___child[SIDE_RGHT] = r; \</span>
<a name="l00279"></a>00279 <span class="preprocessor"> nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \</span>
<a name="l00280"></a>00280 <span class="preprocessor"> \</span>
<a name="l00281"></a>00281 <span class="preprocessor"> return (nr); \</span>
<a name="l00282"></a>00282 <span class="preprocessor"> } \</span>
<a name="l00283"></a>00283 <span class="preprocessor"> \</span>
<a name="l00284"></a>00284 <span class="preprocessor"> static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \</span>
<a name="l00285"></a>00285 <span class="preprocessor"> &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \</span>
<a name="l00286"></a>00286 <span class="preprocessor"> &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \</span>
<a name="l00287"></a>00287 <span class="preprocessor"> &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \</span>
<a name="l00288"></a>00288 <span class="preprocessor"> &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \</span>
<a name="l00289"></a>00289 <span class="preprocessor"> }</span>
<a name="l00290"></a>00290 <span class="preprocessor"></span>
<a name="l00291"></a>00291 <span class="preprocessor">#define RBN_CREATE_CODE(__t_name) \</span>
<a name="l00292"></a>00292 <span class="preprocessor"> DEF_RBN_CREATE(__t_name) { \</span>
<a name="l00293"></a>00293 <span class="preprocessor"> TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \</span>
<a name="l00294"></a>00294 <span class="preprocessor"> new->root = NULL; \</span>
<a name="l00295"></a>00295 <span class="preprocessor"> new->size = 0; \</span>
<a name="l00296"></a>00296 <span class="preprocessor"> return (new); \</span>
<a name="l00297"></a>00297 <span class="preprocessor"> } </span>
<a name="l00298"></a>00298 <span class="preprocessor"></span>
<a name="l00299"></a>00299 <span class="preprocessor">#define RBN_INSERT_CODE(__t_name) \</span>
<a name="l00300"></a>00300 <span class="preprocessor"> DEF_RBN_INSERT(__t_name) { \</span>
<a name="l00301"></a>00301 <span class="preprocessor"> NODETYPE(__t_name) *cur, *par, *grp, *ggp; \</span>
<a name="l00302"></a>00302 <span class="preprocessor"> side_t lastdir; \</span>
<a name="l00303"></a>00303 <span class="preprocessor"> int cmp; \</span>
<a name="l00304"></a>00304 <span class="preprocessor"> NODETYPE(__t_name) fake; \</span>
<a name="l00305"></a>00305 <span class="preprocessor"> \</span>
<a name="l00306"></a>00306 <span class="preprocessor"> fake.___c = COLOR_BLK; \</span>
<a name="l00307"></a>00307 <span class="preprocessor"> fake.___child[SIDE_RGHT] = tree->root; \</span>
<a name="l00308"></a>00308 <span class="preprocessor"> fake.___child[SIDE_LEFT] = NULL; \</span>
<a name="l00309"></a>00309 <span class="preprocessor"> ggp = grp = NULL; \</span>
<a name="l00310"></a>00310 <span class="preprocessor"> par = &fake; \</span>
<a name="l00311"></a>00311 <span class="preprocessor"> cur = tree->root; \</span>
<a name="l00312"></a>00312 <span class="preprocessor"> lastdir = SIDE_RGHT; \</span>
<a name="l00313"></a>00313 <span class="preprocessor"> \</span>
<a name="l00314"></a>00314 <span class="preprocessor"> for (;;) { \</span>
<a name="l00315"></a>00315 <span class="preprocessor"> </span><span class="comment">/* Search loop BEGIN */</span> \
<a name="l00316"></a>00316 if (cur == NULL) { \
<a name="l00317"></a>00317 par->___child[lastdir] = cur = new_node; \
<a name="l00318"></a>00318 cur->___s = lastdir; \
<a name="l00319"></a>00319 cur->___c = COLOR_RED; \
<a name="l00320"></a>00320 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \
<a name="l00321"></a>00321 \
<a name="l00322"></a>00322 if (__isRED(par)) <span class="comment">/* red violation */</span> \
<a name="l00323"></a>00323 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \
<a name="l00324"></a>00324 \
<a name="l00325"></a>00325 tree->root = fake.___child[SIDE_RGHT]; \
<a name="l00326"></a>00326 tree->root->___c = COLOR_BLK; \
<a name="l00327"></a>00327 ++(tree->size); \
<a name="l00328"></a>00328 \
<a name="l00329"></a>00329 return (E_OK); \
<a name="l00330"></a>00330 } else if (isRED(lch) && isRED(rch)) { \
<a name="l00331"></a>00331 <span class="comment">/* color switch */</span> \
<a name="l00332"></a>00332 cur->___c = COLOR_RED; \
<a name="l00333"></a>00333 lch->___c = rch->___c = COLOR_BLK; \
<a name="l00334"></a>00334 \
<a name="l00335"></a>00335 if (__isRED(par)) <span class="comment">/* red violation */</span> \
<a name="l00336"></a>00336 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
<a name="l00337"></a>00337 } else if (__isRED(par) && __isRED(cur)) { \
<a name="l00338"></a>00338 <span class="comment">/* red violation */</span> \
<a name="l00339"></a>00339 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
<a name="l00340"></a>00340 } \
<a name="l00341"></a>00341 \
<a name="l00342"></a>00342 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \
<a name="l00343"></a>00343 \
<a name="l00344"></a>00344 if (cmp == 0) { \
<a name="l00345"></a>00345 lastdir = cur->___s; \
<a name="l00346"></a>00346 _E(color_t tmp_c = cur->___c;) \
<a name="l00347"></a>00347 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \
<a name="l00348"></a>00348 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \
<a name="l00349"></a>00349 tree->root = fake.___child[SIDE_RGHT]; \
<a name="l00350"></a>00350 tree->root->___c = COLOR_BLK; \
<a name="l00351"></a>00351 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \
<a name="l00352"></a>00352 \
<a name="l00353"></a>00353 assert(cur->___s == lastdir); \
<a name="l00354"></a>00354 assert(cur->___c == tmp_c); \
<a name="l00355"></a>00355 assert(cur->___child[SIDE_LEFT] == tmp_l); \
<a name="l00356"></a>00356 assert(cur->___child[SIDE_RGHT] == tmp_r); \
<a name="l00357"></a>00357 \
<a name="l00358"></a>00358 return (E_COLL); \
<a name="l00359"></a>00359 } else if (cmp < 0) { \
<a name="l00360"></a>00360 <span class="comment">/* go right */</span> \
<a name="l00361"></a>00361 PTRMOVE(rch); \
<a name="l00362"></a>00362 lastdir = SIDE_RGHT; \
<a name="l00363"></a>00363 } else { \
<a name="l00364"></a>00364 <span class="comment">/* go left */</span> \
<a name="l00365"></a>00365 PTRMOVE(lch); \
<a name="l00366"></a>00366 lastdir = SIDE_LEFT; \
<a name="l00367"></a>00367 } \
<a name="l00368"></a>00368 } <span class="comment">/* Search loop END */</span> \
<a name="l00369"></a>00369 \
<a name="l00370"></a>00370 abort (); \
<a name="l00371"></a>00371 return (E_FAIL); \
<a name="l00372"></a>00372 }
<a name="l00373"></a>00373
<a name="l00374"></a>00374 <span class="preprocessor">#define RBN_SEARCH_CODE(__t_name) \</span>
<a name="l00375"></a>00375 <span class="preprocessor"> DEF_RBN_SEARCH(__t_name) { \</span>
<a name="l00376"></a>00376 <span class="preprocessor"> NODETYPE(__t_name) *node; \</span>
<a name="l00377"></a>00377 <span class="preprocessor"> int cmp; \</span>
<a name="l00378"></a>00378 <span class="preprocessor"> \</span>
<a name="l00379"></a>00379 <span class="preprocessor"> node = tree->root; \</span>
<a name="l00380"></a>00380 <span class="preprocessor"> \</span>
<a name="l00381"></a>00381 <span class="preprocessor"> while (node != NULL) { \</span>
<a name="l00382"></a>00382 <span class="preprocessor"> cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \</span>
<a name="l00383"></a>00383 <span class="preprocessor"> \</span>
<a name="l00384"></a>00384 <span class="preprocessor"> if (cmp == 0) \</span>
<a name="l00385"></a>00385 <span class="preprocessor"> break; \</span>
<a name="l00386"></a>00386 <span class="preprocessor"> else if (cmp < 0) \</span>
<a name="l00387"></a>00387 <span class="preprocessor"> node = node->___child[SIDE_RGHT]; \</span>
<a name="l00388"></a>00388 <span class="preprocessor"> else \</span>
<a name="l00389"></a>00389 <span class="preprocessor"> node = node->___child[SIDE_LEFT]; \</span>
<a name="l00390"></a>00390 <span class="preprocessor"> } \</span>
<a name="l00391"></a>00391 <span class="preprocessor"> \</span>
<a name="l00392"></a>00392 <span class="preprocessor"> return (node); \</span>
<a name="l00393"></a>00393 <span class="preprocessor"> }</span>
<a name="l00394"></a>00394 <span class="preprocessor"></span>
<a name="l00395"></a>00395 <span class="preprocessor">#define __WALK_STACK_SIZE 32</span>
<a name="l00396"></a>00396 <span class="preprocessor"></span><span class="preprocessor">#define __WALK_STACK_GROW 16</span>
<a name="l00397"></a>00397 <span class="preprocessor"></span>
<a name="l00398"></a>00398 <span class="preprocessor">#define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count</span>
<a name="l00399"></a>00399 <span class="preprocessor"></span><span class="preprocessor">#define POP(n) (n) = node_stack[--node_stack_count]</span>
<a name="l00400"></a>00400 <span class="preprocessor"></span><span class="preprocessor">#define TOP (node_stack[node_stack_count-1])</span>
<a name="l00401"></a>00401 <span class="preprocessor"></span><span class="preprocessor">#define CNT node_stack_count</span>
<a name="l00402"></a>00402 <span class="preprocessor"></span>
<a name="l00403"></a>00403 <span class="preprocessor">#define RBN_WALK_CODE(__t_name) \</span>
<a name="l00404"></a>00404 <span class="preprocessor"> DEF_RBN_WALK(__t_name) { \</span>
<a name="l00405"></a>00405 <span class="preprocessor"> NODETYPE(__t_name) **node_stack; \</span>
<a name="l00406"></a>00406 <span class="preprocessor"> register uint16_t node_stack_size; \</span>
<a name="l00407"></a>00407 <span class="preprocessor"> register uint16_t node_stack_count; \</span>
<a name="l00408"></a>00408 <span class="preprocessor"> \</span>
<a name="l00409"></a>00409 <span class="preprocessor"> node_stack_count = 0; \</span>
<a name="l00410"></a>00410 <span class="preprocessor"> node_stack_size = __WALK_STACK_SIZE; \</span>
<a name="l00411"></a>00411 <span class="preprocessor"> node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \</span>
<a name="l00412"></a>00412 <span class="preprocessor"> \</span>
<a name="l00413"></a>00413 <span class="preprocessor"> PUSH(tree->root); \</span>
<a name="l00414"></a>00414 <span class="preprocessor"> \</span>
<a name="l00415"></a>00415 <span class="preprocessor"> switch (order) { \</span>
<a name="l00416"></a>00416 <span class="preprocessor"> case PREORDER: \</span>
<a name="l00417"></a>00417 <span class="preprocessor"> while (CNT > 0) { \</span>
<a name="l00418"></a>00418 <span class="preprocessor"> callback (TOP, cbarg); \</span>
<a name="l00419"></a>00419 <span class="preprocessor"> if (TOP->___child[SIDE_LEFT] != NULL) { \</span>
<a name="l00420"></a>00420 <span class="preprocessor"> PUSH(TOP->___child[SIDE_LEFT]); \</span>
<a name="l00421"></a>00421 <span class="preprocessor"> } else { \</span>
<a name="l00422"></a>00422 <span class="preprocessor"> __pre: \</span>
<a name="l00423"></a>00423 <span class="preprocessor"> if (TOP->___child[SIDE_RGHT] != NULL) { \</span>
<a name="l00424"></a>00424 <span class="preprocessor"> TOP = TOP->___child[SIDE_RGHT]; \</span>
<a name="l00425"></a>00425 <span class="preprocessor"> } else { \</span>
<a name="l00426"></a>00426 <span class="preprocessor"> if (--CNT > 0) \</span>
<a name="l00427"></a>00427 <span class="preprocessor"> goto __pre; \</span>
<a name="l00428"></a>00428 <span class="preprocessor"> else \</span>
<a name="l00429"></a>00429 <span class="preprocessor"> break; \</span>
<a name="l00430"></a>00430 <span class="preprocessor"> } \</span>
<a name="l00431"></a>00431 <span class="preprocessor"> } \</span>
<a name="l00432"></a>00432 <span class="preprocessor"> } \</span>
<a name="l00433"></a>00433 <span class="preprocessor"> break; \</span>
<a name="l00434"></a>00434 <span class="preprocessor"> case INORDER: \</span>
<a name="l00435"></a>00435 <span class="preprocessor"> while (CNT > 0) { \</span>
<a name="l00436"></a>00436 <span class="preprocessor"> if (TOP->___child[SIDE_LEFT] != NULL) { \</span>
<a name="l00437"></a>00437 <span class="preprocessor"> PUSH(TOP->___child[SIDE_LEFT]); \</span>
<a name="l00438"></a>00438 <span class="preprocessor"> } else { \</span>
<a name="l00439"></a>00439 <span class="preprocessor"> __in: \</span>
<a name="l00440"></a>00440 <span class="preprocessor"> callback (TOP, cbarg); \</span>
<a name="l00441"></a>00441 <span class="preprocessor"> if (TOP->___child[SIDE_RGHT] != NULL) { \</span>
<a name="l00442"></a>00442 <span class="preprocessor"> TOP = TOP->___child[SIDE_RGHT]; \</span>
<a name="l00443"></a>00443 <span class="preprocessor"> } else { \</span>
<a name="l00444"></a>00444 <span class="preprocessor"> if (--CNT > 0) \</span>
<a name="l00445"></a>00445 <span class="preprocessor"> goto __in; \</span>
<a name="l00446"></a>00446 <span class="preprocessor"> else \</span>
<a name="l00447"></a>00447 <span class="preprocessor"> break; \</span>
<a name="l00448"></a>00448 <span class="preprocessor"> } \</span>
<a name="l00449"></a>00449 <span class="preprocessor"> } \</span>
<a name="l00450"></a>00450 <span class="preprocessor"> } \</span>
<a name="l00451"></a>00451 <span class="preprocessor"> break; \</span>
<a name="l00452"></a>00452 <span class="preprocessor"> case POSTORDER: \</span>
<a name="l00453"></a>00453 <span class="preprocessor"> break; \</span>
<a name="l00454"></a>00454 <span class="preprocessor"> default: \</span>
<a name="l00455"></a>00455 <span class="preprocessor"> abort (); \</span>
<a name="l00456"></a>00456 <span class="preprocessor"> } \</span>
<a name="l00457"></a>00457 <span class="preprocessor"> XFREE(node_stack); \</span>
<a name="l00458"></a>00458 <span class="preprocessor"> return; \</span>
<a name="l00459"></a>00459 <span class="preprocessor"> }</span>
<a name="l00460"></a>00460 <span class="preprocessor"></span>
<a name="l00461"></a>00461 <span class="comment">/*</span>
<a name="l00462"></a>00462 <span class="comment"> #undef PUSH</span>
<a name="l00463"></a>00463 <span class="comment"> #undef POP</span>
<a name="l00464"></a>00464 <span class="comment"> #undef TOP</span>
<a name="l00465"></a>00465 <span class="comment"> #undef COUNT </span>
<a name="l00466"></a>00466 <span class="comment">*/</span>
<a name="l00467"></a>00467
<a name="l00468"></a>00468 <span class="comment">/*</span>
<a name="l00469"></a>00469 <span class="comment"> #define RBN_DELETE()</span>
<a name="l00470"></a>00470 <span class="comment"> #define RBN_REMOVE() RBN_DELETE()</span>
<a name="l00471"></a>00471 <span class="comment">*/</span>
<a name="l00472"></a>00472
<a name="l00473"></a>00473 <span class="comment">/*</span>
<a name="l00474"></a>00474 <span class="comment"> #define RBN_NODE_LEFT()</span>
<a name="l00475"></a>00475 <span class="comment"> #define RBN_NODE_RGHT()</span>
<a name="l00476"></a>00476 <span class="comment"> #define RBN_NODE_RIGHT() RBN_NODE_RGHT()</span>
<a name="l00477"></a>00477 <span class="comment"> #define RBN_NODE_COLOR()</span>
<a name="l00478"></a>00478 <span class="comment"> #define RBN_NODE_SIDE()</span>
<a name="l00479"></a>00479 <span class="comment">*/</span>
<a name="l00480"></a>00480
<a name="l00481"></a>00481 <span class="preprocessor">#define RBTREECODE(__t_name) \</span>
<a name="l00482"></a>00482 <span class="preprocessor"> RBN_CREATE_CODE(__t_name) \</span>
<a name="l00483"></a>00483 <span class="preprocessor"> RBN_ROTATE_CODE(__t_name); \</span>
<a name="l00484"></a>00484 <span class="preprocessor"> RBN_NEWNODE_CODE(__t_name) \</span>
<a name="l00485"></a>00485 <span class="preprocessor"> RBN_SEARCH_CODE(__t_name) \</span>
<a name="l00486"></a>00486 <span class="preprocessor"> RBN_INSERT_CODE(__t_name) \</span>
<a name="l00487"></a>00487 <span class="preprocessor"> RBN_WALK_CODE(__t_name) \</span>
<a name="l00488"></a>00488 <span class="preprocessor"> static const char CONCAT2(__t_name, dummy) = 0</span>
<a name="l00489"></a>00489 <span class="preprocessor"></span>
<a name="l00490"></a>00490 OSCAP_HIDDEN_END;
<a name="l00491"></a>00491
<a name="l00492"></a>00492 <span class="preprocessor">#endif </span><span class="comment">/* REDBLACK_H */</span>
</pre></div></div>
<hr size="1"/><address style="text-align: right;"><small>Generated on 30 Jun 2010 for Open SCAP Library by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
|
