1 /* 2 * Copyright (c) 2000, 2001 Peter Bozarov. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by Peter Bozarov. 16 * 4. The name of the author may not be used to endorse or promote products 17 * derived from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* Last modified: Mon Dec 24 11:06:28 EST 2001 33 * Thu Dec 27 15:39:13 EST 2001 34 */ 35 36 # ifndef _LIBDS_H_ 37 # define _LIBDS_H_ 38 39 # define DS_LIB_VERSION_MAJOR 2 40 # define DS_LIB_VERSION_MINOR 1 41 # define DS_LIB_VERSION_STATUS 42 43 # ifdef sun 44 # define const 45 # endif 46 47 typedef void* DSKEY; 48 typedef int (*DSKEYCMPFUN)(const DSKEY,const DSKEY); 49 50 /*----------------------------------------------------------------------* 51 * Tree * 52 *----------------------------------------------------------------------*/ 53 # define AVLTreeNoCopyKeys 0 54 # define AVLTreeCopyKeys 1 55 # define AVLTreeNoKeySize 0 56 57 # define AVLTreeNoCompFun ((void*)0) 58 # define AVLTreeNullData ((void*)0) 59 60 typedef DSKEYCMPFUN AVLKEYCOMPFUN; 61 62 typedef struct avltree AvlTree; 63 typedef AvlTree* AVLTREE; 64 typedef struct avlnode AvlNode; 65 typedef AvlNode* AVLNODE; 66 67 68 /* Default tree making routine for nodes with string keys */ 69 # define avlNewTreeStrKeys() \ 70 avlNewTree((AVLKEYCOMPFUN)strcmp,AVLTreeCopyKeys,AVLTreeNoKeySize) 71 # define avlMake() avlNewTree((void*)0,1,0) 72 # define avlAdd(t,k,d) avlInsert((t),(const DSKEY)(k),(void*)(d)) 73 # define avlRemove(t,k) avlRemoveByKey((t),(k)) 74 # define avlFirstNode(tr) avlMinimumNode((tr)) 75 # define avlLastNode(tr) avlMaximumNode((tr)) 76 # define avlFirst(tr) avlMinimum((tr)) 77 # define avlLast(tr) avlMaximum((tr)) 78 # define avlSize(tr) avlTotalNodes((tr)) 79 80 # define AVLPreWalk 0 81 # define AVLInWalk 1 82 # define AVLPostWalk 2 83 84 /*----------------------------------------------------------------------* 85 * Queue * 86 *----------------------------------------------------------------------*/ 87 88 typedef struct QElem QElem; 89 typedef QElem* QELEM; 90 typedef struct Queue Queue; 91 typedef Queue* QUEUE; 92 93 # define qAdd(q,e) qEnque((q),(void*)(e)) 94 # define qRemove(q) qDeque((q)) 95 # define qSize(q) qLength((q)) 96 97 /*----------------------------------------------------------------------* 98 * Heap * 99 *----------------------------------------------------------------------*/ 100 typedef struct Heap Heap; 101 typedef Heap* HEAP; 102 103 # define HEAP_MAXIMIZE 0 104 # define HEAP_MINIMIZE 1 105 106 typedef DSKEYCMPFUN HEAPCMPFUNC; 107 108 typedef void (*HEAPCHGFUNC)(void*,int); 109 typedef void (*HEAPWALKFUNC)(int,const DSKEY,void*); 110 typedef void (*HEAPPRINTFUNC)(int,void*,void*); 111 112 # define heapAdd(h,k,d) heapInsert((h),(k),(d)) 113 114 /*----------------------------------------------------------------------* 115 * Hashing * 116 *----------------------------------------------------------------------*/ 117 118 typedef unsigned (*HASHFUNC)(DSKEY); 119 typedef DSKEYCMPFUN HASHCMPFUNC; 120 121 typedef struct hashtable HashTable; 122 typedef HashTable* HASHTABLE; 123 124 typedef struct Stack Stack; 125 typedef Stack* STACK; 126 typedef struct PArray PArray; 127 typedef PArray* PARRAY; 128 129 /*----------------------------------------------------------------------* 130 * Set * 131 *----------------------------------------------------------------------*/ 132 typedef struct _set Set; 133 typedef Set* SET; 134 typedef Set* BAG; 135 typedef int (*SETCMPFUN)(void*,void*); 136 137 # define setAppend(s1,s2) setUnion(s1,s2) 138 139 /*----------------------------- ( 139 lines) --------------------------*/ 140 extern void * avlNodeKey(AVLNODE); 141 extern char * avlNodeKeyAsString(void *); 142 extern AVLTREE avlNewTree(int(*)(DSKEY,DSKEY),int,int); 143 extern void avlClose(AVLTREE); 144 extern void avlCloseWithFunction(AVLTREE,void(*)(void *)); 145 extern void avlWalk(AVLTREE,void(*)(void *),int); 146 extern void avlWalkAscending(AVLTREE,void(*)(void *)); 147 extern void avlWalkDescending(AVLTREE,void(*)(void *)); 148 extern int avlHeight(AVLTREE); 149 extern int avlInsert(AVLTREE,const DSKEY,void *); 150 extern AVLNODE avlFindNode(AVLTREE,DSKEY); 151 extern void * avlFind(AVLTREE,DSKEY); 152 extern AVLNODE avlMinimumNode(AVLTREE); 153 extern void * avlMinimum(AVLTREE); 154 extern AVLNODE avlMaximumNode(AVLTREE); 155 extern void * avlMaximum(AVLTREE); 156 extern AVLNODE avlNextNode(AVLTREE,AVLNODE); 157 extern AVLNODE avlNextNodeByKey(AVLTREE,DSKEY); 158 extern AVLNODE avlPrevNode(AVLTREE,AVLNODE); 159 extern AVLNODE avlPrevNodeByKey(AVLTREE,DSKEY); 160 extern int avlGetData(AVLNODE,void **); 161 extern void * avlNodeData(AVLNODE); 162 extern void * avlNodeUpdateData(AVLNODE,void *); 163 extern void * avlUpdateData(AVLTREE,DSKEY,void *); 164 extern void * avlRemoveByKey(AVLTREE,DSKEY); 165 extern int avlRemoveNode(AVLTREE,AVLNODE); 166 extern int avlSetCurrent(AVLTREE,DSKEY); 167 extern int avlClearCurrent(AVLTREE); 168 extern void * avlCurrent(AVLTREE); 169 extern void * avlPrev(AVLTREE); 170 extern void * avlNext(AVLTREE); 171 extern void * avlCut(AVLTREE); 172 extern void avlFreeNode(void *); 173 extern int avlTotalNodes(AVLTREE); 174 extern AVLNODE avlRootNode(AVLTREE); 175 extern AVLNODE avlLeftNode(AVLNODE); 176 extern AVLNODE avlRightNode(AVLNODE); 177 extern int avlNodeHeight(AVLNODE); 178 extern int avlCheck(AVLTREE); 179 extern HASHTABLE htMake(int); 180 extern HASHTABLE htMakeHashTable(int,HASHFUNC,HASHCMPFUNC); 181 extern void htClose(HASHTABLE); 182 extern void htCloseWithFunction(HASHTABLE,void(*)(void*)); 183 extern int htAdd(HASHTABLE,DSKEY,void *); 184 extern void * htFind(HASHTABLE,DSKEY); 185 extern void * htRemove(HASHTABLE,DSKEY); 186 extern int htSize(HASHTABLE); 187 extern int htItems(HASHTABLE); 188 extern int htEmpty(HASHTABLE); 189 extern int htConflicts(HASHTABLE); 190 extern void htWalk(HASHTABLE,int,void(*)(DSKEY,void *,int)); 191 extern HEAP heapMake(void); 192 extern HEAP heapNew(int(*)(DSKEY,DSKEY),int,int,int); 193 extern void heapCloseWithFunction(HEAP,void(*)(void *)); 194 extern void heapClose(HEAP); 195 extern HEAP heapMakeIntKeys(int,int,int); 196 extern HEAP heapMakeDoubleKeys(int,int,int); 197 extern HEAP heapMakeFloatKeys(int,int,int); 198 extern HEAP heapMakeStringKeys(int,int,int); 199 extern int heapSetChgFunc(HEAP,HEAPCHGFUNC); 200 extern int heapInsert(HEAP,const DSKEY,void *); 201 extern void * heapDelete(HEAP,int); 202 extern void * heapFirst(HEAP); 203 extern void * heapPeekFirst(HEAP); 204 extern void * heapElementAt(HEAP,int); 205 extern int heapSize(HEAP); 206 extern int heapEmpty(HEAP); 207 extern void heapWalk(HEAP,HEAPWALKFUNC); 208 extern void heapPrintArray(HEAP,HEAPPRINTFUNC); 209 extern void heapPrintTree(HEAP,HEAPPRINTFUNC); 210 extern int heapCheck(HEAP); 211 extern PARRAY paMake(int,int); 212 extern void paCloseWithFunction(PARRAY,void(*)(void *)); 213 extern void paClose(PARRAY); 214 extern int paAdd(PARRAY,void *); 215 extern void * paRemove(PARRAY,int); 216 extern int paSize(PARRAY); 217 extern void * paReplace(PARRAY,int,void *); 218 extern int paContains(PARRAY,int(*)(void *,void *),void *); 219 extern void * paElementAt(PARRAY,int); 220 extern void * paCurrent(PARRAY); 221 extern void paSetCurrent(PARRAY,int); 222 extern void paClearCurrent(PARRAY); 223 extern void * paFirst(PARRAY); 224 extern void * paLast(PARRAY); 225 extern void * paNext(PARRAY); 226 extern void * paPrev(PARRAY); 227 extern QUEUE qMake(void); 228 extern void qClose(QUEUE); 229 extern void qCloseWithFunction(QUEUE,void(*)(void *)); 230 extern QELEM qEnque(QUEUE,void *); 231 extern void * qDeque(QUEUE); 232 extern int qWalk(QUEUE,void(*)(void *)); 233 extern int qWalkAscending(QUEUE,void(*)(void *)); 234 extern int qWalkDescending(QUEUE,void(*)(void *)); 235 extern int qLength(QUEUE); 236 extern int qEmpty(QUEUE); 237 extern void * qCurrent(QUEUE); 238 extern void qClearCurrent(QUEUE); 239 extern void qSetCurrent(QUEUE,QELEM); 240 extern void * qFirst(QUEUE); 241 extern void * qLast(QUEUE); 242 extern void * qNext(QUEUE); 243 extern void * qPrev(QUEUE); 244 extern void * qElemData(QELEM); 245 extern int qElemInsert(QUEUE,QELEM,QELEM); 246 extern int qElemAttach(QUEUE,QELEM); 247 extern int qElemDetach(QUEUE,QELEM); 248 extern void qElemFree(QELEM); 249 extern QELEM qElemFirst(QUEUE); 250 extern QELEM qElemLast(QUEUE); 251 extern QELEM qElemNext(QELEM); 252 extern QELEM qElemPrev(QELEM); 253 extern QELEM qElemCurr(QUEUE); 254 extern void * qElemRemove(QUEUE,QELEM); 255 extern SET setMake(void); 256 extern SET setNew(SETCMPFUN,int,int); 257 extern void setClose(SET); 258 extern void setCloseWithFunction(SET,void(*)(void *)); 259 extern int setAdd(SET,void *); 260 extern void * setRemove(SET,void *); 261 extern void * setFirst(SET); 262 extern void * setNext(SET); 263 extern int setSize(SET); 264 extern int setEmpty(SET); 265 extern int setContains(SET,void *); 266 extern void * setFind(SET,void *); 267 extern SET setUnion(SET,SET); 268 extern SET setUnion1(SET,SET); 269 extern SET setIntersect(SET,SET); 270 extern SET setDifference(SET,SET); 271 extern SET setXIntersect(SET,SET); 272 extern STACK stkMake(void); 273 extern void stkCloseWithFunction(STACK,void(*)(void *)); 274 extern void stkClose(STACK); 275 extern int stkPush(STACK,void *); 276 extern void * stkPop(STACK); 277 extern void * stkPeek(STACK); 278 extern int stkSize(STACK); 279 extern int stkEmpty(STACK); 280 281 # endif /* ! _LIBDS_H_ */ 282