Debian Codegraph @

apps/tools/ivfix/IfHasher.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library 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 GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 #include <Inventor/SbDict.h>
38 #include <Inventor/SbPList.h>
39 #include <Inventor/fields/SoMFVec2f.h>
40 #include <Inventor/fields/SoMFVec3f.h>
41
42 #include "IfAssert.h"
43 #include "IfHasher.h"
44
45 /////////////////////////////////////////////////////////////////////////////
46 //
47 // Constructors for 2- or 3-dimensional vectors.
48 //
49 /////////////////////////////////////////////////////////////////////////////
50
51 IfHasher::IfHasher(SoMFVec2f *field, int maxNumVectors,
52 const SbVec2f &min, const SbVec2f &scale)
53 {
54 dimension = 2;
55
56 field2 = field;
57 field3 = NULL;
58
59 hashMin[0] = min[0];
60 hashMin[1] = min[1];
61 hashMin[2] = 0.0;
62
63 hashScale[0] = scale[0];
64 hashScale[1] = scale[1];
65 hashScale[2] = 1.0;
66
67 maxNum = maxNumVectors;
68
69 commonConstructor();
70 }
71
72 IfHasher::IfHasher(SoMFVec3f *field, int maxNumVectors,
73 const SbVec3f &min, const SbVec3f &scale)
74 {
75 dimension = 3;
76
77 field2 = NULL;
78 field3 = field;
79
80 hashMin = min;
81 hashScale = scale;
82
83 maxNum = maxNumVectors;
84
85 commonConstructor();
86 }
87
88 /////////////////////////////////////////////////////////////////////////////
89 //
90 // Stuff common to both constructors.
91 //
92 /////////////////////////////////////////////////////////////////////////////
93
94 void
95 IfHasher::commonConstructor()
96 {
97 // Create an array of HashEntry instances
98 entries = new HashEntry[maxNum];
99 curEntry = 0;
100
101 // Make room in the field and begin editing
102 if (dimension == 2) {
103 field2->setNum(maxNum);
104 vectors2 = field2->startEditing();
105 vectors3 = NULL;
106 }
107 else {
108 field3->setNum(maxNum);
109 vectors3 = field3->startEditing();
110 vectors2 = NULL;
111 }
112
113 // Set up the dictionary
114 vectorDict = new SbDict(1235);
115
116 // Multiply the scale values by some arbitrary numbers to make
117 // the hash function more random
118 hashScale[0] *= 233;
119 hashScale[1] *= 72091;
120 hashScale[2] *= 453451;
121 }
122
123 /////////////////////////////////////////////////////////////////////////////
124 //
125 // Destructor.
126 //
127 /////////////////////////////////////////////////////////////////////////////
128
129 IfHasher::~IfHasher()
130 {
131 }
132
133 /////////////////////////////////////////////////////////////////////////////
134 //
135 // These add a vector to the list, returning its index. Room is
136 // made in the field, if necessary.
137 //
138 /////////////////////////////////////////////////////////////////////////////
139
140 int
141 IfHasher::addVector(const SbVec2f &newVector)
142 {
143 ASSERT(vectorDict != NULL);
144 ASSERT(dimension == 2);
145
146 // See if we need to add this one, or is it already there
147 int index;
148 SbBool notThere = addIfNotThere(newVector.getValue(), index);
149
150 // If it's not there, we need to add it to the field
151 if (notThere)
152 vectors2[index] = newVector;
153
154 return index;
155 }
156
157 int
158 IfHasher::addVector(const SbVec3f &newVector)
159 {
160 ASSERT(vectorDict != NULL);
161 ASSERT(dimension == 3);
162
163 // See if we need to add this one, or is it already there
164 int index;
165 SbBool notThere = addIfNotThere(newVector.getValue(), index);
166
167 // If it's not there, we need to add it to the field
168 if (notThere)
169 vectors3[index] = newVector;
170
171 return index;
172 }
173
174 /////////////////////////////////////////////////////////////////////////////
175 //
176 // Adds the given vector to the hash table, if it is not already
177 // there. Returns TRUE if the vector was added.
178 //
179 /////////////////////////////////////////////////////////////////////////////
180
181 SbBool
182 IfHasher::addIfNotThere(const float *newVector, int &index)
183 {
184 ASSERT(curEntry < maxNum - 1);
185
186 // Find the hash key
187 uint32_t key = hashVector(newVector);
188
189 // See if there already is a list of vectors with the same key
190 void *list;
191 if (vectorDict->find(key, list)) {
192
193 // If so, look through the list for an exact match
194 HashEntry *entry, *prevEntry = NULL;
195 for (entry = (HashEntry *) list; entry != NULL; entry = entry->next) {
196
197 ASSERT(entry->index < curEntry);
198
199 // If the vectors are the same, re-use the old one and stop
200 if (sameVector(newVector, entry->index)) {
201 index = entry->index;
202 return FALSE;
203 }
204
205 prevEntry = entry;
206 }
207
208 // If there were no matches, add the new vector to the end of
209 // the list
210 ASSERT(prevEntry != NULL);
211 entry = &entries[curEntry];
212 entry->index = curEntry;
213 entry->next = NULL;
214 prevEntry->next = entry;
215 }
216
217 // If there were no entries in the dictionary, start one
218 else {
219 HashEntry *entry = &entries[curEntry];
220 entry->index = curEntry;
221 entry->next = NULL;
222 vectorDict->enter(key, entry);
223 }
224
225 index = curEntry++;
226 return TRUE;
227 }
228
229 /////////////////////////////////////////////////////////////////////////////
230 //
231 // Hash function for finding duplicate vectors.
232 //
233 /////////////////////////////////////////////////////////////////////////////
234
235 uint32_t
236 IfHasher::hashVector(const float *v)
237 {
238 float sum = 0.0;
239 for (int i = 0; i < dimension; i++)
240 sum += (v[i] - hashMin[i]) * hashScale[i];
241 return (int32_t) sum;
242 }
243
244 /////////////////////////////////////////////////////////////////////////////
245 //
246 // Returns TRUE if the given vector matches the given existing vector.
247 //
248 /////////////////////////////////////////////////////////////////////////////
249
250 SbBool
251 IfHasher::sameVector(const float *vector, int index)
252 {
253 if (dimension == 2)
254 return (vector[0] == vectors2[index][0] &&
255 vector[1] == vectors2[index][1]);
256 else
257 return (vector[0] == vectors3[index][0] &&
258 vector[1] == vectors3[index][1] &&
259 vector[2] == vectors3[index][2]);
260 }
261
262 /////////////////////////////////////////////////////////////////////////////
263 //
264 // Finishes up.
265 //
266 /////////////////////////////////////////////////////////////////////////////
267
268 void
269 IfHasher::finish()
270 {
271 // Stop editing and set the field to contain the correct number of
272 // values
273 if (dimension == 2) {
274 field2->finishEditing();
275 field2->setNum(curEntry);
276 }
277 else {
278 field3->finishEditing();
279 field3->setNum(curEntry);
280 }
281
282 // Get rid of the dictionary and the HashEntry instances
283 delete vectorDict;
284 delete [] entries;
285
286 // Make sure nobody uses this again
287 vectorDict = NULL;
288 }