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