src/base/collection/FBaseColLinkedList.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                FBaseColLinkedList.cpp
  20  * @brief               This is the implementation for LinkedList class.
  21  */
  22
  23 #include <new>
  24 #include <unique_ptr.h>
  25 #include <FBaseColLinkedList.h>
  26 #include <FBaseResult.h>
  27 #include <FBaseSysLog.h>
  28
  29
  30 namespace Tizen { namespace Base { namespace Collection
  31 {
  32
  33 class _ListNode
  34         : public Object
  35 {
  36 public:
  37         _ListNode(void);
  38         virtual ~_ListNode(void);
  39
  40         _ListNode* pPrev;
  41         _ListNode* pNext;
  42         Object* pObj;
  43         _ListNode* pNextBlock;
  44
  45 };
  46
  47 _ListNode::_ListNode(void)
  48         : pPrev(null)
  49         , pNext(null)
  50         , pObj(null)
  51         , pNextBlock(null)
  52 {
  53 }
  54
  55 _ListNode::~_ListNode(void)
  56 {
  57 }
  58
  59 class _LinkedListEnumerator
  60         : public IBidirectionalEnumerator
  61         , public Object
  62 {
  63 public:
  64         _LinkedListEnumerator(const LinkedList& list, int modCount);
  65
  66         virtual ~_LinkedListEnumerator(void);
  67
  68         virtual Object* GetCurrent(void) const;
  69         virtual result MoveNext(void);
  70         virtual result Reset(void);
  71
  72         virtual result MovePrevious();
  73         virtual result ResetLast();
  74
  75 private:
  76         const LinkedList& __list;
  77         _ListNode* __pNode;
  78         int __modCount;
  79
  80 };
  81
  82 _LinkedListEnumerator::_LinkedListEnumerator(const LinkedList& list, int modCount)
  83         : __list(list)
  84         , __pNode(null)
  85         , __modCount(modCount)
  86 {
  87 }
  88
  89 _LinkedListEnumerator::~_LinkedListEnumerator(void)
  90 {
  91 }
  92
  93 Object*
  94 _LinkedListEnumerator::GetCurrent(void) const
  95 {
  96         SysTryReturn(NID_BASE_COL, __modCount == __list.__modCount, null, E_INVALID_OPERATION, "[%s] The source collection was modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
  97         SysTryReturn(NID_BASE_COL, __pNode != null, null, E_INVALID_OPERATION, "[%s] Current position is before the first element or past the last element.", GetErrorMessage(E_INVALID_OPERATION));
  98         SetLastResult(E_SUCCESS);
  99         return __pNode->pObj;
 100 }
 101
 102 result
 103 _LinkedListEnumerator::MoveNext(void)
 104 {
 105         SysTryReturnResult(NID_BASE_COL, __modCount == __list.__modCount, E_INVALID_OPERATION, "The source collection was modified after the creation of this enumerator.");
 106
 107         if (__pNode == null)
 108         {
 109                 __pNode = __list.__pListHead;
 110                 if (__pNode == null)
 111                 {
 112                         return E_OUT_OF_RANGE;
 113                 }
 114         }
 115         else
 116         {
 117                 if (__pNode->pNext != null)
 118                 {
 119                         __pNode = __pNode->pNext;
 120                 }
 121                 else
 122                 {
 123                         return E_OUT_OF_RANGE;
 124                 }
 125         }
 126
 127         return E_SUCCESS;
 128 }
 129
 130 result
 131 _LinkedListEnumerator::Reset(void)
 132 {
 133         SysTryReturnResult(NID_BASE_COL, __modCount == __list.__modCount, E_INVALID_OPERATION, "The source collection was modified after the creation of this enumerator.");
 134
 135         __pNode = null;
 136         return E_SUCCESS;
 137 }
 138
 139 result
 140 _LinkedListEnumerator::MovePrevious(void)
 141 {
 142         SysTryReturnResult(NID_BASE_COL, __modCount == __list.__modCount, E_INVALID_OPERATION, "The source collection was modified after the creation of this enumerator.");
 143
 144         if (__pNode == null)
 145         {
 146                 __pNode = __list.__pListTail;
 147                 if (__pNode == null)
 148                 {
 149                         return E_OUT_OF_RANGE;
 150                 }
 151         }
 152         else
 153         {
 154                 if (__pNode->pPrev != null)
 155                 {
 156                         __pNode = __pNode->pPrev;
 157                 }
 158                 else
 159                 {
 160                         return E_OUT_OF_RANGE;
 161                 }
 162         }
 163
 164         return E_SUCCESS;
 165 }
 166
 167 result
 168 _LinkedListEnumerator::ResetLast(void)
 169 {
 170         return Reset();
 171 }
 172
 173 LinkedList::LinkedList(DeleterFunctionType deleter)
 174         : __pListHead(null)
 175         , __pListTail(null)
 176         , __pAvailableHead(null)
 177         , __pAvailableTail(null)
 178         , __pBlocks(null)
 179         , __count(0)
 180         , __capacity(0)
 181         , __modCount(0)
 182         , __deleter(deleter)
 183         , __pLinkedListImpl(null)
 184 {
 185 }
 186
 187 LinkedList::~LinkedList(void)
 188 {
 189         RemoveAll();
 190         DeleteBlock();
 191 }
 192
 193 result
 194 LinkedList::Add(Object* pObj)
 195 {
 196         SysTryReturnResult(NID_BASE_COL, pObj != null, E_INVALID_ARG, "Invalid argument used. The pObj is null");
 197
 198         result r = E_SUCCESS;
 199         if (__count == 0)
 200         {
 201                 r = InsertFirst(pObj);
 202         }
 203         else
 204         {
 205                 r = InsertLast(pObj);
 206         }
 207
 208         if (r != E_SUCCESS)
 209         {
 210                 SysLogException(NID_BASE_COL, r, "[%s] Propagating.", GetErrorMessage(r));
 211         }
 212
 213         __modCount++;
 214
 215         return r;
 216 }
 217
 218 result
 219 LinkedList::AddItems(const ICollection& collection)
 220 {
 221         result r = InsertItemsFrom(collection, __count);
 222         if (r != E_SUCCESS)
 223         {
 224                 SysLogException(NID_BASE_COL, r, "[%s] Propagating.", GetErrorMessage(r));
 225         }
 226
 227         return r;
 228 }
 229
 230 IEnumerator*
 231 LinkedList::GetEnumeratorN(void) const
 232 {
 233         return GetBidirectionalEnumeratorN();
 234 }
 235
 236 IBidirectionalEnumerator*
 237 LinkedList::GetBidirectionalEnumeratorN() const
 238 {
 239         std::unique_ptr< _LinkedListEnumerator > pEnum(new (std::nothrow) _LinkedListEnumerator(*this, __modCount));
 240         SysTryReturn(NID_BASE_COL, pEnum != null, null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 241
 242         SetLastResult(E_SUCCESS);
 243         return pEnum.release();
 244 }
 245
 246 const Object*
 247 LinkedList::GetAt(int index) const
 248 {
 249         SysTryReturn(NID_BASE_COL, index >= 0 && index < __count, null, E_OUT_OF_RANGE, "[%s] The index(%d) MUST be greater than or equal to 0, and less than the number of elements(%d).", GetErrorMessage(E_OUT_OF_RANGE), index, __count);
 250
 251         _ListNode* pNode = GetNode(index);
 252         SetLastResult(E_SUCCESS);
 253         return pNode->pObj;
 254 }
 255
 256 Object*
 257 LinkedList::GetAt(int index)
 258 {
 259         SysTryReturn(NID_BASE_COL, index >= 0 && index < __count, null, E_OUT_OF_RANGE, "[%s] The index(%d) MUST be greater than or equal to 0, and less than the number of elements(%d).", GetErrorMessage(E_OUT_OF_RANGE), index, __count);
 260
 261         const Object* pObj = (static_cast< const LinkedList* >(this))->GetAt(index);
 262         SetLastResult(E_SUCCESS);
 263         return const_cast< Object* >(pObj);
 264 }
 265
 266 IList*
 267 LinkedList::GetItemsN(int startIndex, int count) const
 268 {
 269         result r = E_SUCCESS;
 270
 271         SysTryReturn(NID_BASE_COL, startIndex >= 0 && count >= 0, null, E_OUT_OF_RANGE, "[%s] Both of the startIndex(%d) and count(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_OUT_OF_RANGE), startIndex, count);
 272         SysTryReturn(NID_BASE_COL, startIndex < __count, null, E_OUT_OF_RANGE,
 273                 "[%s] The startIndex(%d) MUST be less than the number of elements(%d).", GetErrorMessage(E_OUT_OF_RANGE), startIndex, __count);
 274         SysTryReturn(NID_BASE_COL, count <= __count && (startIndex + count <= __count), null, E_OUT_OF_RANGE,
 275                 "[%s] The startIndex(%d) + count(%d) MUST be less than or equal to the number of elements(%d).", GetErrorMessage(E_OUT_OF_RANGE), startIndex, count, __count);
 276
 277         _ListNode* pNode = GetNode(startIndex);
 278
 279         int linkedListCount = startIndex + count;
 280         std::unique_ptr< LinkedList > pList(new (std::nothrow) LinkedList());
 281         SysTryReturn(NID_BASE_COL, pList != null, null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 282
 283         for (int i = startIndex; i < linkedListCount; i++)
 284         {
 285                 r = pList->Add(pNode->pObj);
 286                 SysTryReturn(NID_BASE_COL, r == E_SUCCESS, null, r, "[%s] Propagating.", GetErrorMessage(r));
 287                 pNode = pNode->pNext;
 288         }
 289         SetLastResult(r);
 290         return pList.release();
 291 }
 292
 293 result
 294 LinkedList::IndexOf(const Object& obj, int& index) const
 295 {
 296         return IndexOf(obj, 0, __count, index);
 297 }
 298
 299 result
 300 LinkedList::IndexOf(const Object& obj, int startIndex, int& index) const
 301 {
 302         SysTryReturn(NID_BASE_COL, (startIndex >= 0 && startIndex < __count), E_OUT_OF_RANGE, E_OUT_OF_RANGE, "[%s] The startIndex(%d) MUST be greater than or equal to 0, and less than the number of elements(%d).", GetErrorMessage(E_OUT_OF_RANGE), startIndex, __count);
 303         return IndexOf(obj, startIndex, (__count - startIndex), index);
 304 }
 305
 306 result
 307 LinkedList::IndexOf(const Object& obj, int startIndex, int count, int& index) const
 308 {
 309         SysTryReturnResult(NID_BASE_COL, __count != 0, E_OBJ_NOT_FOUND, "The linkedlist is empty.");
 310         SysTryReturnResult(NID_BASE_COL, startIndex >= 0 && count >= 0, E_OUT_OF_RANGE, "Both of the startIndex(%d) and count(%d) MUST be greater than or equal to 0.", startIndex, count);
 311         SysTryReturnResult(NID_BASE_COL, startIndex < __count, E_OUT_OF_RANGE,
 312                 "The startIndex(%d) MUST be less than the number of elements(%d).", startIndex, __count);
 313         SysTryReturnResult(NID_BASE_COL, count <= __count && (startIndex + count <= __count), E_OUT_OF_RANGE,
 314                 "The startIndex(%d) + count(%d) MUST be less than or equal to the number of elements(%d).", startIndex, count, __count);
 315
 316         result r = E_OBJ_NOT_FOUND;
 317         _ListNode* pNode = GetNode(startIndex);
 318
 319         int linkedListCount = startIndex + count;
 320         for (int i = startIndex; i < linkedListCount; i++)
 321         {
 322                 if (pNode->pObj->Equals(obj))
 323                 {
 324                         index = i;
 325                         r = E_SUCCESS;
 326                         break;
 327                 }
 328                 pNode = pNode->pNext;
 329         }
 330
 331         return r;
 332 }
 333
 334 result
 335 LinkedList::InsertAt(Object* pObj, int index)
 336 {
 337         SysTryReturnResult(NID_BASE_COL, pObj != null, E_INVALID_ARG, "Invalid argument used. The pObj is null");
 338         SysTryReturnResult(NID_BASE_COL, index >= 0 && index <= __count, E_OUT_OF_RANGE, "The index(%d) MUST be greater than or equal to 0, and less than or equal to the number of elements(%d).", index, __count);
 339
 340         result r = E_SUCCESS;
 341         if (index == 0)
 342         {
 343                 r = InsertFirst(pObj);
 344         }
 345         else if (index == __count)
 346         {
 347                 r = InsertLast(pObj);
 348         }
 349         else
 350         {
 351                 _ListNode* pNode = GetNode(index - 1);
 352                 if (pNode != null)
 353                 {
 354                         r = InsertNext(pObj, pNode);
 355                 }
 356         }
 357
 358         if (r != E_SUCCESS)
 359         {
 360                 SysLogException(NID_BASE_COL, r, "[%s] Propagating.", GetErrorMessage(r));
 361         }
 362
 363         __modCount++;
 364
 365         return r;
 366 }
 367
 368 result
 369 LinkedList::InsertItemsFrom(const ICollection& collection, int startIndex)
 370 {
 371         SysTryReturn(NID_BASE_COL, startIndex >= 0 && startIndex <= __count, E_OUT_OF_RANGE, E_OUT_OF_RANGE, "[%s] The startIndex(%d) MUST be greater than or equal to 0, and less than or equal to the number of elements(%d).", GetErrorMessage(E_OUT_OF_RANGE), startIndex, __count);
 372
 373         result r = E_SUCCESS;
 374         int insertingCount = collection.GetCount();
 375
 376         if (insertingCount <= 0)
 377         {
 378                 return E_SUCCESS;
 379         }
 380
 381         int available = __capacity - __count;
 382         if (available < insertingCount)
 383         {
 384                 r = AddBlock(insertingCount - available);
 385                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
 386         }
 387
 388         std::unique_ptr< IEnumerator > pEnum(collection.GetEnumeratorN());
 389         SysTryReturnResult(NID_BASE_COL, pEnum != null, GetLastResult(), "Propagating.");
 390
 391         __modCount++;
 392
 393         while (true)
 394         {
 395                 r = pEnum->MoveNext();
 396                 // enumerator is reached to the end of collection
 397                 if (E_OUT_OF_RANGE == r)
 398                 {
 399                         r = E_SUCCESS;
 400                         break;
 401                 }
 402                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 403
 404                 Object* pObj = pEnum->GetCurrent();
 405                 SysTryReturnResult(NID_BASE_COL, pObj != null, GetLastResult(), "Propagating.");
 406
 407                 r = InsertAt(pObj, startIndex++);
 408                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 409         }
 410
 411         return E_SUCCESS;
 412 }
 413
 414 result
 415 LinkedList::LastIndexOf(const Object& obj, int& index) const
 416 {
 417         _ListNode* pNode = __pListTail;
 418         for (int i = (__count - 1); i >= 0; i--)
 419         {
 420                 if (pNode->pObj->Equals(obj))
 421                 {
 422                         index = i;
 423                         return E_SUCCESS;
 424                 }
 425                 pNode = pNode->pPrev;
 426         }
 427
 428         SysLogException(NID_BASE_COL, E_OBJ_NOT_FOUND, "The object is not in the list.");
 429         return E_OBJ_NOT_FOUND;
 430 }
 431
 432 result
 433 LinkedList::Remove(const Object& obj)
 434 {
 435         _ListNode* pNode = __pListHead;
 436         for (int i = 0; i < __count; i++)
 437         {
 438                 if (pNode->pObj->Equals(obj))
 439                 {
 440                         __modCount++;
 441                         RemoveNode(pNode);
 442                         __count--;
 443                         return E_SUCCESS;
 444                 }
 445                 pNode = pNode->pNext;
 446         }
 447
 448         SysLogException(NID_BASE_COL, E_OBJ_NOT_FOUND, "The object is not in the list.");
 449         return E_OBJ_NOT_FOUND;
 450 }
 451
 452 result
 453 LinkedList::RemoveAt(int index)
 454 {
 455         SysTryReturnResult(NID_BASE_COL, index < __count && index >= 0, E_OUT_OF_RANGE, "The index(%d) MUST be greater than or equal to 0, and less than the number of elements(%d).", index, __count);
 456
 457         __modCount++;
 458         _ListNode* pNode = GetNode(index);
 459         RemoveNode(pNode);
 460         __count--;
 461
 462         return E_SUCCESS;
 463 }
 464
 465 result
 466 LinkedList::RemoveItems(int startIndex, int count)
 467 {
 468         SysTryReturnResult(NID_BASE_COL, startIndex >= 0 && count >= 0, E_OUT_OF_RANGE, "Both of the startIndex(%d) and count(%d) MUST be greater than or equal to 0.", startIndex, count);
 469         SysTryReturnResult(NID_BASE_COL, startIndex < __count, E_OUT_OF_RANGE,
 470                 "The startIndex(%d) MUST be less than the number of elements(%d).", startIndex, __count);
 471         SysTryReturnResult(NID_BASE_COL, count <= __count && (startIndex + count <= __count), E_OUT_OF_RANGE,
 472                 "The startIndex(%d) + count(%d) MUST be less than or equal to the number of elements(%d).", startIndex, count, __count);
 473
 474         __modCount++;
 475         _ListNode* pNode = GetNode(startIndex);
 476
 477         int linkedListCount = startIndex + count;
 478         for (int i = startIndex; i < linkedListCount; i++)
 479         {
 480                 _ListNode* pNextNode = pNode->pNext;
 481                 RemoveNode(pNode);
 482                 pNode = pNextNode;
 483         }
 484         __count -= count;
 485
 486         return E_SUCCESS;
 487 }
 488
 489 result
 490 LinkedList::RemoveItems(const ICollection& collection)
 491 {
 492         result r = E_SUCCESS;
 493         std::unique_ptr< IEnumerator > pEnum(collection.GetEnumeratorN());
 494         SysTryReturnResult(NID_BASE_COL, pEnum != null, GetLastResult(), "Propagating.");
 495
 496         while (true)
 497         {
 498                 r = pEnum->MoveNext();
 499                 // enumerator is reached to the end of collection
 500                 if (E_OUT_OF_RANGE == r)
 501                 {
 502                         r = E_SUCCESS;
 503                         break;
 504                 }
 505                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 506
 507                 Object* pTemp = pEnum->GetCurrent();
 508                 SysTryReturnResult(NID_BASE_COL, pTemp != null, GetLastResult(), "Propagating.");
 509
 510                 r = Remove(*pTemp);
 511                 SysTryLog(NID_BASE_COL, !IsFailed(r), "[%s] Propagating.", GetErrorMessage(r));
 512         }
 513
 514         return r;
 515 }
 516
 517 void
 518 LinkedList::RemoveAll()
 519 {
 520         if (__count > 0)
 521         {
 522                 if (__pListHead == null)
 523                 {
 524                         __count = 0;
 525                         return;
 526                 }
 527
 528                 __modCount++;
 529
 530                 for (_ListNode* pNode = __pListHead; pNode != __pListTail; pNode = pNode->pNext)
 531                 {
 532                         __deleter(pNode->pObj);
 533                         pNode->pObj = null;
 534                 }
 535
 536                 if (__pListTail != null)
 537                 {
 538                         __deleter(__pListTail->pObj);
 539                         __pListTail->pObj = null;
 540                 }
 541
 542                 if (__pAvailableHead == null)
 543                 {
 544                         __pAvailableHead = __pListHead;
 545                         __pAvailableTail = __pListTail;
 546                 }
 547                 else
 548                 {
 549                         __pAvailableTail->pNext = __pListHead;
 550                         __pListHead->pPrev = __pAvailableTail;
 551                         __pAvailableTail = __pListTail;
 552                 }
 553                 __pListHead = null;
 554                 __pListTail = null;
 555                 __count = 0;
 556         }
 557 }
 558
 559 result
 560 LinkedList::SetAt(Object* pObj, int index)
 561 {
 562         SysTryReturnResult(NID_BASE_COL, pObj != null, E_INVALID_ARG, "Invalid argument used. The pObj is null");
 563         SysTryReturnResult(NID_BASE_COL, index >= 0 && index < __count, E_OUT_OF_RANGE, "The index(%d) MUST be greater than or equal to 0, less than the number of elements(%d).", index, __count);
 564
 565         __modCount++;
 566         _ListNode* pNode = GetNode(index);
 567
 568         __deleter(pNode->pObj);
 569
 570         pNode->pObj = pObj;
 571
 572         return E_SUCCESS;
 573 }
 574
 575 result
 576 LinkedList::Sort(const IComparer& comparer)
 577 {
 578         if (__count == 0)
 579         {
 580                 return E_SUCCESS;
 581         }
 582
 583         ArrayList arrayList;
 584         arrayList.Construct(*this);
 585
 586         result r = arrayList.Sort(comparer);
 587         SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 588
 589         std::unique_ptr< IEnumerator > pEnum(arrayList.GetEnumeratorN());
 590         SysTryReturnResult(NID_BASE_COL, pEnum != null, GetLastResult(), "Propagating.");
 591
 592         _ListNode* pNode = GetNode(0);
 593
 594         while (pEnum->MoveNext() == E_SUCCESS)
 595         {
 596                 Object* pItem = pEnum->GetCurrent();
 597                 SysTryReturnResult(NID_BASE_COL, pItem != null, GetLastResult(), "Propagating.");
 598
 599                 pNode->pObj = pItem;
 600                 pNode = pNode->pNext;
 601                 SysTryReturnResult(NID_BASE_COL, pNode != null, GetLastResult(), "Propagating.");
 602         }
 603
 604         return r;
 605 }
 606
 607 int
 608 LinkedList::GetCount(void) const
 609 {
 610         return __count;
 611 }
 612
 613 bool
 614 LinkedList::Contains(const Object& obj) const
 615 {
 616         if (__count == 0)
 617         {
 618                 return false;
 619         }
 620
 621         _ListNode* pNode = GetNode(0);
 622
 623         while (pNode != null)
 624         {
 625                 if (pNode->pObj->Equals(obj))
 626                 {
 627                         return true;
 628                 }
 629                 pNode = pNode->pNext;
 630         }
 631
 632         return false;
 633 }
 634
 635 bool
 636 LinkedList::ContainsAll(const ICollection& collection) const
 637 {
 638         result r = E_SUCCESS;
 639         SetLastResult(r);
 640
 641         if (collection.GetCount() == 0)
 642         {
 643                 return true;
 644         }
 645
 646         std::unique_ptr< IEnumerator > pEnum(collection.GetEnumeratorN());
 647         SysTryReturn(NID_BASE_COL, pEnum != null, false, GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
 648
 649         while ((r = pEnum->MoveNext()) != E_OUT_OF_RANGE)
 650         {
 651                 SysTryReturn(NID_BASE_COL, r == E_SUCCESS, false, r, "[%s] Propagating.", GetErrorMessage(r));
 652
 653                 Object* pTemp = pEnum->GetCurrent();
 654                 SysTryReturn(NID_BASE_COL, pTemp != null, false, GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
 655
 656                 if (!Contains(*pTemp))
 657                 {
 658                         return false;
 659                 }
 660         }
 661
 662         return true;
 663 }
 664
 665 bool
 666 LinkedList::Equals(const Object& obj) const
 667 {
 668         if (&obj == this)
 669         {
 670                 return true;
 671         }
 672
 673         const LinkedList* pOther = dynamic_cast< const LinkedList* >(&obj);
 674         if (pOther == null)
 675         {
 676                 return false;
 677         }
 678         else if (__count != pOther->__count)
 679         {
 680                 return false;
 681         }
 682         else
 683         {
 684                 _ListNode* pNode = __pListHead;
 685                 _ListNode* pOtherNode = pOther->__pListHead;
 686                 for (int i = 0; i < __count; i++)
 687                 {
 688                         if (!(pNode->pObj->Equals(*(pOtherNode->pObj))))
 689                         {
 690                                 return false;
 691                         }
 692
 693                         pNode = pNode->pNext;
 694                         pOtherNode = pOtherNode->pNext;
 695                 }
 696         }
 697
 698         return true;
 699 }
 700
 701 int
 702 LinkedList::GetHashCode(void) const
 703 {
 704         int hash = 0;
 705         _ListNode* pNode = __pListHead;
 706         for (int i = 0; i < __count; i++)
 707         {
 708                 hash += pNode->pObj->GetHashCode();
 709                 pNode = pNode->pNext;
 710         }
 711
 712         return hash;
 713 }
 714
 715 DeleterFunctionType
 716 LinkedList::GetDeleter(void) const
 717 {
 718         return __deleter;
 719 }
 720
 721 result
 722 LinkedList::AddBlock(int blockSize)
 723 {
 724         result r = E_SUCCESS;
 725
 726         _ListNode* pNode = new (std::nothrow) _ListNode[blockSize];
 727         SysTryReturnResult(NID_BASE_COL, pNode != null, E_OUT_OF_MEMORY, "Memory allocation failed.");
 728
 729         // add link
 730         for (int i = 0; i < blockSize - 1; i++)
 731         {
 732                 pNode[i].pNext = &pNode[i + 1];
 733                 pNode[i + 1].pPrev = &pNode[i];
 734         }
 735
 736         // add to __pBlocks
 737         if (__pBlocks == null)
 738         {
 739                 __pBlocks = pNode;
 740         }
 741         else
 742         {
 743                 _ListNode* pBlock = __pBlocks;
 744                 while (pBlock->pNextBlock != null)
 745                 {
 746                         pBlock = pBlock->pNextBlock;
 747                 }
 748                 pBlock->pNextBlock = pNode;
 749         }
 750
 751         // add to available nodes
 752         if (__pAvailableHead == null)
 753         {
 754                 __pAvailableHead = pNode;
 755         }
 756         else
 757         {
 758                 __pAvailableTail->pNext = pNode;
 759                 pNode->pPrev = __pAvailableTail;
 760         }
 761         __pAvailableTail = &pNode[blockSize - 1];
 762
 763         __capacity += blockSize;
 764
 765         return r;
 766 }
 767
 768 void
 769 LinkedList::DeleteBlock(void)
 770 {
 771         while (__pBlocks != null)
 772         {
 773                 _ListNode* pNode = __pBlocks->pNextBlock;
 774                 delete[] __pBlocks;
 775                 __pBlocks = pNode;
 776         }
 777 }
 778
 779 result
 780 LinkedList::InsertFirst(Object* pObj)
 781 {
 782         if (__count == __capacity)
 783         {
 784                 result r = AddBlock();
 785                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 786         }
 787
 788         _ListNode* pNode = GetNewNode();
 789
 790         pNode->pObj = pObj;
 791
 792         if (__pListHead == null)
 793         {
 794                 __pListHead = pNode;
 795                 __pListTail = pNode;
 796         }
 797         else
 798         {
 799                 pNode->pNext = __pListHead;
 800                 __pListHead->pPrev = pNode;
 801                 __pListHead = pNode;
 802         }
 803         __count++;
 804
 805         return E_SUCCESS;
 806 }
 807
 808 result
 809 LinkedList::InsertLast(Object* pObj)
 810 {
 811         if (__count == __capacity)
 812         {
 813                 result r = AddBlock();
 814                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 815         }
 816
 817         _ListNode* pNode = GetNewNode();
 818
 819         pNode->pObj = pObj;
 820         if (__pListHead == null)
 821         {
 822                 __pListHead = pNode;
 823                 __pListTail = pNode;
 824         }
 825         else
 826         {
 827                 pNode->pPrev = __pListTail;
 828                 __pListTail->pNext = pNode;
 829                 __pListTail = pNode;
 830         }
 831
 832         __count++;
 833
 834         return E_SUCCESS;
 835 }
 836
 837 result
 838 LinkedList::InsertNext(Object* pObj, _ListNode* pPrevNode)
 839 {
 840         SysTryReturnResult(NID_BASE_COL, pPrevNode != null, E_INVALID_ARG, "pPrevNode is null.");
 841
 842         if (__count == __capacity)
 843         {
 844                 result r = AddBlock();
 845                 SysTryReturnResult(NID_BASE_COL, r == E_SUCCESS, r, "Propagating.");
 846         }
 847
 848         _ListNode* pNode = GetNewNode();
 849
 850         pNode->pObj = pObj;
 851         pNode->pPrev = pPrevNode;
 852         pNode->pNext = pPrevNode->pNext;
 853
 854         pPrevNode->pNext->pPrev = pNode;
 855         pPrevNode->pNext = pNode;
 856
 857         __count++;
 858
 859         return E_SUCCESS;
 860 }
 861
 862 _ListNode*
 863 LinkedList::GetNewNode(void)
 864 {
 865         SysTryReturn(NID_BASE_COL, __pAvailableHead != null, null, E_INVALID_STATE, "[%s] There is no available node.", GetErrorMessage(E_INVALID_STATE));
 866
 867         _ListNode* pNode = __pAvailableHead;
 868
 869         if (__pAvailableHead == __pAvailableTail)
 870         {
 871                 __pAvailableHead = null;
 872                 __pAvailableTail = null;
 873         }
 874         else
 875         {
 876                 __pAvailableHead = __pAvailableHead->pNext;
 877                 __pAvailableHead->pPrev = null;
 878         }
 879
 880         pNode->pNext = null;
 881         pNode->pPrev = null;
 882
 883         return pNode;
 884 }
 885
 886 _ListNode*
 887 LinkedList::GetNode(int index) const
 888 {
 889         _ListNode* pNode = null;
 890         if (index > static_cast< int >(__count / 2))
 891         {
 892                 pNode = __pListTail;
 893                 for (int i = __count - 1; i > index; i--)
 894                 {
 895                         pNode = pNode->pPrev;
 896                 }
 897         }
 898         else
 899         {
 900                 pNode = __pListHead;
 901                 for (int i = 0; i < index; i++)
 902                 {
 903                         pNode = pNode->pNext;
 904                 }
 905         }
 906
 907         return pNode;
 908 }
 909
 910 void
 911 LinkedList::RemoveNode(_ListNode* pNode)
 912 {
 913         // remove links
 914         if (pNode == __pListHead)
 915         {
 916                 __pListHead = pNode->pNext;
 917                 if (__pListHead != null)
 918                 {
 919                         __pListHead->pPrev = null;
 920                 }
 921                 else
 922                 {
 923                         __pListTail = null;
 924                 }
 925         }
 926         else if (pNode == __pListTail)
 927         {
 928                 __pListTail = pNode->pPrev;
 929                 __pListTail->pNext = null;
 930         }
 931         else
 932         {
 933                 pNode->pNext->pPrev = pNode->pPrev;
 934                 pNode->pPrev->pNext = pNode->pNext;
 935         }
 936
 937         pNode->pNext = null;
 938         pNode->pPrev = null;
 939
 940         __deleter(pNode->pObj);
 941         pNode->pObj = null;
 942
 943         // add to available list
 944         if (__pAvailableHead == null)
 945         {
 946                 __pAvailableHead = pNode;
 947                 __pAvailableTail = pNode;
 948         }
 949         else
 950         {
 951                 __pAvailableTail->pNext = pNode;
 952                 pNode->pPrev = __pAvailableTail;
 953                 __pAvailableTail = pNode;
 954         }
 955 }
 956
 957 void
 958 LinkedList::SetDeleter(DeleterFunctionType deleter)
 959 {
 960         __deleter = deleter;
 961 }
 962
 963 } } }  // Tizen::Base::Collection