OpenShot Audio Library | OpenShotAudio 0.3.2
Loading...
Searching...
No Matches
juce_HashMap.h
1/*
2 ==============================================================================
3
4 This file is part of the JUCE library.
5 Copyright (c) 2017 - ROLI Ltd.
6
7 JUCE is an open source library subject to commercial or open-source
8 licensing.
9
10 The code included in this file is provided under the terms of the ISC license
11 http://www.isc.org/downloads/software-support-policy/isc-license. Permission
12 To use, copy, modify, and/or distribute this software for any purpose with or
13 without fee is hereby granted provided that the above copyright notice and
14 this permission notice appear in all copies.
15
16 JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
17 EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
18 DISCLAIMED.
19
20 ==============================================================================
21*/
22
23namespace juce
24{
25
26//==============================================================================
35{
37 static int generateHash (uint32 key, int upperLimit) noexcept { return (int) (key % (uint32) upperLimit); }
39 static int generateHash (int32 key, int upperLimit) noexcept { return generateHash ((uint32) key, upperLimit); }
41 static int generateHash (uint64 key, int upperLimit) noexcept { return (int) (key % (uint64) upperLimit); }
43 static int generateHash (int64 key, int upperLimit) noexcept { return generateHash ((uint64) key, upperLimit); }
45 static int generateHash (const String& key, int upperLimit) noexcept { return generateHash ((uint32) key.hashCode(), upperLimit); }
47 static int generateHash (const var& key, int upperLimit) noexcept { return generateHash (key.toString(), upperLimit); }
49 static int generateHash (const void* key, int upperLimit) noexcept { return generateHash ((uint64) (pointer_sized_uint) key, upperLimit); }
51 static int generateHash (const Uuid& key, int upperLimit) noexcept { return generateHash (key.hash(), upperLimit); }
52};
53
54
55//==============================================================================
99template <typename KeyType,
100 typename ValueType,
101 class HashFunctionType = DefaultHashFunctions,
102 class TypeOfCriticalSectionToUse = DummyCriticalSection>
104{
105private:
106 using KeyTypeParameter = typename TypeHelpers::ParameterType<KeyType>::type;
107 using ValueTypeParameter = typename TypeHelpers::ParameterType<ValueType>::type;
108
109public:
110 //==============================================================================
121 explicit HashMap (int numberOfSlots = defaultHashTableSize,
123 : hashFunctionToUse (hashFunction)
124 {
125 hashSlots.insertMultiple (0, nullptr, numberOfSlots);
126 }
127
130 {
131 clear();
132 }
133
134 //==============================================================================
139 void clear()
140 {
141 const ScopedLockType sl (getLock());
142
143 for (auto i = hashSlots.size(); --i >= 0;)
144 {
145 auto* h = hashSlots.getUnchecked(i);
146
147 while (h != nullptr)
148 {
149 const std::unique_ptr<HashEntry> deleter (h);
150 h = h->nextEntry;
151 }
152
153 hashSlots.set (i, nullptr);
154 }
155
156 totalNumItems = 0;
157 }
158
159 //==============================================================================
161 inline int size() const noexcept
162 {
163 return totalNumItems;
164 }
165
170 inline ValueType operator[] (KeyTypeParameter keyToLookFor) const
171 {
172 const ScopedLockType sl (getLock());
173
174 if (auto* entry = getEntry (getSlot (keyToLookFor), keyToLookFor))
175 return entry->value;
176
177 return ValueType();
178 }
179
185 inline ValueType& getReference (KeyTypeParameter keyToLookFor)
186 {
187 const ScopedLockType sl (getLock());
188 auto hashIndex = generateHashFor (keyToLookFor, getNumSlots());
189
190 auto* firstEntry = hashSlots.getUnchecked (hashIndex);
191
192 if (auto* entry = getEntry (firstEntry, keyToLookFor))
193 return entry->value;
194
195 auto* entry = new HashEntry (keyToLookFor, ValueType(), firstEntry);
196 hashSlots.set (hashIndex, entry);
197 ++totalNumItems;
198
199 if (totalNumItems > (getNumSlots() * 3) / 2)
200 remapTable (getNumSlots() * 2);
201
202 return entry->value;
203 }
204
205 //==============================================================================
207 bool contains (KeyTypeParameter keyToLookFor) const
208 {
209 const ScopedLockType sl (getLock());
210
211 return (getEntry (getSlot (keyToLookFor), keyToLookFor) != nullptr);
212 }
213
215 bool containsValue (ValueTypeParameter valueToLookFor) const
216 {
217 const ScopedLockType sl (getLock());
218
219 for (auto i = getNumSlots(); --i >= 0;)
220 for (auto* entry = hashSlots.getUnchecked(i); entry != nullptr; entry = entry->nextEntry)
221 if (entry->value == valueToLookFor)
222 return true;
223
224 return false;
225 }
226
227 //==============================================================================
232 void set (KeyTypeParameter newKey, ValueTypeParameter newValue) { getReference (newKey) = newValue; }
233
235 void remove (KeyTypeParameter keyToRemove)
236 {
237 const ScopedLockType sl (getLock());
238 auto hashIndex = generateHashFor (keyToRemove, getNumSlots());
239 auto* entry = hashSlots.getUnchecked (hashIndex);
240 HashEntry* previous = nullptr;
241
242 while (entry != nullptr)
243 {
244 if (entry->key == keyToRemove)
245 {
246 const std::unique_ptr<HashEntry> deleter (entry);
247
248 entry = entry->nextEntry;
249
250 if (previous != nullptr)
251 previous->nextEntry = entry;
252 else
253 hashSlots.set (hashIndex, entry);
254
255 --totalNumItems;
256 }
257 else
258 {
259 previous = entry;
260 entry = entry->nextEntry;
261 }
262 }
263 }
264
266 void removeValue (ValueTypeParameter valueToRemove)
267 {
268 const ScopedLockType sl (getLock());
269
270 for (auto i = getNumSlots(); --i >= 0;)
271 {
272 auto* entry = hashSlots.getUnchecked(i);
273 HashEntry* previous = nullptr;
274
275 while (entry != nullptr)
276 {
277 if (entry->value == valueToRemove)
278 {
279 const std::unique_ptr<HashEntry> deleter (entry);
280
281 entry = entry->nextEntry;
282
283 if (previous != nullptr)
284 previous->nextEntry = entry;
285 else
286 hashSlots.set (i, entry);
287
288 --totalNumItems;
289 }
290 else
291 {
292 previous = entry;
293 entry = entry->nextEntry;
294 }
295 }
296 }
297 }
298
304 {
305 const ScopedLockType sl (getLock());
306
309
310 for (auto i = getNumSlots(); --i >= 0;)
311 {
312 HashEntry* nextEntry = nullptr;
313
314 for (auto* entry = hashSlots.getUnchecked(i); entry != nullptr; entry = nextEntry)
315 {
316 auto hashIndex = generateHashFor (entry->key, newNumberOfSlots);
317
318 nextEntry = entry->nextEntry;
319 entry->nextEntry = newSlots.getUnchecked (hashIndex);
320
321 newSlots.set (hashIndex, entry);
322 }
323 }
324
325 hashSlots.swapWith (newSlots);
326 }
327
333 {
334 return hashSlots.size();
335 }
336
337 //==============================================================================
339 template <class OtherHashMapType>
341 {
342 const ScopedLockType lock1 (getLock());
343 const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
344
345 hashSlots.swapWith (otherHashMap.hashSlots);
346 std::swap (totalNumItems, otherHashMap.totalNumItems);
347 }
348
349 //==============================================================================
354 inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return lock; }
355
357 using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
358
359private:
360 //==============================================================================
361 class HashEntry
362 {
363 public:
364 HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry* const next)
365 : key (k), value (val), nextEntry (next)
366 {}
367
368 const KeyType key;
369 ValueType value;
370 HashEntry* nextEntry;
371
372 JUCE_DECLARE_NON_COPYABLE (HashEntry)
373 };
374
375public:
376 //==============================================================================
399 struct Iterator
400 {
402 : hashMap (hashMapToIterate), entry (nullptr), index (0)
403 {}
404
406 : hashMap (other.hashMap), entry (other.entry), index (other.index)
407 {}
408
414 {
415 if (entry != nullptr)
416 entry = entry->nextEntry;
417
418 while (entry == nullptr)
419 {
420 if (index >= hashMap.getNumSlots())
421 return false;
422
423 entry = hashMap.hashSlots.getUnchecked (index++);
424 }
425
426 return true;
427 }
428
433 {
434 return entry != nullptr ? entry->key : KeyType();
435 }
436
441 {
442 return entry != nullptr ? entry->value : ValueType();
443 }
444
447 {
448 entry = nullptr;
449 index = 0;
450 }
451
452 Iterator& operator++() noexcept { next(); return *this; }
453 ValueType operator*() const { return getValue(); }
454 bool operator!= (const Iterator& other) const noexcept { return entry != other.entry || index != other.index; }
455 void resetToEnd() noexcept { index = hashMap.getNumSlots(); }
456
457 private:
458 //==============================================================================
459 const HashMap& hashMap;
460 HashEntry* entry;
461 int index;
462
463 // using the copy constructor is ok, but you cannot assign iterators
464 Iterator& operator= (const Iterator&) = delete;
465
466 JUCE_LEAK_DETECTOR (Iterator)
467 };
468
470 Iterator begin() const noexcept { Iterator i (*this); i.next(); return i; }
471
473 Iterator end() const noexcept { Iterator i (*this); i.resetToEnd(); return i; }
474
475private:
476 //==============================================================================
477 enum { defaultHashTableSize = 101 };
478 friend struct Iterator;
479
480 HashFunctionType hashFunctionToUse;
481 Array<HashEntry*> hashSlots;
482 int totalNumItems = 0;
483 TypeOfCriticalSectionToUse lock;
484
485 int generateHashFor (KeyTypeParameter key, int numSlots) const
486 {
487 const int hash = hashFunctionToUse.generateHash (key, numSlots);
488 jassert (isPositiveAndBelow (hash, numSlots)); // your hash function is generating out-of-range numbers!
489 return hash;
490 }
491
492 static inline HashEntry* getEntry (HashEntry* firstEntry, KeyType keyToLookFor) noexcept
493 {
494 for (auto* entry = firstEntry; entry != nullptr; entry = entry->nextEntry)
495 if (entry->key == keyToLookFor)
496 return entry;
497
498 return nullptr;
499 }
500
501 inline HashEntry* getSlot (KeyType key) const noexcept { return hashSlots.getUnchecked (generateHashFor (key, getNumSlots())); }
502
503 JUCE_DECLARE_NON_COPYABLE_WITH_LEAK_DETECTOR (HashMap)
504};
505
506} // namespace juce
void swapWith(OtherArrayType &otherArray) noexcept
Definition juce_Array.h:621
ElementType getUnchecked(int index) const
Definition juce_Array.h:252
const TypeOfCriticalSectionToUse & getLock() const noexcept
int size() const noexcept
Definition juce_Array.h:215
void set(int indexToChange, ParameterType newValue)
Definition juce_Array.h:542
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
Definition juce_Array.h:480
int getNumSlots() const noexcept
bool containsValue(ValueTypeParameter valueToLookFor) const
const TypeOfCriticalSectionToUse & getLock() const noexcept
Iterator begin() const noexcept
ValueType operator[](KeyTypeParameter keyToLookFor) const
void swapWith(OtherHashMapType &otherHashMap) noexcept
void remove(KeyTypeParameter keyToRemove)
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
void remapTable(int newNumberOfSlots)
bool contains(KeyTypeParameter keyToLookFor) const
void removeValue(ValueTypeParameter valueToRemove)
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Iterator end() const noexcept
ValueType & getReference(KeyTypeParameter keyToLookFor)
int size() const noexcept
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
static int generateHash(const void *key, int upperLimit) noexcept
static int generateHash(int32 key, int upperLimit) noexcept
static int generateHash(const String &key, int upperLimit) noexcept
static int generateHash(int64 key, int upperLimit) noexcept
static int generateHash(uint64 key, int upperLimit) noexcept
static int generateHash(const Uuid &key, int upperLimit) noexcept
static int generateHash(const var &key, int upperLimit) noexcept
static int generateHash(uint32 key, int upperLimit) noexcept
ValueType getValue() const
KeyType getKey() const
void reset() noexcept