inc/FBaseColMultiHashMapT.h

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