1 /***************************************************************************
2 begin : Fri Jan 02 2009
3 copyright : (C) 2009 by Martin Preuss
4 email : martin@libchipcard.de
5
6 ***************************************************************************
7 * *
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21 * MA 02111-1307 USA *
22 * *
23 ***************************************************************************/
24
25
26 #ifdef HAVE_CONFIG_H
27 # include <config.h>
28 #endif
29
30 #define DISABLE_DEBUGLOG
31
32 #include "tree_p.h"
33 #include <gwenhywfar/misc.h>
34 #include <gwenhywfar/debug.h>
35
36
37
38
GWEN_Tree_new(void)39 GWEN_TREE *GWEN_Tree_new(void)
40 {
41 GWEN_TREE *l;
42
43 GWEN_NEW_OBJECT(GWEN_TREE, l);
44 return l;
45 }
46
47
GWEN_Tree_free(GWEN_TREE * l)48 void GWEN_Tree_free(GWEN_TREE *l)
49 {
50 if (l) {
51 GWEN_FREE_OBJECT(l);
52 }
53 }
54
55
56
GWEN_Tree_GetCount(const GWEN_TREE * l)57 int GWEN_Tree_GetCount(const GWEN_TREE *l)
58 {
59 assert(l);
60 return l->count;
61 }
62
63
64
GWEN_Tree_Add(GWEN_TREE * l,GWEN_TREE_ELEMENT * el)65 void GWEN_Tree_Add(GWEN_TREE *l, GWEN_TREE_ELEMENT *el)
66 {
67 assert(l);
68 assert(el);
69 if (el->treePtr) {
70 /* element is already part of another list */
71 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
72 assert(0);
73 }
74 else {
75 if (l->firstElement==0)
76 l->firstElement=el;
77
78 el->prevElement=l->lastElement;
79 if (l->lastElement)
80 l->lastElement->nextElement=el;
81 l->lastElement=el;
82
83 el->treePtr=l;
84 el->parent=NULL;
85 l->count++;
86 }
87 }
88
89
90
GWEN_Tree_AddList(GWEN_TREE * dest,GWEN_TREE * l)91 void GWEN_Tree_AddList(GWEN_TREE *dest, GWEN_TREE *l)
92 {
93 GWEN_TREE_ELEMENT *el;
94
95 assert(dest);
96 assert(l);
97
98 while ((el=l->firstElement)) {
99 GWEN_Tree_Del(el);
100 GWEN_Tree_Add(dest, el);
101 }
102 }
103
104
105
GWEN_Tree_Insert(GWEN_TREE * l,GWEN_TREE_ELEMENT * el)106 void GWEN_Tree_Insert(GWEN_TREE *l, GWEN_TREE_ELEMENT *el)
107 {
108 assert(l);
109 assert(el);
110 if (el->treePtr) {
111 /* element is already part of another list */
112 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
113 }
114 else {
115 el->nextElement=l->firstElement;
116 l->firstElement=el;
117
118 if (l->lastElement==0)
119 l->lastElement=el;
120
121 el->treePtr=l;
122 el->parent=NULL;
123 l->count++;
124 }
125 }
126
127
128
GWEN_Tree_Del(GWEN_TREE_ELEMENT * el)129 void GWEN_Tree_Del(GWEN_TREE_ELEMENT *el)
130 {
131 GWEN_TREE *l;
132
133 l=el->treePtr;
134
135 if (l==0) {
136 /* not part of any list */
137 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
138 }
139 else {
140 /* unlink from previous */
141 if (el->prevElement)
142 el->prevElement->nextElement=el->nextElement;
143
144 /* unlink from next */
145 if (el->nextElement)
146 el->nextElement->prevElement=el->prevElement;
147
148 /* unlink from list */
149 if (l->firstElement==el)
150 l->firstElement=el->nextElement;
151 if (l->lastElement==el)
152 l->lastElement=el->prevElement;
153 l->count--;
154
155 /* unlink from parent */
156 if (el->parent) {
157 if (el->parent->firstChild==el)
158 el->parent->firstChild=el->nextElement;
159 if (el->parent->lastChild==el)
160 el->parent->lastChild=el->prevElement;
161 el->parent->count--;
162 }
163
164 el->nextElement=NULL;
165 el->prevElement=NULL;
166 el->parent=NULL;
167 el->treePtr=NULL;
168 }
169 }
170
171
172
GWEN_Tree_Replace(GWEN_TREE_ELEMENT * elToReplace,GWEN_TREE_ELEMENT * elReplacement)173 void GWEN_Tree_Replace(GWEN_TREE_ELEMENT *elToReplace, GWEN_TREE_ELEMENT *elReplacement)
174 {
175 GWEN_TREE *l;
176
177 l=elToReplace->treePtr;
178
179 if (l==0) {
180 /* not part of any list */
181 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any tree");
182 assert(0);
183 }
184 else {
185 if (elReplacement->treePtr!=NULL) {
186 /* replacement already is a part of another tree */
187 DBG_ERROR(GWEN_LOGDOMAIN, "Replacement element already is part of a tree");
188 assert(0);
189 }
190 else {
191 elReplacement->nextElement=NULL;
192 elReplacement->prevElement=NULL;
193 elReplacement->parent=NULL;
194
195 elReplacement->treePtr=elToReplace->treePtr;
196
197 /* relink with previous */
198 if (elToReplace->prevElement)
199 elToReplace->prevElement->nextElement=elReplacement;
200
201 /* relink with next */
202 if (elToReplace->nextElement)
203 elToReplace->nextElement->prevElement=elReplacement;
204
205 /* relink with tree */
206 if (l->firstElement==elToReplace)
207 l->firstElement=elReplacement;
208 if (l->lastElement==elToReplace)
209 l->lastElement=elReplacement;
210 l->count-=(elToReplace->count)+1;
211 l->count+=(elReplacement->count)+1;
212
213 /* relink with parent */
214 if (elToReplace->parent) {
215 elReplacement->parent=elToReplace->parent;
216 if (elToReplace->parent->firstChild==elToReplace)
217 elToReplace->parent->firstChild=elToReplace;
218 if (elToReplace->parent->lastChild==elToReplace)
219 elToReplace->parent->lastChild=elToReplace;
220 elToReplace->count-=(elToReplace->count)+1;
221 elToReplace->count+=(elReplacement->count)+1;
222 }
223
224 elToReplace->nextElement=NULL;
225 elToReplace->prevElement=NULL;
226 elToReplace->parent=NULL;
227 elToReplace->treePtr=NULL;
228 }
229 }
230 }
231
232
233
GWEN_Tree_AddChild(GWEN_TREE_ELEMENT * where,GWEN_TREE_ELEMENT * el)234 void GWEN_Tree_AddChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el)
235 {
236 if (el->treePtr) {
237 /* element is already part of another tree */
238 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
239 assert(0);
240 }
241 else {
242 if (where->firstChild==0)
243 where->firstChild=el;
244
245 el->prevElement=where->lastChild;
246 if (where->lastChild)
247 where->lastChild->nextElement=el;
248 where->lastChild=el;
249
250 el->parent=where;
251
252 el->treePtr=where->treePtr;
253 el->treePtr->count++;
254 where->count++;
255 }
256 }
257
258
259
GWEN_Tree_InsertChild(GWEN_TREE_ELEMENT * where,GWEN_TREE_ELEMENT * el)260 void GWEN_Tree_InsertChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el)
261 {
262 if (el->treePtr) {
263 /* element is already part of another list */
264 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
265 assert(0);
266 }
267 else {
268 el->nextElement=where->firstChild;
269 where->firstChild=el;
270
271 if (where->lastChild==NULL)
272 where->lastChild=el;
273
274 el->parent=where;
275
276 el->treePtr=where->treePtr;
277 el->treePtr->count++;
278 where->count++;
279 }
280 }
281
282
283
GWEN_Tree_GetFirst(const GWEN_TREE * l)284 void *GWEN_Tree_GetFirst(const GWEN_TREE *l)
285 {
286 if (l->firstElement)
287 return l->firstElement->data;
288 return 0;
289 }
290
291
292
GWEN_Tree_GetLast(const GWEN_TREE * l)293 void *GWEN_Tree_GetLast(const GWEN_TREE *l)
294 {
295 if (l->lastElement)
296 return l->lastElement->data;
297 return 0;
298 }
299
300
301
302
303
GWEN_TreeElement_new(void * d)304 GWEN_TREE_ELEMENT *GWEN_TreeElement_new(void *d)
305 {
306 GWEN_TREE_ELEMENT *el;
307
308 GWEN_NEW_OBJECT(GWEN_TREE_ELEMENT, el);
309 el->data=d;
310
311 return el;
312 }
313
314
315
GWEN_TreeElement_free(GWEN_TREE_ELEMENT * el)316 void GWEN_TreeElement_free(GWEN_TREE_ELEMENT *el)
317 {
318 if (el) {
319 if (el->treePtr)
320 GWEN_Tree_Del(el);
321 if (el->firstChild) {
322 DBG_ERROR(GWEN_LOGDOMAIN, "Tree element still has children");
323 assert(0);
324 }
325 GWEN_FREE_OBJECT(el);
326 }
327 }
328
329
330
GWEN_TreeElement_GetPrevious(const GWEN_TREE_ELEMENT * el)331 void *GWEN_TreeElement_GetPrevious(const GWEN_TREE_ELEMENT *el)
332 {
333 if (el->prevElement)
334 return el->prevElement->data;
335 return 0;
336 }
337
338
339
GWEN_TreeElement_GetNext(const GWEN_TREE_ELEMENT * el)340 void *GWEN_TreeElement_GetNext(const GWEN_TREE_ELEMENT *el)
341 {
342 if (el->nextElement)
343 return el->nextElement->data;
344 return 0;
345 }
346
347
348
GWEN_TreeElement_GetBelow(const GWEN_TREE_ELEMENT * el)349 void *GWEN_TreeElement_GetBelow(const GWEN_TREE_ELEMENT *el)
350 {
351 if (el->firstChild) /* look down */
352 return el->firstChild->data;
353 else if (el->nextElement) /* look right */
354 return el->nextElement->data;
355 else {
356 /* look for a parent which has a right neighbour */
357 while (el && el->parent) {
358 if (el->parent->nextElement) /* look right of parent */
359 return el->parent->nextElement->data;
360 /* parent has no right neighbour, consult its parent */
361 el=el->parent;
362 }
363 }
364
365 return NULL;
366 }
367
368
369
GWEN_TreeElement_GetFirstChild(const GWEN_TREE_ELEMENT * el)370 void *GWEN_TreeElement_GetFirstChild(const GWEN_TREE_ELEMENT *el)
371 {
372 if (el->firstChild)
373 return el->firstChild->data;
374 return NULL;
375 }
376
377
378
GWEN_TreeElement_GetLastChild(const GWEN_TREE_ELEMENT * el)379 void *GWEN_TreeElement_GetLastChild(const GWEN_TREE_ELEMENT *el)
380 {
381 if (el->lastChild)
382 return el->lastChild->data;
383 return NULL;
384 }
385
386
387
GWEN_TreeElement_GetParent(const GWEN_TREE_ELEMENT * el)388 void *GWEN_TreeElement_GetParent(const GWEN_TREE_ELEMENT *el)
389 {
390 if (el->parent)
391 return el->parent->data;
392 return NULL;
393 }
394
395
396
GWEN_TreeElement_GetChildrenCount(const GWEN_TREE_ELEMENT * el)397 uint32_t GWEN_TreeElement_GetChildrenCount(const GWEN_TREE_ELEMENT *el)
398 {
399 assert(el);
400 return el->count;
401 }
402
403
404
405
406
407
408
409
410