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 unique keys in this map.
 602          *
 603          * @since 2.0
 604          *
 605          * @return              A list of all unique 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 specific error code can be accessed using the GetLastResult() method.
 610          * @see                 GetValuesN()
 611          */
 612         virtual IListT< KeyType >* GetKeysN(void) const
 613         {
 614                 ClearLastResult();
 615
 616                 result r = E_SUCCESS;
 617                 int keyCount = 0;
 618
 619                 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
 620                 r = pList->Construct(__count);
 621                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 622
 623                 for (int i = 0; i < __capacity; i++)
 624                 {
 625                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 626                         {
 627                                 r = pList->Add(pEntry->key);
 628                                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 629                                 keyCount++;
 630                         }
 631                 }
 632
 633                 return pList;
 634
 635 CATCH:
 636                 delete pList;
 637
 638                 SetLastResult(r);
 639                 return null;
 640         }
 641
 642         /**
 643          * Gets a list of all the values in this map.
 644          *
 645          * @since 2.0
 646          *
 647          * @return              A list of all the values in this map, @n
 648          *                              else @c null if an exception occurs
 649          * @exception   E_SUCCESS               The method is successful.
 650          * @exception   E_OUT_OF_MEMORY The memory is insufficient.
 651          * @remarks     The specific error code can be accessed using the GetLastResult() method.
 652          * @see                 GetKeysN()
 653          */
 654         virtual IListT< ValueType >* GetValuesN(void) const
 655         {
 656                 ClearLastResult();
 657
 658                 result r = E_SUCCESS;
 659
 660                 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
 661                 r = pList->Construct(__count);
 662                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 663
 664                 for (int i = 0; i < __capacity; i++)
 665                 {
 666                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 667                         {
 668                                 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 669                                 {
 670                                         r = pList->Add(pNode->value);
 671                                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 672                                 }
 673                         }
 674                 }
 675
 676                 return pList;
 677
 678 CATCH:
 679                 delete pList;
 680
 681                 SetLastResult(r);
 682                 return null;
 683         }
 684
 685         /**
 686          * Removes all the values for the specified key.
 687          *
 688          * @since 2.0
 689          *
 690          * @return              An error code
 691          * @param[in]   key The key to remove
 692          * @exception   E_SUCCESS                       The method is successful.
 693          * @exception   E_INVALID_ARG           The specified input parameter is invalid, or
 694          *                                                                      the comparer has failed to compare the keys.
 695          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 696          * @see                 Add()
 697          */
 698         virtual result Remove(const KeyType& key)
 699         {
 700                 result r = E_OBJ_NOT_FOUND;
 701                 int hash = Hash(key);
 702                 int i = hash & (__capacity - 1);
 703
 704                 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
 705                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 706                 {
 707                         if (hash == pEntry->hash)
 708                         {
 709                                 int cmpResult;
 710                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 711                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 712
 713                                 r = E_OBJ_NOT_FOUND;
 714
 715                                 if (cmpResult == 0)
 716                                 {
 717                                         __modCount++;
 718                                         if (pPrev == pEntry)
 719                                         {
 720                                                 __pTable[i] = pEntry->pNext;
 721                                         }
 722                                         else
 723                                         {
 724                                                 pPrev->pNext = pEntry->pNext;
 725                                         }
 726
 727                                         __ValueNodeT< ValueType >* pNode = pEntry->pList;
 728                                         while (null != pNode)
 729                                         {
 730                                                 __ValueNodeT< ValueType >* pTemp = pNode;
 731                                                 pNode = pNode->pNext;
 732                                                 delete pTemp;
 733                                                 __count--;
 734                                         }
 735                                         delete pEntry;
 736                                         r = E_SUCCESS;
 737                                         break;
 738                                 }
 739                         }
 740                         pPrev = pEntry;
 741                 }
 742
 743                 return r;
 744         }
 745
 746         /**
 747          * Removes the specified value associated with the specified key. @n
 748          * The key is also removed if there is no value associated with it.
 749          *
 750          * @since 2.0
 751          *
 752          * @return              An error code
 753          * @param[in]   key The key whose mapping is to remove from the map
 754          * @param[in]   value   The value to remove
 755          * @exception   E_SUCCESS                       The method is successful.
 756          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 757          *                                                                      the comparer has failed to compare the keys.
 758          * @exception   E_OBJ_NOT_FOUND         The specified @c key and @c value pair is not found in the map.
 759          * @see                 Add()
 760          */
 761         virtual result Remove(const KeyType& key, const ValueType& value)
 762         {
 763                 result r = E_OBJ_NOT_FOUND;
 764                 int hash = Hash(key);
 765                 int i = hash & (__capacity - 1);
 766
 767                 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
 768                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 769                 {
 770                         if (hash == pEntry->hash)
 771                         {
 772                                 int cmpResult;
 773                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 774                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 775
 776                                 r = E_OBJ_NOT_FOUND;
 777                                 if (cmpResult == 0)
 778                                 {
 779                                         __ValueNodeT< ValueType >* pPrevNode = pEntry->pList;
 780                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 781                                         {
 782                                                 if (value == pNode->value)
 783                                                 {
 784                                                         __modCount++;
 785                                                         __count--;
 786                                                         if (pPrevNode == pNode)
 787                                                         {
 788                                                                 pEntry->pList = pNode->pNext;
 789                                                         }
 790                                                         else
 791                                                         {
 792                                                                 pPrevNode->pNext = pNode->pNext;
 793                                                         }
 794
 795                                                         delete pNode;
 796
 797                                                         pEntry->modCount++;
 798
 799                                                         if (null == pEntry->pList)
 800                                                         {
 801                                                                 if (pPrev == pEntry)
 802                                                                 {
 803                                                                         __pTable[i] = pEntry->pNext;
 804                                                                 }
 805                                                                 else
 806                                                                 {
 807                                                                         pPrev->pNext = pEntry->pNext;
 808                                                                 }
 809                                                                 delete pEntry;
 810                                                         }
 811                                                         r = E_SUCCESS;
 812                                                         break;
 813                                                 }
 814                                                 pPrevNode = pNode;
 815                                         }
 816                                         if (!IsFailed(r))
 817                                         {
 818                                                 break;
 819                                         }
 820                                 }
 821                         }
 822                         pPrev = pEntry;
 823                 }
 824
 825                 return r;
 826         }
 827
 828         /**
 829          * Removes all key-value pairs in this map.
 830          *
 831          * @since 2.0
 832          */
 833         virtual void RemoveAll(void)
 834         {
 835                 if (__count > 0)
 836                 {
 837                         __modCount++;
 838                         Reset();
 839                         __count = 0;
 840                 }
 841         }
 842
 843         /**
 844          * Replaces the value associated with the key with the specified @c newValue.
 845          *
 846          * @since 2.0
 847          *
 848          * @return              An error code
 849          * @param[in]   key                     A key
 850          * @param[in]   value           A value to replace
 851          * @param[in]   newValue        A new value to replace the existing value
 852          * @exception   E_SUCCESS               The method is successful.
 853          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 854          *                                                                      the comparer has failed to compare the keys.
 855          * @exception   E_OBJ_NOT_FOUND   The specified @c key and @c value pair is not found in the map.
 856          * @remarks             To add a new key-value pair, use the Add() method.
 857          * @see                 Add()
 858          * @see                 GetValuesN()
 859          */
 860         virtual result SetValue(const KeyType& key, const ValueType& value, const ValueType& newValue)
 861         {
 862                 result r = E_SUCCESS;
 863                 int hash = Hash(key);
 864                 int i = hash & (__capacity - 1);
 865                 __ValueNodeT< ValueType >* pNode = null;
 866                 bool pairExist = false;
 867                 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
 868                 while (null != pEntry)
 869                 {
 870                         if (hash == pEntry->hash)
 871                         {
 872                                 int cmpResult;
 873                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 874                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 875
 876                                 if (cmpResult == 0)
 877                                 {
 878                                         pNode = pEntry->pList;
 879                                         while (true)
 880                                         {
 881                                                 if (pNode->value == value)
 882                                                 {
 883                                                         __modCount++;
 884                                                         pNode->value = newValue;
 885                                                         pairExist = true;
 886                                                         break;
 887                                                 }
 888                                                 if (pNode->pNext != null)
 889                                                 {
 890                                                         pNode = pNode->pNext;
 891                                                 }
 892                                                 else
 893                                                 {
 894                                                         pEntry->modCount++;
 895                                                         break;
 896                                                 }
 897                                         }
 898                                         break;
 899                                 }
 900                         }
 901                         pEntry = pEntry->pNext;
 902                 }
 903
 904                 if (!pairExist)
 905                 {
 906                         r = E_OBJ_NOT_FOUND;
 907                 }
 908
 909                 return r;
 910         }
 911
 912         /**
 913          * Gets the number of values currently stored in this map.
 914          *
 915          * @since 2.0
 916          *
 917          * @return              The number of values currently stored in this map
 918          */
 919         virtual int GetCount(void) const
 920         {
 921                 return __count;
 922         }
 923
 924         /**
 925          * Gets the number of values whose keys match the specified key.
 926          *
 927          * @since 2.0
 928          *
 929          * @return              An error code
 930          * @param[in]   key     A key to locate
 931          * @param[out]  count   The number of values whose key is @c key
 932          * @exception   E_SUCCESS                       The method is successful.
 933          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 934          *                                                                      the comparer has failed to compare the keys.
 935          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 936          */
 937         virtual result GetCount(const KeyType& key, int& count) const
 938         {
 939                 result r = E_OBJ_NOT_FOUND;
 940                 int hash = Hash(key);
 941                 int i = hash & (__capacity - 1);
 942
 943                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 944                 {
 945                         if (hash == pEntry->hash)
 946                         {
 947                                 int cmpResult;
 948                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
 949                                 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 950
 951                                 if (0 == cmpResult)
 952                                 {
 953                                         int __count = 0;
 954                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 955                                         {
 956                                                 __count++;
 957                                         }
 958                                         count = __count;
 959                                         r = E_SUCCESS;
 960                                         break;
 961                                 }
 962
 963                                 r = E_OBJ_NOT_FOUND;
 964                         }
 965                 }
 966
 967                 return r;
 968         }
 969
 970         /**
 971          * Checks whether the map contains the specified key and value.
 972          *
 973          * @since 2.0
 974          *
 975          * @return              An error code
 976          * @param[in]   key     The key to locate
 977          * @param[in]   value   The value to locate
 978          * @param[out]  out             Set to @c true if the map contains the specified key and value pair, @n
 979          *                                              else @c false
 980          * @exception   E_SUCCESS                       The method is successful.
 981          * @exception   E_INVALID_ARG           The current state of the instance prohibits the execution of the specified operation, or
 982          *                                                                      the comparer has failed to compare the keys.
 983          * @see                 ContainsKey()
 984          * @see                 ContainsValue()
 985          */
 986         virtual result Contains(const KeyType& key, const ValueType& value, bool& out) const
 987         {
 988                 out = false;
 989
 990                 result r = E_SUCCESS;
 991                 int hash = Hash(key);
 992                 int i = hash & (__capacity - 1);
 993
 994                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 995                 {
 996                         if (hash == pEntry->hash)
 997                         {
 998                                 int cmpResult;
 999                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1000                                 if (IsFailed(r))
1001                                 {
1002                                         AppLogException("[%s] Propagating.", GetErrorMessage(r));
1003                                         out = false;
1004                                         return E_INVALID_ARG;
1005                                 }
1006
1007                                 if (cmpResult == 0)
1008                                 {
1009                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1010                                         {
1011                                                 if (value == pNode->value)
1012                                                 {
1013                                                         r = E_SUCCESS;
1014                                                         out = true;
1015                                                         break;
1016                                                 }
1017                                         }
1018                                         break;
1019                                 }
1020                         }
1021                 }
1022
1023                 return E_SUCCESS;
1024         }
1025
1026         /**
1027          * Checks whether the map contains the specified key.
1028          *
1029          * @since 2.0
1030          *
1031          * @return              An error code
1032          * @param[in]   key     The key to locate
1033          * @param[out]  out             Set to @c true if the map contains the specified key, @n
1034          *                                              else @c false
1035          * @exception   E_SUCCESS                       The method is successful.
1036          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
1037          *                                                                      the comparer has failed to compare the keys.
1038          * @see                 ContainsValue()
1039          * @see                 Contains()
1040          */
1041         virtual result ContainsKey(const KeyType& key, bool& out) const
1042         {
1043                 out = false;
1044                 result r = E_SUCCESS;
1045                 int hash = Hash(key);
1046                 int i = hash & (__capacity - 1);
1047
1048                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1049                 {
1050                         if (hash == pEntry->hash)
1051                         {
1052                                 int cmpResult;
1053                                 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1054                                 if (IsFailed(r))
1055                                 {
1056                                         AppLogException("[%s] Propagating.", GetErrorMessage(r));
1057                                         out = false;
1058                                         return E_INVALID_ARG;
1059                                 }
1060                                 if (cmpResult == 0)
1061                                 {
1062                                         out = true;
1063                                         break;
1064                                 }
1065                         }
1066                 }
1067
1068                 return E_SUCCESS;
1069         }
1070
1071         /**
1072          * Checks whether the map contains the specified value.
1073          *
1074          * @since 2.0
1075          *
1076          * @return              @c true if the map contains the specified value, @n
1077          *                              else @c false
1078          * @param[in]   value   The value to locate
1079          *
1080          * @see                 ContainsKey()
1081          * @see                 Contains()
1082          */
1083         virtual bool ContainsValue(const ValueType& value) const
1084         {
1085                 bool out = false;
1086                 for (int i = 0; i < __capacity; i++)
1087                 {
1088                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1089                         {
1090                                 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1091                                 {
1092                                         if (value == pNode->value)
1093                                         {
1094                                                 out = true;
1095                                                 break;
1096                                         }
1097                                 }
1098
1099                                 if (out)
1100                                         break;
1101                         }
1102
1103                         if (out)
1104                                 break;
1105                 }
1106
1107                 return out;
1108         }
1109
1110         /**
1111          * Compares the specified instance to the current instance for equality.
1112          *
1113          * @since 2.0
1114          *
1115          * @return              @c true if the two instances are equal, @n
1116          *                              else @c false
1117          * @param[in]   obj The object to compare with the current instance
1118          * @remarks             This method returns @c true only if the specified object is also an instance of the %MultiHashMapT class,
1119          *                              both maps have the same number of elements, and both maps contain the same elements.
1120          */
1121         virtual bool Equals(const Object& obj) const
1122         {
1123                 result r = E_SUCCESS;
1124                 bool out = true;
1125
1126                 const MultiHashMapT< KeyType, ValueType >* other = dynamic_cast< const MultiHashMapT< KeyType, ValueType >* >(&obj);
1127                 if (null == other) // obj is not MultiHashMapT<KeyType, ValueType>
1128                 {
1129                         out = false;
1130                 }
1131                 else if (other == this)
1132                 {
1133                         out = true;
1134                 }
1135                 else if (__count != other->__count)
1136                 {
1137                         out = false;
1138                 }
1139                 else
1140                 {
1141                         for (int i = 0; i < __capacity; i++)
1142                         {
1143                                 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1144                                 {
1145                                         for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1146                                         {
1147                                                 r = other->Contains(pEntry->key, pNode->value, out);
1148                                         }
1149                                         if (!out)
1150                                         {
1151                                                 break;
1152                                         }
1153                                 }
1154                                 if (!out)
1155                                 {
1156                                         break;
1157                                 }
1158                         }
1159                 }
1160
1161                 return out;
1162         }
1163
1164         /**
1165          * Gets the hash value of the current instance.
1166          *
1167          * @since 2.0
1168          *
1169          * @return      The hash value of the current instance
1170          * @remarks     The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
1171          *                      the used hash function must generate a random distribution for all inputs.
1172          */
1173         virtual int GetHashCode(void) const
1174         {
1175                 int hash = 0;
1176
1177                 for (int i = 0; i < __capacity; i++)
1178                 {
1179                         for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1180                         {
1181                                 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1182                                 {
1183                                         hash += reinterpret_cast< int >(&pNode->value);
1184                                 }
1185                                 hash += reinterpret_cast< int >(&pEntry->key);
1186                         }
1187                 }
1188                 return hash;
1189         }
1190 private:
1191         /**
1192          * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
1193          *
1194          * @param[in]   map An instance of %MultiHashMapT to initialize the current instance
1195          */
1196         MultiHashMapT(const MultiHashMapT< KeyType, ValueType >& map);
1197
1198         /**
1199          * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
1200          *
1201          * @param[in]   map An instance of %MultiHashMapT
1202          */
1203         MultiHashMapT< KeyType, ValueType >& operator =(const MultiHashMapT< KeyType, ValueType >& map);
1204
1205         /**
1206          * Copies all the pairs from the specified map to this map.
1207          *
1208          * @return              An error code
1209          * @param[in]   map The map to copy
1210          * @exception   E_SUCCESS                       The method is successful.
1211          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation. @n
1212          *                                                                      The @c map is modified during the operation of this method.
1213          */
1214         result AddAll(const IMultiMapT< KeyType, ValueType >& map)
1215         {
1216                 result r = E_SUCCESS;
1217
1218                 IMultiMapT< KeyType, ValueType >* pMap = const_cast< IMultiMapT< KeyType, ValueType >* >(&map);
1219                 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
1220
1221                 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
1222
1223                 while (true)
1224                 {
1225                         KeyType key;
1226                         ValueType value;
1227
1228                         r = pMapEnum->MoveNext();
1229                         // enumerator is reached to the end of collection
1230                         if (E_OUT_OF_RANGE == r)
1231                         {
1232                                 r = E_SUCCESS;
1233                                 break;
1234                         }
1235                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1236
1237                         r = pMapEnum->GetKey(key);
1238                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1239
1240                         r = pMapEnum->GetValue(value);
1241                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1242
1243                         r = Add(key, value);
1244                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1245                 }
1246
1247                 if (null != pMapEnum)
1248                 {
1249                         delete pMapEnum;
1250                 }
1251                 return r;
1252
1253 CATCH:
1254                 if (null != pMapEnum)
1255                 {
1256                         delete pMapEnum;
1257                 }
1258                 return r;
1259         }
1260
1261         /**
1262          * Gets a hash value for the specified object.
1263          *
1264          * @return              The hash value for the specified object
1265          * @param[in]   obj     The object to get hash value
1266          */
1267         int Hash(const KeyType& obj) const
1268         {
1269                 int h = __pProvider->GetHashCode(obj);
1270
1271                 h ^= (h >> 20) ^ (h >> 12);
1272
1273                 return h ^ (h >> 7) ^ (h >> 4);
1274         }
1275
1276         /**
1277          * Resizes the contents of this map into a new array with a
1278          * larger capacity. @n
1279          * This method is called automatically when the
1280          * number of keys in this map reaches its threshold.
1281          *
1282          * @return              An error code
1283          * @param[in]   newCapacity     The new capacity @n
1284          *                                                      It must be a power of 2 and must be greater than current capacity.
1285          * @exception   E_SUCCESS                       The method is successful.
1286          * @exception   E_OUT_OF_MEMORY         The memory is insufficient.
1287          */
1288         result Resize(int newCapacity)
1289         {
1290                 result r = E_SUCCESS;
1291                 __MultiHashMapEntryT< KeyType, ValueType >** newTable = new __MultiHashMapEntryT< KeyType, ValueType >*[newCapacity];
1292                 TryCatch(newTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
1293                 for (int i = 0; i < newCapacity; i++)
1294                 {
1295                         newTable[i] = null;
1296                 }
1297
1298                 for (int i = 0; i < __capacity; i++)
1299                 {
1300                         __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1301                         while (null != pEntry)
1302                         {
1303                                 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1304                                 int i = pEntry->hash & (newCapacity - 1);
1305                                 pEntry->pNext = newTable[i];
1306                                 newTable[i] = pEntry;
1307                                 pEntry = pNext;
1308                         }
1309                 }
1310
1311                 delete[] __pTable;
1312                 __pTable = newTable;
1313                 __capacity = newCapacity;
1314                 __threshold = static_cast< int >(__capacity * __loadFactor);
1315
1316                 return r;
1317
1318 CATCH:
1319                 return r;
1320         }
1321
1322         /**
1323          *  Clears all key-value pairs in this map.
1324          *
1325          */
1326         void Reset(void)
1327         {
1328                 for (int i = 0; i < __capacity; i++)
1329                 {
1330                         __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1331                         while (null != pEntry)
1332                         {
1333                                 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1334                                 __ValueNodeT< ValueType >* pNode = pEntry->pList;
1335                                 while (null != pNode)
1336                                 {
1337                                         __ValueNodeT< ValueType >* pTemp = pNode;
1338                                         pNode = pNode->pNext;
1339                                         delete pTemp;
1340                                 }
1341                                 delete pEntry;
1342                                 pEntry = pNext;
1343                         }
1344                         __pTable[i] = null;
1345                 }
1346         }
1347
1348         __MultiHashMapEntryT< KeyType, ValueType >** __pTable;
1349         int __count;
1350         int __capacity;
1351         float __loadFactor;
1352         int __threshold;
1353         IHashCodeProviderT< KeyType >* __pProvider;
1354         IComparerT< KeyType >* __pComparer;
1355         bool __defaultConstruct;
1356         int __modCount;
1357
1358         static const int DEFAULT_CAPACITY = 16;
1359         static const float DEFAULT_LOAD_FACTOR;
1360
1361         friend class __MultiHashMapEnumeratorT< KeyType, ValueType >;
1362
1363 }; // MultiHashMapT
1364
1365 //
1366 // @class       __ValueNodeT
1367 // @brief       This class is a node for MultiHashMapT.
1368 // @since 2.0
1369 //
1370 template< class ValueType >
1371 class __ValueNodeT
1372         : public Object
1373 {
1374 public:
1375         /**
1376          * This is the constructor for this class.
1377          *
1378          * @since 2.0
1379          *
1380          * @param[in]   v       An object to include in this node
1381          */
1382         __ValueNodeT(const ValueType& v)
1383                 : pNext(null)
1384                 , value(v)
1385         {
1386         }
1387
1388         /**
1389          * This is the destructor for this class.
1390          *
1391          * @since 2.0
1392          */
1393         virtual ~__ValueNodeT(void)
1394         {
1395         }
1396
1397         /**
1398          * Internal variable.
1399          *
1400          * @since 2.0
1401          */
1402         __ValueNodeT< ValueType >* pNext;
1403
1404         /**
1405          * Internal variable.
1406          *
1407          * @since 2.0
1408          */
1409         ValueType value;
1410
1411 }; // __ValueNodeT
1412
1413 //
1414 // @class       __MultiHashMapEntryT
1415 // @brief       This class is an entry for MultiHashMapT class.
1416 // @since 2.0
1417 //
1418 template< class KeyType, class ValueType >
1419 class __MultiHashMapEntryT
1420         : public Object
1421 {
1422 public:
1423         /**
1424          * This is the constructor for this class.
1425          *
1426          * @since 2.0
1427          *
1428          * @param[in]   keyType         A key to include in this entry
1429          * @param[in]   list    A list of values whose key is specified @n
1430          *                                              It cannot be @c null.
1431          * @param[in]   next    A pointer to the next entry
1432          * @param[in]   h               An hash value of the key
1433          */
1434         __MultiHashMapEntryT(const KeyType& keyType, __ValueNodeT< ValueType >* list, __MultiHashMapEntryT< KeyType, ValueType >* next, int h)
1435                 : key(keyType)
1436                 , pList(list)
1437                 , pNext(next)
1438                 , hash(h)
1439                 , modCount(0)
1440         {
1441         }
1442
1443         /**
1444          * This is the destructor for this class.
1445          *
1446          * @since 2.0
1447          */
1448         virtual ~__MultiHashMapEntryT(void)
1449         {
1450         }
1451
1452         /**
1453          * Internal variable.
1454          *
1455          * @since 2.0
1456          */
1457         KeyType key;
1458
1459         /**
1460          * Internal variable.
1461          *
1462          * @since 2.0
1463          */
1464         __ValueNodeT< ValueType >* pList;
1465
1466         /**
1467          * Internal variable.
1468          *
1469          * @since 2.0
1470          */
1471         __MultiHashMapEntryT< KeyType, ValueType >* pNext;
1472
1473         /**
1474          * Internal variable.
1475          *
1476          * @since 2.0
1477          */
1478         int hash;
1479
1480         /**
1481          * Internal variable.
1482          *
1483          * @since 2.0
1484          */
1485         int modCount;
1486
1487         friend class __EntryValueEnumeratorT< KeyType, ValueType >;
1488
1489 }; // __MultiHashMapEntryT
1490
1491 //
1492 // @class       __MultiHashMapEnumeratorT
1493 // @brief       This class is an implementation of IMapEnumeratorT for %MultiHashMapT.
1494 // @since 2.0
1495 //
1496 template< class KeyType, class ValueType >
1497 class __MultiHashMapEnumeratorT
1498         : public IMapEnumeratorT< KeyType, ValueType >
1499         , public Object
1500 {
1501 public:
1502         /**
1503          * This is the constructor for this class.
1504          *
1505          * @since 2.0
1506          *
1507          * @param[in]   map                     A map to enumerate
1508          * @param[in]   modCount        The modification count to detect the change in the map
1509          */
1510         __MultiHashMapEnumeratorT(const MultiHashMapT< KeyType, ValueType >& map, int modCount)
1511                 : __map(map)
1512                 , __modCount(modCount)
1513                 , __pEntry(null)
1514                 , __pNode(null)
1515                 , __index(-1)
1516         {
1517         }
1518
1519         /**
1520          * This is the destructor for this class.
1521          *
1522          * @since 2.0
1523          */
1524         virtual ~__MultiHashMapEnumeratorT(void)
1525         {
1526         }
1527
1528         /**
1529          * Gets the current object in the map.
1530          *
1531          * @since 2.0
1532          *
1533          * @return              An error code
1534          * @param[out]  obj The current object
1535          * @exception   E_INVALID_OPERATION       Either of the following conditions has occurred: @n
1536          *                                                                      - The current state of the instance prohibits the execution of the specified operation. @n
1537          *                                                                      - This enumerator is currently positioned before the first element or
1538          *                                                                      past the last element. @n
1539          *                                   - The map is modified after this enumerator is created.
1540          * @exception   E_SUCCESS                       The method is successful.
1541          */
1542         result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1543         {
1544                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1545                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1546                 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1547                         "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1548
1549                 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pNode->value);
1550                 return E_SUCCESS;
1551         }
1552
1553         /**
1554          * Moves this enumerator to the next element of the map. @n
1555          * After the enumerator is first created or reset using the Reset() method,
1556          * the first call to this method positions the enumerator to the first element in the @c collection.
1557          *
1558          * @since 2.0
1559          *
1560          * @return              An error code
1561          * @exception   E_SUCCESS                       The method is successful.
1562          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
1563          *                                                                      the map is modified after this enumerator is created.
1564          * @exception   E_OUT_OF_RANGE          The enumerator has passed the end of the map.
1565          * @see                 Reset()
1566          */
1567         result MoveNext(void)
1568         {
1569                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1570                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1571
1572                 result r = E_SUCCESS;
1573                 if ((null != __pNode) && (__pNode->pNext != null))
1574                 {
1575                         __pNode = __pNode->pNext;
1576                 }
1577                 else if ((null != __pEntry) && (__pEntry->pNext != null))
1578                 {
1579                         __pEntry = __pEntry->pNext;
1580                         __pNode = __pEntry->pList;
1581                 }
1582                 else
1583                 {
1584                         while (true)
1585                         {
1586                                 if (++__index >= static_cast< int >(__map.__capacity))
1587                                 {
1588                                         // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1589                                         r = E_OUT_OF_RANGE;
1590                                         break;
1591                                 }
1592                                 __pEntry = __map.__pTable[__index];
1593                                 if (null != __pEntry)
1594                                 {
1595                                         __pNode = __pEntry->pList;
1596                                         break;
1597                                 }
1598                         }
1599                 }
1600
1601                 return r;
1602         }
1603
1604         /**
1605          * Positions this enumerator before the first element in the map.
1606          *
1607          * @since 2.0
1608          *
1609          * @return              An error code
1610          * @exception   E_SUCCESS                       The method is successful.
1611          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
1612          *                                                                      the map is modified after this enumerator is created.
1613          */
1614         result Reset(void)
1615         {
1616                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1617                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1618
1619                 __index = -1;
1620                 __pEntry = null;
1621                 __pNode = null;
1622                 return E_SUCCESS;
1623         }
1624
1625         /**
1626          * Gets the current key in the map.
1627          *
1628          * @since 2.0
1629          *
1630          * @return              An error code
1631          * @param[out]  key The current key
1632          * @exception   E_INVALID_OPERATION       Either of the following conditions has occurred: @n
1633          *                                                                      - The current state of the instance prohibits the execution of the specified operation. @n
1634          *                                                                      - This enumerator is currently positioned before the first element or
1635          *                                                                      past the last element. @n
1636          *                                                                      -  The map is modified after this enumerator is created.
1637          * @exception   E_SUCCESS                       The method is successful.
1638          */
1639         result GetKey(KeyType& key) const
1640         {
1641                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1642                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1643                 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1644                         "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1645
1646                 key = __pEntry->key;
1647                 return E_SUCCESS;
1648         }
1649
1650         /**
1651          * Gets the current value in the map.
1652          *
1653          * @since 2.0
1654          *
1655          * @return              An error code
1656          * @param[out]  value The current value
1657          * @exception   E_INVALID_OPERATION       Either of the following conditions has occurred: @n
1658          *                                                                      - The current state of the instance prohibits the execution of the specified operation. @n
1659          *                                                                      - This enumerator is currently positioned before the first element or
1660          *                                                                      past the last element. @n
1661          *                                                                      - The map is modified after the enumerator is created.
1662          * @exception   E_SUCCESS                       The method is successful.
1663          */
1664         result GetValue(ValueType& value) const
1665         {
1666                 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1667                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1668                 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1669                         "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1670
1671                 value = __pNode->value;
1672                 return E_SUCCESS;
1673         }
1674
1675 private:
1676         const MultiHashMapT< KeyType, ValueType >& __map;
1677         int __modCount;
1678         __MultiHashMapEntryT< KeyType, ValueType >* __pEntry;
1679         __ValueNodeT< ValueType >* __pNode;
1680         int __index;
1681
1682 }; // __MultiHashMapEnumeratorT
1683
1684 //
1685 // @class       __EntryValueEnumeratorT
1686 // @brief       This class is an implementation of IEnumeratorT to enumerate values whose key is the same.
1687 // @since 2.0
1688 //
1689 template< class KeyType, class ValueType >
1690 class __EntryValueEnumeratorT
1691         : public IEnumeratorT< ValueType >
1692         , public Object
1693 {
1694 public:
1695         /**
1696          * Initializes an instance of __EntryValueEnumeratorT with the specified parameters.
1697          *
1698          * @since 2.0
1699          *
1700          * @param[in]   entry           An entry to enumerate
1701          * @param[in]   modCount        The modification count to detect the change in the entry
1702          */
1703         __EntryValueEnumeratorT(const __MultiHashMapEntryT< KeyType, ValueType >& entry, int modCount)
1704                 : __entry(entry)
1705                 , __modCount(modCount)
1706                 , __pNode(null)
1707         {
1708         }
1709
1710
1711         /**
1712          * This is the destructor for this class.
1713          *
1714          * @since 2.0
1715          */
1716         virtual ~__EntryValueEnumeratorT(void)
1717         {
1718         }
1719
1720         /**
1721          * Gets the current value in the entry.
1722          *
1723          * @since 2.0
1724          *
1725          * @return              An error code
1726          * @param[out]  obj The current value
1727          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred: @n
1728          *                                                                      - The current state of the instance prohibits the execution of the specified operation. @n
1729          *                                                                      - This enumerator is currently positioned before the first element or
1730          *                                                                      past the last element. @n
1731          *                                                                      - The entry is modified after this enumerator is created.
1732          * @exception   E_SUCCESS                       The method is successful.
1733          */
1734         result GetCurrent(ValueType& obj) const
1735         {
1736                 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1737                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1738                 TryReturn(__pNode != null, E_INVALID_OPERATION, "[%s] Invalid position(pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1739
1740                 obj = __pNode->value;
1741                 return E_SUCCESS;
1742         }
1743
1744         /**
1745          * Moves this enumerator to the next element of the entry. @n
1746          * After the enumerator is first created or reset using the Reset() method,
1747          * the first call to this method positions the enumerator to the first element in the collection.
1748          *
1749          * @since 2.0
1750          *
1751          * @return              An error code
1752          * @exception   E_SUCCESS                       The method is successful.
1753          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
1754          *                                                                      the entry is modified after this enumerator is created.
1755          * @exception   E_OUT_OF_RANGE          The enumerator has passed the end of the entry.
1756          * @see                 Reset()
1757          */
1758         result MoveNext(void)
1759         {
1760                 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1761                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1762
1763                 result r = E_SUCCESS;
1764                 if (null == __pNode)
1765                 {
1766                         __pNode = __entry.pList;
1767                         AppAssert(null != __pNode);
1768                 }
1769                 else if ((null != __pNode) && (__pNode->pNext != null))
1770                 {
1771                         __pNode = __pNode->pNext;
1772                 }
1773                 else
1774                 {
1775                         // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1776                         r = E_OUT_OF_RANGE;
1777                 }
1778
1779                 return r;
1780         }
1781
1782         /**
1783          * Positions this enumerator before the first element in the entry.
1784          *
1785          * @since 2.0
1786          *
1787          * @return              An error code
1788          * @exception   E_SUCCESS                       The method is successful.
1789          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
1790          *                                                                      the entry is modified after this enumerator is created.
1791          */
1792         result Reset(void)
1793         {
1794                 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1795                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1796
1797                 __pNode = null;
1798                 return E_SUCCESS;
1799         }
1800
1801 private:
1802         const __MultiHashMapEntryT< KeyType, ValueType >& __entry;
1803         int __modCount;
1804         __ValueNodeT< ValueType >* __pNode;
1805
1806 }; // __EntryValueEnumeratorT
1807
1808 //
1809 // @class       __MultiHashMapDefaultProviderT
1810 // @brief       This class is an implementation of IHashCodeProviderT for HashMap.
1811 // @since 2.0
1812 //
1813 template< class KeyType >
1814 class __MultiHashMapDefaultProviderT
1815         : public IHashCodeProviderT< KeyType >
1816         , public Object
1817 {
1818 public:
1819         /**
1820         * This is the default constructor for this class.
1821         *
1822         * @since 2.0
1823         */
1824         __MultiHashMapDefaultProviderT(void) {}
1825
1826         /**
1827         * This is the destructor for this class.
1828         *
1829         * @since 2.0
1830         */
1831         virtual ~__MultiHashMapDefaultProviderT(void) {}
1832
1833         // Operation
1834
1835         /**
1836         * Gets the hash code of the specified instance.
1837         *
1838         * @since 2.0
1839         *
1840         * @return               The hash code
1841         * @see                  Tizen::Base::Object::GetHashCode()
1842         */
1843         virtual int GetHashCode(const KeyType& obj) const
1844         {
1845                 return (int) obj;
1846         }
1847
1848 }; // __MultiHashMapDefaultProviderT
1849
1850 template< class KeyType, class ValueType >
1851 const float MultiHashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1852
1853 }}}   // Tizen::Base::Collection
1854
1855 #endif //_FBASE_COL_MULTI_HASH_MAP_T_H_