OpenShot Library | libopenshot-audio 0.2.0
juce_HashMap.h
1
2/** @weakgroup juce_core-containers
3 * @{
4 */
5/*
6 ==============================================================================
7
8 This file is part of the JUCE library.
9 Copyright (c) 2017 - ROLI Ltd.
10
11 JUCE is an open source library subject to commercial or open-source
12 licensing.
13
14 The code included in this file is provided under the terms of the ISC license
15 http://www.isc.org/downloads/software-support-policy/isc-license. Permission
16 To use, copy, modify, and/or distribute this software for any purpose with or
17 without fee is hereby granted provided that the above copyright notice and
18 this permission notice appear in all copies.
19
20 JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
21 EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
22 DISCLAIMED.
23
24 ==============================================================================
25*/
26
27namespace juce
28{
29
30//==============================================================================
31/**
32 A simple class to generate hash functions for some primitive types, intended for
33 use with the HashMap class.
34 @see HashMap
35
36 @tags{Core}
37*/
39{
40 /** Generates a simple hash from an unsigned int. */
41 static int generateHash (uint32 key, int upperLimit) noexcept { return (int) (key % (uint32) upperLimit); }
42 /** Generates a simple hash from an integer. */
43 static int generateHash (int32 key, int upperLimit) noexcept { return generateHash ((uint32) key, upperLimit); }
44 /** Generates a simple hash from a uint64. */
45 static int generateHash (uint64 key, int upperLimit) noexcept { return (int) (key % (uint64) upperLimit); }
46 /** Generates a simple hash from an int64. */
47 static int generateHash (int64 key, int upperLimit) noexcept { return generateHash ((uint64) key, upperLimit); }
48 /** Generates a simple hash from a string. */
49 static int generateHash (const String& key, int upperLimit) noexcept { return generateHash ((uint32) key.hashCode(), upperLimit); }
50 /** Generates a simple hash from a variant. */
51 static int generateHash (const var& key, int upperLimit) noexcept { return generateHash (key.toString(), upperLimit); }
52 /** Generates a simple hash from a void ptr. */
53 static int generateHash (const void* key, int upperLimit) noexcept { return generateHash ((uint64) (pointer_sized_uint) key, upperLimit); }
54 /** Generates a simple hash from a UUID. */
55 static int generateHash (const Uuid& key, int upperLimit) noexcept { return generateHash (key.hash(), upperLimit); }
56};
57
58
59//==============================================================================
60/**
61 Holds a set of mappings between some key/value pairs.
62
63 The types of the key and value objects are set as template parameters.
64 You can also specify a class to supply a hash function that converts a key value
65 into an hashed integer. This class must have the form:
66
67 @code
68 struct MyHashGenerator
69 {
70 int generateHash (MyKeyType key, int upperLimit) const
71 {
72 // The function must return a value 0 <= x < upperLimit
73 return someFunctionOfMyKeyType (key) % upperLimit;
74 }
75 };
76 @endcode
77
78 Like the Array class, the key and value types are expected to be copy-by-value
79 types, so if you define them to be pointer types, this class won't delete the
80 objects that they point to.
81
82 If you don't supply a class for the HashFunctionType template parameter, the
83 default one provides some simple mappings for strings and ints.
84
85 @code
86 HashMap<int, String> hash;
87 hash.set (1, "item1");
88 hash.set (2, "item2");
89
90 DBG (hash [1]); // prints "item1"
91 DBG (hash [2]); // prints "item2"
92
93 // This iterates the map, printing all of its key -> value pairs..
94 for (HashMap<int, String>::Iterator i (hash); i.next();)
95 DBG (i.getKey() << " -> " << i.getValue());
96 @endcode
97
98 @tparam HashFunctionType The class of hash function, which must be copy-constructible.
99 @see CriticalSection, DefaultHashFunctions, NamedValueSet, SortedSet
100
101 @tags{Core}
102*/
103template <typename KeyType,
104 typename ValueType,
105 class HashFunctionType = DefaultHashFunctions,
106 class TypeOfCriticalSectionToUse = DummyCriticalSection>
108{
109private:
110 using KeyTypeParameter = typename TypeHelpers::ParameterType<KeyType>::type;
111 using ValueTypeParameter = typename TypeHelpers::ParameterType<ValueType>::type;
112
113public:
114 //==============================================================================
115 /** Creates an empty hash-map.
116
117 @param numberOfSlots Specifies the number of hash entries the map will use. This will be
118 the "upperLimit" parameter that is passed to your generateHash()
119 function. The number of hash slots will grow automatically if necessary,
120 or it can be remapped manually using remapTable().
121 @param hashFunction An instance of HashFunctionType, which will be copied and
122 stored to use with the HashMap. This parameter can be omitted
123 if HashFunctionType has a default constructor.
124 */
125 explicit HashMap (int numberOfSlots = defaultHashTableSize,
126 HashFunctionType hashFunction = HashFunctionType())
127 : hashFunctionToUse (hashFunction)
128 {
129 hashSlots.insertMultiple (0, nullptr, numberOfSlots);
130 }
131
132 /** Destructor. */
134 {
135 clear();
136 }
137
138 //==============================================================================
139 /** Removes all values from the map.
140 Note that this will clear the content, but won't affect the number of slots (see
141 remapTable and getNumSlots).
142 */
143 void clear()
144 {
145 const ScopedLockType sl (getLock());
146
147 for (auto i = hashSlots.size(); --i >= 0;)
148 {
149 auto* h = hashSlots.getUnchecked(i);
150
151 while (h != nullptr)
152 {
153 const std::unique_ptr<HashEntry> deleter (h);
154 h = h->nextEntry;
155 }
156
157 hashSlots.set (i, nullptr);
158 }
159
160 totalNumItems = 0;
161 }
162
163 //==============================================================================
164 /** Returns the current number of items in the map. */
165 inline int size() const noexcept
166 {
167 return totalNumItems;
168 }
169
170 /** Returns the value corresponding to a given key.
171 If the map doesn't contain the key, a default instance of the value type is returned.
172 @param keyToLookFor the key of the item being requested
173 */
174 inline ValueType operator[] (KeyTypeParameter keyToLookFor) const
175 {
176 const ScopedLockType sl (getLock());
177
178 if (auto* entry = getEntry (getSlot (keyToLookFor), keyToLookFor))
179 return entry->value;
180
181 return ValueType();
182 }
183
184 /** Returns a reference to the value corresponding to a given key.
185 If the map doesn't contain the key, a default instance of the value type is
186 added to the map and a reference to this is returned.
187 @param keyToLookFor the key of the item being requested
188 */
189 inline ValueType& getReference (KeyTypeParameter keyToLookFor)
190 {
191 const ScopedLockType sl (getLock());
192 auto hashIndex = generateHashFor (keyToLookFor, getNumSlots());
193
194 auto* firstEntry = hashSlots.getUnchecked (hashIndex);
195
196 if (auto* entry = getEntry (firstEntry, keyToLookFor))
197 return entry->value;
198
199 auto* entry = new HashEntry (keyToLookFor, ValueType(), firstEntry);
200 hashSlots.set (hashIndex, entry);
201 ++totalNumItems;
202
203 if (totalNumItems > (getNumSlots() * 3) / 2)
204 remapTable (getNumSlots() * 2);
205
206 return entry->value;
207 }
208
209 //==============================================================================
210 /** Returns true if the map contains an item with the specied key. */
211 bool contains (KeyTypeParameter keyToLookFor) const
212 {
213 const ScopedLockType sl (getLock());
214
215 return (getEntry (getSlot (keyToLookFor), keyToLookFor) != nullptr);
216 }
217
218 /** Returns true if the hash contains at least one occurrence of a given value. */
219 bool containsValue (ValueTypeParameter valueToLookFor) const
220 {
221 const ScopedLockType sl (getLock());
222
223 for (auto i = getNumSlots(); --i >= 0;)
224 for (auto* entry = hashSlots.getUnchecked(i); entry != nullptr; entry = entry->nextEntry)
225 if (entry->value == valueToLookFor)
226 return true;
227
228 return false;
229 }
230
231 //==============================================================================
232 /** Adds or replaces an element in the hash-map.
233 If there's already an item with the given key, this will replace its value. Otherwise, a new item
234 will be added to the map.
235 */
236 void set (KeyTypeParameter newKey, ValueTypeParameter newValue) { getReference (newKey) = newValue; }
237
238 /** Removes an item with the given key. */
239 void remove (KeyTypeParameter keyToRemove)
240 {
241 const ScopedLockType sl (getLock());
242 auto hashIndex = generateHashFor (keyToRemove, getNumSlots());
243 auto* entry = hashSlots.getUnchecked (hashIndex);
244 HashEntry* previous = nullptr;
245
246 while (entry != nullptr)
247 {
248 if (entry->key == keyToRemove)
249 {
250 const std::unique_ptr<HashEntry> deleter (entry);
251
252 entry = entry->nextEntry;
253
254 if (previous != nullptr)
255 previous->nextEntry = entry;
256 else
257 hashSlots.set (hashIndex, entry);
258
259 --totalNumItems;
260 }
261 else
262 {
263 previous = entry;
264 entry = entry->nextEntry;
265 }
266 }
267 }
268
269 /** Removes all items with the given value. */
270 void removeValue (ValueTypeParameter valueToRemove)
271 {
272 const ScopedLockType sl (getLock());
273
274 for (auto i = getNumSlots(); --i >= 0;)
275 {
276 auto* entry = hashSlots.getUnchecked(i);
277 HashEntry* previous = nullptr;
278
279 while (entry != nullptr)
280 {
281 if (entry->value == valueToRemove)
282 {
283 const std::unique_ptr<HashEntry> deleter (entry);
284
285 entry = entry->nextEntry;
286
287 if (previous != nullptr)
288 previous->nextEntry = entry;
289 else
290 hashSlots.set (i, entry);
291
292 --totalNumItems;
293 }
294 else
295 {
296 previous = entry;
297 entry = entry->nextEntry;
298 }
299 }
300 }
301 }
302
303 /** Remaps the hash-map to use a different number of slots for its hash function.
304 Each slot corresponds to a single hash-code, and each one can contain multiple items.
305 @see getNumSlots()
306 */
307 void remapTable (int newNumberOfSlots)
308 {
309 const ScopedLockType sl (getLock());
310
311 Array<HashEntry*> newSlots;
312 newSlots.insertMultiple (0, nullptr, newNumberOfSlots);
313
314 for (auto i = getNumSlots(); --i >= 0;)
315 {
316 HashEntry* nextEntry = nullptr;
317
318 for (auto* entry = hashSlots.getUnchecked(i); entry != nullptr; entry = nextEntry)
319 {
320 auto hashIndex = generateHashFor (entry->key, newNumberOfSlots);
321
322 nextEntry = entry->nextEntry;
323 entry->nextEntry = newSlots.getUnchecked (hashIndex);
324
325 newSlots.set (hashIndex, entry);
326 }
327 }
328
329 hashSlots.swapWith (newSlots);
330 }
331
332 /** Returns the number of slots which are available for hashing.
333 Each slot corresponds to a single hash-code, and each one can contain multiple items.
334 @see getNumSlots()
335 */
336 inline int getNumSlots() const noexcept
337 {
338 return hashSlots.size();
339 }
340
341 //==============================================================================
342 /** Efficiently swaps the contents of two hash-maps. */
343 template <class OtherHashMapType>
344 void swapWith (OtherHashMapType& otherHashMap) noexcept
345 {
346 const ScopedLockType lock1 (getLock());
347 const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
348
349 hashSlots.swapWith (otherHashMap.hashSlots);
350 std::swap (totalNumItems, otherHashMap.totalNumItems);
351 }
352
353 //==============================================================================
354 /** Returns the CriticalSection that locks this structure.
355 To lock, you can call getLock().enter() and getLock().exit(), or preferably use
356 an object of ScopedLockType as an RAII lock for it.
357 */
358 inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return lock; }
359
360 /** Returns the type of scoped lock to use for locking this array */
361 using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
362
363private:
364 //==============================================================================
365 class HashEntry
366 {
367 public:
368 HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry* const next)
369 : key (k), value (val), nextEntry (next)
370 {}
371
372 const KeyType key;
373 ValueType value;
374 HashEntry* nextEntry;
375
376 JUCE_DECLARE_NON_COPYABLE (HashEntry)
377 };
378
379public:
380 //==============================================================================
381 /** Iterates over the items in a HashMap.
382
383 To use it, repeatedly call next() until it returns false, e.g.
384 @code
385 HashMap <String, String> myMap;
386
387 HashMap<String, String>::Iterator i (myMap);
388
389 while (i.next())
390 {
391 DBG (i.getKey() << " -> " << i.getValue());
392 }
393 @endcode
394
395 The order in which items are iterated bears no resemblance to the order in which
396 they were originally added!
397
398 Obviously as soon as you call any non-const methods on the original hash-map, any
399 iterators that were created beforehand will cease to be valid, and should not be used.
400
401 @see HashMap
402 */
403 struct Iterator
404 {
405 Iterator (const HashMap& hashMapToIterate) noexcept
406 : hashMap (hashMapToIterate), entry (nullptr), index (0)
407 {}
408
409 Iterator (const Iterator& other) noexcept
410 : hashMap (other.hashMap), entry (other.entry), index (other.index)
411 {}
412
413 /** Moves to the next item, if one is available.
414 When this returns true, you can get the item's key and value using getKey() and
415 getValue(). If it returns false, the iteration has finished and you should stop.
416 */
417 bool next() noexcept
418 {
419 if (entry != nullptr)
420 entry = entry->nextEntry;
421
422 while (entry == nullptr)
423 {
424 if (index >= hashMap.getNumSlots())
425 return false;
426
427 entry = hashMap.hashSlots.getUnchecked (index++);
428 }
429
430 return true;
431 }
432
433 /** Returns the current item's key.
434 This should only be called when a call to next() has just returned true.
435 */
436 KeyType getKey() const
437 {
438 return entry != nullptr ? entry->key : KeyType();
439 }
440
441 /** Returns the current item's value.
442 This should only be called when a call to next() has just returned true.
443 */
444 ValueType getValue() const
445 {
446 return entry != nullptr ? entry->value : ValueType();
447 }
448
449 /** Resets the iterator to its starting position. */
450 void reset() noexcept
451 {
452 entry = nullptr;
453 index = 0;
454 }
455
456 Iterator& operator++() noexcept { next(); return *this; }
457 ValueType operator*() const { return getValue(); }
458 bool operator!= (const Iterator& other) const noexcept { return entry != other.entry || index != other.index; }
459 void resetToEnd() noexcept { index = hashMap.getNumSlots(); }
460
461 private:
462 //==============================================================================
463 const HashMap& hashMap;
464 HashEntry* entry;
465 int index;
466
467 // using the copy constructor is ok, but you cannot assign iterators
468 Iterator& operator= (const Iterator&) = delete;
469
470 JUCE_LEAK_DETECTOR (Iterator)
471 };
472
473 /** Returns a start iterator for the values in this tree. */
474 Iterator begin() const noexcept { Iterator i (*this); i.next(); return i; }
475
476 /** Returns an end iterator for the values in this tree. */
477 Iterator end() const noexcept { Iterator i (*this); i.resetToEnd(); return i; }
478
479private:
480 //==============================================================================
481 enum { defaultHashTableSize = 101 };
482 friend struct Iterator;
483
484 HashFunctionType hashFunctionToUse;
485 Array<HashEntry*> hashSlots;
486 int totalNumItems = 0;
487 TypeOfCriticalSectionToUse lock;
488
489 int generateHashFor (KeyTypeParameter key, int numSlots) const
490 {
491 const int hash = hashFunctionToUse.generateHash (key, numSlots);
492 jassert (isPositiveAndBelow (hash, numSlots)); // your hash function is generating out-of-range numbers!
493 return hash;
494 }
495
496 static inline HashEntry* getEntry (HashEntry* firstEntry, KeyType keyToLookFor) noexcept
497 {
498 for (auto* entry = firstEntry; entry != nullptr; entry = entry->nextEntry)
499 if (entry->key == keyToLookFor)
500 return entry;
501
502 return nullptr;
503 }
504
505 inline HashEntry* getSlot (KeyType key) const noexcept { return hashSlots.getUnchecked (generateHashFor (key, getNumSlots())); }
506
507 JUCE_DECLARE_NON_COPYABLE_WITH_LEAK_DETECTOR (HashMap)
508};
509
510} // namespace juce
511
512/** @}*/
Holds a resizable array of primitive or copy-by-value objects.
Definition juce_Array.h:60
void swapWith(OtherArrayType &otherArray) noexcept
This swaps the contents of this array with those of another array.
Definition juce_Array.h:578
ElementType getUnchecked(int index) const
Returns one of the elements in the array, without checking the index passed in.
Definition juce_Array.h:256
int size() const noexcept
Returns the current number of elements in the array.
Definition juce_Array.h:219
void set(int indexToChange, ParameterType newValue)
Replaces an element with a new value.
Definition juce_Array.h:499
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
Inserts multiple copies of an element into the array at a given position.
Definition juce_Array.h:437
Holds a set of mappings between some key/value pairs.
~HashMap()
Destructor.
int getNumSlots() const noexcept
Returns the number of slots which are available for hashing.
bool containsValue(ValueTypeParameter valueToLookFor) const
Returns true if the hash contains at least one occurrence of a given value.
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this structure.
Iterator begin() const noexcept
Returns a start iterator for the values in this tree.
ValueType operator[](KeyTypeParameter keyToLookFor) const
Returns the value corresponding to a given key.
void swapWith(OtherHashMapType &otherHashMap) noexcept
Efficiently swaps the contents of two hash-maps.
void remove(KeyTypeParameter keyToRemove)
Removes an item with the given key.
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Adds or replaces an element in the hash-map.
void remapTable(int newNumberOfSlots)
Remaps the hash-map to use a different number of slots for its hash function.
bool contains(KeyTypeParameter keyToLookFor) const
Returns true if the map contains an item with the specied key.
void removeValue(ValueTypeParameter valueToRemove)
Removes all items with the given value.
void clear()
Removes all values from the map.
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Returns the type of scoped lock to use for locking this array.
Iterator end() const noexcept
Returns an end iterator for the values in this tree.
ValueType & getReference(KeyTypeParameter keyToLookFor)
Returns a reference to the value corresponding to a given key.
int size() const noexcept
Returns the current number of items in the map.
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Creates an empty hash-map.
The JUCE String class!
Definition juce_String.h:43
A universally unique 128-bit identifier.
Definition juce_Uuid.h:43
A variant class, that can be used to hold a range of primitive values.
A simple class to generate hash functions for some primitive types, intended for use with the HashMap...
static int generateHash(const void *key, int upperLimit) noexcept
Generates a simple hash from a void ptr.
static int generateHash(int32 key, int upperLimit) noexcept
Generates a simple hash from an integer.
static int generateHash(const String &key, int upperLimit) noexcept
Generates a simple hash from a string.
static int generateHash(int64 key, int upperLimit) noexcept
Generates a simple hash from an int64.
static int generateHash(uint64 key, int upperLimit) noexcept
Generates a simple hash from a uint64.
static int generateHash(const Uuid &key, int upperLimit) noexcept
Generates a simple hash from a UUID.
static int generateHash(const var &key, int upperLimit) noexcept
Generates a simple hash from a variant.
static int generateHash(uint32 key, int upperLimit) noexcept
Generates a simple hash from an unsigned int.
Iterates over the items in a HashMap.
ValueType getValue() const
Returns the current item's value.
bool next() noexcept
Moves to the next item, if one is available.
KeyType getKey() const
Returns the current item's key.
void reset() noexcept
Resets the iterator to its starting position.