inc/FBaseColMultiHashMapT.h

   1 //
   2 // Copyright (c) 2012 Samsung Electronics Co., Ltd.
   3 //
   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
   7 //
   8 // http://www.apache.org/licenses/LICENSE-2.0
   9 //
  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.
  15 //
  16
  17 /**
  18  * @file                FBaseColMultiHashMapT.h
  19  * @brief               This is the header file for the %MultiHashMapT class.
  20  *
  21  * This header file contains the declarations of the %MultiHashMapT class.
  22  */
  23 #ifndef _FBASE_COL_MULTI_HASH_MAP_T_H_
  24 #define _FBASE_COL_MULTI_HASH_MAP_T_H_
  25
  26 #include <FBaseObject.h>
  27 #include <FBaseResult.h>
  28 #include <FBaseColIComparerT.h>
  29 #include <FBaseColIHashCodeProviderT.h>
  30 #include <FBaseColIListT.h>
  31 #include <FBaseColIMultiMapT.h>
  32 #include <FBaseColMapEntryT.h>
  33 #include <FBaseComparerT.h>
  34 #include <FBaseFloat.h>
  35
  36 namespace Tizen { namespace Base { namespace Collection
  37 {
  38
  39 template< class KeyType, class ValueType > class __MultiHashMapEntryT;
  40 template< class KeyType, class ValueType > class __MultiHashMapEnumeratorT;
  41 template< class KeyType, class ValueType > class __EntryValueEnumeratorT;
  42 template< class KeyType > class __MultiHashMapDefaultProviderT;
  43
  44 template< class ValueType > class __ValueNodeT;
  45
  46 /**
  47  * @class MultiHashMapT
  48  * @brief This class represents a template-based collection of associated keys and values that are organized based on the hash code of a key.
  49  *
  50  * @since 2.0
  51  *
  52  * The %MultiHashMapT class represents a template-based collection of associated keys and values that are organized based on the hash code of a key.
  53  * There is no limit on the number of elements having the same key, but duplicate elements with the same key are not allowed.
  54  * The key and value cannot be @c null. Several methods in the %MultiHashMapT class need an assignment(=) operator of KeyType, as well as assignment(=) and equivalent(==) operators of ValueType.
  55  * @n
  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>.
  57  *
  58  * The following example demonstrates how to use the %MultiHashMapT class.
  59
  60  *
  61  * @code
  62  *
  63  *      #include <FBase.h>
  64  *
  65  *      using namespace Tizen::Base;
  66  *      using namespace Tizen::Base::Collection;
  67  *
  68  *      void
  69  *      MyClass::MultiHashMapTSample(void)
  70  *      {
  71  *              MultiHashMapT< int, int > map;
  72  *
  73  *              // Constructs a MultiHashMap instance with default capacity, load factor, hash code provider, and comparer
  74  *              map.Construct();
  75  *
  76  *              int key;
  77  *              int value;
  78  *
  79  *              map.Add(1, 1000);               // map.GetCount() : 1, map : (1 -> 1000)
  80  *              map.Add(2, 2000);               // map.GetCount() : 2, map : (1 -> 1000), (2 -> 2000)
  81  *              map.Add(3, 3000);               // map.GetCount() : 3, map : (1 -> 1000), (2 -> 2000), (3 -> 3000)
  82  *              map.Add(3, 30);                 // map.GetCount() : 4, map : (1 -> 1000), (2 -> 2000), (3 -> 3000, 30)
  83  *
  84  *              // Gets values with the specified key
  85  *              key = 1;
  86  *              IEnumeratorT< int >*    pValueEnum = map.GetValuesN(key);
  87  *              while (pValueEnum->MoveNext() == E_SUCCESS)
  88  *              {
  89  *                      pValueEnum->GetCurrent(value);
  90  *              }
  91  *
  92  *              delete pValueEnum;
  93  *
  94  *              // Removes the values with the specified key
  95  *              key = 3;
  96  *              map.Remove(key);                // 30, 3000 removed
  97  *
  98  *              // Uses an enumerator to access elements in the map
  99  *              IMapEnumeratorT< int, int >*    pMapEnum = map.GetMapEnumeratorN();
 100  *              while (pMapEnum->MoveNext() == E_SUCCESS)
 101  *              {
 102  *                      pMapEnum->GetKey(key);
 103  *                      pMapEnum->GetValue(value);
 104  *              }
 105  *
 106  *              delete pMapEnum;
 107  *      }
 108  *
 109  * @endcode
 110  */
 111 template< class KeyType, class ValueType >
 112 class MultiHashMapT
 113         : public IMultiMapT< KeyType, ValueType >
 114         , public Object
 115 {
 116 public:
 117         /**
 118          * The object is not fully constructed after this constructor is called. For full construction, @n
 119          * the Construct() method must be called right after calling this constructor.
 120          *
 121          * @since 2.0
 122          */
 123         MultiHashMapT(void)
 124                 : __pTable(null)
 125                 , __count(0)
 126                 , __capacity(0)
 127                 , __loadFactor(0)
 128                 , __threshold(0)
 129                 , __pProvider(null)
 130                 , __pComparer(null)
 131                 , __defaultConstruct(false)
 132                 , __modCount(0)
 133         {
 134         }
 135
 136         /**
 137          * This destructor overrides Tizen::Base::Object::~Object().
 138          *
 139          * @since 2.0
 140          */
 141         virtual ~MultiHashMapT(void)
 142         {
 143                 if (null != __pTable)
 144                 {
 145                         Reset();
 146                         delete[] __pTable;
 147                 }
 148
 149                 if (__defaultConstruct)
 150                 {
 151                         delete __pProvider;
 152                         delete __pComparer;
 153                 }
 154
 155         }
 156
 157         /**
 158          * Initializes this instance of %MultiHashMapT with the given capacity and load factor.
 159          *
 160          * @since 2.0
 161          *
 162          * @return              An error code
 163          * @param[in]   capacity                        The initial capacity
 164          * @param[in]   loadFactor                      The maximum ratio of elements to buckets
 165          * @exception   E_SUCCESS                       The method is successful.
 166          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 167          *                                                                      - A specified input parameter is invalid.
 168          *                                                                      - The specified @c capacity or the specified @c loadFactor is negative.
 169          * @remarks             The key type must be a primitive data type.
 170          * @see                 MultiHashMapT()
 171          */
 172         result Construct(int capacity = 16, float loadFactor = 0.75)
 173         {
 174                 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
 175                 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
 176
 177                 result r = E_SUCCESS;
 178
 179                 // set capacity
 180                 if (capacity == 0)
 181                 {
 182                         __capacity = DEFAULT_CAPACITY;
 183                 }
 184                 else
 185                 {
 186                         __capacity = 1;
 187                         while (__capacity < capacity)
 188                         {
 189                                 __capacity <<= 1;
 190                         }
 191                 }
 192
 193                 // set load factor
 194                 if (Float::Compare(loadFactor, 0) == 0)
 195                 {
 196                         __loadFactor = DEFAULT_LOAD_FACTOR;
 197                 }
 198                 else
 199                 {
 200                         __loadFactor = loadFactor;
 201                 }
 202
 203                 // set threshold
 204                 __threshold = static_cast< int >(__capacity * __loadFactor);
 205
 206                 // set hash code provider
 207                 __pProvider = new __MultiHashMapDefaultProviderT< KeyType >();
 208                 TryCatch(__pProvider != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 209
 210                 // set comparer
 211                 __pComparer = new Tizen::Base::ComparerT< KeyType >();
 212                 TryCatch(__pComparer != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 213
 214                 __defaultConstruct = true;
 215
 216                 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
 217                 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 218
 219                 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
 220
 221                 return r;
 222
 223 CATCH:
 224                 __capacity = 0;
 225                 delete __pProvider;
 226                 delete __pComparer;
 227
 228                 return r;
 229         }
 230
 231         /**
 232          * Initializes this instance of %MultiHashMapT by copying the elements of the specified map.
 233          *
 234          * @since 2.0
 235          *
 236          * @return              An error code
 237          * @param[in]   map                                     The map to copy
 238          * @param[in]   loadFactor                      The maximum ratio of elements to buckets @n
 239          *                                                                      If it is @c 0, the default load factor(0.75) is used.
 240          * @exception   E_SUCCESS                       The method is successful.
 241          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 242          *                                                                      - A specified input parameter is invalid
 243          *                                                                      - The specified @c loadFactor is negative.
 244          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
 245          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 246          *                                                                      - The specified @c map is modified during the operation of this method.
 247          * @see                 MultiHashMapT()
 248          */
 249         result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor = 0.75)
 250         {
 251                 TryReturn((loadFactor >= 0), E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
 252
 253                 result r = E_SUCCESS;
 254
 255                 if (Float::Compare(loadFactor, 0) == 0)
 256                 {
 257                         loadFactor = DEFAULT_LOAD_FACTOR;
 258                 }
 259
 260                 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
 261                 r = Construct(capacity, loadFactor);
 262                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 263
 264                 r = AddAll(map);
 265                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 266
 267                 return r;
 268
 269 CATCH:
 270                 Reset();
 271                 delete[] __pTable;
 272                 __pTable = null;
 273
 274                 __capacity = 0;
 275
 276                 __pProvider = null;
 277                 delete __pProvider;
 278
 279                 __pComparer = null;
 280                 delete __pComparer;
 281
 282                 return r;
 283         }
 284
 285         /**
 286          * Initializes this instance of %MultiHashMapT that is empty,
 287          * with the specified initial capacity, load factor, hash code provider, and comparer.
 288          *
 289          * @since 2.0
 290          *
 291          * @return              An error code
 292          * @param[in]   capacity                The initial capacity @n
 293          *                                                              If it is @c 0, the default capacity(16) is used.
 294          * @param[in]   loadFactor              The maximum ratio of elements to buckets @n
 295          *                                                              If it is @c 0, the default load factor(0.75) is used.
 296          * @param[in]   provider                An instance of the IHashCodeProvider derived class that supplies the hash codes
 297          *                                                              for all the keys in this map
 298          * @param[in]   comparer                An instance of the IComparer derived class to use when comparing the keys
 299          * @exception   E_SUCCESS               The method is successful.
 300          * @exception   E_INVALID_ARG   Either of the following conditions has occurred:
 301          *                                                              - A specified input parameter is invalid.
 302          *                                                              - The specified @c capacity or the specified @c loadFactor is negative.
 303          * @remarks             The instances of hash code provider and the comparer are not deallocated later from this map.
 304          * @see                 MultiHashMapT()
 305          */
 306         result Construct(int capacity, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
 307                                          const IComparerT< KeyType >& comparer)
 308         {
 309                 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
 310                 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
 311
 312                 result r = E_SUCCESS;
 313                 // set capacity
 314                 if (capacity == 0)
 315                 {
 316                         __capacity = DEFAULT_CAPACITY;
 317                 }
 318                 else
 319                 {
 320                         __capacity = 1;
 321                         while (__capacity < capacity)
 322                         {
 323                                 __capacity <<= 1;
 324                         }
 325                 }
 326
 327                 // set load factor
 328                 if (Float::Compare(loadFactor, 0) == 0)
 329                 {
 330                         __loadFactor = DEFAULT_LOAD_FACTOR;
 331                 }
 332                 else
 333                 {
 334                         __loadFactor = loadFactor;
 335                 }
 336
 337                 // set threshold
 338                 __threshold = static_cast< int >(__capacity * __loadFactor);
 339
 340                 // set hash code provider
 341                 __pProvider = const_cast< IHashCodeProviderT< KeyType >* >(&provider);
 342
 343                 // set comparer
 344                 __pComparer = const_cast< IComparerT< KeyType >* >(&comparer);
 345
 346                 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
 347                 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 348
 349                 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
 350
 351                 return r;
 352
 353 CATCH:
 354                 __capacity = 0;
 355                 __pProvider = null;
 356                 __pComparer = null;
 357
 358                 return r;
 359         }
 360
 361         /**
 362          * Initializes this instance of %MultiHashMapT by copying the elements of the specified map,
 363          * with the specified load factor, hash code provider, and comparer.
 364          *
 365          * @since 2.0
 366          *
 367          * @return              An error code
 368          * @param[in]   map                                     The map to copy
 369          * @param[in]   loadFactor                      The maximum ratio of elements to buckets @n
 370          *                                                                      If it is @c 0, the default load factor(0.75) is used.
 371          * @param[in]   provider                        An instance of the IHashCodeProvider derived class that supplies the hash codes
 372          *                                                                      for all the keys in this map
 373          * @param[in]   comparer                        An instance of the IComparer derived class to use when comparing the keys
 374          * @exception   E_SUCCESS                       The method is successful.
 375          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 376          *                                                                      - A specified input parameter is invalid.
 377          *                                                                      - The specified @c loadFactor is negative.
 378          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
 379          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 380          *                                                                      - The specified @c map is modified during the operation of this method.
 381          * @remarks             The instances of the hash code provider and the comparer are not deallocated later from this map.
 382          * @see                 MultiHashMapT()
 383          */
 384         result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
 385                                          const IComparerT< KeyType >& comparer)
 386         {
 387                 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
 388
 389                 result r = E_SUCCESS;
 390
 391                 if (Float::Compare(loadFactor, 0) == 0)
 392                 {
 393                         loadFactor = DEFAULT_LOAD_FACTOR;
 394                 }
 395
 396                 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
 397
 398                 r = Construct(capacity, loadFactor, provider, comparer);
 399                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 400
 401                 r = AddAll(map);
 402                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 403
 404                 return r;
 405
 406 CATCH:
 407                 Reset();
 408                 delete[] __pTable;
 409                 __pTable = null;
 410
 411                 __capacity = 0;
 412                 __pProvider = null;
 413                 __pComparer = null;
 414
 415                 return r;
 416         }
 417
 418         /**
 419          * Adds the specified key-value pair to this map.
 420          *
 421          * @since 2.0
 422          *
 423          * @return              An error code
 424          * @param[in]   key                                     The key of the value to add
 425          * @param[in]   value                           The value to add
 426          * @exception   E_SUCCESS                       The method is successful.
 427          * @exception   E_OBJ_ALREADY_EXIST     The specified @c key and @c value pair already exists.
 428          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 429          *                                                                      - A specified input parameter is invalid.
 430          *                                                                      - The comparer has failed to compare the keys.
 431          * @remarks     SetItem() can be used to set a value to a key that does not already exist. @n
 432          *                              However, setting a value to a key that already exists overwrites this value.
 433          * @see                 Remove()
 434          * @see                 SetValue()
 435          */
 436         virtual result Add(const KeyType& key, const ValueType& value)
 437         {
 438                 result r = E_SUCCESS;
 439                 int hash = Hash(key);
 440                 int i = hash & (__capacity - 1);
 441                 __ValueNodeT< ValueType >* pNode = null;
 442                 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
 443                 while (null != pEntry)
 444                 {
 445                         if (hash == pEntry->hash)
 446                         {
 447                                 int cmpResult;
 448                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 449                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 450
 451                                 if (cmpResult == 0)
 452                                 {
 453                                         pNode = pEntry->pList;
 454                                         while (true)
 455                                         {
 456                                                 if (pNode->value == value)
 457                                                 {
 458                                                         return E_OBJ_ALREADY_EXIST;
 459                                                 }
 460
 461                                                 if (pNode->pNext != null)
 462                                                 {
 463                                                         pNode = pNode->pNext;
 464                                                 }
 465                                                 else
 466                                                 {
 467                                                         pEntry->modCount++;
 468                                                         break;
 469                                                 }
 470                                         }
 471                                         break;
 472                                 }
 473                         }
 474                         pEntry = pEntry->pNext;
 475                 }
 476
 477                 __ValueNodeT< ValueType >* pNewNode = new __ValueNodeT< ValueType >(value);
 478                 TryReturn(pNewNode != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 479
 480                 // key is not exist in this map.
 481                 if (pEntry == null)
 482                 {
 483                         __MultiHashMapEntryT< KeyType, ValueType >* pNewEntry = new __MultiHashMapEntryT< KeyType, ValueType >(key, pNewNode, __pTable[i],
 484                                                                                                                                                                                                                                    hash);
 485                         TryReturn(pNewEntry != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 486                         __pTable[i] = pNewEntry;
 487                 }
 488                 // key is already exist in this map, but value is not.
 489                 else
 490                 {
 491                         // pNode is the last value associated to the key
 492                         pNode->pNext = pNewNode;
 493                 }
 494
 495                 __modCount++;
 496
 497                 if (__count++ >= __threshold)
 498                 {
 499                         r = Resize(__capacity * 2);
 500                         TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
 501                 }
 502
 503                 return E_SUCCESS;
 504         }
 505
 506         /**
 507          * Gets the enumerator of this map.
 508          *
 509          * @since 2.0
 510          *
 511          * @return              The enumerator (an instance of the IMapEnumeratorT derived class) of this map, @n
 512          *                              else @c null if an exception occurs
 513          * @exception   E_SUCCESS               The method is successful.
 514          * @exception   E_OUT_OF_MEMORY The memory is insufficient.
 515          * @remarks
 516          *                              - If the key has multiple values, the enumeration proceeds as follows: @n
 517          *                              {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
 518          *                              - The specific error code can be accessed using the GetLastResult() method.
 519          * @see                 Tizen::Base::Collection::IEnumerator
 520          * @see                 Tizen::Base::Collection::IMapEnumerator
 521          */
 522         virtual IEnumeratorT< MapEntryT< KeyType, ValueType > >* GetEnumeratorN(void) const
 523         {
 524                 result r = E_SUCCESS;
 525
 526                 __MultiHashMapEnumeratorT< KeyType, ValueType >* pEnum = new __MultiHashMapEnumeratorT< KeyType, ValueType >(*this, __modCount);
 527                 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 528
 529                 SetLastResult(E_SUCCESS);
 530                 return pEnum;
 531
 532 CATCH:
 533                 SetLastResult(r);
 534                 return null;
 535         }
 536
 537         /**
 538          * Gets the IMapEnumerator of this map.
 539          *
 540          * @since 2.0
 541          *
 542          * @return              The enumerator (an instance of the IMapEnumeratorT derived class) of this map, @n
 543          *                              else @c null if an exception occurs
 544          * @exception   E_SUCCESS                               The method is successful.
 545          * @exception   E_OUT_OF_MEMORY                 The memory is insufficient.
 546          * @remarks
 547          *                              - If the key has multiple values, the enumeration proceeds like this: @n
 548          *                              {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
 549          *                              - The specific error code can be accessed using the GetLastResult() method.
 550          * @see                 Tizen::Base::Collection::IEnumerator
 551          * @see                 Tizen::Base::Collection::IMapEnumerator
 552          */
 553         virtual IMapEnumeratorT< KeyType, ValueType >* GetMapEnumeratorN(void) const
 554         {
 555                 return dynamic_cast< IMapEnumeratorT< KeyType, ValueType >* >(GetEnumeratorN());
 556         }
 557
 558         /**
 559          * Gets the enumerator of the values associated with the specified key.
 560          *
 561          * @since 2.0
 562          *
 563          * @return              The enumerator (an instance of the IEnumeratorT derived class) of the values associated with the specified key, @n
 564          *                              else @c null if an exception occurs
 565          * @param[in]   key                                     The key to locate
 566          * @exception   E_SUCCESS                       The method is successful.
 567          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 568          *                                                                      - A specified input parameter is invalid.
 569          *                                                                      - The comparer has failed to compare the keys.
 570          * @exception   E_OBJ_NOT_FOUND         The specified @c key has not been found in the map.
 571          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 572          * @see                 SetValue()
 573          */
 574         virtual IEnumeratorT< ValueType >* GetValuesN(const KeyType& key) const
 575         {
 576                 result r = E_OBJ_NOT_FOUND;
 577
 578                 int hash = Hash(key);
 579                 int i = hash & (__capacity - 1);
 580                 IEnumeratorT< ValueType >* pEnum = null;
 581
 582                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 583                 {
 584                         if (hash == pEntry->hash)
 585                         {
 586                                 int cmpResult;
 587                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 588                                 TryCatch(r == E_SUCCESS, r = E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 589
 590                                 if (0 == cmpResult)
 591                                 {
 592                                         pEnum = new __EntryValueEnumeratorT< KeyType, ValueType >(*pEntry, pEntry->modCount);
 593                                         TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 594                                         r = E_SUCCESS;
 595                                         break;
 596                                 }
 597
 598                                 r = E_OBJ_NOT_FOUND;
 599                         }
 600                 }
 601
 602                 SetLastResult(r);
 603                 return pEnum;
 604
 605 CATCH:
 606                 SetLastResult(r);
 607                 return null;
 608         }
 609
 610         /**
 611          * Gets a list of all the unique keys in this map.
 612          *
 613          * @since 2.0
 614          *
 615          * @return              The list of all the unique keys in this map, @n
 616          *                              else @c null if an exception occurs
 617          * @exception   E_SUCCESS               The method is successful.
 618          * @exception   E_OUT_OF_MEMORY The memory is insufficient.
 619          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 620          * @see                 GetValuesN()
 621          */
 622         virtual IListT< KeyType >* GetKeysN(void) const
 623         {
 624                 ClearLastResult();
 625
 626                 result r = E_SUCCESS;
 627                 int keyCount = 0;
 628
 629                 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
 630                 r = pList->Construct(__count);
 631                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 632
 633                 for (int i = 0; i < __capacity; i++)
 634                 {
 635                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 636                         {
 637                                 r = pList->Add(pEntry->key);
 638                                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 639                                 keyCount++;
 640                         }
 641                 }
 642
 643                 return pList;
 644
 645 CATCH:
 646                 delete pList;
 647
 648                 SetLastResult(r);
 649                 return null;
 650         }
 651
 652         /**
 653          * Gets a list of all the values in this map.
 654          *
 655          * @since 2.0
 656          *
 657          * @return              The list of all the values in this map, @n
 658          *                              else @c null if an exception occurs
 659          * @exception   E_SUCCESS               The method is successful.
 660          * @exception   E_OUT_OF_MEMORY The memory is insufficient.
 661          * @remarks     The specific error code can be accessed using the GetLastResult() method.
 662          * @see                 GetKeysN()
 663          */
 664         virtual IListT< ValueType >* GetValuesN(void) const
 665         {
 666                 ClearLastResult();
 667
 668                 result r = E_SUCCESS;
 669
 670                 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
 671                 r = pList->Construct(__count);
 672                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 673
 674                 for (int i = 0; i < __capacity; i++)
 675                 {
 676                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 677                         {
 678                                 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 679                                 {
 680                                         r = pList->Add(pNode->value);
 681                                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 682                                 }
 683                         }
 684                 }
 685
 686                 return pList;
 687
 688 CATCH:
 689                 delete pList;
 690
 691                 SetLastResult(r);
 692                 return null;
 693         }
 694
 695         /**
 696          * Removes all the values for the specified key.
 697          *
 698          * @since 2.0
 699          *
 700          * @return              An error code
 701          * @param[in]   key                             The key to remove
 702          * @exception   E_SUCCESS                       The method is successful.
 703          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 704          *                                                                      - The specified input parameter is invalid.
 705          *                                                                      - The comparer has failed to compare the keys.
 706          * @exception   E_OBJ_NOT_FOUND         The specified @c key has not been found in the map.
 707          * @see                 Add()
 708          */
 709         virtual result Remove(const KeyType& key)
 710         {
 711                 result r = E_OBJ_NOT_FOUND;
 712                 int hash = Hash(key);
 713                 int i = hash & (__capacity - 1);
 714
 715                 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
 716                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 717                 {
 718                         if (hash == pEntry->hash)
 719                         {
 720                                 int cmpResult;
 721                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 722                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 723
 724                                 r = E_OBJ_NOT_FOUND;
 725
 726                                 if (cmpResult == 0)
 727                                 {
 728                                         __modCount++;
 729                                         if (pPrev == pEntry)
 730                                         {
 731                                                 __pTable[i] = pEntry->pNext;
 732                                         }
 733                                         else
 734                                         {
 735                                                 pPrev->pNext = pEntry->pNext;
 736                                         }
 737
 738                                         __ValueNodeT< ValueType >* pNode = pEntry->pList;
 739                                         while (null != pNode)
 740                                         {
 741                                                 __ValueNodeT< ValueType >* pTemp = pNode;
 742                                                 pNode = pNode->pNext;
 743                                                 delete pTemp;
 744                                                 __count--;
 745                                         }
 746                                         delete pEntry;
 747                                         r = E_SUCCESS;
 748                                         break;
 749                                 }
 750                         }
 751                         pPrev = pEntry;
 752                 }
 753
 754                 return r;
 755         }
 756
 757         /**
 758          * Removes the specified value associated with the specified key. @n
 759          * The key is also removed if there is no value associated with it.
 760          *
 761          * @since 2.0
 762          *
 763          * @return              An error code
 764          * @param[in]   key                             The key whose mapping is removed from the map
 765          * @param[in]   value                           The value to remove
 766          * @exception   E_SUCCESS                       The method is successful.
 767          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 768          *                                                                      - A specified input parameter is invalid.
 769          *                                                                      - The comparer has failed to compare the keys.
 770          * @exception   E_OBJ_NOT_FOUND         The specified @c key and @c value pair is not found in the map.
 771          * @see                 Add()
 772          */
 773         virtual result Remove(const KeyType& key, const ValueType& value)
 774         {
 775                 result r = E_OBJ_NOT_FOUND;
 776                 int hash = Hash(key);
 777                 int i = hash & (__capacity - 1);
 778
 779                 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
 780                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 781                 {
 782                         if (hash == pEntry->hash)
 783                         {
 784                                 int cmpResult;
 785                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 786                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 787
 788                                 r = E_OBJ_NOT_FOUND;
 789                                 if (cmpResult == 0)
 790                                 {
 791                                         __ValueNodeT< ValueType >* pPrevNode = pEntry->pList;
 792                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 793                                         {
 794                                                 if (value == pNode->value)
 795                                                 {
 796                                                         __modCount++;
 797                                                         __count--;
 798                                                         if (pPrevNode == pNode)
 799                                                         {
 800                                                                 pEntry->pList = pNode->pNext;
 801                                                         }
 802                                                         else
 803                                                         {
 804                                                                 pPrevNode->pNext = pNode->pNext;
 805                                                         }
 806
 807                                                         delete pNode;
 808
 809                                                         pEntry->modCount++;
 810
 811                                                         if (null == pEntry->pList)
 812                                                         {
 813                                                                 if (pPrev == pEntry)
 814                                                                 {
 815                                                                         __pTable[i] = pEntry->pNext;
 816                                                                 }
 817                                                                 else
 818                                                                 {
 819                                                                         pPrev->pNext = pEntry->pNext;
 820                                                                 }
 821                                                                 delete pEntry;
 822                                                         }
 823                                                         r = E_SUCCESS;
 824                                                         break;
 825                                                 }
 826                                                 pPrevNode = pNode;
 827                                         }
 828                                         if (!IsFailed(r))
 829                                         {
 830                                                 break;
 831                                         }
 832                                 }
 833                         }
 834                         pPrev = pEntry;
 835                 }
 836
 837                 return r;
 838         }
 839
 840         /**
 841          * Removes all the key-value pairs in this map.
 842          *
 843          * @since 2.0
 844          */
 845         virtual void RemoveAll(void)
 846         {
 847                 if (__count > 0)
 848                 {
 849                         __modCount++;
 850                         Reset();
 851                         __count = 0;
 852                 }
 853         }
 854
 855         /**
 856          * Replaces the value associated with the key, with the specified @c newValue.
 857          *
 858          * @since 2.0
 859          *
 860          * @return              An error code
 861          * @param[in]   key                                     The key
 862          * @param[in]   value                           The value to replace
 863          * @param[in]   newValue                        The new value to replace the existing value
 864          * @exception   E_SUCCESS                       The method is successful.
 865          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 866          *                                                                      - The specified input parameter is invalid.
 867          *                                                                      - The comparer has failed to compare the keys.
 868          * @exception   E_OBJ_NOT_FOUND         The specified @c key and @c value pair is not found in the map.
 869          * @remarks             To add a new key-value pair, use the Add() method.
 870          * @see                 GetValuesN()
 871          */
 872         virtual result SetValue(const KeyType& key, const ValueType& value, const ValueType& newValue)
 873         {
 874                 result r = E_SUCCESS;
 875                 int hash = Hash(key);
 876                 int i = hash & (__capacity - 1);
 877                 __ValueNodeT< ValueType >* pNode = null;
 878                 bool pairExist = false;
 879                 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
 880                 while (null != pEntry)
 881                 {
 882                         if (hash == pEntry->hash)
 883                         {
 884                                 int cmpResult;
 885                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 886                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 887
 888                                 if (cmpResult == 0)
 889                                 {
 890                                         pNode = pEntry->pList;
 891                                         while (true)
 892                                         {
 893                                                 if (pNode->value == value)
 894                                                 {
 895                                                         __modCount++;
 896                                                         pNode->value = newValue;
 897                                                         pairExist = true;
 898                                                         break;
 899                                                 }
 900                                                 if (pNode->pNext != null)
 901                                                 {
 902                                                         pNode = pNode->pNext;
 903                                                 }
 904                                                 else
 905                                                 {
 906                                                         pEntry->modCount++;
 907                                                         break;
 908                                                 }
 909                                         }
 910                                         break;
 911                                 }
 912                         }
 913                         pEntry = pEntry->pNext;
 914                 }
 915
 916                 if (!pairExist)
 917                 {
 918                         r = E_OBJ_NOT_FOUND;
 919                 }
 920
 921                 return r;
 922         }
 923
 924         /**
 925          * Gets the number of values currently stored in this map.
 926          *
 927          * @since 2.0
 928          *
 929          * @return              The number of values currently stored in this map
 930          */
 931         virtual int GetCount(void) const
 932         {
 933                 return __count;
 934         }
 935
 936         /**
 937          * Gets the number of values whose keys match the specified key.
 938          *
 939          * @since 2.0
 940          *
 941          * @return              An error code
 942          * @param[in]   key                                     The key to locate
 943          * @param[out]  count                           The number of values whose key is @c key
 944          * @exception   E_SUCCESS                       The method is successful.
 945          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 946          *                                                                      - A specified input parameter is invalid.
 947          *                                                                      - The comparer has failed to compare the keys.
 948          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 949          */
 950         virtual result GetCount(const KeyType& key, int& count) const
 951         {
 952                 result r = E_OBJ_NOT_FOUND;
 953                 int hash = Hash(key);
 954                 int i = hash & (__capacity - 1);
 955
 956                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 957                 {
 958                         if (hash == pEntry->hash)
 959                         {
 960                                 int cmpResult;
 961                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 962                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 963
 964                                 if (0 == cmpResult)
 965                                 {
 966                                         int __count = 0;
 967                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 968                                         {
 969                                                 __count++;
 970                                         }
 971                                         count = __count;
 972                                         r = E_SUCCESS;
 973                                         break;
 974                                 }
 975
 976                                 r = E_OBJ_NOT_FOUND;
 977                         }
 978                 }
 979
 980                 return r;
 981         }
 982
 983         /**
 984          * Checks whether the map contains the specified key and value.
 985          *
 986          * @since 2.0
 987          *
 988          * @return              An error code
 989          * @param[in]   key                             The key to locate
 990          * @param[in]   value                           The value to locate
 991          * @param[out]  out                                     Set to @c true if the map contains the specified key and value pair, @n
 992          *                                                                      else @c false
 993          * @exception   E_SUCCESS                       The method is successful.
 994          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 995          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 996          *                                                                      - The comparer has failed to compare the keys.
 997          * @see                 ContainsKey()
 998          * @see                 ContainsValue()
 999          */
1000         virtual result Contains(const KeyType& key, const ValueType& value, bool& out) const
1001         {
1002                 out = false;
1003
1004                 result r = E_SUCCESS;
1005                 int hash = Hash(key);
1006                 int i = hash & (__capacity - 1);
1007
1008                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1009                 {
1010                         if (hash == pEntry->hash)
1011                         {
1012                                 int cmpResult;
1013                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1014                                 if (IsFailed(r))
1015                                 {
1016                                         AppLogException("[%s] Propagating.", GetErrorMessage(r));
1017                                         out = false;
1018                                         return E_INVALID_ARG;
1019                                 }
1020
1021                                 if (cmpResult == 0)
1022                                 {
1023                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1024                                         {
1025                                                 if (value == pNode->value)
1026                                                 {
1027                                                         r = E_SUCCESS;
1028                                                         out = true;
1029                                                         break;
1030                                                 }
1031                                         }
1032                                         break;
1033                                 }
1034                         }
1035                 }
1036
1037                 return E_SUCCESS;
1038         }
1039
1040         /**
1041          * Checks whether the map contains the specified key.
1042          *
1043          * @since 2.0
1044          *
1045          * @return              An error code
1046          * @param[in]   key                             The key to locate
1047          * @param[out]  out                                     Set to @c true if the map contains the specified key, @n
1048          *                                                                      else @c false
1049          * @exception   E_SUCCESS                       The method is successful.
1050          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
1051          *                                                                      - A specified input parameter is invalid.
1052          *                                                                      - The comparer has failed to compare the keys.
1053          * @see                 ContainsValue()
1054          * @see                 Contains()
1055          */
1056         virtual result ContainsKey(const KeyType& key, bool& out) const
1057         {
1058                 out = false;
1059                 result r = E_SUCCESS;
1060                 int hash = Hash(key);
1061                 int i = hash & (__capacity - 1);
1062
1063                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1064                 {
1065                         if (hash == pEntry->hash)
1066                         {
1067                                 int cmpResult;
1068                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1069                                 if (IsFailed(r))
1070                                 {
1071                                         AppLogException("[%s] Propagating.", GetErrorMessage(r));
1072                                         out = false;
1073                                         return E_INVALID_ARG;
1074                                 }
1075                                 if (cmpResult == 0)
1076                                 {
1077                                         out = true;
1078                                         break;
1079                                 }
1080                         }
1081                 }
1082
1083                 return E_SUCCESS;
1084         }
1085
1086         /**
1087          * Checks whether the map contains the specified value.
1088          *
1089          * @since 2.0
1090          *
1091          * @return              @c true if the map contains the specified value, @n
1092          *                              else @c false
1093          * @param[in]   value   The value to locate
1094          *
1095          * @see                 ContainsKey()
1096          * @see                 Contains()
1097          */
1098         virtual bool ContainsValue(const ValueType& value) const
1099         {
1100                 bool out = false;
1101                 for (int i = 0; i < __capacity; i++)
1102                 {
1103                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1104                         {
1105                                 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1106                                 {
1107                                         if (value == pNode->value)
1108                                         {
1109                                                 out = true;
1110                                                 break;
1111                                         }
1112                                 }
1113
1114                                 if (out)
1115                                         break;
1116                         }
1117
1118                         if (out)
1119                                 break;
1120                 }
1121
1122                 return out;
1123         }
1124
1125         /**
1126          * Compares the specified instance to the current instance for equality.
1127          *
1128          * @since 2.0
1129          *
1130          * @return              @c true if the two instances are equal, @n
1131          *                              else @c false
1132          * @param[in]   obj The object to compare with the current instance
1133          * @remarks             This method returns @c true only if the specified object is also an instance of the %MultiHashMapT class,
1134          *                              both the maps have the same number of elements, and both the maps contain the same elements.
1135          */
1136         virtual bool Equals(const Object& obj) const
1137         {
1138                 result r = E_SUCCESS;
1139                 bool out = true;
1140
1141                 const MultiHashMapT< KeyType, ValueType >* other = dynamic_cast< const MultiHashMapT< KeyType, ValueType >* >(&obj);
1142                 if (null == other) // obj is not MultiHashMapT<KeyType, ValueType>
1143                 {
1144                         out = false;
1145                 }
1146                 else if (other == this)
1147                 {
1148                         out = true;
1149                 }
1150                 else if (__count != other->__count)
1151                 {
1152                         out = false;
1153                 }
1154                 else
1155                 {
1156                         for (int i = 0; i < __capacity; i++)
1157                         {
1158                                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1159                                 {
1160                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1161                                         {
1162                                                 r = other->Contains(pEntry->key, pNode->value, out);
1163                                         }
1164                                         if (!out)
1165                                         {
1166                                                 break;
1167                                         }
1168                                 }
1169                                 if (!out)
1170                                 {
1171                                         break;
1172                                 }
1173                         }
1174                 }
1175
1176                 return out;
1177         }
1178
1179         /**
1180          * Gets the hash value of the current instance.
1181          *
1182          * @since 2.0
1183          *
1184          * @return      The hash value of the current instance
1185          * @remarks     The two Tizen::Base::Object::Equals() instances must return the same hash value. @n
1186          *                      For better performance, the used hash function must generate a random distribution for all the inputs.
1187          */
1188         virtual int GetHashCode(void) const
1189         {
1190                 int hash = 0;
1191
1192                 for (int i = 0; i < __capacity; i++)
1193                 {
1194                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1195                         {
1196                                 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1197                                 {
1198                                         hash += reinterpret_cast< int >(&pNode->value);
1199                                 }
1200                                 hash += reinterpret_cast< int >(&pEntry->key);
1201                         }
1202                 }
1203                 return hash;
1204         }
1205 private:
1206         /**
1207          * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
1208          *
1209          * @param[in]   map An instance of %MultiHashMapT to initialize the current instance
1210          */
1211         MultiHashMapT(const MultiHashMapT< KeyType, ValueType >& map);
1212
1213         /**
1214          * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
1215          *
1216          * @param[in]   map An instance of %MultiHashMapT
1217          */
1218         MultiHashMapT< KeyType, ValueType >& operator =(const MultiHashMapT< KeyType, ValueType >& map);
1219
1220         /**
1221          * Copies all the pairs from the specified map to this map.
1222          *
1223          * @return              An error code
1224          * @param[in]   map                             The map to copy
1225          * @exception   E_SUCCESS                       The method is successful.
1226          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation. @n
1227          *                                                                      The @c map is modified during the operation of this method.
1228          */
1229         result AddAll(const IMultiMapT< KeyType, ValueType >& map)
1230         {
1231                 result r = E_SUCCESS;
1232
1233                 IMultiMapT< KeyType, ValueType >* pMap = const_cast< IMultiMapT< KeyType, ValueType >* >(&map);
1234                 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
1235
1236                 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
1237
1238                 while (true)
1239                 {
1240                         KeyType key;
1241                         ValueType value;
1242
1243                         r = pMapEnum->MoveNext();
1244                         // enumerator is reached to the end of collection
1245                         if (E_OUT_OF_RANGE == r)
1246                         {
1247                                 r = E_SUCCESS;
1248                                 break;
1249                         }
1250                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1251
1252                         r = pMapEnum->GetKey(key);
1253                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1254
1255                         r = pMapEnum->GetValue(value);
1256                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1257
1258                         r = Add(key, value);
1259                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1260                 }
1261
1262                 if (null != pMapEnum)
1263                 {
1264                         delete pMapEnum;
1265                 }
1266                 return r;
1267
1268 CATCH:
1269                 if (null != pMapEnum)
1270                 {
1271                         delete pMapEnum;
1272                 }
1273                 return r;
1274         }
1275
1276         /**
1277          * Gets a hash value for the specified object.
1278          *
1279          * @return              The hash value for the specified object
1280          * @param[in]   obj     The object to get hash value
1281          */
1282         int Hash(const KeyType& obj) const
1283         {
1284                 int h = __pProvider->GetHashCode(obj);
1285
1286                 h ^= (h >> 20) ^ (h >> 12);
1287
1288                 return h ^ (h >> 7) ^ (h >> 4);
1289         }
1290
1291         /**
1292          * Resizes the contents of this map into a new array with a
1293          * larger capacity. @n
1294          * This method is called automatically when the
1295          * number of keys in this map reaches its threshold.
1296          *
1297          * @return              An error code
1298          * @param[in]   newCapacity     The new capacity @n
1299          *                                                      It must be a power of 2 and must be greater than current capacity.
1300          * @exception   E_SUCCESS                       The method is successful.
1301          * @exception   E_OUT_OF_MEMORY         The memory is insufficient.
1302          */
1303         result Resize(int newCapacity)
1304         {
1305                 result r = E_SUCCESS;
1306                 __MultiHashMapEntryT< KeyType, ValueType >** newTable = new __MultiHashMapEntryT< KeyType, ValueType >*[newCapacity];
1307                 TryCatch(newTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
1308                 for (int i = 0; i < newCapacity; i++)
1309                 {
1310                         newTable[i] = null;
1311                 }
1312
1313                 for (int i = 0; i < __capacity; i++)
1314                 {
1315                         __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1316                         while (null != pEntry)
1317                         {
1318                                 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1319                                 int i = pEntry->hash & (newCapacity - 1);
1320                                 pEntry->pNext = newTable[i];
1321                                 newTable[i] = pEntry;
1322                                 pEntry = pNext;
1323                         }
1324                 }
1325
1326                 delete[] __pTable;
1327                 __pTable = newTable;
1328                 __capacity = newCapacity;
1329                 __threshold = static_cast< int >(__capacity * __loadFactor);
1330
1331                 return r;
1332
1333 CATCH:
1334                 return r;
1335         }
1336
1337         /**
1338          *  Clears all key-value pairs in this map.
1339          *
1340          */
1341         void Reset(void)
1342         {
1343                 for (int i = 0; i < __capacity; i++)
1344                 {
1345                         __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1346                         while (null != pEntry)
1347                         {
1348                                 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1349                                 __ValueNodeT< ValueType >* pNode = pEntry->pList;
1350                                 while (null != pNode)
1351                                 {
1352                                         __ValueNodeT< ValueType >* pTemp = pNode;
1353                                         pNode = pNode->pNext;
1354                                         delete pTemp;
1355                                 }
1356                                 delete pEntry;
1357                                 pEntry = pNext;
1358                         }
1359                         __pTable[i] = null;
1360                 }
1361         }
1362
1363         __MultiHashMapEntryT< KeyType, ValueType >** __pTable;
1364         int __count;
1365         int __capacity;
1366         float __loadFactor;
1367         int __threshold;
1368         IHashCodeProviderT< KeyType >* __pProvider;
1369         IComparerT< KeyType >* __pComparer;
1370         bool __defaultConstruct;
1371         int __modCount;
1372
1373         static const int DEFAULT_CAPACITY = 16;
1374         static const float DEFAULT_LOAD_FACTOR;
1375
1376         friend class __MultiHashMapEnumeratorT< KeyType, ValueType >;
1377
1378 }; // MultiHashMapT
1379
1380 //
1381 // @class       __ValueNodeT
1382 // @brief       This class is a node for MultiHashMapT.
1383 // @since 2.0
1384 //
1385 template< class ValueType >
1386 class __ValueNodeT
1387         : public Object
1388 {
1389 public:
1390         /**
1391          * This is the constructor for this class.
1392          *
1393          * @since 2.0
1394          *
1395          * @param[in]   v       The object to include in this node
1396          */
1397         __ValueNodeT(const ValueType& v)
1398                 : pNext(null)
1399                 , value(v)
1400         {
1401         }
1402
1403         /**
1404          * This is the destructor for this class.
1405          *
1406          * @since 2.0
1407          */
1408         virtual ~__ValueNodeT(void)
1409         {
1410         }
1411
1412         /**
1413          * Internal variable.
1414          *
1415          * @since 2.0
1416          */
1417         __ValueNodeT< ValueType >* pNext;
1418
1419         /**
1420          * Internal variable.
1421          *
1422          * @since 2.0
1423          */
1424         ValueType value;
1425
1426 }; // __ValueNodeT
1427
1428 //
1429 // @class       __MultiHashMapEntryT
1430 // @brief       This class is an entry for MultiHashMapT class.
1431 // @since 2.0
1432 //
1433 template< class KeyType, class ValueType >
1434 class __MultiHashMapEntryT
1435         : public Object
1436 {
1437 public:
1438         /**
1439          * This is the constructor for this class.
1440          *
1441          * @since 2.0
1442          *
1443          * @param[in]   keyType         The key to include in this entry
1444          * @param[in]   list            The list of values whose key is specified @n
1445          *                                                      It cannot be @c null.
1446          * @param[in]   next            A pointer to the next entry
1447          * @param[in]   h                       The hash value of the key
1448          */
1449         __MultiHashMapEntryT(const KeyType& keyType, __ValueNodeT< ValueType >* list, __MultiHashMapEntryT< KeyType, ValueType >* next, int h)
1450                 : key(keyType)
1451                 , pList(list)
1452                 , pNext(next)
1453                 , hash(h)
1454                 , modCount(0)
1455         {
1456         }
1457
1458         /**
1459          * This is the destructor for this class.
1460          *
1461          * @since 2.0
1462          */
1463         virtual ~__MultiHashMapEntryT(void)
1464         {
1465         }
1466
1467         /**
1468          * Internal variable.
1469          *
1470          * @since 2.0
1471          */
1472         KeyType key;
1473
1474         /**
1475          * Internal variable.
1476          *
1477          * @since 2.0
1478          */
1479         __ValueNodeT< ValueType >* pList;
1480
1481         /**
1482          * Internal variable.
1483          *
1484          * @since 2.0
1485          */
1486         __MultiHashMapEntryT< KeyType, ValueType >* pNext;
1487
1488         /**
1489          * Internal variable.
1490          *
1491          * @since 2.0
1492          */
1493         int hash;
1494
1495         /**
1496          * Internal variable.
1497          *
1498          * @since 2.0
1499          */
1500         int modCount;
1501
1502         friend class __EntryValueEnumeratorT< KeyType, ValueType >;
1503
1504 }; // __MultiHashMapEntryT
1505
1506 //
1507 // @class       __MultiHashMapEnumeratorT
1508 // @brief       This class is an implementation of IMapEnumeratorT for %MultiHashMapT.
1509 // @since 2.0
1510 //
1511 template< class KeyType, class ValueType >
1512 class __MultiHashMapEnumeratorT
1513         : public IMapEnumeratorT< KeyType, ValueType >
1514         , public Object
1515 {
1516 public:
1517         /**
1518          * This is the constructor for this class.
1519          *
1520          * @since 2.0
1521          *
1522          * @param[in]   map                     The map to enumerate
1523          * @param[in]   modCount        The modification count to detect the change in the map
1524          */
1525         __MultiHashMapEnumeratorT(const MultiHashMapT< KeyType, ValueType >& map, int modCount)
1526                 : __map(map)
1527                 , __modCount(modCount)
1528                 , __pEntry(null)
1529                 , __pNode(null)
1530                 , __index(-1)
1531         {
1532         }
1533
1534         /**
1535          * This is the destructor for this class.
1536          *
1537          * @since 2.0
1538          */
1539         virtual ~__MultiHashMapEnumeratorT(void)
1540         {
1541         }
1542
1543         /**
1544          * Gets the current object in the map.
1545          *
1546          * @since 2.0
1547          *
1548          * @return              An error code
1549          * @param[out]  obj                                             The current object
1550          * @exception   E_INVALID_OPERATION             Either of the following conditions has occurred:
1551          *                                                                              - The current state of the instance prohibits the execution of the specified operation. @n
1552          *                                                                              - This enumerator is currently positioned before the first element or
1553          *                                                                              past the last element.
1554          *                                                                              - The map is modified after this enumerator is created.
1555          * @exception   E_SUCCESS                               The method is successful.
1556          */
1557         result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1558         {
1559                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1560                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1561                 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1562                         "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1563
1564                 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pNode->value);
1565                 return E_SUCCESS;
1566         }
1567
1568         /**
1569          * Moves this enumerator to the next element of the map. @n
1570          * After the enumerator is first created or reset using the Reset() method,
1571          * the first call to this method positions the enumerator to the first element in the collection.
1572          *
1573          * @since 2.0
1574          *
1575          * @return              An error code
1576          * @exception   E_SUCCESS                       The method is successful.
1577          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
1578          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
1579          *                                                                      - The map is modified after this enumerator is created.
1580          * @exception   E_OUT_OF_RANGE          The enumerator has passed the end of the map.
1581          * @see                 Reset()
1582          */
1583         result MoveNext(void)
1584         {
1585                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1586                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1587
1588                 result r = E_SUCCESS;
1589                 if ((null != __pNode) && (__pNode->pNext != null))
1590                 {
1591                         __pNode = __pNode->pNext;
1592                 }
1593                 else if ((null != __pEntry) && (__pEntry->pNext != null))
1594                 {
1595                         __pEntry = __pEntry->pNext;
1596                         __pNode = __pEntry->pList;
1597                 }
1598                 else
1599                 {
1600                         while (true)
1601                         {
1602                                 if (++__index >= static_cast< int >(__map.__capacity))
1603                                 {
1604                                         // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1605                                         r = E_OUT_OF_RANGE;
1606                                         break;
1607                                 }
1608                                 __pEntry = __map.__pTable[__index];
1609                                 if (null != __pEntry)
1610                                 {
1611                                         __pNode = __pEntry->pList;
1612                                         break;
1613                                 }
1614                         }
1615                 }
1616
1617                 return r;
1618         }
1619
1620         /**
1621          * Positions this enumerator before the first element in the map.
1622          *
1623          * @since 2.0
1624          *
1625          * @return              An error code
1626          * @exception   E_SUCCESS                       The method is successful.
1627          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
1628          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
1629          *                                                                      - The map is modified after this enumerator is created.
1630          */
1631         result Reset(void)
1632         {
1633                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1634                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1635
1636                 __index = -1;
1637                 __pEntry = null;
1638                 __pNode = null;
1639                 return E_SUCCESS;
1640         }
1641
1642         /**
1643          * Gets the current key in the map.
1644          *
1645          * @since 2.0
1646          *
1647          * @return              An error code
1648          * @param[out]  key                                             The current key
1649          * @exception   E_INVALID_OPERATION             Either of the following conditions has occurred:
1650          *                                                                              - The current state of the instance prohibits the execution of the specified operation. @n
1651          *                                                                              - This enumerator is currently positioned before the first element or
1652          *                                                                                past the last element. @n
1653          *                                                                              - The map is modified after this enumerator is created.
1654          * @exception   E_SUCCESS                               The method is successful.
1655          */
1656         result GetKey(KeyType& key) const
1657         {
1658                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1659                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1660                 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1661                         "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1662
1663                 key = __pEntry->key;
1664                 return E_SUCCESS;
1665         }
1666
1667         /**
1668          * Gets the current value in the map.
1669          *
1670          * @since 2.0
1671          *
1672          * @return              An error code
1673          * @param[out]  value                                   The current value
1674          * @exception   E_INVALID_OPERATION             Either of the following conditions has occurred:
1675          *                                                                              - The current state of the instance prohibits the execution of the specified operation. @n
1676          *                                                                              - This enumerator is currently positioned before the first element or
1677          *                                                                                past the last element. @n
1678          *                                                                              - The map is modified after the enumerator is created.
1679          * @exception   E_SUCCESS                               The method is successful.
1680          */
1681         result GetValue(ValueType& value) const
1682         {
1683                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1684                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1685                 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1686                         "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1687
1688                 value = __pNode->value;
1689                 return E_SUCCESS;
1690         }
1691
1692 private:
1693         const MultiHashMapT< KeyType, ValueType >& __map;
1694         int __modCount;
1695         __MultiHashMapEntryT< KeyType, ValueType >* __pEntry;
1696         __ValueNodeT< ValueType >* __pNode;
1697         int __index;
1698
1699 }; // __MultiHashMapEnumeratorT
1700
1701 //
1702 // @class       __EntryValueEnumeratorT
1703 // @brief       This class is an implementation of IEnumeratorT to enumerate values whose key is the same.
1704 // @since 2.0
1705 //
1706 template< class KeyType, class ValueType >
1707 class __EntryValueEnumeratorT
1708         : public IEnumeratorT< ValueType >
1709         , public Object
1710 {
1711 public:
1712         /**
1713          * Initializes an instance of __EntryValueEnumeratorT with the specified parameters.
1714          *
1715          * @since 2.0
1716          *
1717          * @param[in]   entry           The entry to enumerate
1718          * @param[in]   modCount        The modification count to detect the change in the entry
1719          */
1720         __EntryValueEnumeratorT(const __MultiHashMapEntryT< KeyType, ValueType >& entry, int modCount)
1721                 : __entry(entry)
1722                 , __modCount(modCount)
1723                 , __pNode(null)
1724         {
1725         }
1726
1727
1728         /**
1729          * This is the destructor for this class.
1730          *
1731          * @since 2.0
1732          */
1733         virtual ~__EntryValueEnumeratorT(void)
1734         {
1735         }
1736
1737         /**
1738          * Gets the current value in the entry.
1739          *
1740          * @since 2.0
1741          *
1742          * @return              An error code
1743          * @param[out]  obj                                     The current value
1744          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
1745          *                                                                      - The current state of the instance prohibits the execution of the specified operation. @n
1746          *                                                                      - This enumerator is currently positioned before the first element or
1747          *                                                                      past the last element.
1748          *                                                                      - The entry is modified after this enumerator is created.
1749          * @exception   E_SUCCESS                       The method is successful.
1750          */
1751         result GetCurrent(ValueType& obj) const
1752         {
1753                 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1754                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1755                 TryReturn(__pNode != null, E_INVALID_OPERATION, "[%s] Invalid position(pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1756
1757                 obj = __pNode->value;
1758                 return E_SUCCESS;
1759         }
1760
1761         /**
1762          * Moves this enumerator to the next element of the entry. @n
1763          * After the enumerator is first created or reset using the Reset() method,
1764          * the first call to this method positions the enumerator to the first element in the collection.
1765          *
1766          * @since 2.0
1767          *
1768          * @return              An error code
1769          * @exception   E_SUCCESS                       The method is successful.
1770          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
1771          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
1772          *                                                                      - The entry is modified after this enumerator is created.
1773          * @exception   E_OUT_OF_RANGE          The enumerator has passed the end of the entry.
1774          * @see                 Reset()
1775          */
1776         result MoveNext(void)
1777         {
1778                 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1779                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1780
1781                 result r = E_SUCCESS;
1782                 if (null == __pNode)
1783                 {
1784                         __pNode = __entry.pList;
1785                         AppAssert(null != __pNode);
1786                 }
1787                 else if ((null != __pNode) && (__pNode->pNext != null))
1788                 {
1789                         __pNode = __pNode->pNext;
1790                 }
1791                 else
1792                 {
1793                         // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1794                         r = E_OUT_OF_RANGE;
1795                 }
1796
1797                 return r;
1798         }
1799
1800         /**
1801          * Positions this enumerator before the first element in the entry.
1802          *
1803          * @since 2.0
1804          *
1805          * @return              An error code
1806          * @exception   E_SUCCESS                       The method is successful.
1807          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
1808          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
1809          *                                                                      - The entry is modified after this enumerator is created.
1810          */
1811         result Reset(void)
1812         {
1813                 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1814                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1815
1816                 __pNode = null;
1817                 return E_SUCCESS;
1818         }
1819
1820 private:
1821         const __MultiHashMapEntryT< KeyType, ValueType >& __entry;
1822         int __modCount;
1823         __ValueNodeT< ValueType >* __pNode;
1824
1825 }; // __EntryValueEnumeratorT
1826
1827 //
1828 // @class       __MultiHashMapDefaultProviderT
1829 // @brief       This class is an implementation of IHashCodeProviderT for HashMap.
1830 // @since 2.0
1831 //
1832 template< class KeyType >
1833 class __MultiHashMapDefaultProviderT
1834         : public IHashCodeProviderT< KeyType >
1835         , public Object
1836 {
1837 public:
1838         /**
1839         * This is the default constructor for this class.
1840         *
1841         * @since 2.0
1842         */
1843         __MultiHashMapDefaultProviderT(void) {}
1844
1845         /**
1846         * This is the destructor for this class.
1847         *
1848         * @since 2.0
1849         */
1850         virtual ~__MultiHashMapDefaultProviderT(void) {}
1851
1852         // Operation
1853
1854         /**
1855         * Gets the hash code of the specified instance.
1856         *
1857         * @since 2.0
1858         *
1859         * @return               The hash code
1860         * @see                  Tizen::Base::Object::GetHashCode()
1861         */
1862         virtual int GetHashCode(const KeyType& obj) const
1863         {
1864                 return (int) obj;
1865         }
1866
1867 }; // __MultiHashMapDefaultProviderT
1868
1869 template< class KeyType, class ValueType >
1870 const float MultiHashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1871
1872 }}}   // Tizen::Base::Collection
1873
1874 #endif //_FBASE_COL_MULTI_HASH_MAP_T_H_