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>
38 namespace Tizen { namespace Base { namespace Collection
41 template< class KeyType, class ValueType > class __HashMapEntryT;
42 template< class KeyType, class ValueType > class __HashMapEnumeratorT;
43 template< class KeyType > class __HashMapDefaultProviderT;
47 * @brief This class provides a template-based collection of associated keys and values
48 * that are organized based on the hash code of the key.
52 * The %HashMapT class provides a template-based collection of associated keys and values
53 * that are organized based on the hash code of the key.
54 * It contains unique keys and each key maps to one single value.
55 * The key and value cannot be a null reference. Several methods in the %HashMapT class need assignment (=) operators of KeyType and ValueType.
57 * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/hashmap_multihashmap.htm">HashMap and MultiHashMap</a>.
59 * The following example demonstrates how to use the %HashMapT class.
64 * using namespace Tizen::Base;
65 * using namespace Tizen::Base::Collection;
68 * MyClass::HashMapTSample(void)
70 * HashMapT< int, int > map;
72 * // Constructs a %HashMapT instance with default capacity, load factor, hash code provider, and comparer
75 * map.Add(1, 100); // map.GetCount() : 1
76 * map.Add(2, 200); // map.GetCount() : 2
77 * map.Add(3, 300); // map.GetCount() : 3
82 * // Gets a value with the specified key
84 * map.GetValue(key, value); // value : 100
86 * // Removes the value with the specified key
89 * // Uses an enumerator to access elements in the map
90 * IMapEnumeratorT< int, int >* pMapEnum = map.GetMapEnumeratorN();
91 * while (pMapEnum->MoveNext() == E_SUCCESS)
93 * pMapEnum->GetKey(key);
94 * pMapEnum->GetValue(value);
101 template< class KeyType, class ValueType >
103 : public IMapT< KeyType, ValueType >
108 * The object is not fully constructed after this constructor is called. For full construction, @n
109 * the Construct() method must be called right after calling this constructor.
121 , __defaultConstruct(false)
127 * This destructor overrides Tizen::Base::Object::~Object().
131 virtual ~HashMapT(void)
133 if (null != __pTable)
139 if (__defaultConstruct)
148 * Initializes this instance of %HashMapT with the specified parameters.
152 * @return An error code
153 * @param[in] capacity The initial capacity
154 * @param[in] loadFactor The maximum ratio of elements to buckets
155 * @exception E_SUCCESS The method is successful.
156 * @exception E_INVALID_ARG A specified input parameter is invalid, or
157 * the @c capacity or the @c loadFactor is negative.
158 * @remarks To work properly, the key type must be of a primitive number type.
161 result Construct(int capacity = 16, float loadFactor = 0.75)
163 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
164 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
166 result r = E_SUCCESS;
170 __capacity = DEFAULT_CAPACITY;
175 while (__capacity < capacity)
181 if (Float::Compare(loadFactor, 0) == 0)
183 __loadFactor = DEFAULT_LOAD_FACTOR;
187 __loadFactor = loadFactor;
190 __threshold = static_cast< int >(__capacity * __loadFactor);
192 __pProvider = new __HashMapDefaultProviderT< KeyType >();
193 TryCatch(__pProvider != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
195 __pComparer = new Tizen::Base::ComparerT< KeyType >();
196 TryCatch(__pComparer != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
198 __defaultConstruct = true;
200 __pTable = new __HashMapEntryT< KeyType, ValueType >*[__capacity];
201 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
203 memset(__pTable, null, sizeof(__HashMapEntryT< KeyType, ValueType >*) * __capacity);
216 * Initializes this instance of %HashMapT by copying the elements of the specified @c map.
220 * @return An error code
221 * @param[in] map The map to copy
222 * @param[in] loadFactor The maximum ratio of elements to buckets
223 * @exception E_SUCCESS The method is successful.
224 * @exception E_INVALID_ARG A specified input parameter is invalid, or
225 * the @c loadFactor is negative.
226 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
227 * the @c map is modified during the operation of this method.
230 result Construct(const IMapT< KeyType, ValueType >& map, float loadFactor = 0.75)
232 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
234 result r = E_SUCCESS;
236 if (Float::Compare(loadFactor, 0) == 0)
238 loadFactor = DEFAULT_LOAD_FACTOR;
241 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
243 r = Construct(capacity, loadFactor);
244 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
247 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
268 * Initializes this instance of an empty %HashMapT class, with the specified initial capacity, load factor, hash code provider, and comparer.
272 * @return An error code
273 * @param[in] capacity The initial capacity @n
274 * If it is @c 0, the default capacity (16) is used.
275 * @param[in] loadFactor The maximum ratio of the elements to buckets @n
276 * If it is @c 0, the default load factor (0.75) is used.
277 * @param[in] provider An instance of the IHashCodeProviderT-derived class that supplies the hash codes
278 * for all keys in this map
279 * @param[in] comparer An instance of the IComparerT-derived class to use when comparing keys
280 * @exception E_SUCCESS The method is successful.
281 * @exception E_INVALID_ARG Either of the following conditions has occurred: @n
282 * - A specified input parameter is invalid. @n
283 * - The specified @c capacity is negative. @n
284 * - The @c loadFactor is negative.
285 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
288 result Construct(int capacity, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
289 const IComparerT< KeyType >& comparer)
291 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
292 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
294 result r = E_SUCCESS;
298 __capacity = DEFAULT_CAPACITY;
303 while (__capacity < capacity)
309 if (Float::Compare(loadFactor, 0) == 0)
311 __loadFactor = DEFAULT_LOAD_FACTOR;
315 __loadFactor = loadFactor;
318 __threshold = static_cast< int >(__capacity * __loadFactor);
320 __pProvider = const_cast< IHashCodeProviderT< KeyType >* >(&provider);
322 __pComparer = const_cast< IComparerT< KeyType >* >(&comparer);
324 __pTable = new __HashMapEntryT< KeyType, ValueType >*[__capacity];
325 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
327 memset(__pTable, null, sizeof(__HashMapEntryT< KeyType, ValueType >*) * __capacity);
340 * Initializes this instance of %HashMapT by copying the elements of the specified @c map,
341 * with the specified load factor, hash code provider, and comparer.
345 * @return An error code
346 * @param[in] map The map to copy
347 * @param[in] loadFactor The maximum ratio of elements to buckets @n
348 * If it is @c 0, the default load factor (0.75) is used.
349 * @param[in] provider An instance of the IHashCodeProviderT-derived class that supplies the hash codes
350 * for all keys in this map
351 * @param[in] comparer An instance of the IComparerT-derived class to use when comparing keys
352 * @exception E_SUCCESS The method is successful.
353 * @exception E_INVALID_ARG Either of the following conditions has occurred: @n
354 * - A specified input parameter is invalid. @n
355 * - The @c loadFactor is negative. @n
356 * - The @c provider is a @c null or the @c comparer is a @c null.
357 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
358 * the @c map is modified during the operation of this method.
359 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
362 result Construct(const IMapT< KeyType, ValueType >& map, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
363 const IComparerT< KeyType >& comparer)
365 TryReturn((loadFactor >= 0), E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
367 result r = E_SUCCESS;
368 if (Float::Compare(loadFactor, 0) == 0)
370 loadFactor = DEFAULT_LOAD_FACTOR;
373 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
374 r = Construct(capacity, loadFactor, provider, comparer);
375 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
378 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
395 * Adds the specified key-value pair to a map.
399 * @return An error code
400 * @param[in] key The key of the value to add
401 * @param[in] value The value to add
402 * @exception E_SUCCESS The method is successful.
403 * @exception E_INVALID_ARG A specified input parameter is invalid, or
404 * the comparer has failed to compare the keys.
405 * @exception E_OBJ_ALREADY_EXIST The specified @c key already exists.
408 virtual result Add(const KeyType& key, const ValueType& value)
410 __HashMapEntryT< KeyType, ValueType >* pNewEntry;
412 result r = E_SUCCESS;
413 int hash = Hash(key);
414 int i = hash & (__capacity - 1);
417 r = ContainsKey(key, out);
418 TryReturn((!out), E_OBJ_ALREADY_EXIST, "[%s] The key is already exist in this collection.", GetErrorMessage(E_OBJ_ALREADY_EXIST));
419 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
422 pNewEntry = new __HashMapEntryT< KeyType, ValueType >(key, value, __pTable[i], hash);
423 TryReturn(pNewEntry != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
424 __pTable[i] = pNewEntry;
427 if (__count++ >= __threshold)
429 r = Resize(__capacity * 2);
430 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
437 * Gets the elements of a map in an instance of the IMapEnumeratorT-derived class.
441 * @return An instance of the IMapEnumeratorT-derived class if successful, @n
442 * else @c null if an exception occurs
443 * @exception E_SUCCESS The method is successful.
444 * @exception E_OUT_OF_MEMORY The memory is insufficient.
445 * @remarks The specific error code can be accessed using the GetLastResult() method.
446 * @see Tizen::Base::Collection::IEnumerator
447 * @see Tizen::Base::Collection::IMapEnumerator
449 virtual IEnumeratorT< MapEntryT< KeyType, ValueType > >* GetEnumeratorN(void) const
451 result r = E_SUCCESS;
453 __HashMapEnumeratorT< KeyType, ValueType >* pEnum = new __HashMapEnumeratorT< KeyType, ValueType >(*this, __modCount);
454 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
456 SetLastResult(E_SUCCESS);
465 * Gets the elements of a map in an instance of the IMapEnumeratorT class.
469 * @return An instance of the IMapEnumeratorT class if successful, @n
470 * else @c null if an exception occurs
471 * @exception E_SUCCESS The method is successful.
472 * @exception E_OUT_OF_MEMORY The memory is insufficient.
473 * @remarks The specific error code can be accessed using the GetLastResult() method.
474 * @see Tizen::Base::Collection::IEnumerator
475 * @see Tizen::Base::Collection::IMapEnumerator
477 virtual IMapEnumeratorT< KeyType, ValueType >* GetMapEnumeratorN(void) const
479 return dynamic_cast< IMapEnumeratorT< KeyType, ValueType >* >(GetEnumeratorN());
483 * Gets the value associated with the specified @c key.
487 * @return The value associated with the key, @n
488 * else @c null if an exception occurs
489 * @param[in] key The key to locate
490 * @param[out] value The value associated with the key
491 * @exception E_SUCCESS The method is successful.
492 * @exception E_INVALID_ARG A specified input parameter is invalid, or
493 * The comparer has failed to compare the keys.
494 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
497 virtual result GetValue(const KeyType& key, ValueType& value) const
499 result r = E_OBJ_NOT_FOUND;
501 int hash = Hash(key);
502 int i = hash & (__capacity - 1);
504 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
506 if (hash == pEntry->hash)
509 r = __pComparer->Compare(key, pEntry->key, cmpResult);
510 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
514 value = pEntry->value;
520 return E_OBJ_NOT_FOUND;
524 * Gets the value associated with the specified @c key.
528 * @return The value associated with the key, @n
529 * else @c null if an exception occurs
530 * @param[in] key The key to locate
531 * @param[out] value The value associated with the key
532 * @exception E_SUCCESS The method is successful.
533 * @exception E_INVALID_ARG A specified input parameter is invalid, or
534 * the comparer has failed to compare the keys.
535 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
538 virtual result GetValue(const KeyType& key, ValueType& value)
540 return (static_cast< const HashMapT< KeyType, ValueType >* >(this))->GetValue(key, value);
544 * Gets a list of all the keys in a map.
548 * @return A pointer to an IListT object containing all the keys in the map, @n
549 * else @c null if an exception occurs
550 * @exception E_SUCCESS The method is successful.
551 * @exception E_OUT_OF_MEMORY The memory is insufficient.
552 * @remarks The order of the keys is the same as the corresponding values in the IListT interface returned by the GetValuesN() method.
553 * @remarks The specific error code can be accessed using the GetLastResult() method.
556 virtual IListT< KeyType >* GetKeysN(void) const
558 result r = E_SUCCESS;
560 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
561 TryCatch(pList != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
563 r = pList->Construct(__count);
564 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
566 for (int i = 0; i < __capacity; i++)
568 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
570 r = pList->Add(pEntry->key);
571 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
575 SetLastResult(E_SUCCESS);
586 * Gets all the values in a map.
590 * @return A pointer to an IListT object containing all the values in the map, @n
591 * else @c null if an exception occurs
592 * @exception E_SUCCESS The method is successful.
593 * @exception E_OUT_OF_MEMORY The memory is insufficient.
594 * @remarks The specific error code can be accessed using the GetLastResult() method.
597 virtual IListT< ValueType >* GetValuesN(void) const
599 result r = E_SUCCESS;
601 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
602 TryCatch(pList != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
604 r = pList->Construct(__count);
605 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
607 for (int i = 0; i < __capacity; i++)
609 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
611 r = pList->Add(pEntry->value);
612 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
616 SetLastResult(E_SUCCESS);
627 * Removes the value associated with the specified @c key.
631 * @return An error code
632 * @param[in] key The key to remove
633 * @exception E_SUCCESS The method is successful.
634 * @exception E_INVALID_ARG The specified input parameter is invalid, or
635 * the comparer has failed to compare the keys.
636 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
639 virtual result Remove(const KeyType& key)
641 result r = E_OBJ_NOT_FOUND;
642 int hash = Hash(key);
643 int i = hash & (__capacity - 1);
645 __HashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
646 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
648 if (hash == pEntry->hash)
651 r = __pComparer->Compare(key, pEntry->key, cmpResult);
652 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
659 __pTable[i] = pEntry->pNext;
663 pPrev->pNext = pEntry->pNext;
675 return E_OBJ_NOT_FOUND;
679 * Removes all key-value pairs in the map.
683 virtual void RemoveAll(void)
694 * Replaces the value associated with the specified @c key with the specified new @c value.
698 * @return An error code
699 * @param[in] key The key for which the value is to replace
700 * @param[in] value The new value to replace
701 * @exception E_SUCCESS The method is successful.
702 * @exception E_INVALID_ARG A specified input parameter is invalid, or
703 * the comparer has failed to compare the keys.
704 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
705 * @remarks Use the Add() method to add a new key-value pair.
709 virtual result SetValue(const KeyType& key, const ValueType& value)
711 result r = E_SUCCESS;
712 int hash = Hash(key);
713 int i = hash & (__capacity - 1);
716 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
718 if (hash == pEntry->hash)
720 r = __pComparer->Compare(key, pEntry->key, cmpResult);
721 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
724 pEntry->value = value;
741 * Gets the number of pairs currently stored in a map.
745 * @return The pairs stored in the map
747 virtual int GetCount(void) const
753 * Checks whether a map contains the specified @c key.
757 * @return An error code
758 * @param[in] key The key to locate
759 * @param[out] out Set to @c true if the map contains the specified @c key, @n
761 * @exception E_SUCCESS The method is successful.
762 * @exception E_INVALID_ARG A specified input parameter is invalid, or
763 * the comparer has failed to compare the keys.
764 * @see ContainsValue()
766 virtual result ContainsKey(const KeyType& key, bool& out) const
770 result r = E_SUCCESS;
771 int hash = Hash(key);
772 int i = hash & (__capacity - 1);
774 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
776 if (hash == pEntry->hash)
779 r = __pComparer->Compare(key, pEntry->key, cmpResult);
780 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
794 * Checks whether a map contains the specified @c value.
798 * @return @c true if the map contains the specified @c value, @n
800 * @param[in] value The value to locate
804 virtual bool ContainsValue(const ValueType& value) const
806 for (int i = 0; i < __capacity; i++)
808 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
810 if (value == pEntry->value)
821 * Compares two instances of the %HashMapT class.
825 * @return @c true if the two instances match, @n
827 * @param[in] obj The object to compare with the current instance
828 * @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.
830 virtual bool Equals(const Object& obj) const
832 const HashMapT< KeyType, ValueType >* other = dynamic_cast< const HashMapT< KeyType, ValueType >* >(&obj);
837 else if (other == this)
841 else if (__count != other->__count)
847 for (int i = 0; i < __capacity; i++)
849 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
851 ValueType otherValue;
852 result r = other->GetValue(pEntry->key, otherValue);
857 if (pEntry->value != otherValue)
869 * Gets the hash value of the current instance.
873 * @return The hash value of the current instance
874 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
875 * the used hash function must generate a random distribution for all inputs.
877 virtual int GetHashCode(void) const
880 for (int i = 0; i < __capacity; i++)
882 for (__HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
884 hash += reinterpret_cast< int >(&pEntry->key);
885 hash += reinterpret_cast< int >(&pEntry->value);
893 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
895 * @param[in] map The instance of the %HashMapT class to copy from
897 HashMapT(const HashMapT< KeyType, ValueType >& map);
900 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
902 * @param[in] map An instance of %HashMapT
904 HashMapT< KeyType, ValueType >& operator =(const HashMapT< KeyType, ValueType >& map);
907 * Copies all the pairs from a specified @c map to this map.
909 * @return An error code
910 * @param[in] map The map to copy
911 * @exception E_SUCCESS The method is successful.
912 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
913 * The @c map is modified during the operation of this method.
915 result AddAll(const IMapT< KeyType, ValueType >& map)
917 result r = E_SUCCESS;
919 IMapT< KeyType, ValueType >* pMap = const_cast< IMapT< KeyType, ValueType >* >(&map);
920 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
922 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
924 while ((r = pMapEnum->MoveNext()) != E_OUT_OF_RANGE)
926 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
931 r = pMapEnum->GetKey(key);
932 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
934 r = pMapEnum->GetValue(value);
935 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
937 int hash = Hash(key);
938 int i = hash & (__capacity - 1);
939 __HashMapEntryT< KeyType, ValueType >* pNewEntry = new __HashMapEntryT< KeyType, ValueType >(key, value, __pTable[i], hash);
941 TryCatch(pNewEntry != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
942 __pTable[i] = pNewEntry;
946 if (null != pMapEnum)
954 if (null != pMapEnum)
963 * Gets the hash value for the specified object.
965 * @return The hash value for the specified object
966 * @param[in] obj The object to get hash value
968 int Hash(const KeyType& obj) const
970 int h = __pProvider->GetHashCode(obj);
972 h ^= (h >> 20) ^ (h >> 12);
974 return h ^ (h >> 7) ^ (h >> 4);
978 * Resizes the content of a map to a new array with a greater capacity.
980 * @return An error code
981 * @param[in] newCapacity The new capacity @n
982 * It must be a power of two and greater than the current capacity.
983 * @exception E_SUCCESS The method is successful.
984 * @exception E_OUT_OF_MEMORY The memory is insufficient.
985 * @remarks This method is called automatically when the number of keys in a map reaches its threshold.
987 result Resize(int newCapacity)
989 result r = E_SUCCESS;
990 __HashMapEntryT< KeyType, ValueType >** pNewTable = new __HashMapEntryT< KeyType, ValueType >*[newCapacity];
991 TryReturn(pNewTable != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
993 memset(pNewTable, null, sizeof(__HashMapEntryT< KeyType, ValueType >*) * newCapacity);
995 for (int i = 0; i < __capacity; i++)
997 __HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
998 while (null != pEntry)
1000 __HashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1001 int i = pEntry->hash & (newCapacity - 1);
1002 pEntry->pNext = pNewTable[i];
1003 pNewTable[i] = pEntry;
1009 __pTable = pNewTable;
1010 __capacity = newCapacity;
1011 __threshold = static_cast< int >(__capacity * __loadFactor);
1017 * Clears all key-value pairs in this map.
1021 for (int i = 0; i < __capacity; i++)
1023 __HashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1024 while (null != pEntry)
1026 __HashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1034 __HashMapEntryT< KeyType, ValueType >** __pTable;
1039 IHashCodeProviderT< KeyType >* __pProvider;
1040 IComparerT< KeyType >* __pComparer;
1041 bool __defaultConstruct;
1044 static const int DEFAULT_CAPACITY = 16;
1045 static const float DEFAULT_LOAD_FACTOR;
1047 friend class __HashMapEnumeratorT< KeyType, ValueType >;
1052 // @class __HashMapEntryT
1053 // @brief This is an entry for the %HashMapT class.
1056 template< class KeyType, class ValueType >
1057 class __HashMapEntryT
1062 * This is the constructor for this class.
1066 * @param[in] k The key to include in this entry
1067 * @param[in] v The value to include in this entry
1068 * @param[in] next A pointer to the next entry
1069 * @param[in] h A hash value of the key
1071 __HashMapEntryT(const KeyType& k, const ValueType& v, __HashMapEntryT< KeyType, ValueType >* next, int h)
1080 * This is the destructor for this class.
1084 virtual ~__HashMapEntryT(void)
1089 * Internal variable.
1096 * Internal variable.
1103 * Internal variable.
1110 * Internal variable.
1114 __HashMapEntryT< KeyType, ValueType >* pNext;
1116 }; // __HashMapEntryT
1119 // @class __HashMapEnumeratorT
1120 // @brief This is an implementation of the IMapEnumeratorT interface for the %HashMapT class.
1123 template< class KeyType, class ValueType >
1124 class __HashMapEnumeratorT
1125 : public IMapEnumeratorT< KeyType, ValueType >
1130 * This is the constructor for this class.
1134 * @param[in] map The map to enumerate
1135 * @param[in] modCount The modification count to detect the change in the map
1137 __HashMapEnumeratorT(const HashMapT< KeyType, ValueType >& map, int modCount)
1139 , __modCount(modCount)
1147 * This is the destructor for this class.
1151 virtual ~__HashMapEnumeratorT(void)
1157 * Gets the current object in the map.
1161 * @return An error code
1162 * @param[out] obj The current object
1163 * @exception E_SUCCESS The method is successful.
1164 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1165 * This enumerator is currently positioned before the first element or
1166 * past the last element or the map is modified after this enumerator is created.
1168 virtual result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1170 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1171 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1172 TryReturn((__pEntry != null), E_INVALID_OPERATION, "[%s] Invalid position(pEntry is null).", GetErrorMessage(E_INVALID_OPERATION));
1174 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pEntry->value);
1179 * Moves this enumerator to the next elements of the map.
1180 * 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.
1184 * @return An error code
1185 * @exception E_SUCCESS The method is successful.
1186 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1187 * the map is modified after this enumerator is created.
1188 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the map.
1191 virtual result MoveNext(void)
1193 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1194 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1196 if ((null != __pEntry) && (null != __pEntry->pNext))
1198 __pEntry = __pEntry->pNext;
1203 while (++__index < __map.__capacity)
1205 __pEntry = __map.__pTable[__index];
1206 if (null != __pEntry)
1213 return E_OUT_OF_RANGE;
1217 * Positions the enumerator before the first element in a map.
1221 * @return An error code
1222 * @exception E_SUCCESS The method is successful.
1223 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1224 * the map is modified after this enumerator is created.
1226 virtual result Reset(void)
1228 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1229 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1237 * Gets the current key in a map.
1241 * @return An error code
1242 * @param[out] key The current key
1243 * @exception E_SUCCESS The method is successful.
1244 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1245 * This enumerator is currently positioned before the first element or
1246 * past the last element or the map is modified after this enumerator is created.
1248 virtual result GetKey(KeyType& key) const
1250 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1251 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1252 TryReturn((__pEntry != null), E_INVALID_OPERATION, "[%s] Invalid position(pEntry is null).", GetErrorMessage(E_INVALID_OPERATION));
1254 key = __pEntry->key;
1259 * Gets the current value in a map.
1263 * @return An error code
1264 * @param[out] value The current value
1265 * @exception E_SUCCESS The method is successful.
1266 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1267 * This enumerator is currently positioned before the first element or
1268 * past the last element or the map is modified after the enumerator is created.
1270 virtual result GetValue(ValueType& value) const
1272 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1273 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1274 TryReturn((__pEntry != null), E_INVALID_OPERATION, "[%s] Invalid position(pEntry is null).", GetErrorMessage(E_INVALID_OPERATION));
1276 value = __pEntry->value;
1281 const HashMapT< KeyType, ValueType >& __map;
1283 __HashMapEntryT< KeyType, ValueType >* __pEntry;
1286 }; // __HashMapEnumeratorT
1289 // @class __HashMapDefaultProviderT
1290 // @brief This is an implementation of the IHashCodeProviderT interface for the HashMap class.
1293 template< class KeyType >
1294 class __HashMapDefaultProviderT
1295 : public IHashCodeProviderT< KeyType >
1300 * This is the default constructor for this class.
1304 __HashMapDefaultProviderT(void) {}
1307 * This is the destructor for this class.
1311 virtual ~__HashMapDefaultProviderT(void) {}
1314 * Gets the hash code of the specified object.
1318 * @return The hash code of the specified object
1319 * @see Tizen::Base::Object::GetHashCode
1321 virtual int GetHashCode(const KeyType& obj) const
1326 }; // __HashMapDefaultProviderT
1328 template< class KeyType, class ValueType >
1329 const float HashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1331 }}} // Tizen::Base::Collection
1333 #endif //_FBASE_COL_HASH_MAP_T_H_