lib/libUPnP/Neptune/Source/Core/NptList.h

   1 /*****************************************************************
   2 |
   3 |   Neptune - Lists
   4 |
   5 | Copyright (c) 2002-2008, Axiomatic Systems, LLC.
   6 | All rights reserved.
   7 |
   8 | Redistribution and use in source and binary forms, with or without
   9 | modification, are permitted provided that the following conditions are met:
  10 |     * Redistributions of source code must retain the above copyright
  11 |       notice, this list of conditions and the following disclaimer.
  12 |     * Redistributions in binary form must reproduce the above copyright
  13 |       notice, this list of conditions and the following disclaimer in the
  14 |       documentation and/or other materials provided with the distribution.
  15 |     * Neither the name of Axiomatic Systems nor the
  16 |       names of its contributors may be used to endorse or promote products
  17 |       derived from this software without specific prior written permission.
  18 |
  19 | THIS SOFTWARE IS PROVIDED BY AXIOMATIC SYSTEMS ''AS IS'' AND ANY
  20 | EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  21 | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22 | DISCLAIMED. IN NO EVENT SHALL AXIOMATIC SYSTEMS BE LIABLE FOR ANY
  23 | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  24 | (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  25 | LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  26 | ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  28 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 |
  30  ****************************************************************/
  31
  32 #ifndef _NPT_LIST_H_
  33 #define _NPT_LIST_H_
  34
  35 /*----------------------------------------------------------------------
  36 |   includes
  37 +---------------------------------------------------------------------*/
  38 #include "NptResults.h"
  39 #include "NptTypes.h"
  40 #include "NptConstants.h"
  41 #include "NptCommon.h"
  42
  43 /*----------------------------------------------------------------------
  44 |   constants
  45 +---------------------------------------------------------------------*/
  46 const int NPT_ERROR_LIST_EMPTY              = NPT_ERROR_BASE_LIST - 0;
  47 const int NPT_ERROR_LIST_OPERATION_ABORTED  = NPT_ERROR_BASE_LIST - 1;
  48 const int NPT_ERROR_LIST_OPERATION_CONTINUE = NPT_ERROR_BASE_LIST - 2;
  49
  50 /*----------------------------------------------------------------------
  51 |   NPT_List
  52 +---------------------------------------------------------------------*/
  53 template <typename T>
  54 class NPT_List
  55 {
  56 protected:
  57     class Item;
  58
  59 public:
  60     // types
  61     typedef T Element;
  62
  63     class Iterator {
  64     public:
  65         Iterator() : m_Item(NULL) {}
  66         explicit Iterator(Item* item) : m_Item(item) {}
  67         Iterator(const Iterator& copy) : m_Item(copy.m_Item) {}
  68         T&  operator*()  const { return m_Item->m_Data; }
  69         T*  operator->() const { return &m_Item->m_Data;}
  70         Iterator& operator++()  { // prefix
  71             m_Item = m_Item->m_Next;
  72             return (*this);
  73         }
  74         Iterator operator++(int) { // postfix
  75             Iterator saved_this = *this;
  76             m_Item = m_Item->m_Next;
  77             return saved_this;
  78         }
  79         Iterator& operator--() { // prefix
  80             m_Item = m_Item->m_Prev;
  81             return (*this);
  82         }
  83         Iterator operator--(int) { // postfix
  84             Iterator saved_this = *this;
  85             m_Item = m_Item->m_Prev;
  86             return saved_this;
  87         }
  88         operator bool() const {
  89             return m_Item != NULL;
  90         }
  91         bool operator==(const Iterator& other) const {
  92             return m_Item == other.m_Item;
  93         }
  94         bool operator!=(const Iterator& other) const {
  95             return m_Item != other.m_Item;
  96         }
  97         void operator=(const Iterator& other) {
  98             m_Item = other.m_Item;
  99         }
 100         void operator=(Item* item) {
 101             m_Item = item;
 102         }
 103
 104     private:
 105         Item* m_Item;
 106
 107         // friends
 108         friend class NPT_List<T>;
 109     };
 110
 111     // methods
 112     NPT_List();
 113     NPT_List(const NPT_List<T>& list);
 114     ~NPT_List();
 115     NPT_Result   Add(const T& data);
 116     NPT_Result   Insert(const Iterator where, const T& data);
 117     NPT_Result   Remove(const T& data, bool all=false);
 118     NPT_Result   Erase(const Iterator position);
 119     NPT_Result   PopHead(T& data);
 120     bool         Contains(const T& data) const;
 121     NPT_Result   Clear();
 122     NPT_Result   Get(NPT_Ordinal index, T& data) const;
 123     NPT_Result   Get(NPT_Ordinal index, T*& data) const;
 124     NPT_Cardinal GetItemCount() const { return m_ItemCount; }
 125     Iterator     GetFirstItem() const { return Iterator(m_Head); }
 126     Iterator     GetLastItem() const  { return Iterator(m_Tail); }
 127     Iterator     GetItem(NPT_Ordinal index) const;
 128
 129     // list manipulation
 130     NPT_Result   Add(NPT_List<T>& list);
 131     NPT_Result   Remove(const NPT_List<T>& list, bool all=false);
 132     NPT_Result   Cut(NPT_Cardinal keep, NPT_List<T>& cut);
 133
 134     // item manipulation
 135     NPT_Result   Add(Item& item);
 136     NPT_Result   Detach(Item& item);
 137     NPT_Result   Insert(const Iterator where, Item& item);
 138
 139     // list operations
 140     // keep these template members defined here because MSV6 does not let
 141     // us define them later
 142     template <typename X>
 143     NPT_Result Apply(const X& function) const
 144     {
 145         Item* item = m_Head;
 146         while (item) {
 147             function(item->m_Data);
 148             item = item->m_Next;
 149         }
 150
 151         return NPT_SUCCESS;
 152     }
 153
 154     template <typename X, typename P>
 155     NPT_Result ApplyUntil(const X& function, const P& predicate, bool* match = NULL) const
 156     {
 157         Item* item = m_Head;
 158         while (item) {
 159             NPT_Result return_value;
 160             if (predicate(function(item->m_Data), return_value)) {
 161                 if (match) *match = true;
 162                 return return_value;
 163             }
 164             item = item->m_Next;
 165         }
 166
 167         if (match) *match = false;
 168         return NPT_SUCCESS;
 169     }
 170
 171     template <typename P>
 172     Iterator Find(const P& predicate, NPT_Ordinal n=0) const
 173     {
 174         Item* item = m_Head;
 175         while (item) {
 176             if (predicate(item->m_Data)) {
 177                 if (n == 0) {
 178                     return Iterator(item);
 179                 }
 180                 --n;
 181             }
 182             item = item->m_Next;
 183         }
 184
 185         return Iterator(NULL);
 186     }
 187
 188     // Merge sort algorithm
 189     // http://en.wikipedia.org/wiki/Mergesort
 190     template <typename X>
 191     NPT_Result Sort(const X& function)
 192     {
 193         if (GetItemCount() <= 1) return NPT_SUCCESS;
 194
 195         NPT_List<T> right;
 196         NPT_CHECK(Cut(GetItemCount() >> 1, right));
 197
 198         // sort the left side
 199         Sort(function);
 200
 201         // sort the right side
 202         right.Sort(function);
 203
 204         // merge the two back inline
 205         if (function(m_Tail->m_Data, right.m_Head->m_Data) > 0) {
 206             Merge(right, function);
 207         } else {
 208             // append right
 209             right.m_Head->m_Prev = m_Tail;
 210             m_Tail->m_Next = right.m_Head;
 211             m_Tail = right.m_Tail;
 212             m_ItemCount += right.m_ItemCount;
 213
 214             right.m_ItemCount = 0;
 215             right.m_Head = right.m_Tail = NULL;
 216         }
 217
 218         return NPT_SUCCESS;
 219     }
 220
 221     template <typename X>
 222     NPT_Result Merge(NPT_List<T>& other, const X& function)
 223     {
 224         Iterator left = GetFirstItem();
 225         Iterator right;
 226         while (left && other.m_Head) {
 227             if (function(*left, other.m_Head->m_Data) <= 0) {
 228                 ++left;
 229             } else {
 230                 // remove head and insert it
 231                 Item* head = other.m_Head;
 232                 other.Detach(*head);
 233                 Insert(left, *head);
 234             }
 235         }
 236
 237         // add what's left of other if any
 238         if (other.m_Head) {
 239             other.m_Head->m_Prev = m_Tail;
 240             if (m_Tail) m_Tail->m_Next = other.m_Head;
 241             m_Tail = other.m_Tail;
 242             if (!m_Head) m_Head = other.m_Head;
 243             other.m_Head = other.m_Tail = NULL;
 244         }
 245         m_ItemCount += other.m_ItemCount;
 246         other.m_ItemCount = 0;
 247         return NPT_SUCCESS;
 248     }
 249
 250     // operators
 251     void operator=(const NPT_List<T>& other);
 252     bool operator==(const NPT_List<T>& other) const;
 253     bool operator!=(const NPT_List<T>& other) const;
 254
 255 protected:
 256     // types
 257     class Item
 258     {
 259     public:
 260         // methods
 261         Item(const T& data) : m_Next(0), m_Prev(0), m_Data(data) {}
 262
 263         // members
 264         Item* m_Next;
 265         Item* m_Prev;
 266         T     m_Data;
 267
 268         // friends
 269         //friend class NPT_List<T>;
 270         //friend class NPT_List<T>::Iterator;
 271     };
 272
 273     // members
 274     NPT_Cardinal m_ItemCount;
 275     Item*        m_Head;
 276     Item*        m_Tail;
 277 };
 278
 279 /*----------------------------------------------------------------------
 280 |   NPT_List<T>::NPT_List
 281 +---------------------------------------------------------------------*/
 282 template <typename T>
 283 inline
 284 NPT_List<T>::NPT_List() : m_ItemCount(0), m_Head(0), m_Tail(0)
 285 {
 286 }
 287
 288 /*----------------------------------------------------------------------
 289 |   NPT_List<T>::NPT_List
 290 +---------------------------------------------------------------------*/
 291 template <typename T>
 292 inline
 293 NPT_List<T>::NPT_List(const NPT_List<T>& list) : m_ItemCount(0), m_Head(0), m_Tail(0)
 294 {
 295     *this = list;
 296 }
 297
 298 /*----------------------------------------------------------------------
 299 |   NPT_List<T>::~NPT_List<T>
 300 +---------------------------------------------------------------------*/
 301 template <typename T>
 302 inline
 303 NPT_List<T>::~NPT_List()
 304 {
 305     Clear();
 306 }
 307
 308 /*----------------------------------------------------------------------
 309 |   NPT_List<T>::operator=
 310 +---------------------------------------------------------------------*/
 311 template <typename T>
 312 void
 313 NPT_List<T>::operator=(const NPT_List<T>& list)
 314 {
 315     // cleanup
 316     Clear();
 317
 318     // copy the new list
 319     Item* item = list.m_Head;
 320     while (item) {
 321         Add(item->m_Data);
 322         item = item->m_Next;
 323     }
 324 }
 325
 326 /*----------------------------------------------------------------------
 327 |   NPT_List<T>::operator==
 328 +---------------------------------------------------------------------*/
 329 template <typename T>
 330 bool
 331 NPT_List<T>::operator==(const NPT_List<T>& other) const
 332 {
 333     // quick test
 334     if (m_ItemCount != other.m_ItemCount) return false;
 335
 336     // compare all elements one by one
 337     Item* our_item = m_Head;
 338     Item* their_item = other.m_Head;
 339     while (our_item && their_item) {
 340         if (our_item->m_Data != their_item->m_Data) return false;
 341         our_item   = our_item->m_Next;
 342         their_item = their_item->m_Next;
 343     }
 344
 345     return our_item == NULL && their_item == NULL;
 346 }
 347
 348 /*----------------------------------------------------------------------
 349 |   NPT_List<T>::operator!=
 350 +---------------------------------------------------------------------*/
 351 template <typename T>
 352 inline
 353 bool
 354 NPT_List<T>::operator!=(const NPT_List<T>& other) const
 355 {
 356     return !(*this == other);
 357 }
 358
 359 /*----------------------------------------------------------------------
 360 |   NPT_List<T>::Clear
 361 +---------------------------------------------------------------------*/
 362 template <typename T>
 363 NPT_Result
 364 NPT_List<T>::Clear()
 365 {
 366     // delete all items
 367     Item* item = m_Head;
 368     while (item) {
 369         Item* next = item->m_Next;
 370         delete item;
 371         item = next;
 372     }
 373
 374     m_ItemCount = 0;
 375     m_Head      = NULL;
 376     m_Tail      = NULL;
 377
 378     return NPT_SUCCESS;
 379 }
 380
 381 /*----------------------------------------------------------------------
 382 |   NPT_List<T>::Add
 383 +---------------------------------------------------------------------*/
 384 template <typename T>
 385 NPT_Result
 386 NPT_List<T>::Add(Item& item)
 387 {
 388     // add element at the tail
 389     if (m_Tail) {
 390         item.m_Prev = m_Tail;
 391         item.m_Next = NULL;
 392         m_Tail->m_Next = &item;
 393         m_Tail = &item;
 394     } else {
 395         m_Head = &item;
 396         m_Tail = &item;
 397         item.m_Next = NULL;
 398         item.m_Prev = NULL;
 399     }
 400
 401     // one more item in the list now
 402     ++m_ItemCount;
 403
 404     return NPT_SUCCESS;
 405 }
 406
 407 /*----------------------------------------------------------------------
 408 |   NPT_List<T>::Add
 409 +---------------------------------------------------------------------*/
 410 template <typename T>
 411 NPT_Result
 412 NPT_List<T>::Add(NPT_List<T>& list)
 413 {
 414     // copy the new list
 415     Item* item = list.m_Head;
 416     while (item) {
 417         Add(item->m_Data);
 418         item = item->m_Next;
 419     }
 420
 421     return NPT_SUCCESS;
 422 }
 423
 424 /*----------------------------------------------------------------------
 425 |   NPT_List<T>::Add
 426 +---------------------------------------------------------------------*/
 427 template <typename T>
 428 inline
 429 NPT_Result
 430 NPT_List<T>::Add(const T& data)
 431 {
 432     return Add(*new Item(data));
 433 }
 434
 435 /*----------------------------------------------------------------------
 436 |   NPT_List<T>::GetItem
 437 +---------------------------------------------------------------------*/
 438 template <typename T>
 439 typename NPT_List<T>::Iterator
 440 NPT_List<T>::GetItem(NPT_Ordinal n) const
 441 {
 442     Iterator result;
 443     if (n >= m_ItemCount) return result;
 444
 445     result = m_Head;
 446     for (unsigned int i=0; i<n; i++) {
 447         ++result;
 448     }
 449
 450     return result;
 451 }
 452
 453 /*----------------------------------------------------------------------
 454 |   NPT_List<T>::Insert
 455 +---------------------------------------------------------------------*/
 456 template <typename T>
 457 inline
 458 NPT_Result
 459 NPT_List<T>::Insert(Iterator where, const T&data)
 460 {
 461     return Insert(where, *new Item(data));
 462 }
 463
 464 /*----------------------------------------------------------------------
 465 |   NPT_List<T>::Insert
 466 +---------------------------------------------------------------------*/
 467 template <typename T>
 468 NPT_Result
 469 NPT_List<T>::Insert(Iterator where, Item& item)
 470 {
 471     // insert the item in the list
 472     Item* position = where.m_Item;
 473     if (position) {
 474         // insert at position
 475         item.m_Next = position;
 476         item.m_Prev = position->m_Prev;
 477         position->m_Prev = &item;
 478         if (item.m_Prev) {
 479             item.m_Prev->m_Next = &item;
 480         } else {
 481             // this is the new head
 482             m_Head = &item;
 483         }
 484
 485         // one more item in the list now
 486         ++m_ItemCount;
 487     } else {
 488         // insert at tail
 489         return Add(item);
 490     }
 491
 492     return NPT_SUCCESS;
 493 }
 494
 495 /*----------------------------------------------------------------------
 496 |   NPT_List<T>::Erase
 497 +---------------------------------------------------------------------*/
 498 template <typename T>
 499 NPT_Result
 500 NPT_List<T>::Erase(Iterator position)
 501 {
 502     if (!position) return NPT_ERROR_NO_SUCH_ITEM;
 503     Detach(*position.m_Item);
 504     delete position.m_Item;
 505
 506     return NPT_SUCCESS;
 507 }
 508
 509 /*----------------------------------------------------------------------
 510 |   NPT_List<T>::Remove
 511 +---------------------------------------------------------------------*/
 512 template <typename T>
 513 NPT_Result
 514 NPT_List<T>::Remove(const T& data, bool all)
 515 {
 516     Item* item = m_Head;
 517     NPT_Cardinal matches = 0;
 518
 519     while (item) {
 520         Item* next = item->m_Next;
 521         if (item->m_Data == data) {
 522             // we found a match
 523             ++matches;
 524
 525             // detach item
 526             Detach(*item);
 527
 528             // destroy the item
 529             delete item;
 530
 531             if (!all) return NPT_SUCCESS;
 532         }
 533         item = next;
 534     }
 535
 536     return matches?NPT_SUCCESS:NPT_ERROR_NO_SUCH_ITEM;
 537 }
 538
 539 /*----------------------------------------------------------------------
 540 |   NPT_List<T>::Remove
 541 +---------------------------------------------------------------------*/
 542 template <typename T>
 543 NPT_Result
 544 NPT_List<T>::Remove(const NPT_List<T>& list, bool all)
 545 {
 546     Item* item = list.m_Head;
 547     while (item) {
 548         Remove(item->m_Data, all);
 549         item = item->m_Next;
 550     }
 551
 552     return NPT_SUCCESS;
 553 }
 554
 555 /*----------------------------------------------------------------------
 556 |   NPT_List<T>::Detach
 557 +---------------------------------------------------------------------*/
 558 template <typename T>
 559 NPT_Result
 560 NPT_List<T>::Detach(Item& item)
 561 {
 562     // remove item
 563     if (item.m_Prev) {
 564         // item is not the head
 565         if (item.m_Next) {
 566             // item is not the tail
 567             item.m_Next->m_Prev = item.m_Prev;
 568             item.m_Prev->m_Next = item.m_Next;
 569         } else {
 570             // item is the tail
 571             m_Tail = item.m_Prev;
 572             m_Tail->m_Next = NULL;
 573         }
 574     } else {
 575         // item is the head
 576         m_Head = item.m_Next;
 577         if (m_Head) {
 578             // item is not the tail
 579             m_Head->m_Prev = NULL;
 580         } else {
 581             // item is also the tail
 582             m_Tail = NULL;
 583         }
 584     }
 585
 586     // one less item in the list now
 587     --m_ItemCount;
 588
 589     return NPT_SUCCESS;
 590 }
 591
 592 /*----------------------------------------------------------------------
 593 |   NPT_List<T>::Get
 594 +---------------------------------------------------------------------*/
 595 template <typename T>
 596 NPT_Result
 597 NPT_List<T>::Get(NPT_Ordinal index, T& data) const
 598 {
 599     T* data_pointer;
 600     NPT_CHECK(Get(index, data_pointer));
 601     data = *data_pointer;
 602     return NPT_SUCCESS;
 603 }
 604
 605 /*----------------------------------------------------------------------
 606 |   NPT_List<T>::Get
 607 +---------------------------------------------------------------------*/
 608 template <typename T>
 609 NPT_Result
 610 NPT_List<T>::Get(NPT_Ordinal index, T*& data) const
 611 {
 612     Item* item = m_Head;
 613
 614     if (index < m_ItemCount) {
 615         while (index--) item = item->m_Next;
 616         data = &item->m_Data;
 617         return NPT_SUCCESS;
 618     } else {
 619         data = NULL;
 620         return NPT_ERROR_NO_SUCH_ITEM;
 621     }
 622 }
 623
 624 /*----------------------------------------------------------------------
 625 |   NPT_List<T>::PopHead
 626 +---------------------------------------------------------------------*/
 627 template <typename T>
 628 NPT_Result
 629 NPT_List<T>::PopHead(T& data)
 630 {
 631     // check that we have an element
 632     if (m_Head == NULL) return NPT_ERROR_LIST_EMPTY;
 633
 634     // copy the head item's data
 635     data = m_Head->m_Data;
 636
 637     // discard the head item
 638     Item* head = m_Head;
 639     m_Head = m_Head->m_Next;
 640     if (m_Head) {
 641         m_Head->m_Prev = NULL;
 642     } else {
 643         m_Tail = NULL;
 644     }
 645     delete head;
 646
 647     // update the count
 648     --m_ItemCount;
 649
 650     return NPT_SUCCESS;
 651 }
 652
 653 /*----------------------------------------------------------------------
 654 |   NPT_List<T>::Contains
 655 +---------------------------------------------------------------------*/
 656 template <typename T>
 657 bool
 658 NPT_List<T>::Contains(const T& data) const
 659 {
 660     Item* item = m_Head;
 661     while (item) {
 662         if (item->m_Data == data) return true;
 663         item = item->m_Next;
 664     }
 665
 666     return false;
 667 }
 668
 669 /*----------------------------------------------------------------------
 670 |   NPT_List<T>::Cut
 671 +---------------------------------------------------------------------*/
 672 template <typename T>
 673 NPT_Result
 674 NPT_List<T>::Cut(NPT_Cardinal keep, NPT_List<T>& cut)
 675 {
 676     cut.Clear();
 677
 678     // shortcut
 679     if (keep >= GetItemCount()) return NPT_SUCCESS;
 680
 681     // update new counts first
 682     cut.m_ItemCount = m_ItemCount-keep;
 683     m_ItemCount = keep;
 684
 685     // look for the cut-point item
 686     Item* item = m_Head;
 687     while (keep--) { item = item->m_Next;}
 688
 689     // the cut list goes from the cut-point item to the tail
 690     cut.m_Head = item;
 691     cut.m_Tail = m_Tail;
 692
 693     // update the portion of the list we keep
 694     if (item == m_Head) m_Head = NULL;
 695     m_Tail = item->m_Prev;
 696
 697     // update the cut list
 698     if (item->m_Prev) item->m_Prev->m_Next = NULL;
 699     item->m_Prev = NULL;
 700
 701     return NPT_SUCCESS;
 702 }
 703
 704 #endif // _NPT_LIST_H_