2 // Copyright (c) 2012 Samsung Electronics Co., Ltd.
4 // Licensed under the Apache License, Version 2.0 (the License);
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
8 // http://www.apache.org/licenses/LICENSE-2.0
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
18 * @file FBaseColHashMapT.h
19 * @brief This is the header file for the %HashMapT class.
21 * This header file contains the declarations of the %HashMapT class.
23 #ifndef _FBASE_COL_HASH_MAP_T_H_
24 #define _FBASE_COL_HASH_MAP_T_H_
26 #include <FBaseObject.h>
27 #include <FBaseResult.h>
28 #include <FBaseColIComparerT.h>
29 #include <FBaseColIHashCodeProviderT.h>
30 #include <FBaseColIListT.h>
31 #include <FBaseColIMapT.h>
32 #include <FBaseColArrayListT.h>
33 #include <FBaseColMapEntryT.h>
34 #include <FBaseComparerT.h>
35 #include <FBaseFloat.h>
37 namespace Tizen { namespace Base { namespace Collection
40 template< class KeyType, class ValueType > class __HashMapEntryT;
41 template< class KeyType, class ValueType > class __HashMapEnumeratorT;
42 template< class KeyType > class __HashMapDefaultProviderT;
46 * @brief This class provides a template-based collection of associated keys and values
47 * that are organized based on the hash code of the key.
51 * The %HashMapT class provides a template-based collection of associated keys and values
52 * that are organized based on the hash code of the key.
53 * It contains unique keys and each key maps to one single value.
54 * The key and value cannot be a null reference. Several methods in the %HashMapT class need assignment (=) operators of KeyType and ValueType.
56 * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/hashmap_multihashmap.htm">HashMap and MultiHashMap</a>.
58 * The following example demonstrates how to use the %HashMapT class.
63 * using namespace Tizen::Base;
64 * using namespace Tizen::Base::Collection;
67 * MyClass::HashMapTSample(void)
69 * HashMapT< int, int > map;
71 * // Constructs a %HashMapT instance with default capacity, load factor, hash code provider, and comparer
74 * map.Add(1, 100); // map.GetCount() : 1
75 * map.Add(2, 200); // map.GetCount() : 2
76 * map.Add(3, 300); // map.GetCount() : 3
81 * // Gets a value with the specified key
83 * map.GetValue(key, value); // value : 100
85 * // Removes the value with the specified key
88 * // Uses an enumerator to access elements in the map
89 * IMapEnumeratorT< int, int >* pMapEnum = map.GetMapEnumeratorN();
90 * while (pMapEnum->MoveNext() == E_SUCCESS)
92 * pMapEnum->GetKey(key);
93 * pMapEnum->GetValue(value);
100 template< class KeyType, class ValueType >
102 : public IMapT< KeyType, ValueType >
107 * The object is not fully constructed after this constructor is called. For full construction, @n
108 * the Construct() method must be called right after calling this constructor.
120 , __defaultConstruct(false)
126 * This destructor overrides Tizen::Base::Object::~Object().
130 virtual ~HashMapT(void)
132 if (null != __pTable)
138 if (__defaultConstruct)
147 * Initializes this instance of %HashMapT with the specified parameters.
151 * @return An error code
152 * @param[in] capacity The initial capacity
153 * @param[in] loadFactor The maximum ratio of elements to buckets
154 * @exception E_SUCCESS The method is successful.
155 * @exception E_INVALID_ARG A specified input parameter is invalid, or
156 * the @c capacity or the @c loadFactor is negative.
157 * @remarks To work properly, the key type must be of a primitive number type.
160 result Construct(int capacity = 16, float loadFactor = 0.75)
162 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
163 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
165 result r = E_SUCCESS;
169 __capacity = DEFAULT_CAPACITY;
174 while (__capacity < capacity)
180 if (Float::Compare(loadFactor, 0) == 0)
182 __loadFactor = DEFAULT_LOAD_FACTOR;
186 __loadFactor = loadFactor;
189 __threshold = static_cast< int >(__capacity * __loadFactor);
191 __pProvider = new __HashMapDefaultProviderT< KeyType >();
192 TryCatch(__pProvider != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
194 __pComparer = new Tizen::Base::ComparerT< KeyType >();
195 TryCatch(__pComparer != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
197 __defaultConstruct = true;
199 __pTable = new __HashMapEntryT< KeyType, ValueType >*[__capacity];
200 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
202 memset(__pTable, null, sizeof(__HashMapEntryT< KeyType, ValueType >*) * __capacity);
215 * Initializes this instance of %HashMapT by copying the elements of the specified @c map.
219 * @return An error code
220 * @param[in] map The map to copy
221 * @param[in] loadFactor The maximum ratio of elements to buckets
222 * @exception E_SUCCESS The method is successful.
223 * @exception E_INVALID_ARG A specified input parameter is invalid, or
224 * the @c loadFactor is negative.
225 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
226 * the @c map is modified during the operation of this method.
229 result Construct(const IMapT< KeyType, ValueType >& map, float loadFactor = 0.75)
231 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
233 result r = E_SUCCESS;
235 if (Float::Compare(loadFactor, 0) == 0)
237 loadFactor = DEFAULT_LOAD_FACTOR;
240 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
242 r = Construct(capacity, loadFactor);
243 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
246 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
267 * Initializes this instance of an empty %HashMapT class, with the specified initial capacity, load factor, hash code provider, and comparer.
271 * @return An error code
272 * @param[in] capacity The initial capacity @n
273 * If it is @c 0, the default capacity (16) is used.
274 * @param[in] loadFactor The maximum ratio of the elements to buckets @n
275 * If it is @c 0, the default load factor (0.75) is used.
276 * @param[in] provider An instance of the IHashCodeProviderT-derived class that supplies the hash codes
277 * for all keys in this map
278 * @param[in] comparer An instance of the IComparerT-derived class to use when comparing keys
279 * @exception E_SUCCESS The method is successful.
280 * @exception E_INVALID_ARG Either of the following conditions has occurred: @n
281 * - A specified input parameter is invalid. @n
282 * - The specified @c capacity is negative. @n
283 * - The @c loadFactor is negative.
284 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
287 result Construct(int capacity, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
288 const IComparerT< KeyType >& comparer)
290 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
291 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
293 result r = E_SUCCESS;
297 __capacity = DEFAULT_CAPACITY;
302 while (__capacity < capacity)
308 if (Float::Compare(loadFactor, 0) == 0)
310 __loadFactor = DEFAULT_LOAD_FACTOR;
314 __loadFactor = loadFactor;
317 __threshold = static_cast< int >(__capacity * __loadFactor);
319 __pProvider = const_cast< IHashCodeProviderT< KeyType >* >(&provider);
321 __pComparer = const_cast< IComparerT< KeyType >* >(&comparer);
323 __pTable = new __HashMapEntryT< KeyType, ValueType >*[__capacity];
324 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
326 memset(__pTable, null, sizeof(__HashMapEntryT< KeyType, ValueType >*) * __capacity);
339 * Initializes this instance of %HashMapT by copying the elements of the specified @c map,
340 * with the specified load factor, hash code provider, and comparer.
344 * @return An error code
345 * @param[in] map The map to copy
346 * @param[in] loadFactor The maximum ratio of elements to buckets @n
347 * If it is @c 0, the default load factor (0.75) is used.
348 * @param[in] provider An instance of the IHashCodeProviderT-derived class that supplies the hash codes
349 * for all keys in this map
350 * @param[in] comparer An instance of the IComparerT-derived class to use when comparing keys
351 * @exception E_SUCCESS The method is successful.
352 * @exception E_INVALID_ARG Either of the following conditions has occurred: @n
353 * - A specified input parameter is invalid. @n
354 * - The @c loadFactor is negative. @n
355 * - The @c provider is a @c null or the @c comparer is a @c null.
356 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
357 * the @c map is modified during the operation of this method.
358 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
361 result Construct(const IMapT< KeyType, ValueType >& map, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
362 const IComparerT< KeyType >& comparer)
364 TryReturn((loadFactor >= 0), E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
366 result r = E_SUCCESS;
367 if (Float::Compare(loadFactor, 0) == 0)
369 loadFactor = DEFAULT_LOAD_FACTOR;
372 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
373 r = Construct(capacity, loadFactor, provider, comparer);
374 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
377 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
394 * Adds the specified key-value pair to a map.
398 * @return An error code
399 * @param[in] key The key of the value to add
400 * @param[in] value The value to add
401 * @exception E_SUCCESS The method is successful.
402 * @exception E_INVALID_ARG A specified input parameter is invalid, or
403 * the comparer has failed to compare the keys.
404 * @exception E_OBJ_ALREADY_EXIST The specified @c key already exists.
407 virtual result Add(const KeyType& key, const ValueType& value)
409 __HashMapEntryT< KeyType, ValueType >* pNewEntry;
411 result r = E_SUCCESS;
412 int hash = Hash(key);
413 int i = hash & (__capacity - 1);
416 r = ContainsKey(key, out);
417 TryReturn((!out), E_OBJ_ALREADY_EXIST, "[%s] The key is already exist in this collection.", GetErrorMessage(E_OBJ_ALREADY_EXIST));
418 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
421 pNewEntry = new __HashMapEntryT< KeyType, ValueType >(key, value, __pTable[i], hash);
422 TryReturn(pNewEntry != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
423 __pTable[i] = pNewEntry;
426 if (__count++ >= __threshold)
428 r = Resize(__capacity * 2);
429 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
436 * Gets the elements of a map in an instance of the IMapEnumeratorT-derived class.
440 * @return An instance of the IMapEnumeratorT-derived class if successful, @n
441 * else @c null if an exception occurs
442 * @exception E_SUCCESS The method is successful.
443 * @exception E_OUT_OF_MEMORY The memory is insufficient.
444 * @remarks The specific error code can be accessed using the GetLastResult() method.
445 * @see Tizen::Base::Collection::IEnumerator
446 * @see Tizen::Base::Collection::IMapEnumerator
448 virtual IEnumeratorT< MapEntryT< KeyType, ValueType > >* GetEnumeratorN(void) const
450 result r = E_SUCCESS;
452 __HashMapEnumeratorT< KeyType, ValueType >* pEnum = new __HashMapEnumeratorT< KeyType, ValueType >(*this, __modCount);
453 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
455 SetLastResult(E_SUCCESS);
464 * Gets the elements of a map in an instance of the IMapEnumeratorT class.
468 * @return An instance of the IMapEnumeratorT class if successful, @n
469 * else @c null if an exception occurs
470 * @exception E_SUCCESS The method is successful.
471 * @exception E_OUT_OF_MEMORY The memory is insufficient.
472 * @remarks The specific error code can be accessed using the GetLastResult() method.
473 * @see Tizen::Base::Collection::IEnumerator
474 * @see Tizen::Base::Collection::IMapEnumerator
476 virtual IMapEnumeratorT< KeyType, ValueType >* GetMapEnumeratorN(void) const
478 return dynamic_cast< IMapEnumeratorT< KeyType, ValueType >* >(GetEnumeratorN());
482 * Gets the value associated with the specified @c key.
486 * @return The value associated with the key, @n
487 * else @c null if an exception occurs
488 * @param[in] key The key to locate
489 * @param[out] value The value associated with the key
490 * @exception E_SUCCESS The method is successful.
491 * @exception E_INVALID_ARG A specified input parameter is invalid, or
492 * The comparer has failed to compare the keys.
493 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
496 virtual result GetValue(const KeyType& key, ValueType& value) const
498 result r = E_OBJ_NOT_FOUND;
500 int hash = Hash(key);
501 int i = hash & (__capacity - 1);
503 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
505 if (hash == pEntry->hash)
508 r = __pComparer->Compare(key, pEntry->key, cmpResult);
509 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
513 value = pEntry->value;
519 return E_OBJ_NOT_FOUND;
523 * Gets the value associated with the specified @c key.
527 * @return The value associated with the key, @n
528 * else @c null if an exception occurs
529 * @param[in] key The key to locate
530 * @param[out] value The value associated with the key
531 * @exception E_SUCCESS The method is successful.
532 * @exception E_INVALID_ARG A specified input parameter is invalid, or
533 * the comparer has failed to compare the keys.
534 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
537 virtual result GetValue(const KeyType& key, ValueType& value)
539 return (static_cast< const HashMapT< KeyType, ValueType >* >(this))->GetValue(key, value);
543 * Gets a list of all the keys in a map.
547 * @return A pointer to an IListT object containing all the keys in the map, @n
548 * else @c null if an exception occurs
549 * @exception E_SUCCESS The method is successful.
550 * @exception E_OUT_OF_MEMORY The memory is insufficient.
551 * @remarks The order of the keys is the same as the corresponding values in the IListT interface returned by the GetValuesN() method.
552 * @remarks The specific error code can be accessed using the GetLastResult() method.
555 virtual IListT< KeyType >* GetKeysN(void) const
557 result r = E_SUCCESS;
559 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
560 TryCatch(pList != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
562 r = pList->Construct(__count);
563 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
565 for (int i = 0; i < __capacity; i++)
567 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
569 r = pList->Add(pEntry->key);
570 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
574 SetLastResult(E_SUCCESS);
585 * Gets all the values in a map.
589 * @return A pointer to an IListT object containing all the values in the map, @n
590 * else @c null if an exception occurs
591 * @exception E_SUCCESS The method is successful.
592 * @exception E_OUT_OF_MEMORY The memory is insufficient.
593 * @remarks The specific error code can be accessed using the GetLastResult() method.
596 virtual IListT< ValueType >* GetValuesN(void) const
598 result r = E_SUCCESS;
600 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
601 TryCatch(pList != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
603 r = pList->Construct(__count);
604 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
606 for (int i = 0; i < __capacity; i++)
608 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
610 r = pList->Add(pEntry->value);
611 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
615 SetLastResult(E_SUCCESS);
626 * Removes the value associated with the specified @c key.
630 * @return An error code
631 * @param[in] key The key to remove
632 * @exception E_SUCCESS The method is successful.
633 * @exception E_INVALID_ARG The specified input parameter is invalid, or
634 * the comparer has failed to compare the keys.
635 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
638 virtual result Remove(const KeyType& key)
640 result r = E_OBJ_NOT_FOUND;
641 int hash = Hash(key);
642 int i = hash & (__capacity - 1);
644 __HashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
645 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
647 if (hash == pEntry->hash)
650 r = __pComparer->Compare(key, pEntry->key, cmpResult);
651 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
658 __pTable[i] = pEntry->pNext;
662 pPrev->pNext = pEntry->pNext;
674 return E_OBJ_NOT_FOUND;
678 * Removes all key-value pairs in the map.
682 virtual void RemoveAll(void)
693 * Replaces the value associated with the specified @c key with the specified new @c value.
697 * @return An error code
698 * @param[in] key The key for which the value is to replace
699 * @param[in] value The new value to replace
700 * @exception E_SUCCESS The method is successful.
701 * @exception E_INVALID_ARG A specified input parameter is invalid, or
702 * the comparer has failed to compare the keys.
703 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
704 * @remarks Use the Add() method to add a new key-value pair.
708 virtual result SetValue(const KeyType& key, const ValueType& value)
710 result r = E_SUCCESS;
711 int hash = Hash(key);
712 int i = hash & (__capacity - 1);
715 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
717 if (hash == pEntry->hash)
719 r = __pComparer->Compare(key, pEntry->key, cmpResult);
720 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
723 pEntry->value = value;
740 * Gets the number of pairs currently stored in a map.
744 * @return The pairs stored in the map
746 virtual int GetCount(void) const
752 * Checks whether a map contains the specified @c key.
756 * @return An error code
757 * @param[in] key The key to locate
758 * @param[out] out Set to @c true if the map contains the specified @c key, @n
760 * @exception E_SUCCESS The method is successful.
761 * @exception E_INVALID_ARG A specified input parameter is invalid, or
762 * the comparer has failed to compare the keys.
763 * @see ContainsValue()
765 virtual result ContainsKey(const KeyType& key, bool& out) const
769 result r = E_SUCCESS;
770 int hash = Hash(key);
771 int i = hash & (__capacity - 1);
773 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
775 if (hash == pEntry->hash)
778 r = __pComparer->Compare(key, pEntry->key, cmpResult);
779 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
793 * Checks whether a map contains the specified @c value.
797 * @return @c true if the map contains the specified @c value, @n
799 * @param[in] value The value to locate
803 virtual bool ContainsValue(const ValueType& value) const
805 for (int i = 0; i < __capacity; i++)
807 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
809 if (value == pEntry->value)
820 * Compares two instances of the %HashMapT class.
824 * @return @c true if the two instances match, @n
826 * @param[in] obj The object to compare with the current instance
827 * @remarks This method returns @c true if and only if the two instances contain the same number of elements and all the elements of each other.
829 virtual bool Equals(const Object& obj) const
831 const HashMapT< KeyType, ValueType >* other = dynamic_cast< const HashMapT< KeyType, ValueType >* >(&obj);
836 else if (other == this)
840 else if (__count != other->__count)
846 for (int i = 0; i < __capacity; i++)
848 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
850 ValueType otherValue;
851 result r = other->GetValue(pEntry->key, otherValue);
856 if (pEntry->value != otherValue)
868 * Gets the hash value of the current instance.
872 * @return The hash value of the current instance
873 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
874 * the used hash function must generate a random distribution for all inputs.
876 virtual int GetHashCode(void) const
879 for (int i = 0; i < __capacity; i++)
881 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
883 hash += reinterpret_cast< int >(&pEntry->key);
884 hash += reinterpret_cast< int >(&pEntry->value);
892 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
894 * @param[in] map The instance of the %HashMapT class to copy from
896 HashMapT(const HashMapT< KeyType, ValueType >& map);
899 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
901 * @param[in] map An instance of %HashMapT
903 HashMapT< KeyType, ValueType >& operator =(const HashMapT< KeyType, ValueType >& map);
906 * Copies all the pairs from a specified @c map to this map.
908 * @return An error code
909 * @param[in] map The map to copy
910 * @exception E_SUCCESS The method is successful.
911 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
912 * The @c map is modified during the operation of this method.
914 result AddAll(const IMapT< KeyType, ValueType >& map)
916 result r = E_SUCCESS;
918 IMapT< KeyType, ValueType >* pMap = const_cast< IMapT< KeyType, ValueType >* >(&map);
919 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
921 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
923 while ((r = pMapEnum->MoveNext()) != E_OUT_OF_RANGE)
925 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
930 r = pMapEnum->GetKey(key);
931 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
933 r = pMapEnum->GetValue(value);
934 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
936 int hash = Hash(key);
937 int i = hash & (__capacity - 1);
938 __HashMapEntryT< KeyType, ValueType >* pNewEntry = new __HashMapEntryT< KeyType, ValueType >(key, value, __pTable[i], hash);
940 TryCatch(pNewEntry != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
941 __pTable[i] = pNewEntry;
945 if (null != pMapEnum)
953 if (null != pMapEnum)
962 * Gets the hash value for the specified object.
964 * @return The hash value for the specified object
965 * @param[in] obj The object to get hash value
967 int Hash(const KeyType& obj) const
969 int h = __pProvider->GetHashCode(obj);
971 h ^= (h >> 20) ^ (h >> 12);
973 return h ^ (h >> 7) ^ (h >> 4);
977 * Resizes the content of a map to a new array with a greater capacity.
979 * @return An error code
980 * @param[in] newCapacity The new capacity @n
981 * It must be a power of two and greater than the current capacity.
982 * @exception E_SUCCESS The method is successful.
983 * @exception E_OUT_OF_MEMORY The memory is insufficient.
984 * @remarks This method is called automatically when the number of keys in a map reaches its threshold.
986 result Resize(int newCapacity)
988 result r = E_SUCCESS;
989 __HashMapEntryT< KeyType, ValueType >** pNewTable = new __HashMapEntryT< KeyType, ValueType >*[newCapacity];
990 TryReturn(pNewTable != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
992 memset(pNewTable, null, sizeof(__HashMapEntryT< KeyType, ValueType >*) * newCapacity);
994 for (int i = 0; i < __capacity; i++)
996 __HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
997 while (null != pEntry)
999 __HashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1000 int i = pEntry->hash & (newCapacity - 1);
1001 pEntry->pNext = pNewTable[i];
1002 pNewTable[i] = pEntry;
1008 __pTable = pNewTable;
1009 __capacity = newCapacity;
1010 __threshold = static_cast< int >(__capacity * __loadFactor);
1016 * Clears all key-value pairs in this map.
1020 for (int i = 0; i < __capacity; i++)
1022 __HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1023 while (null != pEntry)
1025 __HashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1033 __HashMapEntryT< KeyType, ValueType >** __pTable;
1038 IHashCodeProviderT< KeyType >* __pProvider;
1039 IComparerT< KeyType >* __pComparer;
1040 bool __defaultConstruct;
1043 static const int DEFAULT_CAPACITY = 16;
1044 static const float DEFAULT_LOAD_FACTOR;
1046 friend class __HashMapEnumeratorT< KeyType, ValueType >;
1051 // @class __HashMapEntryT
1052 // @brief This is an entry for the %HashMapT class.
1055 template< class KeyType, class ValueType >
1056 class __HashMapEntryT
1061 * This is the constructor for this class.
1065 * @param[in] k The key to include in this entry
1066 * @param[in] v The value to include in this entry
1067 * @param[in] next A pointer to the next entry
1068 * @param[in] h A hash value of the key
1070 __HashMapEntryT(const KeyType& k, const ValueType& v, __HashMapEntryT< KeyType, ValueType >* next, int h)
1079 * This is the destructor for this class.
1083 virtual ~__HashMapEntryT(void)
1088 * Internal variable.
1095 * Internal variable.
1102 * Internal variable.
1109 * Internal variable.
1113 __HashMapEntryT< KeyType, ValueType >* pNext;
1115 }; // __HashMapEntryT
1118 // @class __HashMapEnumeratorT
1119 // @brief This is an implementation of the IMapEnumeratorT interface for the %HashMapT class.
1122 template< class KeyType, class ValueType >
1123 class __HashMapEnumeratorT
1124 : public IMapEnumeratorT< KeyType, ValueType >
1129 * This is the constructor for this class.
1133 * @param[in] map The map to enumerate
1134 * @param[in] modCount The modification count to detect the change in the map
1136 __HashMapEnumeratorT(const HashMapT< KeyType, ValueType >& map, int modCount)
1138 , __modCount(modCount)
1146 * This is the destructor for this class.
1150 virtual ~__HashMapEnumeratorT(void)
1156 * Gets the current object in the map.
1160 * @return An error code
1161 * @param[out] obj The current object
1162 * @exception E_SUCCESS The method is successful.
1163 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1164 * This enumerator is currently positioned before the first element or
1165 * past the last element or the map is modified after this enumerator is created.
1167 virtual result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1169 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1170 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1171 TryReturn((__pEntry != null), E_INVALID_OPERATION, "[%s] Invalid position(pEntry is null).", GetErrorMessage(E_INVALID_OPERATION));
1173 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pEntry->value);
1178 * Moves this enumerator to the next elements of the map.
1179 * When this enumerator is first created, or when the Reset() method is called, or when the %MoveNext() method is first called, the enumerator positions itself to the first element in the map.
1183 * @return An error code
1184 * @exception E_SUCCESS The method is successful.
1185 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1186 * the map is modified after this enumerator is created.
1187 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the map.
1190 virtual result MoveNext(void)
1192 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1193 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1195 if ((null != __pEntry) && (null != __pEntry->pNext))
1197 __pEntry = __pEntry->pNext;
1202 while (++__index < __map.__capacity)
1204 __pEntry = __map.__pTable[__index];
1205 if (null != __pEntry)
1212 return E_OUT_OF_RANGE;
1216 * Positions the enumerator before the first element in a map.
1220 * @return An error code
1221 * @exception E_SUCCESS The method is successful.
1222 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1223 * the map is modified after this enumerator is created.
1225 virtual result Reset(void)
1227 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1228 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1236 * Gets the current key in a map.
1240 * @return An error code
1241 * @param[out] key The current key
1242 * @exception E_SUCCESS The method is successful.
1243 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1244 * This enumerator is currently positioned before the first element or
1245 * past the last element or the map is modified after this enumerator is created.
1247 virtual result GetKey(KeyType& key) const
1249 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1250 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1251 TryReturn((__pEntry != null), E_INVALID_OPERATION, "[%s] Invalid position(pEntry is null).", GetErrorMessage(E_INVALID_OPERATION));
1253 key = __pEntry->key;
1258 * Gets the current value in a map.
1262 * @return An error code
1263 * @param[out] value The current value
1264 * @exception E_SUCCESS The method is successful.
1265 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1266 * This enumerator is currently positioned before the first element or
1267 * past the last element or the map is modified after the enumerator is created.
1269 virtual result GetValue(ValueType& value) const
1271 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1272 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1273 TryReturn((__pEntry != null), E_INVALID_OPERATION, "[%s] Invalid position(pEntry is null).", GetErrorMessage(E_INVALID_OPERATION));
1275 value = __pEntry->value;
1280 const HashMapT< KeyType, ValueType >& __map;
1282 __HashMapEntryT< KeyType, ValueType >* __pEntry;
1285 }; // __HashMapEnumeratorT
1288 // @class __HashMapDefaultProviderT
1289 // @brief This is an implementation of the IHashCodeProviderT interface for the HashMap class.
1292 template< class KeyType >
1293 class __HashMapDefaultProviderT
1294 : public IHashCodeProviderT< KeyType >
1299 * This is the default constructor for this class.
1303 __HashMapDefaultProviderT(void) {}
1306 * This is the destructor for this class.
1310 virtual ~__HashMapDefaultProviderT(void) {}
1313 * Gets the hash code of the specified object.
1317 * @return The hash code of the specified object
1318 * @see Tizen::Base::Object::GetHashCode
1320 virtual int GetHashCode(const KeyType& obj) const
1325 }; // __HashMapDefaultProviderT
1327 template< class KeyType, class ValueType >
1328 const float HashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1330 }}} // Tizen::Base::Collection
1332 #endif //_FBASE_COL_HASH_MAP_T_H_