1 /*----------------------------------------------------------------------- 2 3 File : clb_stringtrees.h 4 5 Author: Stephan Schulz 6 7 Contents 8 9 Definitions for AVL trees with string keys and up to two int or 10 pointer values. Part of the implementation is based on public domain 11 code by D.D. Sleator. 12 13 Copyright 1998, 1999 by the author. 14 This code is released under the GNU General Public Licence and 15 the GNU Lesser General Public License. 16 See the file COPYING in the main E directory for details.. 17 Run "eprover -h" for contact information. 18 19 Changes 20 21 <1> Thu Sep 25 02:23:01 MET DST 1997 22 New 23 24 -----------------------------------------------------------------------*/ 25 26 #ifndef CLB_STRINGTREES 27 28 #define CLB_STRINGTREES 29 30 #include <clb_dstrings.h> 31 #include <clb_avlgeneric.h> 32 33 /*---------------------------------------------------------------------*/ 34 /* Data type declarations */ 35 /*---------------------------------------------------------------------*/ 36 37 38 39 40 /*---------------------------------------------------------------------*/ 41 /* Exported Functions and Variables */ 42 /*---------------------------------------------------------------------*/ 43 44 45 46 /* General purpose data structure for indexing objects by a string 47 key. Integer values are supported directly, for all other objects 48 pointers can be used (and need to be casted carefully by the 49 wrapper functions). Keys are considered to be part of the tree and 50 will be FREE'd by memory deallocation. Objects pointed to by the 51 value fields are not part of the data stucture and will not be 52 touched by deallocating trees or tree nodes. */ 53 54 typedef struct strtreecell 55 { 56 char *key; 57 IntOrP val1; 58 IntOrP val2; 59 struct strtreecell *lson; 60 struct strtreecell *rson; 61 }StrTreeCell, *StrTree_p; 62 63 64 #define StrTreeCellAlloc() (StrTreeCell*)SizeMalloc(sizeof(StrTreeCell)) 65 #define StrTreeCellFree(junk) SizeFree(junk, sizeof(StrTreeCell)) 66 67 StrTree_p StrTreeCellAllocEmpty(void); 68 void StrTreeFree(StrTree_p junk); 69 StrTree_p StrTreeInsert(StrTree_p *root, StrTree_p newnode); 70 StrTree_p StrTreeStore(StrTree_p *root, char* key, IntOrP val1, IntOrP 71 val2); 72 StrTree_p StrTreeFind(StrTree_p *root, const char* key); 73 StrTree_p StrTreeExtractEntry(StrTree_p *root, const char* key); 74 bool StrTreeDeleteEntry(StrTree_p *root, const char* key); 75 76 AVL_TRAVERSE_DECLARATION(StrTree, StrTree_p) 77 #define StrTreeTraverseExit(stack) PStackFree(stack) 78 79 80 #endif 81 82 /*---------------------------------------------------------------------*/ 83 /* End of File */ 84 /*---------------------------------------------------------------------*/ 85 86 87 88 89 90