GRASS Programmer's Manual
6.4.1(2011)
|
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 }