Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifdef HAVE_CONFIG_H
00027 # include <config.h>
00028 #endif
00029
00030 #define DISABLE_DEBUGLOG
00031
00032 #include "tree_p.h"
00033 #include <gwenhywfar/misc.h>
00034 #include <gwenhywfar/debug.h>
00035
00036
00037
00038
00039 GWEN_TREE *GWEN_Tree_new(void) {
00040 GWEN_TREE *l;
00041
00042 GWEN_NEW_OBJECT(GWEN_TREE, l);
00043 return l;
00044 }
00045
00046
00047 void GWEN_Tree_free(GWEN_TREE *l) {
00048 if (l) {
00049 GWEN_FREE_OBJECT(l);
00050 }
00051 }
00052
00053
00054
00055 int GWEN_Tree_GetCount(const GWEN_TREE *l) {
00056 assert(l);
00057 return l->count;
00058 }
00059
00060
00061
00062 void GWEN_Tree_Add(GWEN_TREE *l, GWEN_TREE_ELEMENT *el) {
00063 assert(l);
00064 assert(el);
00065 if (el->treePtr) {
00066
00067 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00068 assert(0);
00069 }
00070 else {
00071 if (l->firstElement==0)
00072 l->firstElement=el;
00073
00074 el->prevElement=l->lastElement;
00075 if (l->lastElement)
00076 l->lastElement->nextElement=el;
00077 l->lastElement=el;
00078
00079 el->treePtr=l;
00080 el->parent=NULL;
00081 l->count++;
00082 }
00083 }
00084
00085
00086
00087 void GWEN_Tree_AddList(GWEN_TREE *dest, GWEN_TREE *l) {
00088 GWEN_TREE_ELEMENT *el;
00089
00090 assert(dest);
00091 assert(l);
00092
00093 while((el=l->firstElement)) {
00094 GWEN_Tree_Del(el);
00095 GWEN_Tree_Add(dest, el);
00096 }
00097 }
00098
00099
00100
00101 void GWEN_Tree_Insert(GWEN_TREE *l, GWEN_TREE_ELEMENT *el) {
00102 assert(l);
00103 assert(el);
00104 if (el->treePtr) {
00105
00106 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00107 }
00108 else {
00109 el->nextElement=l->firstElement;
00110 l->firstElement=el;
00111
00112 if (l->lastElement==0)
00113 l->lastElement=el;
00114
00115 el->treePtr=l;
00116 el->parent=NULL;
00117 l->count++;
00118 }
00119 }
00120
00121
00122
00123 void GWEN_Tree_Del(GWEN_TREE_ELEMENT *el) {
00124 GWEN_TREE *l;
00125
00126 l=el->treePtr;
00127
00128 if (l==0) {
00129
00130 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
00131 }
00132 else {
00133
00134 if (el->prevElement)
00135 el->prevElement->nextElement=el->nextElement;
00136
00137
00138 if (el->nextElement)
00139 el->nextElement->prevElement=el->prevElement;
00140
00141
00142 if (l->firstElement==el)
00143 l->firstElement=el->nextElement;
00144 if (l->lastElement==el)
00145 l->lastElement=el->prevElement;
00146 l->count--;
00147
00148
00149 if (el->parent) {
00150 if (el->parent->firstChild==el)
00151 el->parent->firstChild=el->nextElement;
00152 if (el->parent->lastChild==el)
00153 el->parent->lastChild=el->prevElement;
00154 el->parent->count--;
00155 }
00156
00157 el->nextElement=NULL;
00158 el->prevElement=NULL;
00159 el->parent=NULL;
00160 el->treePtr=NULL;
00161 }
00162 }
00163
00164
00165
00166 void GWEN_Tree_AddChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el) {
00167 if (el->treePtr) {
00168
00169 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
00170 assert(0);
00171 }
00172 else {
00173 if (where->firstChild==0)
00174 where->firstChild=el;
00175
00176 el->prevElement=where->lastChild;
00177 if (where->lastChild)
00178 where->lastChild->nextElement=el;
00179 where->lastChild=el;
00180
00181 el->parent=where;
00182
00183 el->treePtr=where->treePtr;
00184 el->treePtr->count++;
00185 where->count++;
00186 }
00187 }
00188
00189
00190
00191 void GWEN_Tree_InsertChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el) {
00192 if (el->treePtr) {
00193
00194 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
00195 assert(0);
00196 }
00197 else {
00198 el->nextElement=where->firstChild;
00199 where->firstChild=el;
00200
00201 if (where->lastChild==NULL)
00202 where->lastChild=el;
00203
00204 el->parent=where;
00205
00206 el->treePtr=where->treePtr;
00207 el->treePtr->count++;
00208 where->count++;
00209 }
00210 }
00211
00212
00213
00214 void *GWEN_Tree_GetFirst(const GWEN_TREE *l) {
00215 if (l->firstElement)
00216 return l->firstElement->data;
00217 return 0;
00218 }
00219
00220
00221
00222 void *GWEN_Tree_GetLast(const GWEN_TREE *l) {
00223 if (l->lastElement)
00224 return l->lastElement->data;
00225 return 0;
00226 }
00227
00228
00229
00230
00231
00232 GWEN_TREE_ELEMENT *GWEN_TreeElement_new(void *d) {
00233 GWEN_TREE_ELEMENT *el;
00234
00235 GWEN_NEW_OBJECT(GWEN_TREE_ELEMENT, el);
00236 el->data=d;
00237
00238 return el;
00239 }
00240
00241
00242
00243 void GWEN_TreeElement_free(GWEN_TREE_ELEMENT *el) {
00244 if (el) {
00245 if (el->treePtr)
00246 GWEN_Tree_Del(el);
00247 if (el->firstChild) {
00248 DBG_ERROR(GWEN_LOGDOMAIN, "Tree element still has children");
00249 assert(0);
00250 }
00251 GWEN_FREE_OBJECT(el);
00252 }
00253 }
00254
00255
00256
00257 void *GWEN_TreeElement_GetPrevious(const GWEN_TREE_ELEMENT *el){
00258 if (el->prevElement)
00259 return el->prevElement->data;
00260 return 0;
00261 }
00262
00263
00264
00265 void *GWEN_TreeElement_GetNext(const GWEN_TREE_ELEMENT *el){
00266 if (el->nextElement)
00267 return el->nextElement->data;
00268 return 0;
00269 }
00270
00271
00272
00273 void *GWEN_TreeElement_GetBelow(const GWEN_TREE_ELEMENT *el) {
00274 if (el->firstChild)
00275 return el->firstChild->data;
00276 else if (el->nextElement)
00277 return el->nextElement->data;
00278 else {
00279
00280 while(el && el->parent) {
00281 if (el->parent->nextElement)
00282 return el->parent->nextElement->data;
00283
00284 el=el->parent;
00285 }
00286 }
00287
00288 return NULL;
00289 }
00290
00291
00292
00293 void *GWEN_TreeElement_GetFirstChild(const GWEN_TREE_ELEMENT *el){
00294 if (el->firstChild)
00295 return el->firstChild->data;
00296 return NULL;
00297 }
00298
00299
00300
00301 void *GWEN_TreeElement_GetLastChild(const GWEN_TREE_ELEMENT *el){
00302 if (el->lastChild)
00303 return el->lastChild->data;
00304 return NULL;
00305 }
00306
00307
00308
00309 void *GWEN_TreeElement_GetParent(const GWEN_TREE_ELEMENT *el) {
00310 if (el->parent)
00311 return el->parent->data;
00312 return NULL;
00313 }
00314
00315
00316
00317 uint32_t GWEN_TreeElement_GetChildrenCount(const GWEN_TREE_ELEMENT *el){
00318 assert(el);
00319 return el->count;
00320 }
00321
00322
00323
00324
00325
00326
00327
00328