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 
27 namespace 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 */
103 template <typename KeyType,
104  typename ValueType,
105  class HashFunctionType = DefaultHashFunctions,
106  class TypeOfCriticalSectionToUse = DummyCriticalSection>
107 class HashMap
108 {
109 private:
110  using KeyTypeParameter = typename TypeHelpers::ParameterType<KeyType>::type;
111  using ValueTypeParameter = typename TypeHelpers::ParameterType<ValueType>::type;
112 
113 public:
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 
363 private:
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 
379 public:
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 
479 private:
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 /** @}*/
juce::HashMap::end
Iterator end() const noexcept
Returns an end iterator for the values in this tree.
Definition: juce_HashMap.h:477
juce::DefaultHashFunctions::generateHash
static int generateHash(const void *key, int upperLimit) noexcept
Generates a simple hash from a void ptr.
Definition: juce_HashMap.h:53
juce::HashMap::swapWith
void swapWith(OtherHashMapType &otherHashMap) noexcept
Efficiently swaps the contents of two hash-maps.
Definition: juce_HashMap.h:344
juce::HashMap::getReference
ValueType & getReference(KeyTypeParameter keyToLookFor)
Returns a reference to the value corresponding to a given key.
Definition: juce_HashMap.h:189
juce::Array::insertMultiple
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
juce::Array::swapWith
void swapWith(OtherArrayType &otherArray) noexcept
This swaps the contents of this array with those of another array.
Definition: juce_Array.h:578
juce::HashMap::clear
void clear()
Removes all values from the map.
Definition: juce_HashMap.h:143
juce::DefaultHashFunctions::generateHash
static int generateHash(int64 key, int upperLimit) noexcept
Generates a simple hash from an int64.
Definition: juce_HashMap.h:47
juce::Array::size
int size() const noexcept
Returns the current number of elements in the array.
Definition: juce_Array.h:219
juce::Uuid
A universally unique 128-bit identifier.
Definition: juce_Uuid.h:42
juce::HashMap::remove
void remove(KeyTypeParameter keyToRemove)
Removes an item with the given key.
Definition: juce_HashMap.h:239
juce::Array< HashEntry * >
juce::HashMap
Holds a set of mappings between some key/value pairs.
Definition: juce_HashMap.h:107
juce::HashMap::Iterator::reset
void reset() noexcept
Resets the iterator to its starting position.
Definition: juce_HashMap.h:450
juce::HashMap::Iterator::getValue
ValueType getValue() const
Returns the current item's value.
Definition: juce_HashMap.h:444
juce::HashMap::remapTable
void remapTable(int newNumberOfSlots)
Remaps the hash-map to use a different number of slots for its hash function.
Definition: juce_HashMap.h:307
juce::HashMap::getLock
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this structure.
Definition: juce_HashMap.h:358
juce::HashMap::Iterator
Iterates over the items in a HashMap.
Definition: juce_HashMap.h:403
juce::HashMap::HashMap
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Creates an empty hash-map.
Definition: juce_HashMap.h:125
juce::HashMap::operator[]
ValueType operator[](KeyTypeParameter keyToLookFor) const
Returns the value corresponding to a given key.
Definition: juce_HashMap.h:174
juce::HashMap::removeValue
void removeValue(ValueTypeParameter valueToRemove)
Removes all items with the given value.
Definition: juce_HashMap.h:270
juce::var
A variant class, that can be used to hold a range of primitive values.
Definition: juce_Variant.h:45
juce::DefaultHashFunctions
A simple class to generate hash functions for some primitive types, intended for use with the HashMap...
Definition: juce_HashMap.h:38
juce::DefaultHashFunctions::generateHash
static int generateHash(const Uuid &key, int upperLimit) noexcept
Generates a simple hash from a UUID.
Definition: juce_HashMap.h:55
juce::HashMap< HeavyweightLeakedObjectDetector< OwnerClass > *, String >::ScopedLockType
typename DummyCriticalSection ::ScopedLockType ScopedLockType
Returns the type of scoped lock to use for locking this array.
Definition: juce_HashMap.h:361
juce::Array::getUnchecked
ElementType getUnchecked(int index) const
Returns one of the elements in the array, without checking the index passed in.
Definition: juce_Array.h:256
juce::DefaultHashFunctions::generateHash
static int generateHash(uint32 key, int upperLimit) noexcept
Generates a simple hash from an unsigned int.
Definition: juce_HashMap.h:41
juce::HashMap::Iterator::next
bool next() noexcept
Moves to the next item, if one is available.
Definition: juce_HashMap.h:417
juce::HashMap::getNumSlots
int getNumSlots() const noexcept
Returns the number of slots which are available for hashing.
Definition: juce_HashMap.h:336
juce::HashMap::Iterator::getKey
KeyType getKey() const
Returns the current item's key.
Definition: juce_HashMap.h:436
juce::HashMap::~HashMap
~HashMap()
Destructor.
Definition: juce_HashMap.h:133
juce::DefaultHashFunctions::generateHash
static int generateHash(const String &key, int upperLimit) noexcept
Generates a simple hash from a string.
Definition: juce_HashMap.h:49
juce::HashMap::set
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Adds or replaces an element in the hash-map.
Definition: juce_HashMap.h:236
juce::String
The JUCE String class!
Definition: juce_String.h:42
juce::DefaultHashFunctions::generateHash
static int generateHash(int32 key, int upperLimit) noexcept
Generates a simple hash from an integer.
Definition: juce_HashMap.h:43
juce::HashMap::containsValue
bool containsValue(ValueTypeParameter valueToLookFor) const
Returns true if the hash contains at least one occurrence of a given value.
Definition: juce_HashMap.h:219
juce::HashMap::size
int size() const noexcept
Returns the current number of items in the map.
Definition: juce_HashMap.h:165
juce::HashMap::contains
bool contains(KeyTypeParameter keyToLookFor) const
Returns true if the map contains an item with the specied key.
Definition: juce_HashMap.h:211
juce::HashMap::begin
Iterator begin() const noexcept
Returns a start iterator for the values in this tree.
Definition: juce_HashMap.h:474
juce::Array::set
void set(int indexToChange, ParameterType newValue)
Replaces an element with a new value.
Definition: juce_Array.h:499
juce::DefaultHashFunctions::generateHash
static int generateHash(uint64 key, int upperLimit) noexcept
Generates a simple hash from a uint64.
Definition: juce_HashMap.h:45
juce::DefaultHashFunctions::generateHash
static int generateHash(const var &key, int upperLimit) noexcept
Generates a simple hash from a variant.
Definition: juce_HashMap.h:51