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 #include <gwenhywfar/gwenhywfarapi.h> 27 #include <gwenhywfar/types.h> 28 #include <assert.h> 29 30 31 #ifndef GWEN_DUMMY_EMPTY_ARG 32 /** Necessary for MSVC compiler because it does not accept a left-out 33 macro argument. */ 34 # define GWEN_DUMMY_EMPTY_ARG 35 #endif 36 37 38 #ifndef GWEN_TREE_H 39 #define GWEN_TREE_H 40 41 42 #ifdef __cplusplus 43 extern "C" { 44 #endif 45 46 47 /** @defgroup GWEN_MACRO_TREE Macros For Typesafe Tree Handling 48 * 49 * The macros of this group facilitates typesafe use of trees. 50 * 51 * <p> 52 * Let's assume you have a structure type called MYSTRUCT and you want 53 * to manage lists of them. Let's further assume that you want the 54 * functions dealing with that struct have prefixes like MyStruct (as in 55 * @b MyStruct_new) 56 * </p> 57 * The header file would look like this: 58 * 59 * @code 60 * 61 * / * mystruct.h * / 62 * 63 * #ifndef MYSTRUCT_H 64 * #define MYSTRUCT_H 65 * 66 * typedef struct MYSTRUCT MYSTRUCT; 67 * 68 * GWEN_TREE_FUNCTION_DEFS(MYSTRUCT, MyStruct); 69 * 70 * struct MYSTRUCT { 71 * GWEN_TREE_ELEMENT(MYSTRUCT); 72 * int myData; 73 * } 74 * 75 * 76 * MYSTRUCT *MyStruct_new(int myData); 77 * void MyStruct_free(MYSTRUCT *myStruct); 78 * 79 * #endif 80 * @endcode 81 * <p> 82 * This defines all necessary data and function prototypes needed for 83 * list management. 84 * </p> 85 * 86 * <p> 87 * The code file would look quite similar to the following: 88 * </p> 89 * 90 * @code 91 * 92 * / * mystruct.c * / 93 * 94 * GWEN_TREE_FUNCTIONS(MYSTRUCT, MyStruct) 95 * 96 * MYSTRUCT *MyStruct_new(int myData) { 97 * MYSTRUCT *pMyStruct; 98 * 99 * pMyStruct=(MYSTRUCT*)malloc(sizeof(MYSTRUCT)); 100 * memset(pMyStruct, 0, sizeof(MYSTRUCT)); 101 * 102 * GWEN_TREE_INIT(MYSTRUCT, pMyStruct) 103 * 104 * pMyStruct->myData=myData; 105 * return pMyStruct; 106 * } 107 * 108 * void MyStruct_free(MYSTRUCT *pMyStruct) { 109 * if (pMyStruct) { 110 * pMyStruct->myData=0; 111 * 112 * GWEN_TREE_FINI(MYSTRUCT, pMyStruct) 113 * 114 * free(pMyStruct); 115 * } 116 * } 117 * 118 * @endcode 119 * Please note the three macros used in the code file: 120 * <ul> 121 * <li>@ref GWEN_TREE_FUNCTIONS creates the functions for the list 122 * management</li> 123 * <li>@ref GWEN_TREE_INIT initializes the list data inside your 124 * struct to defined values </li> 125 * <li>@ref GWEN_TREE_FINI frees all ressources occupied by the list 126 * management code. Please note that this macro should be the last 127 * statement inside the destructor function before @b free()</li> 128 * </ul> 129 * 130 * <p>Note: When writing these macro code lines, the original ISO 131 * C89 standard for the C language does not allow terminating the 132 * macro statement with a semicolon ';'. Any recent compiler will 133 * probably silently ignore such an extra ';', but you should be 134 * aware that this can cause problems once one of your users tries 135 * to compile this with a different compiler. Therefore these code 136 * lines should end directly with the closing parentheses.</p> 137 * 138 * <p> 139 * The list management code assumes that there is a function called 140 * (in this example) @b MyStruct_free() (or generally: TYPEPREFIX_free). 141 * This is used when destroying a list of MYSTRUCT elements. In this case 142 * all elements still enlisted are destroyed upon destruction of the list. 143 * </p> 144 */ 145 /*@{*/ 146 147 148 /** @name Internal Functions 149 * 150 * All functions and structs within this group should be considered 151 * internal. They just implement the functionality behind the typesafe list 152 * macros (see @ref GWEN_TREE_FUNCTION_LIB_DEFS and following). 153 */ 154 /*@{*/ 155 typedef struct GWEN_TREE GWEN_TREE; 156 typedef struct GWEN_TREE_ELEMENT GWEN_TREE_ELEMENT; 157 158 159 /** Allocate (create) a new empty list. */ 160 GWENHYWFAR_API 161 GWEN_TREE *GWEN_Tree_new(void); 162 163 /** Free (delete) an existing list. The list elements are 164 * untouched by this function; they need to be freed 165 * beforehand. */ 166 GWENHYWFAR_API 167 void GWEN_Tree_free(GWEN_TREE *l); 168 169 /** Returns the number of elements in this list. This value is 170 * cached in the list structure, so this function is a cheap 171 * function. */ 172 GWENHYWFAR_API 173 int GWEN_Tree_GetCount(const GWEN_TREE *l); 174 175 /** Adds (appends) a toplevel tree element. (This 176 * operation is also called "append" or "push_back" elsewhere.) */ 177 GWENHYWFAR_API 178 void GWEN_Tree_Add(GWEN_TREE *l, GWEN_TREE_ELEMENT *el); 179 180 /** Inserts (prepends) a toplevel tree element at the beginning of the 181 * list. (This operation is also called "prepend" or "push_front" 182 * elsewhere.) */ 183 GWENHYWFAR_API 184 void GWEN_Tree_Insert(GWEN_TREE *l, GWEN_TREE_ELEMENT *el); 185 186 /** Deletes (removes) a tree element from the tree it used to 187 * belong to. The tree element is not free'd or anything, it is 188 * only removed from the list it used to belong to. (This 189 * operation is also called "remove" or "unlink" elsewhere.) */ 190 GWENHYWFAR_API 191 void GWEN_Tree_Del(GWEN_TREE_ELEMENT *el); 192 193 194 /** Replaces a tree element with another one, so the replacement takes the place of the given element. 195 * The given element to replace is unlinked in the process and can be free'd. 196 * The replacement MUST NOT be part of any tree. 197 */ 198 GWENHYWFAR_API 199 void GWEN_Tree_Replace(GWEN_TREE_ELEMENT *elToReplace, GWEN_TREE_ELEMENT *elReplacement); 200 201 /** Adds (appends) the second list to the end of the first 202 * list. (This operation is also called "append" or "concatenate" 203 * elsewhere.) 204 * The second list will be empty upon return. 205 */ 206 GWENHYWFAR_API 207 void GWEN_Tree_AddList(GWEN_TREE *dest, GWEN_TREE *l); 208 209 /** Add a child below the given element. */ 210 GWENHYWFAR_API 211 void GWEN_Tree_AddChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el); 212 213 /** Insert a child below the given element. */ 214 GWENHYWFAR_API 215 void GWEN_Tree_InsertChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el); 216 217 218 /** Returns the data pointer of the first list element. */ 219 GWENHYWFAR_API 220 void *GWEN_Tree_GetFirst(const GWEN_TREE *l); 221 222 /** Returns the data pointer of the last list element. */ 223 GWENHYWFAR_API 224 void *GWEN_Tree_GetLast(const GWEN_TREE *l); 225 226 227 228 /** Allocate (create) a new list element structure. */ 229 GWENHYWFAR_API 230 GWEN_TREE_ELEMENT *GWEN_TreeElement_new(void *d); 231 232 /** Free (delete) a list element structure. */ 233 GWENHYWFAR_API 234 void GWEN_TreeElement_free(GWEN_TREE_ELEMENT *el); 235 236 /** Returns the data pointer of the list element that is the 237 * previous (predecessor) to the given one in its list. If there 238 * is no such prepending list element, returns NULL. */ 239 GWENHYWFAR_API 240 void *GWEN_TreeElement_GetPrevious(const GWEN_TREE_ELEMENT *el); 241 242 /** Returns the data pointer of the list element that is the next 243 * one (successor) to the given one in its list. If there is no 244 * such prepending list element, returns NULL. */ 245 GWENHYWFAR_API 246 void *GWEN_TreeElement_GetNext(const GWEN_TREE_ELEMENT *el); 247 248 /** Returns the element which is logically below the given one. 249 * The order of search is this: 250 * <ul> 251 * <li>first child of the given element </li> 252 * <li>next neighbour of the given element </li> 253 * <li>loop for every parent: check next neighbour of the given element's parent (if any) </li> 254 * </ul> 255 */ 256 GWENHYWFAR_API 257 void *GWEN_TreeElement_GetBelow(const GWEN_TREE_ELEMENT *el); 258 259 /** Returns the first child of the given element. */ 260 GWENHYWFAR_API 261 void *GWEN_TreeElement_GetFirstChild(const GWEN_TREE_ELEMENT *el); 262 263 /** Returns the last child of the given element. */ 264 GWENHYWFAR_API 265 void *GWEN_TreeElement_GetLastChild(const GWEN_TREE_ELEMENT *el); 266 267 GWENHYWFAR_API 268 void *GWEN_TreeElement_GetParent(const GWEN_TREE_ELEMENT *el); 269 270 /** Returns the number of children of the given element */ 271 GWENHYWFAR_API 272 uint32_t GWEN_TreeElement_GetChildrenCount(const GWEN_TREE_ELEMENT *el); 273 274 /*@}*/ 275 276 277 /** @name Typesafe Macros 278 * 279 */ 280 /*@{*/ 281 282 /** 283 * Use this inside the declaration of a struct for which you want to create 284 * lists. 285 */ 286 #define GWEN_TREE_ELEMENT(t) \ 287 GWEN_TREE_ELEMENT *_tree_element; 288 289 /** 290 * Use this macro in your public header files to export only list functions 291 * which do not modify a list. This allows your code to return lists which can 292 * not be modified by callers. It also prevents callers from creating their 293 * own lists (this is sometimes needed). 294 */ 295 #define GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, decl) \ 296 typedef GWEN_TREE t##_TREE; \ 297 \ 298 decl t* pr##_Tree_GetFirst(const t##_TREE *l); \ 299 decl t* pr##_Tree_GetLast(const t##_TREE *l); \ 300 decl t* pr##_Tree_GetNext(const t *element); \ 301 decl t* pr##_Tree_GetPrevious(const t *element); \ 302 decl t* pr##_Tree_GetBelow(const t *element); \ 303 decl uint32_t pr##_Tree_GetCount(const t##_TREE *l); \ 304 decl int pr##_Tree_HasElement(const t##_TREE *l, const t *element); \ 305 decl t* pr##_Tree_GetFirstChild(const t *element); \ 306 decl t* pr##_Tree_GetLastChild(const t *element); \ 307 decl uint32_t pr##_Tree_GetChildrenCount(const t *element); \ 308 decl t* pr##_Tree_GetParent(const t *element); 309 310 311 #define GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, decl) \ 312 typedef GWEN_TREE_ELEMENT t##_TREE_ELEMENT; \ 313 \ 314 decl void pr##_Tree_Clear(t##_TREE *l); \ 315 decl t##_TREE* pr##_Tree_new(); \ 316 decl void pr##_Tree_free(t##_TREE *l); \ 317 decl void pr##_Tree_AddList(t##_TREE *dst, t##_TREE *l); \ 318 decl void pr##_Tree_Add(t##_TREE *list, t *element); \ 319 decl void pr##_Tree_Insert(t##_TREE *list, t *element); \ 320 decl void pr##_Tree_Del(t *element); \ 321 decl void pr##_Tree_Replace(t *elToReplace, t *elReplacement); \ 322 \ 323 decl void pr##_Tree_AddChild(t *where, t *element); \ 324 decl void pr##_Tree_InsertChild(t *where, t *element); \ 325 \ 326 decl int pr##_Tree_HasChildElement(const t *who, const t *element); \ 327 decl void pr##_Tree_ClearChildren(t *element); \ 328 329 330 #define GWEN_TREE_FUNCTION_DEFS_CONST(t, pr) \ 331 GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, GWEN_DUMMY_EMPTY_ARG) 332 333 #define GWEN_TREE_FUNCTION_DEFS_NOCONST(t, pr) \ 334 GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, GWEN_DUMMY_EMPTY_ARG) 335 336 337 /** 338 * Use this in public header files to define some prototypes for list 339 * functions. 340 * Let's assume the type of your list elements is "MYTYPE" and you want to 341 * use the prefix "MyType_" for the list functions. 342 * The following function prototypes will then be created: 343 * <ul> 344 * <li> 345 * void MyType_Tree_Add(MYTYPE *element, MYTYPE_TREE *list);<br> 346 * Adds (appends) a MYTYPE struct at the end of the given 347 * list. (We apologize for the unusual argument order here.) 348 * </li> 349 * <li> 350 * void MyType_Tree_Del(MYTYPE *element);<br> 351 * Removes a MyType struct from the list it is enlisted to. 352 * </li> 353 * <li> 354 * MYTYPE *MyType_Tree_First(MYTYPE *element); <br> 355 * Returns the first element of the given list. 356 * </li> 357 * <li> 358 * MYTYPE* MyType_Tree_Next(const MYTYPE *element);<br> 359 * Returns the next list element to the given one (the 360 * successor) in its list. 361 * </li> 362 * <li> 363 * MYTYPE* MyType_Tree_Previous(const MYTYPE *element);<br> 364 * Returns the previous list element to the given one (the 365 * predecessor) in its list. 366 * </li> 367 * <li> 368 * void MyType_Tree_Clear(MYTYPE *element); <br> 369 * Frees all entries of the given list. 370 * This function assumes that there is a function Mytype_free(). 371 * </li> 372 * <li> 373 * MYTYPE_TREE *MyType_Tree_new(); <br> 374 * Creates a new list of elements of MYTYPE type. 375 * </li> 376 * <li> 377 * void MyType_Tree_free(MYTYPE_TREE *l); <br> 378 * Clears and frees a list of elements of MYTYPE type. 379 * All objects inside the list are freed. 380 * </li> 381 * </ul> 382 * 383 */ 384 #define GWEN_TREE_FUNCTION_LIB_DEFS(t, pr, decl) \ 385 GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, decl) \ 386 GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, decl) 387 388 389 /** 390 * This macro should be used in applications, not in libraries. In 391 * libraries please use the macro @ref GWEN_TREE_FUNCTION_LIB_DEFS. 392 */ 393 #define GWEN_TREE_FUNCTION_DEFS(t, pr) \ 394 GWEN_TREE_FUNCTION_LIB_DEFS(t, pr, GWEN_DUMMY_EMPTY_ARG) 395 396 397 /** 398 * Use this inside your code files (*.c). 399 * Actually implements the functions for which the prototypes have been 400 * defined via @ref GWEN_TREE_FUNCTION_DEFS. 401 */ 402 #define GWEN_TREE_FUNCTIONS(t, pr) \ 403 \ 404 void pr##_Tree_Add(t##_TREE *l, t *element) { \ 405 assert(element); \ 406 assert(element->_tree_element);\ 407 GWEN_Tree_Add(l, element->_tree_element); \ 408 } \ 409 \ 410 void pr##_Tree_AddList(t##_TREE *dst, t##_TREE *l) { \ 411 GWEN_Tree_AddList(dst, l); \ 412 } \ 413 \ 414 void pr##_Tree_Insert(t##_TREE *l, t *element) { \ 415 assert(element); \ 416 assert(element->_tree_element);\ 417 GWEN_Tree_Insert(l, element->_tree_element); \ 418 } \ 419 \ 420 void pr##_Tree_Del(t *element){ \ 421 assert(element); \ 422 assert(element->_tree_element);\ 423 GWEN_Tree_Del(element->_tree_element); \ 424 }\ 425 \ 426 void pr##_Tree_Replace(t *elToReplace, t *elReplacement) { \ 427 assert(elToReplace); \ 428 assert(elToReplace->_tree_element);\ 429 assert(elReplacement); \ 430 assert(elReplacement->_tree_element);\ 431 GWEN_Tree_Replace(elToReplace->_tree_element, elReplacement->_tree_element); \ 432 } \ 433 \ 434 t* pr##_Tree_GetFirst(const t##_TREE *l) { \ 435 if (l) return (t*)GWEN_Tree_GetFirst(l);\ 436 else return 0; \ 437 } \ 438 \ 439 t* pr##_Tree_GetLast(const t##_TREE *l) { \ 440 if (l) return (t*) GWEN_Tree_GetLast(l);\ 441 else return 0; \ 442 } \ 443 \ 444 void pr##_Tree_Clear(t##_TREE *l) { \ 445 t* el; \ 446 while( (el=GWEN_Tree_GetFirst(l)) ) {\ 447 pr##_Tree_Del(el);\ 448 pr##_Tree_ClearChildren(el); \ 449 pr##_free(el);\ 450 } /* while */ \ 451 } \ 452 \ 453 int pr##_Tree_HasElement(const t##_TREE *l, const t *element) { \ 454 const t* el; \ 455 el=(t*)GWEN_Tree_GetFirst(l); \ 456 while(el) {\ 457 if (el==element) \ 458 return 1; \ 459 el=(const t*)GWEN_TreeElement_GetBelow(el->_tree_element); \ 460 } /* while */ \ 461 return 0; \ 462 } \ 463 \ 464 t##_TREE* pr##_Tree_new(){\ 465 return (t##_TREE*)GWEN_Tree_new(); \ 466 }\ 467 \ 468 void pr##_Tree_free(t##_TREE *l) {\ 469 if (l) { \ 470 pr##_Tree_Clear(l);\ 471 GWEN_Tree_free(l); \ 472 }\ 473 } \ 474 \ 475 t* pr##_Tree_GetNext(const t *element) { \ 476 assert(element); \ 477 assert(element->_tree_element);\ 478 return (t*)GWEN_TreeElement_GetNext(element->_tree_element);\ 479 } \ 480 \ 481 t* pr##_Tree_GetPrevious(const t *element) { \ 482 assert(element); \ 483 assert(element->_tree_element);\ 484 return (t*)GWEN_TreeElement_GetPrevious(element->_tree_element);\ 485 } \ 486 \ 487 t* pr##_Tree_GetBelow(const t *element) { \ 488 assert(element); \ 489 assert(element->_tree_element);\ 490 return (t*)GWEN_TreeElement_GetBelow(element->_tree_element);\ 491 } \ 492 \ 493 uint32_t pr##_Tree_GetCount(const t##_TREE *l){\ 494 return GWEN_Tree_GetCount(l);\ 495 } \ 496 \ 497 int pr##_Tree_HasChildElement(const t *who, const t *element) { \ 498 const t* el; \ 499 el=(const t*)GWEN_TreeElement_GetFirstChild(who->_tree_element); \ 500 while(el) {\ 501 if (el==element) \ 502 return 1; \ 503 el=(const t*)GWEN_TreeElement_GetNext(el->_tree_element); \ 504 } /* while */ \ 505 return 0; \ 506 } \ 507 \ 508 void pr##_Tree_AddChild(t *where, t *element) { \ 509 assert(where); \ 510 assert(where->_tree_element);\ 511 assert(element); \ 512 assert(element->_tree_element);\ 513 GWEN_Tree_AddChild(where->_tree_element, element->_tree_element); \ 514 } \ 515 \ 516 void pr##_Tree_InsertChild(t *where, t *element) { \ 517 assert(where); \ 518 assert(where->_tree_element);\ 519 assert(element); \ 520 assert(element->_tree_element);\ 521 GWEN_Tree_InsertChild(where->_tree_element, element->_tree_element); \ 522 } \ 523 \ 524 void pr##_Tree_ClearChildren(t *element) { \ 525 t* c; \ 526 while( (c=GWEN_TreeElement_GetFirstChild(element->_tree_element)) ) {\ 527 pr##_Tree_ClearChildren(c);\ 528 pr##_Tree_Del(c);\ 529 pr##_free(c);\ 530 } /* while */ \ 531 } \ 532 \ 533 t* pr##_Tree_GetFirstChild(const t *element) { \ 534 assert(element); \ 535 assert(element->_tree_element);\ 536 return (t*)GWEN_TreeElement_GetFirstChild(element->_tree_element);\ 537 } \ 538 \ 539 t* pr##_Tree_GetLastChild(const t *element) { \ 540 assert(element); \ 541 assert(element->_tree_element);\ 542 return (t*)GWEN_TreeElement_GetLastChild(element->_tree_element);\ 543 } \ 544 \ 545 uint32_t pr##_Tree_GetChildrenCount(const t *element){\ 546 return GWEN_TreeElement_GetChildrenCount(element->_tree_element);\ 547 } \ 548 \ 549 t* pr##_Tree_GetParent(const t *element) { \ 550 assert(element); \ 551 assert(element->_tree_element);\ 552 return (t*)GWEN_TreeElement_GetParent(element->_tree_element);\ 553 } \ 554 \ 555 556 557 /** 558 * Use this in your code file (*.c) inside the init code for the struct 559 * you want to use in lists (in GWEN these are the functions which end with 560 * "_new". 561 */ 562 #define GWEN_TREE_INIT(t, element) \ 563 element->_tree_element=GWEN_TreeElement_new(element); 564 565 566 /** 567 * Use this in your code file (*.c) inside the fini code for the struct 568 * you want to use in lists (in GWEN these are the functions which end with 569 * "_free". 570 */ 571 #define GWEN_TREE_FINI(t, element) \ 572 if (element && element->_tree_element) { \ 573 GWEN_TreeElement_free(element->_tree_element); \ 574 element->_tree_element=0; \ 575 } 576 577 /*@}*/ 578 579 /*@}*/ /* defgroup */ 580 581 582 #ifdef __cplusplus 583 } 584 #endif 585 586 587 #endif 588 589 590