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         if ( pNode ) memset( pNode, 0, sizeof(dglTreeNode_s) );
00039         return pNode;
00040 }
00041 
00042 void dglTreeNodeCancel( void * pvNode , void * pvParam )
00043 {
00044         if ( ((dglTreeNode_s *)pvNode)->pv  ) free( ((dglTreeNode_s *)pvNode)->pv  );
00045         if ( ((dglTreeNode_s *)pvNode)->pv2 ) free( ((dglTreeNode_s *)pvNode)->pv2 );
00046         free( pvNode );
00047 }
00048 
00049 int dglTreeNodeCompare( const void * pvNodeA , const void * pvNodeB , void * pvParam )
00050 {
00051         if ( ((dglTreeNode_s *)pvNodeA)->nKey < ((dglTreeNode_s *)pvNodeB)->nKey ) return -1;
00052         else if ( ((dglTreeNode_s *)pvNodeA)->nKey > ((dglTreeNode_s *)pvNodeB)->nKey ) return 1;
00053         else return 0;
00054 }
00055 
00056 dglTreeNode_s * dglTreeNodeAdd( void * pavl, dglInt32_t nKey )
00057 {
00058         dglTreeNode_s * pnode;
00059         void **ppvret;
00060         if ( (pnode = dglTreeNodeAlloc()) == NULL ) return NULL;
00061         pnode->nKey = nKey;
00062         ppvret = avl_probe( pavl , pnode );
00063         if ( *ppvret != pnode ) {
00064                 free( pnode );
00065                 pnode = *ppvret;
00066         }
00067         return pnode;
00068 }
00069 
00070 
00071 /*
00072  * AVL Support for data type dglTreeNode2_s
00073  * alloc
00074  * cancel
00075  * compare
00076  * add
00077  */
00078 dglTreeNode2_s * dglTreeNode2Alloc()
00079 {
00080         dglTreeNode2_s * pNode2 = (dglTreeNode2_s*)malloc( sizeof(dglTreeNode2_s) );
00081         if ( pNode2 ) memset( pNode2, 0, sizeof(dglTreeNode2_s) );
00082         return pNode2;
00083 }
00084 
00085 void dglTreeNode2Cancel( void * pvNode2 , void * pvParam )
00086 {
00087         if ( ((dglTreeNode2_s *)pvNode2)->pv  ) free( ((dglTreeNode2_s *)pvNode2)->pv  );
00088         if ( ((dglTreeNode2_s *)pvNode2)->pv2 ) free( ((dglTreeNode2_s *)pvNode2)->pv2 );
00089         if ( ((dglTreeNode2_s *)pvNode2)->pv3 ) free( ((dglTreeNode2_s *)pvNode2)->pv3 );
00090         free( pvNode2 );
00091 }
00092 
00093 int dglTreeNode2Compare( const void * pvNode2A , const void * pvNode2B , void * pvParam )
00094 {
00095         if ( ((dglTreeNode2_s *)pvNode2A)->nKey < ((dglTreeNode2_s *)pvNode2B)->nKey ) return -1;
00096         else if ( ((dglTreeNode2_s *)pvNode2A)->nKey > ((dglTreeNode2_s *)pvNode2B)->nKey ) return 1;
00097         else return 0;
00098 }
00099 
00100 dglTreeNode2_s * dglTreeNode2Add( void * pavl, dglInt32_t nKey )
00101 {
00102         dglTreeNode2_s * pnode;
00103         void **ppvret;
00104         if ( (pnode = dglTreeNode2Alloc()) == NULL ) return NULL;
00105         pnode->nKey = nKey;
00106         ppvret = avl_probe( pavl , pnode );
00107         if ( *ppvret != pnode ) {
00108                 free( pnode );
00109                 pnode = *ppvret;
00110         }
00111         return pnode;
00112 }
00113 
00114 
00115 /*
00116  * AVL Support for data type dglTreeEdge_s
00117  * alloc
00118  * cancel
00119  * compare
00120  * add
00121  */
00122 dglTreeEdge_s * dglTreeEdgeAlloc()
00123 {
00124         dglTreeEdge_s * pEdge = (dglTreeEdge_s*)malloc( sizeof(dglTreeEdge_s) );
00125         if ( pEdge ) memset( pEdge, 0, sizeof(dglTreeEdge_s) );
00126         return pEdge;
00127 }
00128 
00129 void dglTreeEdgeCancel( void * pvEdge , void * pvParam )
00130 {
00131         if ( ((dglTreeEdge_s *)pvEdge)->pv  ) free( ((dglTreeEdge_s *)pvEdge)->pv  );
00132         free( pvEdge );
00133 }
00134 
00135 int dglTreeEdgeCompare( const void * pvEdgeA , const void * pvEdgeB , void * pvParam )
00136 {
00137         if ( ((dglTreeEdge_s *)pvEdgeA)->nKey < ((dglTreeEdge_s *)pvEdgeB)->nKey ) return -1;
00138         else if ( ((dglTreeEdge_s *)pvEdgeA)->nKey > ((dglTreeEdge_s *)pvEdgeB)->nKey ) return 1;
00139         else return 0;
00140 }
00141 
00142 dglTreeEdge_s * dglTreeEdgeAdd( void * pavl, dglInt32_t nKey )
00143 {
00144         dglTreeEdge_s * pedge;
00145         void **ppvret;
00146         if ( (pedge = dglTreeEdgeAlloc()) == NULL ) return NULL;
00147         pedge->nKey = nKey;
00148         ppvret = avl_probe( pavl , pedge );
00149         if ( *ppvret != pedge ) {
00150                 free( pedge );
00151                 pedge = *ppvret;
00152         }
00153         return pedge;
00154 }
00155 
00156 
00157 
00158 /*
00159  * AVL Support for data type dglTreeTouchI32_s
00160  * alloc
00161  * cancel
00162  * compare
00163  * add
00164  */
00165 dglTreeTouchI32_s * dglTreeTouchI32Alloc()
00166 {
00167         dglTreeTouchI32_s * pTouchI32 = (dglTreeTouchI32_s*)malloc( sizeof(dglTreeTouchI32_s) );
00168         pTouchI32->nKey = 0;
00169         return pTouchI32;
00170 }
00171 
00172 void dglTreeTouchI32Cancel( void * pvTouchI32 , void * pvParam )
00173 {
00174         free( pvTouchI32 );
00175 }
00176 
00177 int dglTreeTouchI32Compare( const void * pvTouchI32A , const void * pvTouchI32B , void * pvParam )
00178 {
00179         if ( ((dglTreeTouchI32_s *)pvTouchI32A)->nKey < ((dglTreeTouchI32_s *)pvTouchI32B)->nKey ) return -1;
00180         else if ( ((dglTreeTouchI32_s *)pvTouchI32A)->nKey > ((dglTreeTouchI32_s *)pvTouchI32B)->nKey ) return 1;
00181         else return 0;
00182 }
00183 
00184 dglTreeTouchI32_s * dglTreeTouchI32Add( void * pavl, dglInt32_t nKey )
00185 {
00186         dglTreeTouchI32_s * pnode;
00187         void **ppvret;
00188         if ( (pnode = dglTreeTouchI32Alloc()) == NULL ) return NULL;
00189         pnode->nKey = nKey;
00190         ppvret = avl_probe( pavl , pnode );
00191         if ( *ppvret != pnode ) {
00192                 free( pnode );
00193                 pnode = *ppvret;
00194         }
00195         return pnode;
00196 }
00197 
00198 
00199 
00200 /*
00201  * AVL Support for data type dglTreePredist_s
00202  * alloc
00203  * cancel
00204  * compare
00205  * add
00206  */
00207 dglTreePredist_s * dglTreePredistAlloc()
00208 {
00209         dglTreePredist_s * pPredist = (dglTreePredist_s*)malloc( sizeof(dglTreePredist_s) );
00210         if ( pPredist ) memset( pPredist, 0, sizeof(dglTreePredist_s) );
00211         return pPredist;
00212 }
00213 
00214 void dglTreePredistCancel( void * pvPredist , void * pvParam )
00215 {
00216         free( pvPredist );
00217 }
00218 
00219 int dglTreePredistCompare( const void * pvPredistA , const void * pvPredistB , void * pvParam )
00220 {
00221         if ( ((dglTreePredist_s *)pvPredistA)->nKey < ((dglTreePredist_s *)pvPredistB)->nKey ) return -1;
00222         else if ( ((dglTreePredist_s *)pvPredistA)->nKey > ((dglTreePredist_s *)pvPredistB)->nKey ) return 1;
00223         else return 0;
00224 }
00225 
00226 dglTreePredist_s * dglTreePredistAdd( void * pavl, dglInt32_t nKey )
00227 {
00228         dglTreePredist_s * pnode;
00229         void **ppvret;
00230         if ( (pnode = dglTreePredistAlloc()) == NULL ) return NULL;
00231         pnode->nKey = nKey;
00232         ppvret = avl_probe( pavl , pnode );
00233         if ( *ppvret != pnode ) {
00234                 free( pnode );
00235                 pnode = *ppvret;
00236         }
00237         return pnode;
00238 }
00239 
00240 
00241 
00242 
00243 /*
00244  * AVL Support for data type dglTreeNodePri32_s
00245  * alloc
00246  * cancel
00247  * compare
00248  * add
00249  */
00250 dglTreeNodePri32_s * dglTreeNodePri32Alloc()
00251 {
00252         dglTreeNodePri32_s * pNodePri32 = (dglTreeNodePri32_s*)malloc( sizeof(dglTreeNodePri32_s) );
00253         if ( pNodePri32 ) memset( pNodePri32, 0, sizeof(dglTreeNodePri32_s) );
00254         return pNodePri32;
00255 }
00256 
00257 void dglTreeNodePri32Cancel( void * pvNodePri32 , void * pvParam )
00258 {
00259         free( pvNodePri32 );
00260 }
00261 
00262 int dglTreeNodePri32Compare( const void * pvNodePri32A , const void * pvNodePri32B , void * pvParam )
00263 {
00264         if ( ((dglTreeNodePri32_s *)pvNodePri32A)->nKey < ((dglTreeNodePri32_s *)pvNodePri32B)->nKey ) return -1;
00265         else if ( ((dglTreeNodePri32_s *)pvNodePri32A)->nKey > ((dglTreeNodePri32_s *)pvNodePri32B)->nKey ) return 1;
00266         else return 0;
00267 }
00268 
00269 dglTreeNodePri32_s * dglTreeNodePri32Add( void * pavl, dglInt32_t nKey )
00270 {
00271         dglTreeNodePri32_s * pnode;
00272         void **ppvret;
00273         if ( (pnode = dglTreeNodePri32Alloc()) == NULL ) return NULL;
00274         pnode->nKey = nKey;
00275         ppvret = avl_probe( pavl , pnode );
00276         if ( *ppvret != pnode ) {
00277                 free( pnode );
00278                 pnode = *ppvret;
00279         }
00280         return pnode;
00281 }
00282 
00283 
00284 
00285 /*
00286  * AVL Support for data type dglTreeEdgePri32_s
00287  * alloc
00288  * cancel
00289  * compare
00290  * add
00291  */
00292 dglTreeEdgePri32_s * dglTreeEdgePri32Alloc()
00293 {
00294         dglTreeEdgePri32_s * pEdgePri32 = (dglTreeEdgePri32_s*)malloc( sizeof(dglTreeEdgePri32_s) );
00295         if ( pEdgePri32 ) memset( pEdgePri32, 0, sizeof(dglTreeEdgePri32_s) );
00296         return pEdgePri32;
00297 }
00298 
00299 void dglTreeEdgePri32Cancel( void * pvEdgePri32 , void * pvParam )
00300 {
00301         if ( ((dglTreeEdgePri32_s*)pvEdgePri32)->pnData ) {
00302                 free( ((dglTreeEdgePri32_s*)pvEdgePri32)->pnData );
00303         }
00304         free( pvEdgePri32 );
00305 }
00306 
00307 int dglTreeEdgePri32Compare( const void * pvEdgePri32A , const void * pvEdgePri32B , void * pvParam )
00308 {
00309         if ( ((dglTreeEdgePri32_s *)pvEdgePri32A)->nKey < ((dglTreeEdgePri32_s *)pvEdgePri32B)->nKey ) return -1;
00310         else if ( ((dglTreeEdgePri32_s *)pvEdgePri32A)->nKey > ((dglTreeEdgePri32_s *)pvEdgePri32B)->nKey ) return 1;
00311         else return 0;
00312 }
00313 
00314 dglTreeEdgePri32_s * dglTreeEdgePri32Add( void * pavl, dglInt32_t nKey )
00315 {
00316         dglTreeEdgePri32_s * pnode;
00317         void **ppvret;
00318         if ( (pnode = dglTreeEdgePri32Alloc()) == NULL ) return NULL;
00319         pnode->nKey = nKey;
00320         ppvret = avl_probe( pavl , pnode );
00321         if ( *ppvret != pnode ) {
00322                 free( pnode );
00323                 pnode = *ppvret;
00324         }
00325         return pnode;
00326 }
00327 
00328 
00329 
00330 
00331 /*
00332  * Our AVL allocator
00333  */
00334 static void * _tree_malloc(struct libavl_allocator * allocator, size_t libavl_size)
00335 {
00336         return malloc( libavl_size );
00337 }
00338 
00339 static void _tree_free(struct libavl_allocator * allocator, void *libavl_block)
00340 {
00341         free( libavl_block );
00342 }
00343 
00344 static struct libavl_allocator _tree_allocator = {
00345         _tree_malloc , _tree_free
00346 };
00347 
00348 void * dglTreeGetAllocator() {
00349         return & _tree_allocator;
00350 }

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5