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