gwenhywfar 4.0.3
|
00001 /*************************************************************************** 00002 begin : Fri Jan 02 2009 00003 copyright : (C) 2009 by Martin Preuss 00004 email : martin@libchipcard.de 00005 00006 *************************************************************************** 00007 * * 00008 * This library is free software; you can redistribute it and/or * 00009 * modify it under the terms of the GNU Lesser General Public * 00010 * License as published by the Free Software Foundation; either * 00011 * version 2.1 of the License, or (at your option) any later version. * 00012 * * 00013 * This library is distributed in the hope that it will be useful, * 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 00016 * Lesser General Public License for more details. * 00017 * * 00018 * You should have received a copy of the GNU Lesser General Public * 00019 * License along with this library; if not, write to the Free Software * 00020 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, * 00021 * MA 02111-1307 USA * 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() { 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 /* element is already part of another list */ 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 /* element is already part of another list */ 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 /* not part of any list */ 00130 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list"); 00131 } 00132 else { 00133 /* unlink from previous */ 00134 if (el->prevElement) 00135 el->prevElement->nextElement=el->nextElement; 00136 00137 /* unlink from next */ 00138 if (el->nextElement) 00139 el->nextElement->prevElement=el->prevElement; 00140 00141 /* unlink from list */ 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 /* unlink from parent */ 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 /* element is already part of another tree */ 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 /* element is already part of another list */ 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) /* look down */ 00275 return el->firstChild->data; 00276 else if (el->nextElement) /* look right */ 00277 return el->nextElement->data; 00278 else { 00279 /* look for a parent which has a right neighbour */ 00280 while(el && el->parent) { 00281 if (el->parent->nextElement) /* look right of parent */ 00282 return el->parent->nextElement->data; 00283 /* parent has no right neighbour, consult its parent */ 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