1 /* LIBDGL -- a Directed Graph Library implementation 2 * Copyright (C) 2002 Roberto Micarelli 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 19 /* best view tabstop=4 20 */ 21 22 #ifndef _DGL_TREE_H_ 23 #define _DGL_TREE_H_ 24 25 #define USE_THREADED_AVL 26 27 #if defined(USE_THREADED_AVL) 28 #include "tavl.h" 29 #define avl_table tavl_table 30 #define avl_traverser tavl_traverser 31 #define avl_create tavl_create 32 #define avl_copy tavl_copy 33 #define avl_destroy tavl_destroy 34 #define avl_probe tavl_probe 35 #define avl_insert tavl_insert 36 #define avl_replace tavl_replace 37 #define avl_delete tavl_delete 38 #define avl_find tavl_find 39 #define avl_assert_insert tavl_assert_insert 40 #define avl_assert_delete tavl_assert_delete 41 #define avl_t_init tavl_t_init 42 #define avl_t_first tavl_t_first 43 #define avl_t_last tavl_t_last 44 #define avl_t_find tavl_t_find 45 #define avl_t_insert tavl_t_insert 46 #define avl_t_copy tavl_t_copy 47 #define avl_t_next tavl_t_next 48 #define avl_t_prev tavl_t_prev 49 #define avl_t_cur tavl_t_cur 50 #define avl_t_replace tavl_t_replace 51 #else 52 #include "avl.h" 53 #endif 54 55 56 extern void *dglTreeGetAllocator(); 57 58 /* 59 * Define a node as it is hosted in pNodeTree 60 */ 61 typedef struct _dglTreeNode 62 { 63 long nKey; 64 void *pv; 65 void *pv2; 66 } dglTreeNode_s; 67 extern dglTreeNode_s *dglTreeNodeAlloc(); 68 extern void dglTreeNodeCancel(void *pvNode, void *pvParam); 69 extern int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, 70 void *pvParam); 71 extern dglTreeNode_s *dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey); 72 73 74 /* 75 * Define a version-2 node as it is hosted in pNodeTree 76 */ 77 typedef struct _dglTreeNode2 78 { 79 long nKey; 80 void *pv; 81 void *pv2; 82 void *pv3; 83 } dglTreeNode2_s; 84 extern dglTreeNode2_s *dglTreeNode2Alloc(); 85 extern void dglTreeNode2Cancel(void *pvNode, void *pvParam); 86 extern int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB, 87 void *pvParam); 88 extern dglTreeNode2_s *dglTreeNode2Add(void *pvAVL, dglInt32_t nKey); 89 90 91 /* 92 * Define a edge as it is hosted in pEdgeTree 93 */ 94 typedef struct _dglTreeEdge 95 { 96 dglInt32_t nKey; 97 void *pv; 98 } dglTreeEdge_s; 99 extern dglTreeEdge_s *dglTreeEdgeAlloc(); 100 extern void dglTreeEdgeCancel(void *pvEdge, void *pvParam); 101 extern int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, 102 void *pvParam); 103 extern dglTreeEdge_s *dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey); 104 105 106 /* 107 * Define a dummy entry to 'touch' selected item with a dglInt32_t key 108 * i.e. used to mark visited nodes in a greedy or tree-growing algorithm 109 */ 110 typedef struct _dglTreeTouchI32 111 { 112 dglInt32_t nKey; 113 } dglTreeTouchI32_s; 114 extern dglTreeTouchI32_s *dglTreeTouchI32Alloc(); 115 extern void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam); 116 extern int dglTreeTouchI32Compare(const void *pvTouchI32A, 117 const void *pvTouchI32B, void *pvParam); 118 extern dglTreeTouchI32_s *dglTreeTouchI32Add(void *pvAVL, dglInt32_t nKey); 119 120 121 /* 122 * Define a entry to maintain a predecessor/distance network in shortest-path computation 123 */ 124 typedef struct _dglTreePredist 125 { 126 dglInt32_t nKey; 127 dglInt32_t nFrom; 128 dglInt32_t nDistance; 129 dglInt32_t nCost; 130 dglInt32_t *pnEdge; 131 dglByte_t bFlags; 132 } dglTreePredist_s; 133 extern dglTreePredist_s *dglTreePredistAlloc(); 134 extern void dglTreePredistCancel(void *pvPredist, void *pvParam); 135 extern int dglTreePredistCompare(const void *pvPredistA, 136 const void *pvPredistB, void *pvParam); 137 extern dglTreePredist_s *dglTreePredistAdd(void *pvAVL, dglInt32_t nKey); 138 139 140 /* 141 * 32bit-key Node Prioritizer 142 */ 143 typedef struct _dglTreeNodePri32 144 { 145 dglInt32_t nKey; 146 dglInt32_t cnVal; 147 dglInt32_t *pnVal; 148 } dglTreeNodePri32_s; 149 extern dglTreeNodePri32_s *dglTreeNodePri32Alloc(); 150 extern void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam); 151 extern int dglTreeNodePri32Compare(const void *pvNodePri32A, 152 const void *pvNodePri32B, void *pvParam); 153 extern dglTreeNodePri32_s *dglTreeNodePri32Add(void *pvAVL, dglInt32_t nKey); 154 155 156 /* 157 * 32bit-key Edge Prioritizer 158 */ 159 typedef struct _dglTreeEdgePri32 160 { 161 dglInt32_t nKey; 162 dglInt32_t cnData; 163 dglInt32_t *pnData; 164 } dglTreeEdgePri32_s; 165 extern dglTreeEdgePri32_s *dglTreeEdgePri32Alloc(); 166 extern void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam); 167 extern int dglTreeEdgePri32Compare(const void *pvEdgePri32A, 168 const void *pvEdgePri32B, void *pvParam); 169 extern dglTreeEdgePri32_s *dglTreeEdgePri32Add(void *pvAVL, dglInt32_t nKey); 170 171 172 #endif 173