openshot-audio  0.1.6
juce_HashMap.h
Go to the documentation of this file.
1 /*
2  ==============================================================================
3 
4  This file is part of the juce_core module of the JUCE library.
5  Copyright (c) 2015 - ROLI Ltd.
6 
7  Permission to use, copy, modify, and/or distribute this software for any purpose with
8  or without fee is hereby granted, provided that the above copyright notice and this
9  permission notice appear in all copies.
10 
11  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD
12  TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN
13  NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
15  IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
16  CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 
18  ------------------------------------------------------------------------------
19 
20  NOTE! This permissive ISC license applies ONLY to files within the juce_core module!
21  All other JUCE modules are covered by a dual GPL/commercial license, so if you are
22  using any other modules, be sure to check that you also comply with their license.
23 
24  For more details, visit www.juce.com
25 
26  ==============================================================================
27 */
28 
29 #ifndef JUCE_HASHMAP_H_INCLUDED
30 #define JUCE_HASHMAP_H_INCLUDED
31 
32 
33 //==============================================================================
40 {
42  int generateHash (const int key, const int upperLimit) const noexcept { return std::abs (key) % upperLimit; }
44  int generateHash (const int64 key, const int upperLimit) const noexcept { return std::abs ((int) key) % upperLimit; }
46  int generateHash (const String& key, const int upperLimit) const noexcept { return (int) (((uint32) key.hashCode()) % (uint32) upperLimit); }
48  int generateHash (const var& key, const int upperLimit) const noexcept { return generateHash (key.toString(), upperLimit); }
49 };
50 
51 
52 //==============================================================================
94 template <typename KeyType,
95  typename ValueType,
96  class HashFunctionType = DefaultHashFunctions,
97  class TypeOfCriticalSectionToUse = DummyCriticalSection>
98 class HashMap
99 {
100 private:
101  typedef PARAMETER_TYPE (KeyType) KeyTypeParameter;
102  typedef PARAMETER_TYPE (ValueType) ValueTypeParameter;
103 
104 public:
105  //==============================================================================
116  explicit HashMap (int numberOfSlots = defaultHashTableSize,
117  HashFunctionType hashFunction = HashFunctionType())
118  : hashFunctionToUse (hashFunction), totalNumItems (0)
119  {
120  hashSlots.insertMultiple (0, nullptr, numberOfSlots);
121  }
122 
125  {
126  clear();
127  }
128 
129  //==============================================================================
134  void clear()
135  {
136  const ScopedLockType sl (getLock());
137 
138  for (int i = hashSlots.size(); --i >= 0;)
139  {
140  HashEntry* h = hashSlots.getUnchecked(i);
141 
142  while (h != nullptr)
143  {
144  const ScopedPointer<HashEntry> deleter (h);
145  h = h->nextEntry;
146  }
147 
148  hashSlots.set (i, nullptr);
149  }
150 
151  totalNumItems = 0;
152  }
153 
154  //==============================================================================
156  inline int size() const noexcept
157  {
158  return totalNumItems;
159  }
160 
165  inline ValueType operator[] (KeyTypeParameter keyToLookFor) const
166  {
167  const ScopedLockType sl (getLock());
168 
169  for (const HashEntry* entry = hashSlots.getUnchecked (generateHashFor (keyToLookFor)); entry != nullptr; entry = entry->nextEntry)
170  if (entry->key == keyToLookFor)
171  return entry->value;
172 
173  return ValueType();
174  }
175 
176  //==============================================================================
178  bool contains (KeyTypeParameter keyToLookFor) const
179  {
180  const ScopedLockType sl (getLock());
181 
182  for (const HashEntry* entry = hashSlots.getUnchecked (generateHashFor (keyToLookFor)); entry != nullptr; entry = entry->nextEntry)
183  if (entry->key == keyToLookFor)
184  return true;
185 
186  return false;
187  }
188 
190  bool containsValue (ValueTypeParameter valueToLookFor) const
191  {
192  const ScopedLockType sl (getLock());
193 
194  for (int i = getNumSlots(); --i >= 0;)
195  for (const HashEntry* entry = hashSlots.getUnchecked(i); entry != nullptr; entry = entry->nextEntry)
196  if (entry->value == valueToLookFor)
197  return true;
198 
199  return false;
200  }
201 
202  //==============================================================================
207  void set (KeyTypeParameter newKey, ValueTypeParameter newValue)
208  {
209  const ScopedLockType sl (getLock());
210  const int hashIndex = generateHashFor (newKey);
211 
212  HashEntry* const firstEntry = hashSlots.getUnchecked (hashIndex);
213 
214  for (HashEntry* entry = firstEntry; entry != nullptr; entry = entry->nextEntry)
215  {
216  if (entry->key == newKey)
217  {
218  entry->value = newValue;
219  return;
220  }
221  }
222 
223  hashSlots.set (hashIndex, new HashEntry (newKey, newValue, firstEntry));
224  ++totalNumItems;
225 
226  if (totalNumItems > (getNumSlots() * 3) / 2)
227  remapTable (getNumSlots() * 2);
228  }
229 
231  void remove (KeyTypeParameter keyToRemove)
232  {
233  const ScopedLockType sl (getLock());
234  const int hashIndex = generateHashFor (keyToRemove);
235  HashEntry* entry = hashSlots.getUnchecked (hashIndex);
236  HashEntry* previous = nullptr;
237 
238  while (entry != nullptr)
239  {
240  if (entry->key == keyToRemove)
241  {
242  const ScopedPointer<HashEntry> deleter (entry);
243 
244  entry = entry->nextEntry;
245 
246  if (previous != nullptr)
247  previous->nextEntry = entry;
248  else
249  hashSlots.set (hashIndex, entry);
250 
251  --totalNumItems;
252  }
253  else
254  {
255  previous = entry;
256  entry = entry->nextEntry;
257  }
258  }
259  }
260 
262  void removeValue (ValueTypeParameter valueToRemove)
263  {
264  const ScopedLockType sl (getLock());
265 
266  for (int i = getNumSlots(); --i >= 0;)
267  {
268  HashEntry* entry = hashSlots.getUnchecked(i);
269  HashEntry* previous = nullptr;
270 
271  while (entry != nullptr)
272  {
273  if (entry->value == valueToRemove)
274  {
275  const ScopedPointer<HashEntry> deleter (entry);
276 
277  entry = entry->nextEntry;
278 
279  if (previous != nullptr)
280  previous->nextEntry = entry;
281  else
282  hashSlots.set (i, entry);
283 
284  --totalNumItems;
285  }
286  else
287  {
288  previous = entry;
289  entry = entry->nextEntry;
290  }
291  }
292  }
293  }
294 
299  void remapTable (int newNumberOfSlots)
300  {
301  HashMap newTable (newNumberOfSlots);
302 
303  for (int i = getNumSlots(); --i >= 0;)
304  for (const HashEntry* entry = hashSlots.getUnchecked(i); entry != nullptr; entry = entry->nextEntry)
305  newTable.set (entry->key, entry->value);
306 
307  swapWith (newTable);
308  }
309 
315  {
316  return hashSlots.size();
317  }
318 
319  //==============================================================================
321  template <class OtherHashMapType>
322  void swapWith (OtherHashMapType& otherHashMap) noexcept
323  {
324  const ScopedLockType lock1 (getLock());
325  const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
326 
327  hashSlots.swapWith (otherHashMap.hashSlots);
328  std::swap (totalNumItems, otherHashMap.totalNumItems);
329  }
330 
331  //==============================================================================
336  inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return lock; }
337 
339  typedef typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType;
340 
341 private:
342  //==============================================================================
343  class HashEntry
344  {
345  public:
346  HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry* const next)
347  : key (k), value (val), nextEntry (next)
348  {}
349 
350  const KeyType key;
351  ValueType value;
352  HashEntry* nextEntry;
353 
354  JUCE_DECLARE_NON_COPYABLE (HashEntry)
355  };
356 
357 public:
358  //==============================================================================
381  class Iterator
382  {
383  public:
384  //==============================================================================
385  Iterator (const HashMap& hashMapToIterate)
386  : hashMap (hashMapToIterate), entry (nullptr), index (0)
387  {}
388 
393  bool next()
394  {
395  if (entry != nullptr)
396  entry = entry->nextEntry;
397 
398  while (entry == nullptr)
399  {
400  if (index >= hashMap.getNumSlots())
401  return false;
402 
403  entry = hashMap.hashSlots.getUnchecked (index++);
404  }
405 
406  return true;
407  }
408 
412  KeyType getKey() const
413  {
414  return entry != nullptr ? entry->key : KeyType();
415  }
416 
420  ValueType getValue() const
421  {
422  return entry != nullptr ? entry->value : ValueType();
423  }
424 
425  private:
426  //==============================================================================
427  const HashMap& hashMap;
428  HashEntry* entry;
429  int index;
430 
432  };
433 
434 private:
435  //==============================================================================
436  enum { defaultHashTableSize = 101 };
437  friend class Iterator;
438 
439  HashFunctionType hashFunctionToUse;
440  Array<HashEntry*> hashSlots;
441  int totalNumItems;
442  TypeOfCriticalSectionToUse lock;
443 
444  int generateHashFor (KeyTypeParameter key) const
445  {
446  const int hash = hashFunctionToUse.generateHash (key, getNumSlots());
447  jassert (isPositiveAndBelow (hash, getNumSlots())); // your hash function is generating out-of-range numbers!
448  return hash;
449  }
450 
452 };
453 
454 
455 #endif // JUCE_HASHMAP_H_INCLUDED
int generateHash(const int64 key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:44
ValueType getValue() const
Definition: juce_HashMap.h:420
Definition: juce_Variant.h:46
Definition: juce_HashMap.h:98
#define noexcept
Definition: juce_CompilerSupport.h:141
int size() const noexcept
Definition: juce_HashMap.h:156
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition: juce_HashMap.h:336
bool isPositiveAndBelow(Type valueToTest, Type upperLimit) noexcept
Definition: juce_core.h:238
bool next()
Definition: juce_HashMap.h:393
bool contains(KeyTypeParameter keyToLookFor) const
Definition: juce_HashMap.h:178
void remapTable(int newNumberOfSlots)
Definition: juce_HashMap.h:299
Definition: juce_String.h:43
Definition: juce_HashMap.h:39
#define const
Iterator(const HashMap &hashMapToIterate)
Definition: juce_HashMap.h:385
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Definition: juce_HashMap.h:207
unsigned int uint32
Definition: juce_MathsFunctions.h:51
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Definition: juce_HashMap.h:116
int val
Definition: jpeglib.h:956
Definition: juce_ScopedPointer.h:70
long long int64
Definition: juce_MathsFunctions.h:60
int getNumSlots() const noexcept
Definition: juce_HashMap.h:314
Definition: juce_Array.h:60
int generateHash(const int key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:42
#define jassert(a)
Definition: juce_PlatformDefs.h:146
void removeValue(ValueTypeParameter valueToRemove)
Definition: juce_HashMap.h:262
#define JUCE_DECLARE_NON_COPYABLE(className)
Definition: juce_PlatformDefs.h:191
#define JUCE_DECLARE_NON_COPYABLE_WITH_LEAK_DETECTOR(className)
Definition: juce_PlatformDefs.h:198
void swapWith(OtherHashMapType &otherHashMap) noexcept
Definition: juce_HashMap.h:322
#define nullptr
Definition: juce_CompilerSupport.h:151
TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Definition: juce_HashMap.h:339
void clear()
Definition: juce_HashMap.h:134
Definition: juce_CriticalSection.h:136
Definition: juce_HashMap.h:381
bool containsValue(ValueTypeParameter valueToLookFor) const
Definition: juce_HashMap.h:190
#define PARAMETER_TYPE(a)
int generateHash(const var &key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:48
~HashMap()
Definition: juce_HashMap.h:124
KeyType getKey() const
Definition: juce_HashMap.h:412
int generateHash(const String &key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:46