Ptex
PtexHashMap.h
Go to the documentation of this file.
1/*
2PTEX SOFTWARE
3Copyright 2014 Disney Enterprises, Inc. All rights reserved
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are
7met:
8
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12 * Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the
15 distribution.
16
17 * The names "Disney", "Walt Disney Pictures", "Walt Disney Animation
18 Studios" or the names of its contributors may NOT be used to
19 endorse or promote products derived from this software without
20 specific prior written permission from Walt Disney Pictures.
21
22Disclaimer: THIS SOFTWARE IS PROVIDED BY WALT DISNEY PICTURES AND
23CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
24BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS
25FOR A PARTICULAR PURPOSE, NONINFRINGEMENT AND TITLE ARE DISCLAIMED.
26IN NO EVENT SHALL WALT DISNEY PICTURES, THE COPYRIGHT HOLDER OR
27CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND BASED ON ANY
31THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
34*/
40#ifndef PtexHashMap_h
41#define PtexHashMap_h
42
43#include <vector>
44#include "PtexPlatform.h"
45#include "PtexMutex.h"
46
48
49inline uint32_t memHash(const char* val, int len)
50{
51 int len64 = len & ~7;
52 uint64_t val64[4]; val64[0] = 0;
53 memcpy(&val64[0], &val[len64], len & 7);
54 uint64_t hashval[4] = {0,0,0,0};
55 hashval[0] = val64[0]*16777619;
56
57 for (int i = 0; i+32 <= len64; i+=32) {
58 for (int j = 0; j < 4; ++j) {
59 memcpy(&val64[j], &val[i+j*8], 8);
60 hashval[j] = (hashval[j]*16777619) ^ val64[j];
61 }
62 }
63 hashval[0] = (hashval[0]*16777619) ^ hashval[1];
64 hashval[2] = (hashval[2]*16777619) ^ hashval[3];
65 hashval[0] = (hashval[0]*16777619) ^ hashval[2];
66 return uint32_t(hashval[0]);
67}
68
69inline bool memCompare(const char* a, const char* b, int len)
70{
71 int len64 = len & ~7;
72 uint64_t val64[2];
73 for (int i = 0; i < len64; i+=8) {
74 memcpy(&val64[0], &a[i], 8);
75 memcpy(&val64[1], &b[i], 8);
76 if (val64[0] != val64[1]) return 1;
77 }
78 return memcmp(&a[len64], &b[len64], len & 7);
79}
80
81
83{
84 const char* volatile _val;
85 uint32_t volatile _len;
86 uint32_t volatile _hash;
87 bool volatile _ownsVal;
88
89 void operator=(const StringKey& key); // disallow
90 StringKey(const StringKey& key); // disallow
91
92public:
93 StringKey() : _val(0), _len(0), _hash(0), _ownsVal(false) {}
94 StringKey(const char* val)
95 {
96 _val = val;
97 _len = uint32_t(strlen(val));
99 _ownsVal = false;
100 }
101
102 ~StringKey() { if (_ownsVal) delete [] _val; }
103
104 void copy(volatile StringKey& key) volatile
105 {
106 char* newval = new char[key._len+1];
107 memcpy(newval, key._val, key._len+1);
108 _val = newval;
109 _len = key._len;
110 _hash = key._hash;
111 _ownsVal = true;
112 }
113
114 void move(volatile StringKey& key) volatile
115 {
116 _val = key._val;
117 _len = key._len;
118 _hash = key._hash;
119 _ownsVal = key._ownsVal;
120 key._ownsVal = false;
121 }
122
123 bool matches(const StringKey& key) volatile
124 {
125 return key._hash == _hash && key._len == _len && _val && 0 == memCompare(key._val, _val, _len);
126 }
127
128 bool isEmpty() volatile { return _val==0; }
129
130 uint32_t hash() volatile
131 {
132 return _hash;
133 }
134};
135
137{
138 int _val;
139
140public:
141 IntKey() : _val(0) {}
142 IntKey(int val) : _val(val) {}
143 void copy(volatile IntKey& key) volatile { _val = key._val; }
144 void move(volatile IntKey& key) volatile { _val = key._val; }
145 bool matches(const IntKey& key) volatile { return _val == key._val; }
146 bool isEmpty() volatile { return _val==0; }
147 uint32_t hash() volatile { return (_val*7919) & ~0xf; }
148};
149
150template <typename Key, typename Value>
152{
153 class Entry {
154 Entry(const Entry&); // disallow
155 void operator=(const Entry&); // disallow
156 public:
157 Entry() : key(), value(0) {}
158 Key volatile key;
159 Value volatile value;
160 };
161
162 PtexHashMap(const PtexHashMap&); // disallow
163 void operator=(const PtexHashMap&); // disallow
164
166 {
167 _numEntries = 16;
168 _size = 0;
170 }
171
173 {
174 for (uint32_t i = 0; i < _numEntries; ++i) {
175 if (_entries[i].value) delete _entries[i].value;
176 }
177 delete [] _entries;
178 for (size_t i = 0; i < _oldEntries.size(); ++i) {
179 delete [] _oldEntries[i];
180 }
181 std::vector<Entry*>().swap(_oldEntries);
182 }
183
184public:
186 {
187 initContents();
188 }
189
191 {
193 }
194
195 void clear()
196 {
198 initContents();
199 }
200
201 uint32_t size() const { return _size; }
202
203 Value get(Key& key)
204 {
205 uint32_t mask = _numEntries-1;
206 Entry* entries = getEntries();
207 uint32_t hash = key.hash();
208
209 Value result = 0;
210 for (uint32_t i = hash;; ++i) {
211 Entry& e = entries[i & mask];
212 if (e.key.matches(key)) {
213 result = e.value;
214 break;
215 }
216 if (e.value == 0) {
217 break;
218 }
219 }
220
221 return result;
222 }
223
224 Value tryInsert(Key& key, Value value, size_t& newMemUsed)
225 {
226 Entry* entries = lockEntriesAndGrowIfNeeded(newMemUsed);
227 uint32_t mask = _numEntries-1;
228 uint32_t hash = key.hash();
229
230 Value result = 0;
231 for (uint32_t i = hash;; ++i) {
232 Entry& e = entries[i & mask];
233 if (e.value == 0) {
234 e.value = value;
235 ++_size;
237 e.key.copy(key);
238 result = e.value;
239 break;
240 }
241 while (e.key.isEmpty()) ;
242 if (e.key.matches(key)) {
243 result = e.value;
244 break;
245 }
246 }
247 unlockEntries(entries);
248 return result;
249 }
250
251 template <typename Fn>
252 void foreach(Fn& fn)
253 {
254 Entry* entries = getEntries();
255 for (uint32_t i = 0; i < _numEntries; ++i) {
256 Value v = entries[i].value;
257 if (v) fn(v);
258 }
259 }
260
261private:
263 {
264 while (1) {
265 Entry* entries = _entries;
266 if (entries) return entries;
267 }
268 }
269
271 {
272 while (1) {
273 Entry* entries = _entries;
274 if (entries && AtomicCompareAndSwap(&_entries, entries, (Entry*)0)) {
275 return entries;
276 }
277 }
278 }
279
280 void unlockEntries(Entry* entries)
281 {
282 AtomicStore(&_entries, entries);
283 }
284
286 {
287 Entry* entries = lockEntries();
288 if (_size*2 >= _numEntries) {
289 entries = grow(entries, newMemUsed);
290 }
291 return entries;
292 }
293
294 Entry* grow(Entry* oldEntries, size_t& newMemUsed)
295 {
296 _oldEntries.push_back(oldEntries);
297 uint32_t numNewEntries = _numEntries*2;
298 Entry* entries = new Entry[numNewEntries];
299 newMemUsed = numNewEntries * sizeof(Entry);
300 uint32_t mask = numNewEntries-1;
301 for (uint32_t oldIndex = 0; oldIndex < _numEntries; ++oldIndex) {
302 Entry& oldEntry = oldEntries[oldIndex];
303 if (oldEntry.value) {
304 for (int newIndex = oldEntry.key.hash();; ++newIndex) {
305 Entry& newEntry = entries[newIndex&mask];
306 if (!newEntry.value) {
307 newEntry.key.move(oldEntry.key);
308 newEntry.value = oldEntry.value;
309 break;
310 }
311 }
312 }
313 }
314 _numEntries = numNewEntries;
315 return entries;
316 }
317
318 Entry* volatile _entries;
319 uint32_t volatile _numEntries;
320 uint32_t volatile _size;
321 std::vector<Entry*> _oldEntries;
322};
323
325
326#endif
PTEX_NAMESPACE_BEGIN uint32_t memHash(const char *val, int len)
Definition: PtexHashMap.h:49
bool memCompare(const char *a, const char *b, int len)
Definition: PtexHashMap.h:69
Platform-specific classes, functions, and includes.
PTEX_INLINE void AtomicStore(T volatile *target, T value)
Definition: PtexPlatform.h:284
PTEX_INLINE void PtexMemoryFence()
Definition: PtexPlatform.h:290
PTEX_INLINE bool AtomicCompareAndSwap(T volatile *target, T oldvalue, T newvalue)
Definition: PtexPlatform.h:278
#define PTEX_NAMESPACE_END
Definition: PtexVersion.h:62
IntKey(int val)
Definition: PtexHashMap.h:142
uint32_t hash() volatile
Definition: PtexHashMap.h:147
bool matches(const IntKey &key) volatile
Definition: PtexHashMap.h:145
int _val
Definition: PtexHashMap.h:138
void copy(volatile IntKey &key) volatile
Definition: PtexHashMap.h:143
bool isEmpty() volatile
Definition: PtexHashMap.h:146
void move(volatile IntKey &key) volatile
Definition: PtexHashMap.h:144
Key volatile key
Definition: PtexHashMap.h:158
Entry(const Entry &)
void operator=(const Entry &)
Value volatile value
Definition: PtexHashMap.h:159
Entry * getEntries()
Definition: PtexHashMap.h:262
uint32_t size() const
Definition: PtexHashMap.h:201
void deleteContents()
Definition: PtexHashMap.h:172
PtexHashMap(const PtexHashMap &)
Entry *volatile _entries
Definition: PtexHashMap.h:318
Value get(Key &key)
Definition: PtexHashMap.h:203
void clear()
Definition: PtexHashMap.h:195
void unlockEntries(Entry *entries)
Definition: PtexHashMap.h:280
uint32_t volatile _size
Definition: PtexHashMap.h:320
uint32_t volatile _numEntries
Definition: PtexHashMap.h:319
void initContents()
Definition: PtexHashMap.h:165
void operator=(const PtexHashMap &)
Value tryInsert(Key &key, Value value, size_t &newMemUsed)
Definition: PtexHashMap.h:224
Entry * grow(Entry *oldEntries, size_t &newMemUsed)
Definition: PtexHashMap.h:294
std::vector< Entry * > _oldEntries
Definition: PtexHashMap.h:321
Entry * lockEntries()
Definition: PtexHashMap.h:270
Entry * lockEntriesAndGrowIfNeeded(size_t &newMemUsed)
Definition: PtexHashMap.h:285
StringKey(const char *val)
Definition: PtexHashMap.h:94
uint32_t hash() volatile
Definition: PtexHashMap.h:130
const char *volatile _val
Definition: PtexHashMap.h:84
bool matches(const StringKey &key) volatile
Definition: PtexHashMap.h:123
uint32_t volatile _hash
Definition: PtexHashMap.h:86
bool isEmpty() volatile
Definition: PtexHashMap.h:128
uint32_t volatile _len
Definition: PtexHashMap.h:85
void operator=(const StringKey &key)
bool volatile _ownsVal
Definition: PtexHashMap.h:87
void move(volatile StringKey &key) volatile
Definition: PtexHashMap.h:114
void copy(volatile StringKey &key) volatile
Definition: PtexHashMap.h:104
StringKey(const StringKey &key)