1 /*
2 * Copyright (c) 2002-2010 Stephen Williams (steve@icarus.com)
3 *
4 * This source code is free software; you can redistribute it
5 * and/or modify it in source code form under the terms of the GNU
6 * General Public License as published by the Free Software
7 * Foundation; either version 2 of the License, or (at your option)
8 * any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 */
19
20 # include "StringHeap.h"
21 # include <iostream>
22 # include <cstdlib>
23 # include <cstring>
24 # include <cassert>
25
26 #ifdef CHECK_WITH_VALGRIND
27 # include "ivl_alloc.h"
28 static char **string_pool = NULL;
29 static unsigned string_pool_count = 0;
30 #endif
31
32 static const unsigned DEFAULT_CELL_SIZE = 0x10000;
33
34
StringHeap()35 StringHeap::StringHeap()
36 {
37 cell_base_ = 0;
38 cell_ptr_ = 0;
39 }
40
~StringHeap()41 StringHeap::~StringHeap()
42 {
43 // This is a planned memory leak. The string heap is intended
44 // to hold permanently-allocated strings.
45 }
46
add(const char * text)47 const char* StringHeap::add(const char*text)
48 {
49 unsigned len = strlen(text);
50 unsigned rem = cell_base_==0? 0 : (DEFAULT_CELL_SIZE - cell_ptr_);
51
52 // Special case: huge items get their own allocation.
53 if ( (len+1) >= DEFAULT_CELL_SIZE ) {
54 char*buf = strdup(text);
55 #ifdef CHECK_WITH_VALGRIND
56 string_pool_count += 1;
57 string_pool = (char**)realloc(string_pool,
58 string_pool_count*sizeof(char**));
59 string_pool[string_pool_count-1] = buf;
60 #endif
61 return buf;
62 }
63
64 // If the current cell that I'm working through cannot hold
65 // the current string, then set it aside and get another cell
66 // to put the string into.
67 if (rem < (len+1)) {
68 // release any unused memory. This assumes that a
69 // realloc shrink of the memory region will return the
70 // same pointer.
71 if (rem > 0) {
72 char*old = cell_base_;
73 cell_base_ = (char*)realloc(cell_base_, cell_ptr_);
74 assert(cell_base_ != 0);
75 assert(cell_base_ == old);
76 }
77 // start new cell
78 cell_base_ = (char*)malloc(DEFAULT_CELL_SIZE);
79 cell_ptr_ = 0;
80 rem = DEFAULT_CELL_SIZE;
81 assert(cell_base_ != 0);
82 #ifdef CHECK_WITH_VALGRIND
83 string_pool_count += 1;
84 string_pool = (char **) realloc(string_pool,
85 string_pool_count*sizeof(char **));
86 string_pool[string_pool_count-1] = cell_base_;
87 #endif
88 }
89
90 assert( (len+1) <= rem );
91 char*res = cell_base_ + cell_ptr_;
92 memcpy(res, text, len);
93 cell_ptr_ += len;
94 cell_base_[cell_ptr_++] = 0;
95
96 assert(cell_ptr_ <= DEFAULT_CELL_SIZE);
97
98 return res;
99 }
100
make(const char * text)101 perm_string StringHeap::make(const char*text)
102 {
103 return perm_string(add(text));
104 }
105
106
StringHeapLex()107 StringHeapLex::StringHeapLex()
108 {
109 hit_count_ = 0;
110 add_count_ = 0;
111
112 for (unsigned idx = 0 ; idx < HASH_SIZE ; idx += 1)
113 hash_table_[idx] = 0;
114 }
115
~StringHeapLex()116 StringHeapLex::~StringHeapLex()
117 {
118 }
119
cleanup()120 void StringHeapLex::cleanup()
121 {
122 #ifdef CHECK_WITH_VALGRIND
123 for (unsigned idx = 0 ; idx < string_pool_count ; idx += 1) {
124 free(string_pool[idx]);
125 }
126 free(string_pool);
127 string_pool = NULL;
128 string_pool_count = 0;
129
130 for (unsigned idx = 0 ; idx < HASH_SIZE ; idx += 1) {
131 hash_table_[idx] = 0;
132 }
133 #endif
134 }
135
add_hit_count() const136 unsigned StringHeapLex::add_hit_count() const
137 {
138 return hit_count_;
139 }
140
add_count() const141 unsigned StringHeapLex::add_count() const
142 {
143 return add_count_;
144 }
145
hash_string(const char * text)146 static unsigned hash_string(const char*text)
147 {
148 unsigned h = 0;
149
150 while (*text) {
151 h = (h << 4) ^ (h >> 28) ^ *text;
152 text += 1;
153 }
154 return h;
155 }
156
add(const char * text)157 const char* StringHeapLex::add(const char*text)
158 {
159 unsigned hash_value = hash_string(text) % HASH_SIZE;
160
161 /* If we easily find the string in the hash table, then return
162 that and be done. */
163 if (hash_table_[hash_value]
164 && (strcmp(hash_table_[hash_value], text) == 0)) {
165 hit_count_ += 1;
166 return hash_table_[hash_value];
167 }
168
169 /* The existing hash entry is not a match. Replace it with the
170 newly allocated value, and return the new pointer as the
171 result to the add. */
172 const char*res = StringHeap::add(text);
173 hash_table_[hash_value] = res;
174 add_count_ += 1;
175
176 return res;
177 }
178
make(const char * text)179 perm_string StringHeapLex::make(const char*text)
180 {
181 return perm_string(add(text));
182 }
183
make(const string & text)184 perm_string StringHeapLex::make(const string&text)
185 {
186 return perm_string(add(text.c_str()));
187 }
188
operator ==(perm_string a,const char * b)189 bool operator == (perm_string a, const char*b)
190 {
191 if (a.str() == b)
192 return true;
193
194 if (! (a.str() && b))
195 return false;
196
197 if (strcmp(a.str(), b) == 0)
198 return true;
199
200 return false;
201 }
202
operator ==(perm_string a,perm_string b)203 bool operator == (perm_string a, perm_string b)
204 {
205 return a == b.str();
206 }
207
operator !=(perm_string a,const char * b)208 bool operator != (perm_string a, const char*b)
209 {
210 return ! (a == b);
211 }
212
operator !=(perm_string a,perm_string b)213 bool operator != (perm_string a, perm_string b)
214 {
215 return ! (a == b);
216 }
217
operator <(perm_string a,perm_string b)218 bool operator < (perm_string a, perm_string b)
219 {
220 if (b.str() && !a.str())
221 return true;
222
223 if (b.str() == a.str())
224 return false;
225
226 if (strcmp(a.str(), b.str()) < 0)
227 return true;
228
229 return false;
230 }
231
operator <<(ostream & out,perm_string that)232 ostream& operator << (ostream&out, perm_string that)
233 {
234 if (that.nil())
235 out << "<nil>";
236 else
237 out << that.str();
238 return out;
239 }
240
241 const perm_string empty_perm_string = perm_string::literal("");
242