inc/FBaseColMultiHashMapT.h

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