src/base/collection/FBaseColMultiHashMap.cpp

   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                FBaseColMultiHashMap.cpp
  19  * @brief               This is the implementation for MultiHashMap class.
  20  */
  21
  22 #include <new>
  23 #include <unique_ptr.h>
  24 #include <FBaseColMultiHashMap.h>
  25 #include <FBaseColArrayList.h>
  26 #include <FBaseColMapEntry.h>
  27 #include <FBaseResult.h>
  28 #include <FBaseFloat.h>
  29 #include <FBaseSysLog.h>
  30
  31
  32 namespace Tizen { namespace Base { namespace Collection
  33 {
  34
  35 /**
  36  * @class       __Node
  37  * @brief       This is a node for MultiHashMap.
  38  */
  39 class __Node
  40         : public MapEntry
  41 {
  42 public:
  43         __Node(Object* pKey, Object* pValue);
  44         virtual ~__Node(void);
  45
  46         virtual Object* GetKey(void) const;
  47         virtual Object* GetValue(void) const;
  48
  49 private:
  50         __Node(const __Node& node);
  51         __Node& operator =(const __Node& rhs);
  52
  53         __Node* pNext;
  54
  55         friend class MultiHashMap;
  56         friend class _MultiHashMapEnumerator;
  57         friend class _EntryValueEnumerator;
  58 };
  59
  60 __Node::__Node(Object* pKey, Object* pValue)
  61         : MapEntry(*pKey, *pValue)
  62         , pNext(null)
  63 {
  64 }
  65
  66 __Node::~__Node(void)
  67 {
  68 }
  69
  70 Object*
  71 __Node::GetKey(void) const
  72 {
  73         return _pKey;
  74 }
  75
  76 Object*
  77 __Node::GetValue(void) const
  78 {
  79         return _pValue;
  80 }
  81
  82 /**
  83  * @class       _MultiHashMapEntry
  84  * @brief       This is an entry for MultiHashMap class.
  85  */
  86 class _MultiHashMapEntry
  87 {
  88 public:
  89         _MultiHashMapEntry(Object* key, __Node* list, _MultiHashMapEntry* next, int h);
  90         virtual ~_MultiHashMapEntry(void);
  91
  92         Object* pKey;
  93         __Node* pList;
  94         _MultiHashMapEntry* pNext;
  95         int hash;
  96         int modCount;
  97
  98 private:
  99         _MultiHashMapEntry(const _MultiHashMapEntry& entry);
 100         _MultiHashMapEntry& operator =(const _MultiHashMapEntry& rhs);
 101
 102         friend class MultiHashMap;
 103         friend class _MultiHashMapEnumerator;
 104         friend class _EntryValueEnumerator;
 105
 106 };
 107
 108 _MultiHashMapEntry::_MultiHashMapEntry(Object* key, __Node* list, _MultiHashMapEntry* next, int h)
 109         : pKey(key)
 110         , pList(list)
 111         , pNext(next)
 112         , hash(h)
 113         , modCount(0)
 114 {
 115 }
 116
 117 _MultiHashMapEntry::~_MultiHashMapEntry(void)
 118 {
 119 }
 120
 121 /**
 122  * @class       _MultiHashMapDefaultComparer
 123  * @brief       This is an implementation of IComparer for MultiHashMap.
 124  */
 125 class _MultiHashMapDefaultComparer
 126         : public IComparer
 127         , public Object
 128 {
 129 public:
 130         _MultiHashMapDefaultComparer(void);
 131         virtual ~_MultiHashMapDefaultComparer(void);
 132
 133         virtual result Compare(const Object& obj1, const Object& obj2, int& cmp) const;
 134
 135 };
 136
 137 _MultiHashMapDefaultComparer::_MultiHashMapDefaultComparer(void)
 138 {
 139 }
 140
 141 _MultiHashMapDefaultComparer::~_MultiHashMapDefaultComparer(void)
 142 {
 143 }
 144
 145 result
 146 _MultiHashMapDefaultComparer::Compare(const Object& obj1, const Object& obj2, int& cmp) const
 147 {
 148         if (obj1.Equals(obj2))
 149         {
 150                 cmp = 0;
 151         }
 152         else
 153         {
 154                 cmp = 1;
 155         }
 156
 157         return E_SUCCESS;
 158 }
 159
 160 /**
 161  * @class       _MultiHashMapDefaultProvider
 162  * @brief       This is an implementation of IHashCodeProvider for MultiHashMap.
 163  */
 164 class _MultiHashMapDefaultProvider
 165         : public IHashCodeProvider
 166         , public Object
 167 {
 168 public:
 169         _MultiHashMapDefaultProvider(void) {}
 170         virtual ~_MultiHashMapDefaultProvider(void) {}
 171
 172         using Object::GetHashCode;
 173         virtual int GetHashCode(const Object& obj) const
 174         {
 175                 return obj.GetHashCode();
 176         }
 177
 178 };
 179
 180 /**
 181  * @class       _MultiHashMapEnumerator
 182  * @brief       This is an implementation of IMapEnumerator for MultiHashMap.
 183  */
 184 class _MultiHashMapEnumerator
 185         : public IMapEnumerator
 186         , public Object
 187 {
 188 public:
 189         _MultiHashMapEnumerator(const MultiHashMap& map, int modCount);
 190         virtual ~_MultiHashMapEnumerator(void);
 191
 192         virtual Object* GetCurrent(void) const;
 193         virtual result MoveNext(void);
 194         virtual result Reset(void);
 195         virtual Object* GetKey(void) const;
 196         virtual Object* GetValue(void) const;
 197
 198 private:
 199         const MultiHashMap& __map;
 200         int __modCount;
 201         _MultiHashMapEntry* __pEntry;
 202         __Node* __pNode;
 203         int __index;
 204
 205 };
 206
 207 _MultiHashMapEnumerator::_MultiHashMapEnumerator(const MultiHashMap& map, int modCount)
 208         : __map(map)
 209         , __modCount(modCount)
 210         , __pEntry(null)
 211         , __pNode(null)
 212         , __index(-1)
 213 {
 214 }
 215
 216 _MultiHashMapEnumerator::~_MultiHashMapEnumerator(void)
 217 {
 218 }
 219
 220 Object*
 221 _MultiHashMapEnumerator::GetCurrent(void) const
 222 {
 223         SysTryReturn(NID_BASE_COL, (__modCount == __map.__modCount), null, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 224         SysTryReturn(NID_BASE_COL, (__pEntry != null && __pNode != null), null, E_INVALID_OPERATION, "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
 225
 226         SetLastResult(E_SUCCESS);
 227         return __pNode;
 228 }
 229
 230 result
 231 _MultiHashMapEnumerator::MoveNext(void)
 232 {
 233         SysTryReturnResult(NID_BASE_COL, (__modCount == __map.__modCount), E_INVALID_OPERATION, "The source collection was modified after the creation of this enumerator.");
 234
 235         if ((null != __pNode) && (__pNode->pNext != null))
 236         {
 237                 __pNode = __pNode->pNext;
 238                 return E_SUCCESS;
 239         }
 240         else if ((null != __pEntry) && (__pEntry->pNext != null))
 241         {
 242                 __pEntry = __pEntry->pNext;
 243                 __pNode = __pEntry->pList;
 244                 return E_SUCCESS;
 245         }
 246         else
 247         {
 248                 while (++__index < __map.__capacity)
 249                 {
 250                         __pEntry = __map.__pTable[__index];
 251                         if (null != __pEntry)
 252                         {
 253                                 __pNode = __pEntry->pList;
 254                                 return E_SUCCESS;
 255                         }
 256                 }
 257         }
 258
 259         return E_OUT_OF_RANGE;
 260 }
 261
 262 result
 263 _MultiHashMapEnumerator::Reset(void)
 264 {
 265         SysTryReturnResult(NID_BASE_COL, (__modCount == __map.__modCount), E_INVALID_OPERATION, "The source collection was modified after the creation of this enumerator.");
 266
 267         __index = -1;
 268         __pEntry = null;
 269         __pNode = null;
 270
 271         return E_SUCCESS;
 272 }
 273
 274 Object*
 275 _MultiHashMapEnumerator::GetKey(void) const
 276 {
 277         SysTryReturn(NID_BASE_COL, (__modCount == __map.__modCount), null, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 278         SysTryReturn(NID_BASE_COL, (__pEntry != null && __pNode != null), null, E_INVALID_OPERATION, "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
 279
 280         SetLastResult(E_SUCCESS);
 281         return __pEntry->pKey;
 282 }
 283
 284 Object*
 285 _MultiHashMapEnumerator::GetValue(void) const
 286 {
 287         SysTryReturn(NID_BASE_COL, (__modCount == __map.__modCount), null, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 288         SysTryReturn(NID_BASE_COL, (__pEntry != null && __pNode != null), null, E_INVALID_OPERATION, "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
 289
 290         SetLastResult(E_SUCCESS);
 291         return __pNode->GetValue();
 292 }
 293
 294 /**
 295  * @class       _EntryValueEnumerator
 296  * @brief       This is an implementation of IEnumerator to enumerate values whose key is the same.
 297  */
 298 class _EntryValueEnumerator
 299         : public IEnumerator
 300         , public Object
 301 {
 302 public:
 303         _EntryValueEnumerator(const _MultiHashMapEntry& entry, int modCount);
 304         virtual ~_EntryValueEnumerator(void);
 305
 306         virtual Object* GetCurrent(void) const;
 307         virtual result MoveNext(void);
 308         virtual result Reset(void);
 309
 310 private:
 311         const _MultiHashMapEntry& __entry;
 312         int __modCount;
 313         __Node* __pNode;
 314
 315 };
 316
 317 _EntryValueEnumerator::_EntryValueEnumerator(const _MultiHashMapEntry& entry, int modCount)
 318         : __entry(entry)
 319         , __modCount(modCount)
 320         , __pNode(null)
 321 {
 322 }
 323
 324 _EntryValueEnumerator::~_EntryValueEnumerator(void)
 325 {
 326 }
 327
 328 Object*
 329 _EntryValueEnumerator::GetCurrent(void) const
 330 {
 331         SysTryReturn(NID_BASE_COL, __modCount == __entry.modCount, null, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 332         SysTryReturn(NID_BASE_COL, __pNode != null, null, E_INVALID_OPERATION, "[%s] Invalid position(pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
 333
 334         SetLastResult(E_SUCCESS);
 335         return __pNode->GetValue();
 336 }
 337
 338 result
 339 _EntryValueEnumerator::MoveNext(void)
 340 {
 341         SysTryReturn(NID_BASE_COL, (__modCount == __entry.modCount), E_INVALID_OPERATION, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 342
 343         if (__pNode == null)
 344         {
 345                 __pNode = __entry.pList;
 346                 SysAssert(null != __pNode);
 347         }
 348         else if (__pNode->pNext != null)
 349         {
 350                 __pNode = __pNode->pNext;
 351         }
 352         else
 353         {
 354                 // Do not log the E_OUT_OF_RANGE, because it's normal or trivial in most cases.
 355                 return E_OUT_OF_RANGE;
 356         }
 357
 358         return E_SUCCESS;
 359 }
 360
 361 result
 362 _EntryValueEnumerator::Reset(void)
 363 {
 364         SysTryReturn(NID_BASE_COL, (__modCount == __entry.modCount), E_INVALID_OPERATION, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 365
 366         __pNode = null;
 367         return E_SUCCESS;
 368 }
 369
 370 const float MultiHashMap::DEFAULT_LOAD_FACTOR = 0.75;
 371
 372 MultiHashMap::MultiHashMap(DeleterFunctionType deleter)
 373         : __pTable(null)
 374         , __count(0)
 375         , __capacity(0)
 376         , __loadFactor(0)
 377         , __threshold(0)
 378         , __pProvider(null)
 379         , __pComparer(null)
 380         , __needToRemoveProviderComparer(false)
 381         , __modCount(0)
 382         , __deleter(deleter)
 383         , __pMultiHashMapImpl(null)
 384 {
 385 }
 386
 387 MultiHashMap::~MultiHashMap(void)
 388 {
 389         __modCount++;
 390         if (__pTable != null)
 391         {
 392                 Reset();
 393                 delete[] __pTable;
 394         }
 395
 396         if (__needToRemoveProviderComparer)
 397         {
 398                 delete __pProvider;
 399                 delete __pComparer;
 400         }
 401 }
 402
 403 result
 404 MultiHashMap::Construct(int capacity, float loadFactor)
 405 {
 406         SysTryReturnResult(NID_BASE_COL, capacity >= 0, E_INVALID_ARG, "The capacity(%d) MUST be greater than or equal to 0.", capacity);
 407         SysTryReturnResult(NID_BASE_COL, loadFactor >= 0, E_INVALID_ARG, "The loadFactor(%f) MUST be greater than or equal to 0.0.", loadFactor);
 408
 409         std::unique_ptr< IHashCodeProvider > pProvider(new (std::nothrow) _MultiHashMapDefaultProvider());
 410         SysTryReturnResult(NID_BASE_COL, pProvider != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 411
 412         std::unique_ptr< IComparer > pComparer(new (std::nothrow) _MultiHashMapDefaultComparer());
 413         SysTryReturnResult(NID_BASE_COL, pComparer != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 414
 415         __needToRemoveProviderComparer = true;
 416
 417         result r = Construct(capacity, loadFactor, *(pProvider.release()), *(pComparer.release()));
 418         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 419
 420         return r;
 421 }
 422
 423 result
 424 MultiHashMap::Construct(const IMultiMap& map, float loadFactor)
 425 {
 426         SysTryReturnResult(NID_BASE_COL, loadFactor >= 0, E_INVALID_ARG, "The loadFactor(%f) MUST be greater than or equal to 0.0.", loadFactor);
 427
 428         std::unique_ptr< IHashCodeProvider > pProvider(new (std::nothrow) _MultiHashMapDefaultProvider());
 429         SysTryReturnResult(NID_BASE_COL, pProvider != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 430
 431         std::unique_ptr< IComparer > pComparer(new (std::nothrow) _MultiHashMapDefaultComparer());
 432         SysTryReturnResult(NID_BASE_COL, pComparer != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 433
 434         __needToRemoveProviderComparer = true;
 435
 436         result r = Construct(map, loadFactor, *(pProvider.release()), *(pComparer.release()));
 437         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 438
 439         return r;
 440 }
 441
 442 result
 443 MultiHashMap::Construct(int capacity, float loadFactor, const IHashCodeProvider& provider, const IComparer& comparer)
 444 {
 445         SysTryReturnResult(NID_BASE_COL, capacity >= 0, E_INVALID_ARG, "The capacity(%d) MUST be greater than or equal to 0.", capacity);
 446         SysTryReturnResult(NID_BASE_COL, loadFactor >= 0, E_INVALID_ARG, "The loadFactor(%f) MUST be greater than or equal to 0.0.", loadFactor);
 447
 448         int newCapacity = 0;
 449         if (capacity == 0)
 450         {
 451                 newCapacity = DEFAULT_CAPACITY;
 452         }
 453         else
 454         {
 455                 newCapacity = 1;
 456                 while (newCapacity < capacity)
 457                 {
 458                         newCapacity <<= 1;
 459                 }
 460         }
 461
 462         float newLoadFactor = 0;
 463         if (Float::Compare(loadFactor, 0) == 0)
 464         {
 465                 newLoadFactor = DEFAULT_LOAD_FACTOR;
 466         }
 467         else
 468         {
 469                 newLoadFactor = loadFactor;
 470         }
 471
 472         int newThreshold = static_cast< int >(newCapacity * newLoadFactor);
 473         std::unique_ptr< IHashCodeProvider > pProvider(const_cast< IHashCodeProvider* >(&provider));
 474         std::unique_ptr< IComparer > pComparer(const_cast< IComparer* >(&comparer));
 475         std::unique_ptr< _MultiHashMapEntry*[] > pTable(new (std::nothrow) _MultiHashMapEntry*[newCapacity]);
 476         SysTryReturnResult(NID_BASE_COL, pTable != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 477
 478         memset(pTable.get(), null, sizeof(*(pTable.get())) * newCapacity);
 479
 480         __capacity = newCapacity;
 481         __loadFactor = newLoadFactor;
 482         __threshold = newThreshold;
 483         __pProvider = pProvider.release();
 484         __pComparer = pComparer.release();
 485         __pTable = pTable.release();
 486
 487         return E_SUCCESS;
 488 }
 489
 490 result
 491 MultiHashMap::Construct(const IMultiMap& map, float loadFactor, const IHashCodeProvider& provider, const IComparer& comparer)
 492 {
 493         SysTryReturnResult(NID_BASE_COL, (loadFactor >= 0), E_INVALID_ARG, "The loadFactor(%f) MUST be greater than or equal to 0.0.", loadFactor);
 494
 495         result r = E_SUCCESS;
 496         if (Float::Compare(loadFactor, 0) == 0)
 497         {
 498                 loadFactor = DEFAULT_LOAD_FACTOR;
 499         }
 500
 501         int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
 502
 503         r = Construct(capacity, loadFactor, provider, comparer);
 504         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 505
 506         r = AddAll(map);
 507         SysTryCatch(NID_BASE_COL, r == E_SUCCESS, , r, "[%s] Propagating.", GetErrorMessage(r));
 508         return r;
 509
 510 CATCH:
 511         DeleterFunctionType deleter = GetDeleter();
 512         SetDeleter(SingleObjectDeleter);
 513         Reset();
 514         SetDeleter(deleter);
 515
 516         delete[] __pTable;
 517         __pTable = null;
 518
 519         if (__needToRemoveProviderComparer)
 520         {
 521                 delete __pProvider;
 522                 delete __pComparer;
 523         }
 524
 525         __capacity = 0;
 526         __pProvider = null;
 527         __pComparer = null;
 528
 529         return r;
 530 }
 531
 532 result
 533 MultiHashMap::Add(Object* pKey, Object* pValue)
 534 {
 535         SysTryReturnResult(NID_BASE_COL, pKey != null , E_INVALID_ARG, "Invalid argument used. The pKey is null");
 536         SysTryReturnResult(NID_BASE_COL, pValue != null, E_INVALID_ARG, "Invalid argument used. The pValue is null");
 537
 538         __Node* pNewNode = null;
 539
 540         result r = E_SUCCESS;
 541         int hash = Hash(*pKey);
 542         int i = hash & (__capacity - 1);
 543         __Node* pNode = null;
 544         _MultiHashMapEntry* pEntry = null;
 545
 546         if (__pTable != null)
 547         {
 548                 pEntry = __pTable[i];
 549         }
 550         while (pEntry != null)
 551         {
 552                 if (hash == pEntry->hash)
 553                 {
 554                         int cmpResult = 0;
 555                         r = __pComparer->Compare(*pKey, *(pEntry->pKey), cmpResult);
 556                         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, E_INVALID_ARG, "Translating [%s] into [%s]", GetErrorMessage(r), GetErrorMessage(E_INVALID_ARG));
 557
 558                         if (cmpResult == 0)
 559                         {
 560                                 pNode = pEntry->pList;
 561                                 while (true)
 562                                 {
 563                                         SysTryReturnResult(NID_BASE_COL, !(pNode->_pValue->Equals(*pValue)), E_OBJ_ALREADY_EXIST, "The value is already exist for the key.");
 564
 565                                         if (pNode->pNext != null)
 566                                         {
 567                                                 pNode = pNode->pNext;
 568                                         }
 569                                         else
 570                                         {
 571                                                 pEntry->modCount++;
 572                                                 break;
 573                                         }
 574                                 }
 575                                 break;
 576                         }
 577                 }
 578                 pEntry = pEntry->pNext;
 579         }
 580
 581         pNewNode = new (std::nothrow) __Node(pKey, pValue);
 582         SysTryReturnResult(NID_BASE_COL, pNewNode != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 583
 584         // pKey is not exist in this map.
 585         if (pEntry == null)
 586         {
 587                 _MultiHashMapEntry* pNewEntry = new (std::nothrow) _MultiHashMapEntry(pKey, pNewNode, __pTable[i], hash);
 588                 SysTryReturnResult(NID_BASE_COL, pNewEntry != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 589                 __pTable[i] = pNewEntry;
 590         }
 591         // pKey is already exist in this map, but value is not.
 592         else
 593         {
 594                 // pNode is the last value associated to the pKey
 595                 pNode->pNext = pNewNode;
 596         }
 597
 598         __modCount++;
 599
 600         if (__count++ >= __threshold)
 601         {
 602                 r = Resize(__capacity * 2);
 603                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 604         }
 605
 606         return E_SUCCESS;
 607 }
 608
 609 IEnumerator*
 610 MultiHashMap::GetEnumeratorN(void) const
 611 {
 612         std::unique_ptr< _MultiHashMapEnumerator > pEnum(new (std::nothrow) _MultiHashMapEnumerator(*this, __modCount));
 613         SysTryReturn(NID_BASE_COL, pEnum != null, null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 614
 615         SetLastResult(E_SUCCESS);
 616         return pEnum.release();
 617 }
 618
 619 IMapEnumerator*
 620 MultiHashMap::GetMapEnumeratorN(void) const
 621 {
 622         return dynamic_cast< IMapEnumerator* >(GetEnumeratorN());
 623 }
 624
 625 IEnumerator*
 626 MultiHashMap::GetValuesN(const Object& key) const
 627 {
 628         int hash = Hash(key);
 629         int i = hash & (__capacity - 1);
 630
 631         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 632         {
 633                 if (hash == pEntry->hash)
 634                 {
 635                         int cmpResult = 0;
 636                         result r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 637                         SysTryReturn(NID_BASE_COL, r == E_SUCCESS, null, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 638
 639                         if (cmpResult == 0)
 640                         {
 641                                 std::unique_ptr< IEnumerator > pEnum(new (std::nothrow) _EntryValueEnumerator(*pEntry, pEntry->modCount));
 642                                 SysTryReturn(NID_BASE_COL, pEnum != null, null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 643
 644                                 SetLastResult(E_SUCCESS);
 645                                 return pEnum.release();
 646                         }
 647                 }
 648         }
 649
 650         SetLastResult(E_OBJ_NOT_FOUND);
 651         return null;
 652 }
 653
 654 IList*
 655 MultiHashMap::GetKeysN(void) const
 656 {
 657         result r = E_SUCCESS;
 658         int keyCount = 0;
 659
 660         std::unique_ptr< ArrayList > pList(new (std::nothrow) ArrayList());
 661         SysTryReturn(NID_BASE_COL, pList != null, null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 662
 663         r = pList->Construct(__count);
 664         SysTryReturn(NID_BASE_COL, r == E_SUCCESS, null, r, "[%s] Propagating.", GetErrorMessage(r));
 665
 666         for (int i = 0; i < __capacity; i++)
 667         {
 668                 for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 669                 {
 670                         r = pList->Add(pEntry->pKey);
 671                         SysTryReturn(NID_BASE_COL, r == E_SUCCESS, null, r, "[%s] Propagating.", GetErrorMessage(r));
 672                         keyCount++;
 673                 }
 674         }
 675
 676         SetLastResult(E_SUCCESS);
 677         return pList.release();
 678 }
 679
 680 IList*
 681 MultiHashMap::GetValuesN(void) const
 682 {
 683         result r = E_SUCCESS;
 684
 685         std::unique_ptr< ArrayList > pList(new (std::nothrow) ArrayList());
 686         SysTryReturn(NID_BASE_COL, pList != null, null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 687
 688         r = pList->Construct(__count);
 689         SysTryReturn(NID_BASE_COL, r == E_SUCCESS, null, r, "[%s] Propagating.", GetErrorMessage(r));
 690
 691         for (int i = 0; i < __capacity; i++)
 692         {
 693                 for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 694                 {
 695                         for (__Node* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 696                         {
 697                                 r = pList->Add(pNode->_pValue);
 698                                 SysTryReturn(NID_BASE_COL, r == E_SUCCESS, null, r, "[%s] Propagating.", GetErrorMessage(r));
 699                         }
 700                 }
 701         }
 702
 703         SetLastResult(E_SUCCESS);
 704         return pList.release();
 705 }
 706
 707 result
 708 MultiHashMap::Remove(const Object& key)
 709 {
 710         int hash = Hash(key);
 711         int i = hash & (__capacity - 1);
 712
 713         _MultiHashMapEntry* pPrev = __pTable[i];
 714         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 715         {
 716                 if (hash == pEntry->hash)
 717                 {
 718                         int cmpResult = 0;
 719                         result r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 720                         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, E_INVALID_ARG, "The input argument is invalid");
 721
 722                         if (cmpResult == 0)
 723                         {
 724                                 __modCount++;
 725                                 if (pPrev == pEntry)
 726                                 {
 727                                         __pTable[i] = pEntry->pNext;
 728                                 }
 729                                 else
 730                                 {
 731                                         pPrev->pNext = pEntry->pNext;
 732                                 }
 733
 734                                 __Node* pNode = pEntry->pList;
 735                                 while (pNode != null)
 736                                 {
 737                                         __Node* pTemp = pNode;
 738                                         pNode = pNode->pNext;
 739
 740                                         __deleter(pTemp->_pValue);
 741
 742                                         delete pTemp;
 743                                         __count--;
 744                                 }
 745
 746                                 __deleter(pEntry->pKey);
 747
 748                                 delete pEntry;
 749
 750                                 return E_SUCCESS;
 751                         }
 752                 }
 753                 pPrev = pEntry;
 754         }
 755
 756         return E_OBJ_NOT_FOUND;
 757 }
 758
 759 result
 760 MultiHashMap::Remove(const Object& key, const Object& value)
 761 {
 762         int hash = Hash(key);
 763         int i = hash & (__capacity - 1);
 764
 765         _MultiHashMapEntry* pPrev = __pTable[i];
 766         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 767         {
 768                 if (hash == pEntry->hash)
 769                 {
 770                         int cmpResult = 0;
 771                         result r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 772                         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, E_INVALID_ARG, "The input argument is invalid");
 773
 774                         if (cmpResult == 0)
 775                         {
 776                                 __Node* pPrevNode = pEntry->pList;
 777                                 for (__Node* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 778                                 {
 779                                         if (value.Equals(*(pNode->_pValue)))
 780                                         {
 781                                                 __modCount++;
 782                                                 __count--;
 783                                                 if (pPrevNode == pNode)
 784                                                 {
 785                                                         pEntry->pList = pNode->pNext;
 786                                                 }
 787                                                 else
 788                                                 {
 789                                                         pPrevNode->pNext = pNode->pNext;
 790                                                 }
 791
 792                                                 __deleter(pNode->_pValue);
 793                                                 pNode->_pValue = null;
 794
 795                                                 delete pNode;
 796                                                 pNode = null;
 797
 798                                                 pEntry->modCount++;
 799
 800                                                 if (pEntry->pList == null)
 801                                                 {
 802                                                         if (pPrev == pEntry)
 803                                                         {
 804                                                                 __pTable[i] = pEntry->pNext;
 805                                                         }
 806                                                         else
 807                                                         {
 808                                                                 pPrev->pNext = pEntry->pNext;
 809                                                         }
 810
 811                                                         __deleter(pEntry->pKey);
 812                                                         pEntry->pKey = null;
 813
 814                                                         delete pEntry;
 815                                                         pEntry = null;
 816                                                 }
 817                                                 return E_SUCCESS;
 818                                         }
 819                                         pPrevNode = pNode;
 820                                 }
 821                                 if (!IsFailed(r))
 822                                 {
 823                                         break;
 824                                 }
 825                         }
 826                 }
 827                 pPrev = pEntry;
 828         }
 829
 830         return E_OBJ_NOT_FOUND;
 831 }
 832
 833 void
 834 MultiHashMap::RemoveAll(void)
 835 {
 836         if (__count > 0)
 837         {
 838                 __modCount++;
 839                 Reset();
 840                 __count = 0;
 841         }
 842 }
 843
 844 result
 845 MultiHashMap::SetValue(const Object& key, const Object& value, Object* pNewValue)
 846 {
 847         SysTryReturnResult(NID_BASE_COL, pNewValue != null , E_INVALID_ARG, "Invalid argument used. The pNewValue is null");
 848
 849         result r = E_SUCCESS;
 850         int hash = Hash(key);
 851         int i = hash & (__capacity - 1);
 852         __Node* pNode = null;
 853         _MultiHashMapEntry* pEntry = __pTable[i];
 854         bool pairExist = false;
 855         while (null != pEntry)
 856         {
 857                 if (hash == pEntry->hash)
 858                 {
 859                         int cmpResult = 0;
 860                         r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 861                         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, E_INVALID_ARG, "The input argument is invalid");
 862
 863                         if (cmpResult == 0)
 864                         {
 865                                 pNode = pEntry->pList;
 866                                 while (true)
 867                                 {
 868                                         if (pNode->_pValue->Equals(value))
 869                                         {
 870                                                 __modCount++;
 871                                                 __deleter(pNode->_pValue);
 872                                                 pNode->_pValue = pNewValue;
 873                                                 pairExist = true;
 874                                                 break;
 875                                         }
 876                                         if (pNode->pNext != null)
 877                                         {
 878                                                 pNode = pNode->pNext;
 879                                         }
 880                                         else
 881                                         {
 882                                                 pEntry->modCount++;
 883                                                 break;
 884                                         }
 885                                 }
 886                                 break;
 887                         }
 888                 }
 889                 pEntry = pEntry->pNext;
 890         }
 891
 892         if (!pairExist)
 893         {
 894                 r = E_OBJ_NOT_FOUND;
 895         }
 896
 897         return r;
 898
 899 }
 900
 901 int
 902 MultiHashMap::GetCount(void) const
 903 {
 904         return __count;
 905 }
 906
 907 result
 908 MultiHashMap::GetCount(const Object& key, int& count) const
 909 {
 910         count = 0;
 911
 912         result r = E_OBJ_NOT_FOUND;
 913         int hash = Hash(key);
 914         int i = hash & (__capacity - 1);
 915
 916         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 917         {
 918                 if (hash == pEntry->hash)
 919                 {
 920                         int cmpResult = 0;
 921                         r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 922                         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, E_INVALID_ARG, "The input argument is invalid");
 923
 924                         if (cmpResult == 0)
 925                         {
 926                                 int __count = 0;
 927                                 for (__Node* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 928                                 {
 929                                         __count++;
 930                                 }
 931                                 count = __count;
 932                                 r = E_SUCCESS;
 933                                 break;
 934                         }
 935                 }
 936         }
 937
 938         return r;
 939 }
 940
 941 bool
 942 MultiHashMap::Contains(const Object& key, const Object& value) const
 943 {
 944         result r = E_SUCCESS;
 945         int hash = Hash(key);
 946         int i = hash & (__capacity - 1);
 947
 948         SetLastResult(E_SUCCESS);
 949
 950         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 951         {
 952                 if (hash == pEntry->hash)
 953                 {
 954                         int cmpResult = 0;
 955                         r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 956                         SysTryReturn(NID_BASE_COL, r == E_SUCCESS, false, E_INVALID_ARG, "Translating [%s] into [%s]", GetErrorMessage(r), GetErrorMessage(E_INVALID_ARG));
 957
 958                         if (cmpResult == 0)
 959                         {
 960                                 for (__Node* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
 961                                 {
 962                                         if (value.Equals(*(pNode->_pValue)))
 963                                         {
 964                                                 return true;
 965                                         }
 966                                 }
 967                         }
 968                 }
 969         }
 970
 971         return false;
 972 }
 973
 974 bool
 975 MultiHashMap::ContainsKey(const Object& key) const
 976 {
 977         result r = E_SUCCESS;
 978         int hash = Hash(key);
 979         int i = hash & (__capacity - 1);
 980
 981         SetLastResult(E_SUCCESS);
 982
 983         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
 984         {
 985                 if (hash == pEntry->hash)
 986                 {
 987                         int cmpResult = 0;
 988                         r = __pComparer->Compare(key, *(pEntry->pKey), cmpResult);
 989                         SysTryReturn(NID_BASE_COL, r == E_SUCCESS, false, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
 990
 991                         if (cmpResult == 0)
 992                         {
 993                                 return true;
 994                         }
 995                 }
 996         }
 997
 998         return false;
 999 }
1000
1001 bool
1002 MultiHashMap::ContainsValue(const Object& value) const
1003 {
1004         for (int i = 0; i < __capacity; i++)
1005         {
1006                 for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1007                 {
1008                         for (__Node* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1009                         {
1010                                 if (value.Equals(*(pNode->_pValue)))
1011                                 {
1012                                         return true;
1013                                 }
1014                         }
1015                 }
1016         }
1017         return false;
1018 }
1019
1020 bool
1021 MultiHashMap::Equals(const Object& obj) const
1022 {
1023         const MultiHashMap* pOther = dynamic_cast< const MultiHashMap* >(&obj);
1024         if (pOther == null)
1025         {
1026                 return false;
1027         }
1028         else if (pOther == this)
1029         {
1030                 return true;
1031         }
1032         else if (__count != pOther->__count)
1033         {
1034                 return false;
1035         }
1036         else
1037         {
1038                 bool contain = true;
1039                 for (int i = 0; i < __capacity; i++)
1040                 {
1041                         for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1042                         {
1043                                 for (__Node* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1044                                 {
1045                                         contain = pOther->Contains(*(pEntry->pKey), *(pNode->_pValue));
1046                                         result r = GetLastResult();
1047                                         SysTryReturn(NID_BASE_COL, !IsFailed(r), false, r, "[%s] Propagating", GetErrorMessage(r));
1048                                 }
1049                                 if (!contain)
1050                                 {
1051                                         break;
1052                                 }
1053                         }
1054                         if (!contain)
1055                         {
1056                                 break;
1057                         }
1058                 }
1059                 return contain;
1060         }
1061
1062         return true;
1063 }
1064
1065 int
1066 MultiHashMap::GetHashCode(void) const
1067 {
1068         int hash = 0;
1069         _MultiHashMapEntry* pEntry = null;
1070         _MultiHashMapEntry* pNext = null;
1071         __Node* pNode = null;
1072         for (int i = 0; i < __capacity; i++)
1073         {
1074                 pEntry = __pTable[i];
1075                 while (pEntry != null)
1076                 {
1077                         pNext = pEntry->pNext;
1078                         pNode = pEntry->pList;
1079                         while (pNode != null)
1080                         {
1081                                 hash += pNode->_pValue->GetHashCode();
1082                                 pNode = pNode->pNext;
1083                         }
1084
1085                         hash += pEntry->pKey->GetHashCode();
1086                         pEntry = pNext;
1087                 }
1088         }
1089         return hash;
1090 }
1091
1092 DeleterFunctionType
1093 MultiHashMap::GetDeleter(void) const
1094 {
1095         return __deleter;
1096 }
1097
1098 result
1099 MultiHashMap::AddAll(const IMultiMap& map)
1100 {
1101         result r = E_SUCCESS;
1102         std::unique_ptr< IMapEnumerator > pMapEnum(map.GetMapEnumeratorN());
1103         SysTryReturnResult(NID_BASE_COL, pMapEnum != null, GetLastResult(), "Propagating.");
1104
1105         while ((r = pMapEnum->MoveNext()) != E_OUT_OF_RANGE)
1106         {
1107                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
1108
1109                 Object* pKey = pMapEnum->GetKey();
1110                 SysTryReturnResult(NID_BASE_COL, pKey != null, GetLastResult(), "Propagating.");
1111
1112                 Object* pValue = pMapEnum->GetValue();
1113                 SysTryReturnResult(NID_BASE_COL, pValue != null, GetLastResult(), "Propagating.");
1114
1115                 r = Add(pKey, pValue);
1116                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
1117         }
1118
1119         return E_SUCCESS;
1120 }
1121
1122 int
1123 MultiHashMap::Hash(const Object& obj) const
1124 {
1125         int h = __pProvider->GetHashCode(obj);
1126
1127         h ^= (h >> 20) ^ (h >> 12);
1128
1129         return h ^ (h >> 7) ^ (h >> 4);
1130 }
1131
1132 result
1133 MultiHashMap::Resize(int newCapacity)
1134 {
1135         _MultiHashMapEntry** pNewTable = new (std::nothrow) _MultiHashMapEntry*[newCapacity];
1136         SysTryReturnResult(NID_BASE_COL, pNewTable != null, E_OUT_OF_MEMORY, "");
1137         memset(pNewTable, null, sizeof(*pNewTable) * newCapacity);
1138
1139         for (int i = 0; i < __capacity; i++)
1140         {
1141                 _MultiHashMapEntry* pNext = null;
1142                 int index = 0;
1143                 for (_MultiHashMapEntry* pEntry = __pTable[i]; null != pEntry; pEntry = pNext)
1144                 {
1145                         pNext = pEntry->pNext;
1146                         index = pEntry->hash & (newCapacity - 1);
1147                         pEntry->pNext = pNewTable[index];
1148                         pNewTable[index] = pEntry;
1149                 }
1150         }
1151
1152         delete[] __pTable;
1153         __pTable = pNewTable;
1154         __capacity = newCapacity;
1155         __threshold = static_cast< int >(__capacity * __loadFactor);
1156
1157         return E_SUCCESS;
1158 }
1159
1160 void
1161 MultiHashMap::Reset(void)
1162 {
1163         for (int i = 0; i < __capacity; i++)
1164         {
1165                 _MultiHashMapEntry* pEntry = __pTable[i];
1166                 while (pEntry != null)
1167                 {
1168                         _MultiHashMapEntry* pNext = pEntry->pNext;
1169                         __Node* pNode = pEntry->pList;
1170
1171                         while (pNode != null)
1172                         {
1173                                 std::unique_ptr< __Node > pTemp(pNode);
1174                                 pNode = pNode->pNext;
1175
1176                                 __deleter(pTemp->_pValue);
1177                         }
1178
1179                         __deleter(pEntry->pKey);
1180                         delete pEntry;
1181                         pEntry = pNext;
1182                 }
1183                 __pTable[i] = null;
1184         }
1185 }
1186
1187 void
1188 MultiHashMap::SetDeleter(DeleterFunctionType deleter)
1189 {
1190         __deleter = deleter;
1191 }
1192 } } }  // Tizen::Base::Collectionn