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)
PTEX_INLINE void PtexMemoryFence()
PTEX_INLINE bool AtomicCompareAndSwap(T volatile *target, T oldvalue, T newvalue)
#define PTEX_NAMESPACE_END
Definition PtexVersion.h:62
IntKey(int val)
uint32_t hash() volatile
bool matches(const IntKey &key) volatile
void copy(volatile IntKey &key) volatile
bool isEmpty() volatile
void move(volatile IntKey &key) volatile
Key volatile key
Entry(const Entry &)
void operator=(const Entry &)
Value volatile value
Entry * getEntries()
uint32_t size() const
void deleteContents()
PtexHashMap(const PtexHashMap &)
Entry *volatile _entries
Value get(Key &key)
void unlockEntries(Entry *entries)
uint32_t volatile _size
uint32_t volatile _numEntries
void initContents()
void operator=(const PtexHashMap &)
Value tryInsert(Key &key, Value value, size_t &newMemUsed)
Entry * grow(Entry *oldEntries, size_t &newMemUsed)
std::vector< Entry * > _oldEntries
Entry * lockEntries()
Entry * lockEntriesAndGrowIfNeeded(size_t &newMemUsed)
StringKey(const char *val)
Definition PtexHashMap.h:94
uint32_t hash() volatile
const char *volatile _val
Definition PtexHashMap.h:84
bool matches(const StringKey &key) volatile
uint32_t volatile _hash
Definition PtexHashMap.h:86
bool isEmpty() volatile
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
void copy(volatile StringKey &key) volatile
StringKey(const StringKey &key)