OpenShot Audio Library | OpenShotAudio  0.3.0
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 
23 namespace 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 //==============================================================================
99 template <typename KeyType,
100  typename ValueType,
101  class HashFunctionType = DefaultHashFunctions,
102  class TypeOfCriticalSectionToUse = DummyCriticalSection>
103 class HashMap
104 {
105 private:
106  using KeyTypeParameter = typename TypeHelpers::ParameterType<KeyType>::type;
107  using ValueTypeParameter = typename TypeHelpers::ParameterType<ValueType>::type;
108 
109 public:
110  //==============================================================================
121  explicit HashMap (int numberOfSlots = defaultHashTableSize,
122  HashFunctionType hashFunction = HashFunctionType())
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 
303  void remapTable (int newNumberOfSlots)
304  {
305  const ScopedLockType sl (getLock());
306 
307  Array<HashEntry*> newSlots;
308  newSlots.insertMultiple (0, nullptr, newNumberOfSlots);
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 
332  inline int getNumSlots() const noexcept
333  {
334  return hashSlots.size();
335  }
336 
337  //==============================================================================
339  template <class OtherHashMapType>
340  void swapWith (OtherHashMapType& otherHashMap) noexcept
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 
359 private:
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 
375 public:
376  //==============================================================================
399  struct Iterator
400  {
401  Iterator (const HashMap& hashMapToIterate) noexcept
402  : hashMap (hashMapToIterate), entry (nullptr), index (0)
403  {}
404 
405  Iterator (const Iterator& other) noexcept
406  : hashMap (other.hashMap), entry (other.entry), index (other.index)
407  {}
408 
413  bool next() noexcept
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 
432  KeyType getKey() const
433  {
434  return entry != nullptr ? entry->key : KeyType();
435  }
436 
440  ValueType getValue() const
441  {
442  return entry != nullptr ? entry->value : ValueType();
443  }
444 
446  void reset() noexcept
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 
475 private:
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
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
ValueType & getReference(KeyTypeParameter keyToLookFor)
Definition: juce_HashMap.h:185
int getNumSlots() const noexcept
Definition: juce_HashMap.h:332
bool containsValue(ValueTypeParameter valueToLookFor) const
Definition: juce_HashMap.h:215
Iterator begin() const noexcept
Definition: juce_HashMap.h:470
ValueType operator[](KeyTypeParameter keyToLookFor) const
Definition: juce_HashMap.h:170
void swapWith(OtherHashMapType &otherHashMap) noexcept
Definition: juce_HashMap.h:340
void remove(KeyTypeParameter keyToRemove)
Definition: juce_HashMap.h:235
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Definition: juce_HashMap.h:232
void remapTable(int newNumberOfSlots)
Definition: juce_HashMap.h:303
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition: juce_HashMap.h:354
bool contains(KeyTypeParameter keyToLookFor) const
Definition: juce_HashMap.h:207
void removeValue(ValueTypeParameter valueToRemove)
Definition: juce_HashMap.h:266
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Definition: juce_HashMap.h:357
Iterator end() const noexcept
Definition: juce_HashMap.h:473
int size() const noexcept
Definition: juce_HashMap.h:161
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Definition: juce_HashMap.h:121
static int generateHash(const void *key, int upperLimit) noexcept
Definition: juce_HashMap.h:49
static int generateHash(int32 key, int upperLimit) noexcept
Definition: juce_HashMap.h:39
static int generateHash(const String &key, int upperLimit) noexcept
Definition: juce_HashMap.h:45
static int generateHash(int64 key, int upperLimit) noexcept
Definition: juce_HashMap.h:43
static int generateHash(uint64 key, int upperLimit) noexcept
Definition: juce_HashMap.h:41
static int generateHash(const Uuid &key, int upperLimit) noexcept
Definition: juce_HashMap.h:51
static int generateHash(const var &key, int upperLimit) noexcept
Definition: juce_HashMap.h:47
static int generateHash(uint32 key, int upperLimit) noexcept
Definition: juce_HashMap.h:37
ValueType getValue() const
Definition: juce_HashMap.h:440
bool next() noexcept
Definition: juce_HashMap.h:413
KeyType getKey() const
Definition: juce_HashMap.h:432
void reset() noexcept
Definition: juce_HashMap.h:446