src/base/collection/FBaseColMultiHashMap.cpp

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