1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1996 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /*************************************************************************/
33 /* Author : Alan W Black */
34 /* Date : June 1996 */
35 /*-----------------------------------------------------------------------*/
36 /* */
37 /* A class for building EST_String (char-based) tries for indexing */
38 /* arbitrary objects by Strings */
39 /* */
40 /*=======================================================================*/
41 #include "EST_String.h"
42 #include "EST_StringTrie.h"
43 #include <cstring>
44
45 #define TRIEWIDTH 256
46
47 static void (* trie_delete_function)(void *n) = 0;
48
char2idx(unsigned char k)49 static inline int char2idx(unsigned char k)
50 {
51 // return k & 0x7f; // only seven significant bits;
52 return k;
53 }
54
EST_TrieNode(const int width)55 EST_TrieNode::EST_TrieNode(const int width)
56 {
57 // Initialise a node of given width
58 w=width;
59 d= new EST_TrieNode *[w];
60 contents=0;
61 memset(d,0,w*sizeof(EST_TrieNode *));
62 }
63
~EST_TrieNode()64 EST_TrieNode::~EST_TrieNode()
65 {
66 int i;
67
68 if (trie_delete_function != 0) /* user supplied delete function */
69 trie_delete_function(contents);
70 for (i=0; i<w; i++)
71 delete d[i];
72 delete [] d;
73 }
74
lookup(const unsigned char * key) const75 void *EST_TrieNode::lookup(const unsigned char *key) const
76 {
77 // find key in EST_TrieNode, 0 if not found
78
79 if (*key == '\0')
80 return contents; // base case
81 else
82 {
83 int idx = char2idx(*key);
84 if (d[idx] == 0)
85 return 0; // not there
86 else
87 return d[idx]->lookup(key+1);
88 }
89 }
90
copy_into(EST_StringTrie & trie,const EST_String & path) const91 void EST_TrieNode::copy_into(EST_StringTrie &trie,
92 const EST_String &path) const
93 {
94 // find all items and add them to trie
95
96 if (contents != 0)
97 trie.add(path,contents);
98
99 for (int i=0; i < w; i++)
100 {
101 if (d[i] != 0)
102 {
103 char tail[2];
104 tail[0] = (char)i;
105 tail[1] = '\0';
106 d[i]->copy_into(trie,path+tail);
107 }
108 }
109 }
110
add(const unsigned char * key,void * value)111 void EST_TrieNode::add(const unsigned char *key,void *value)
112 {
113 // add this value
114
115 if (*key == '\0')
116 contents = value;
117 else
118 {
119 int idx = char2idx(*key);
120 if (d[idx] == 0) // need new subnode
121 d[idx] = new EST_TrieNode(w);
122 d[idx]->add(key+1,value);
123 }
124 }
125
EST_StringTrie()126 EST_StringTrie::EST_StringTrie()
127 {
128 tree = new EST_TrieNode(TRIEWIDTH);
129 }
130
copy(const EST_StringTrie & trie)131 void EST_StringTrie::copy(const EST_StringTrie &trie)
132 {
133 // This can't work because of the void* pointers in contents
134 delete tree;
135 tree = new EST_TrieNode(TRIEWIDTH);
136 trie.tree->copy_into(*this,"");
137 }
138
~EST_StringTrie()139 EST_StringTrie::~EST_StringTrie()
140 {
141 delete tree;
142 }
143
lookup(const EST_String & key) const144 void *EST_StringTrie::lookup(const EST_String &key) const
145 {
146 const unsigned char *ckey = (const unsigned char *)(void *)(const char *)key;
147 return tree->lookup(ckey);
148 }
149
add(const EST_String & key,void * item)150 void EST_StringTrie::add(const EST_String &key,void *item)
151 {
152 const unsigned char *ckey = (const unsigned char *)(void *)(const char *)key;
153 tree->add(ckey,item);
154 return;
155 }
156
clear(void)157 void EST_StringTrie::clear(void)
158 {
159 delete tree;
160 tree = new EST_TrieNode(TRIEWIDTH);
161 }
162
clear(void (* deletenode)(void * n))163 void EST_StringTrie::clear(void (*deletenode)(void *n))
164 {
165 // This wont work if we go multi-thread
166 trie_delete_function = deletenode;
167 delete tree;
168 trie_delete_function = 0;
169 tree = new EST_TrieNode(TRIEWIDTH);
170 }
171
172