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