tree.c

Go to the documentation of this file.
00001 /* LIBDGL -- a Directed Graph Library implementation
00002  * Copyright (C) 2002 Roberto Micarelli
00003  *
00004  * This program is free software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 2 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00017  */
00018 
00019 /* best view tabstop=4
00020  */
00021 #include <stdio.h>
00022 #include <string.h>
00023 #include <stdlib.h>
00024 
00025 #include "type.h"
00026 #include "tree.h"
00027 
00028 /*
00029  * AVL Support for data type dglTreeNode_s
00030  * alloc
00031  * cancel
00032  * compare
00033  * add
00034  */
00035 dglTreeNode_s *dglTreeNodeAlloc()
00036 {
00037     dglTreeNode_s *pNode = (dglTreeNode_s *) malloc(sizeof(dglTreeNode_s));
00038 
00039     if (pNode)
00040         memset(pNode, 0, sizeof(dglTreeNode_s));
00041     return pNode;
00042 }
00043 
00044 void dglTreeNodeCancel(void *pvNode, void *pvParam)
00045 {
00046     if (((dglTreeNode_s *) pvNode)->pv)
00047         free(((dglTreeNode_s *) pvNode)->pv);
00048     if (((dglTreeNode_s *) pvNode)->pv2)
00049         free(((dglTreeNode_s *) pvNode)->pv2);
00050     free(pvNode);
00051 }
00052 
00053 int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB,
00054                        void *pvParam)
00055 {
00056     if (((dglTreeNode_s *) pvNodeA)->nKey < ((dglTreeNode_s *) pvNodeB)->nKey)
00057         return -1;
00058     else if (((dglTreeNode_s *) pvNodeA)->nKey >
00059              ((dglTreeNode_s *) pvNodeB)->nKey)
00060         return 1;
00061     else
00062         return 0;
00063 }
00064 
00065 dglTreeNode_s *dglTreeNodeAdd(void *pavl, dglInt32_t nKey)
00066 {
00067     dglTreeNode_s *pnode;
00068     void **ppvret;
00069 
00070     if ((pnode = dglTreeNodeAlloc()) == NULL)
00071         return NULL;
00072     pnode->nKey = nKey;
00073     ppvret = avl_probe(pavl, pnode);
00074     if (*ppvret != pnode) {
00075         free(pnode);
00076         pnode = *ppvret;
00077     }
00078     return pnode;
00079 }
00080 
00081 
00082 /*
00083  * AVL Support for data type dglTreeNode2_s
00084  * alloc
00085  * cancel
00086  * compare
00087  * add
00088  */
00089 dglTreeNode2_s *dglTreeNode2Alloc()
00090 {
00091     dglTreeNode2_s *pNode2 =
00092         (dglTreeNode2_s *) malloc(sizeof(dglTreeNode2_s));
00093     if (pNode2)
00094         memset(pNode2, 0, sizeof(dglTreeNode2_s));
00095     return pNode2;
00096 }
00097 
00098 void dglTreeNode2Cancel(void *pvNode2, void *pvParam)
00099 {
00100     if (((dglTreeNode2_s *) pvNode2)->pv)
00101         free(((dglTreeNode2_s *) pvNode2)->pv);
00102     if (((dglTreeNode2_s *) pvNode2)->pv2)
00103         free(((dglTreeNode2_s *) pvNode2)->pv2);
00104     if (((dglTreeNode2_s *) pvNode2)->pv3)
00105         free(((dglTreeNode2_s *) pvNode2)->pv3);
00106     free(pvNode2);
00107 }
00108 
00109 int dglTreeNode2Compare(const void *pvNode2A, const void *pvNode2B,
00110                         void *pvParam)
00111 {
00112     if (((dglTreeNode2_s *) pvNode2A)->nKey <
00113         ((dglTreeNode2_s *) pvNode2B)->nKey)
00114         return -1;
00115     else if (((dglTreeNode2_s *) pvNode2A)->nKey >
00116              ((dglTreeNode2_s *) pvNode2B)->nKey)
00117         return 1;
00118     else
00119         return 0;
00120 }
00121 
00122 dglTreeNode2_s *dglTreeNode2Add(void *pavl, dglInt32_t nKey)
00123 {
00124     dglTreeNode2_s *pnode;
00125     void **ppvret;
00126 
00127     if ((pnode = dglTreeNode2Alloc()) == NULL)
00128         return NULL;
00129     pnode->nKey = nKey;
00130     ppvret = avl_probe(pavl, pnode);
00131     if (*ppvret != pnode) {
00132         free(pnode);
00133         pnode = *ppvret;
00134     }
00135     return pnode;
00136 }
00137 
00138 
00139 /*
00140  * AVL Support for data type dglTreeEdge_s
00141  * alloc
00142  * cancel
00143  * compare
00144  * add
00145  */
00146 dglTreeEdge_s *dglTreeEdgeAlloc()
00147 {
00148     dglTreeEdge_s *pEdge = (dglTreeEdge_s *) malloc(sizeof(dglTreeEdge_s));
00149 
00150     if (pEdge)
00151         memset(pEdge, 0, sizeof(dglTreeEdge_s));
00152     return pEdge;
00153 }
00154 
00155 void dglTreeEdgeCancel(void *pvEdge, void *pvParam)
00156 {
00157     if (((dglTreeEdge_s *) pvEdge)->pv)
00158         free(((dglTreeEdge_s *) pvEdge)->pv);
00159     free(pvEdge);
00160 }
00161 
00162 int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB,
00163                        void *pvParam)
00164 {
00165     if (((dglTreeEdge_s *) pvEdgeA)->nKey < ((dglTreeEdge_s *) pvEdgeB)->nKey)
00166         return -1;
00167     else if (((dglTreeEdge_s *) pvEdgeA)->nKey >
00168              ((dglTreeEdge_s *) pvEdgeB)->nKey)
00169         return 1;
00170     else
00171         return 0;
00172 }
00173 
00174 dglTreeEdge_s *dglTreeEdgeAdd(void *pavl, dglInt32_t nKey)
00175 {
00176     dglTreeEdge_s *pedge;
00177     void **ppvret;
00178 
00179     if ((pedge = dglTreeEdgeAlloc()) == NULL)
00180         return NULL;
00181     pedge->nKey = nKey;
00182     ppvret = avl_probe(pavl, pedge);
00183     if (*ppvret != pedge) {
00184         free(pedge);
00185         pedge = *ppvret;
00186     }
00187     return pedge;
00188 }
00189 
00190 
00191 
00192 /*
00193  * AVL Support for data type dglTreeTouchI32_s
00194  * alloc
00195  * cancel
00196  * compare
00197  * add
00198  */
00199 dglTreeTouchI32_s *dglTreeTouchI32Alloc()
00200 {
00201     dglTreeTouchI32_s *pTouchI32 =
00202         (dglTreeTouchI32_s *) malloc(sizeof(dglTreeTouchI32_s));
00203     pTouchI32->nKey = 0;
00204     return pTouchI32;
00205 }
00206 
00207 void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam)
00208 {
00209     free(pvTouchI32);
00210 }
00211 
00212 int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B,
00213                            void *pvParam)
00214 {
00215     if (((dglTreeTouchI32_s *) pvTouchI32A)->nKey <
00216         ((dglTreeTouchI32_s *) pvTouchI32B)->nKey)
00217         return -1;
00218     else if (((dglTreeTouchI32_s *) pvTouchI32A)->nKey >
00219              ((dglTreeTouchI32_s *) pvTouchI32B)->nKey)
00220         return 1;
00221     else
00222         return 0;
00223 }
00224 
00225 dglTreeTouchI32_s *dglTreeTouchI32Add(void *pavl, dglInt32_t nKey)
00226 {
00227     dglTreeTouchI32_s *pnode;
00228     void **ppvret;
00229 
00230     if ((pnode = dglTreeTouchI32Alloc()) == NULL)
00231         return NULL;
00232     pnode->nKey = nKey;
00233     ppvret = avl_probe(pavl, pnode);
00234     if (*ppvret != pnode) {
00235         free(pnode);
00236         pnode = *ppvret;
00237     }
00238     return pnode;
00239 }
00240 
00241 
00242 
00243 /*
00244  * AVL Support for data type dglTreePredist_s
00245  * alloc
00246  * cancel
00247  * compare
00248  * add
00249  */
00250 dglTreePredist_s *dglTreePredistAlloc()
00251 {
00252     dglTreePredist_s *pPredist =
00253         (dglTreePredist_s *) malloc(sizeof(dglTreePredist_s));
00254     if (pPredist)
00255         memset(pPredist, 0, sizeof(dglTreePredist_s));
00256     return pPredist;
00257 }
00258 
00259 void dglTreePredistCancel(void *pvPredist, void *pvParam)
00260 {
00261     free(pvPredist);
00262 }
00263 
00264 int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB,
00265                           void *pvParam)
00266 {
00267     if (((dglTreePredist_s *) pvPredistA)->nKey <
00268         ((dglTreePredist_s *) pvPredistB)->nKey)
00269         return -1;
00270     else if (((dglTreePredist_s *) pvPredistA)->nKey >
00271              ((dglTreePredist_s *) pvPredistB)->nKey)
00272         return 1;
00273     else
00274         return 0;
00275 }
00276 
00277 dglTreePredist_s *dglTreePredistAdd(void *pavl, dglInt32_t nKey)
00278 {
00279     dglTreePredist_s *pnode;
00280     void **ppvret;
00281 
00282     if ((pnode = dglTreePredistAlloc()) == NULL)
00283         return NULL;
00284     pnode->nKey = nKey;
00285     ppvret = avl_probe(pavl, pnode);
00286     if (*ppvret != pnode) {
00287         free(pnode);
00288         pnode = *ppvret;
00289     }
00290     return pnode;
00291 }
00292 
00293 
00294 
00295 
00296 /*
00297  * AVL Support for data type dglTreeNodePri32_s
00298  * alloc
00299  * cancel
00300  * compare
00301  * add
00302  */
00303 dglTreeNodePri32_s *dglTreeNodePri32Alloc()
00304 {
00305     dglTreeNodePri32_s *pNodePri32 =
00306         (dglTreeNodePri32_s *) malloc(sizeof(dglTreeNodePri32_s));
00307     if (pNodePri32)
00308         memset(pNodePri32, 0, sizeof(dglTreeNodePri32_s));
00309     return pNodePri32;
00310 }
00311 
00312 void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam)
00313 {
00314     free(pvNodePri32);
00315 }
00316 
00317 int dglTreeNodePri32Compare(const void *pvNodePri32A,
00318                             const void *pvNodePri32B, void *pvParam)
00319 {
00320     if (((dglTreeNodePri32_s *) pvNodePri32A)->nKey <
00321         ((dglTreeNodePri32_s *) pvNodePri32B)->nKey)
00322         return -1;
00323     else if (((dglTreeNodePri32_s *) pvNodePri32A)->nKey >
00324              ((dglTreeNodePri32_s *) pvNodePri32B)->nKey)
00325         return 1;
00326     else
00327         return 0;
00328 }
00329 
00330 dglTreeNodePri32_s *dglTreeNodePri32Add(void *pavl, dglInt32_t nKey)
00331 {
00332     dglTreeNodePri32_s *pnode;
00333     void **ppvret;
00334 
00335     if ((pnode = dglTreeNodePri32Alloc()) == NULL)
00336         return NULL;
00337     pnode->nKey = nKey;
00338     ppvret = avl_probe(pavl, pnode);
00339     if (*ppvret != pnode) {
00340         free(pnode);
00341         pnode = *ppvret;
00342     }
00343     return pnode;
00344 }
00345 
00346 
00347 
00348 /*
00349  * AVL Support for data type dglTreeEdgePri32_s
00350  * alloc
00351  * cancel
00352  * compare
00353  * add
00354  */
00355 dglTreeEdgePri32_s *dglTreeEdgePri32Alloc()
00356 {
00357     dglTreeEdgePri32_s *pEdgePri32 =
00358         (dglTreeEdgePri32_s *) malloc(sizeof(dglTreeEdgePri32_s));
00359     if (pEdgePri32)
00360         memset(pEdgePri32, 0, sizeof(dglTreeEdgePri32_s));
00361     return pEdgePri32;
00362 }
00363 
00364 void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam)
00365 {
00366     if (((dglTreeEdgePri32_s *) pvEdgePri32)->pnData) {
00367         free(((dglTreeEdgePri32_s *) pvEdgePri32)->pnData);
00368     }
00369     free(pvEdgePri32);
00370 }
00371 
00372 int dglTreeEdgePri32Compare(const void *pvEdgePri32A,
00373                             const void *pvEdgePri32B, void *pvParam)
00374 {
00375     if (((dglTreeEdgePri32_s *) pvEdgePri32A)->nKey <
00376         ((dglTreeEdgePri32_s *) pvEdgePri32B)->nKey)
00377         return -1;
00378     else if (((dglTreeEdgePri32_s *) pvEdgePri32A)->nKey >
00379              ((dglTreeEdgePri32_s *) pvEdgePri32B)->nKey)
00380         return 1;
00381     else
00382         return 0;
00383 }
00384 
00385 dglTreeEdgePri32_s *dglTreeEdgePri32Add(void *pavl, dglInt32_t nKey)
00386 {
00387     dglTreeEdgePri32_s *pnode;
00388     void **ppvret;
00389 
00390     if ((pnode = dglTreeEdgePri32Alloc()) == NULL)
00391         return NULL;
00392     pnode->nKey = nKey;
00393     ppvret = avl_probe(pavl, pnode);
00394     if (*ppvret != pnode) {
00395         free(pnode);
00396         pnode = *ppvret;
00397     }
00398     return pnode;
00399 }
00400 
00401 
00402 
00403 
00404 /*
00405  * Our AVL allocator
00406  */
00407 static void *_tree_malloc(struct libavl_allocator *allocator,
00408                           size_t libavl_size)
00409 {
00410     return malloc(libavl_size);
00411 }
00412 
00413 static void _tree_free(struct libavl_allocator *allocator, void *libavl_block)
00414 {
00415     free(libavl_block);
00416 }
00417 
00418 static struct libavl_allocator _tree_allocator = {
00419     _tree_malloc, _tree_free
00420 };
00421 
00422 void *dglTreeGetAllocator()
00423 {
00424     return &_tree_allocator;
00425 }

Generated on Sat Oct 24 03:25:20 2009 for GRASS Programmer's Manual by  doxygen 1.6.1