1 /* BurrTools
2 *
3 * BurrTools is the legal property of its developers, whose
4 * names are listed in the COPYRIGHT file, which is included
5 * within the source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 */
21 #include "disassemblerhashes.h"
22
23 #include "disassemblernode.h"
24
nodeHash(void)25 nodeHash::nodeHash(void) {
26
27 tab_size = 11;
28 tab_entries = 0;
29
30 tab = new disassemblerNode_c* [tab_size];
31
32 memset(tab, 0, tab_size*sizeof(disassemblerNode_c*));
33 }
34
~nodeHash(void)35 nodeHash::~nodeHash(void) {
36 clear();
37
38 delete [] tab;
39 }
40
clear(void)41 void nodeHash::clear(void)
42 {
43 for (unsigned int i = 0; i < tab_size; i++) {
44 while (tab[i]) {
45 disassemblerNode_c * n = tab[i];
46 tab[i] = n->next;
47
48 if (n->decRefCount())
49 delete n;
50 }
51 }
52
53 tab_entries = 0;
54 }
55
insert(disassemblerNode_c * n)56 const disassemblerNode_c * nodeHash::insert(disassemblerNode_c * n) {
57
58 unsigned long h = n->hash() % tab_size;
59
60 disassemblerNode_c * hn = tab[h];
61
62 while (hn) {
63 if (*hn == *n) {
64
65 // let's see, a node for this state already exists, if the found way to this
66 // node is longer than the current way, we replace it with the data of the current
67 // node
68 if (hn->getWaylength() > n->getWaylength())
69 hn->replaceNode(n);
70
71 return hn;
72 }
73
74 hn = hn->next;
75 }
76
77 /* node not in table, insert */
78 n->incRefCount();
79
80 n->next = tab[h];
81 tab[h] = n;
82
83 tab_entries++;
84 if (tab_entries > tab_size) {
85 // rehash
86
87 unsigned long new_size = tab_size * 4 + 1;
88
89 disassemblerNode_c ** new_tab = new disassemblerNode_c* [new_size];
90 memset(new_tab, 0, new_size*sizeof(disassemblerNode_c*));
91
92 for (unsigned int i = 0; i < tab_size; i++) {
93 while (tab[i]) {
94 disassemblerNode_c * n = tab[i];
95 tab[i] = n->next;
96 unsigned long h = n->hash() % new_size;
97 n->next = new_tab[h];
98 new_tab[h] = n;
99 }
100 }
101
102 delete[] tab;
103 tab = new_tab;
104 tab_size = new_size;
105 }
106
107 return 0;
108 }
109
contains(const disassemblerNode_c * n) const110 bool nodeHash::contains(const disassemblerNode_c * n) const {
111 unsigned long h = n->hash() % tab_size;
112
113 disassemblerNode_c * hn = tab[h];
114
115 while (hn) {
116 if (*hn == *n)
117 return true;
118
119 hn = hn->next;
120 }
121
122 return false;
123 }
124
125
126
countingNodeHash(void)127 countingNodeHash::countingNodeHash(void) {
128
129 tab_size = 100;
130 tab_entries = 0;
131
132 tab = new hashNode * [tab_size];
133
134 memset(tab, 0, tab_size*sizeof(hashNode*));
135
136 scanPtr = 0;
137 scanActive = false;
138
139 linkStart = 0;
140 }
141
~countingNodeHash(void)142 countingNodeHash::~countingNodeHash(void)
143 {
144 clear();
145 delete [] tab;
146 }
147
148 /* delete all nodes and empty table for new usage */
clear(void)149 void countingNodeHash::clear(void)
150 {
151 hashNode * hn = linkStart;
152
153 while (hn) {
154 hashNode * hn2 = hn->link;
155
156 if (hn->dat->decRefCount())
157 delete hn->dat;
158
159 delete hn;
160
161 hn = hn2;
162 }
163
164 memset(tab, 0, tab_size*sizeof(hashNode*));
165 tab_entries = 0;
166 linkStart = 0;
167 }
168
insert(disassemblerNode_c * n)169 bool countingNodeHash::insert(disassemblerNode_c * n) {
170
171 unsigned long h = n->hash() % tab_size;
172
173 hashNode * hn = tab[h];
174
175 while (hn) {
176 if (*(hn->dat) == *n)
177 return true;
178
179 hn = hn->next;
180 }
181
182 /* node not in table, insert */
183 n->incRefCount();
184
185 hn = new hashNode;
186 hn->dat = n;
187
188 hn->next = tab[h];
189 tab[h] = hn;
190
191 hn->link = linkStart;
192 linkStart = hn;
193
194 tab_entries++;
195 if (tab_entries > tab_size) {
196
197 unsigned long new_size = tab_size * 4 + 1;
198
199 hashNode ** new_tab = new hashNode* [new_size];
200 memset(new_tab, 0, new_size*sizeof(hashNode*));
201
202 for (unsigned int i = 0; i < tab_size; i++) {
203 while (tab[i]) {
204 hashNode * hn = tab[i];
205 tab[i] = hn->next;
206 unsigned long h = hn->dat->hash() % new_size;
207 hn->next = new_tab[h];
208 new_tab[h] = hn;
209 }
210 }
211
212 delete[] tab;
213 tab = new_tab;
214 tab_size = new_size;
215 }
216
217 return false;
218 }
219
initScan(void)220 void countingNodeHash::initScan(void) {
221
222 bt_assert(!scanActive);
223
224 scanPtr = linkStart;
225 scanActive = true;
226 }
227
nextScan(void)228 const disassemblerNode_c * countingNodeHash::nextScan(void) {
229
230 bt_assert(scanActive);
231
232 if (!scanPtr) {
233 scanActive = false;
234 return 0;
235
236 } else {
237
238 disassemblerNode_c * res = scanPtr->dat;
239 scanPtr = scanPtr->link;
240
241 return res;
242 }
243 }
244
245
246