summaryrefslogtreecommitdiffstats
path: root/lib/libUPnP/Neptune/Source/Core/NptList.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libUPnP/Neptune/Source/Core/NptList.h')
-rw-r--r--lib/libUPnP/Neptune/Source/Core/NptList.h704
1 files changed, 704 insertions, 0 deletions
diff --git a/lib/libUPnP/Neptune/Source/Core/NptList.h b/lib/libUPnP/Neptune/Source/Core/NptList.h
new file mode 100644
index 0000000..37d1802
--- /dev/null
+++ b/lib/libUPnP/Neptune/Source/Core/NptList.h
@@ -0,0 +1,704 @@
+/*****************************************************************
+|
+| Neptune - Lists
+|
+| Copyright (c) 2002-2008, Axiomatic Systems, LLC.
+| All rights reserved.
+|
+| Redistribution and use in source and binary forms, with or without
+| modification, are permitted provided that the following conditions are met:
+| * Redistributions of source code must retain the above copyright
+| notice, this list of conditions and the following disclaimer.
+| * Redistributions in binary form must reproduce the above copyright
+| notice, this list of conditions and the following disclaimer in the
+| documentation and/or other materials provided with the distribution.
+| * Neither the name of Axiomatic Systems nor the
+| names of its contributors may be used to endorse or promote products
+| derived from this software without specific prior written permission.
+|
+| THIS SOFTWARE IS PROVIDED BY AXIOMATIC SYSTEMS ''AS IS'' AND ANY
+| EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+| WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+| DISCLAIMED. IN NO EVENT SHALL AXIOMATIC SYSTEMS BE LIABLE FOR ANY
+| DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+| (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+| LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+| ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+| (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+| SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+|
+ ****************************************************************/
+
+#ifndef _NPT_LIST_H_
+#define _NPT_LIST_H_
+
+/*----------------------------------------------------------------------
+| includes
++---------------------------------------------------------------------*/
+#include "NptResults.h"
+#include "NptTypes.h"
+#include "NptConstants.h"
+#include "NptCommon.h"
+
+/*----------------------------------------------------------------------
+| constants
++---------------------------------------------------------------------*/
+const int NPT_ERROR_LIST_EMPTY = NPT_ERROR_BASE_LIST - 0;
+const int NPT_ERROR_LIST_OPERATION_ABORTED = NPT_ERROR_BASE_LIST - 1;
+const int NPT_ERROR_LIST_OPERATION_CONTINUE = NPT_ERROR_BASE_LIST - 2;
+
+/*----------------------------------------------------------------------
+| NPT_List
++---------------------------------------------------------------------*/
+template <typename T>
+class NPT_List
+{
+protected:
+ class Item;
+
+public:
+ // types
+ typedef T Element;
+
+ class Iterator {
+ public:
+ Iterator() : m_Item(NULL) {}
+ explicit Iterator(Item* item) : m_Item(item) {}
+ Iterator(const Iterator& copy) : m_Item(copy.m_Item) {}
+ T& operator*() const { return m_Item->m_Data; }
+ T* operator->() const { return &m_Item->m_Data;}
+ Iterator& operator++() { // prefix
+ m_Item = m_Item->m_Next;
+ return (*this);
+ }
+ Iterator operator++(int) { // postfix
+ Iterator saved_this = *this;
+ m_Item = m_Item->m_Next;
+ return saved_this;
+ }
+ Iterator& operator--() { // prefix
+ m_Item = m_Item->m_Prev;
+ return (*this);
+ }
+ Iterator operator--(int) { // postfix
+ Iterator saved_this = *this;
+ m_Item = m_Item->m_Prev;
+ return saved_this;
+ }
+ operator bool() const {
+ return m_Item != NULL;
+ }
+ bool operator==(const Iterator& other) const {
+ return m_Item == other.m_Item;
+ }
+ bool operator!=(const Iterator& other) const {
+ return m_Item != other.m_Item;
+ }
+ void operator=(const Iterator& other) {
+ m_Item = other.m_Item;
+ }
+ void operator=(Item* item) {
+ m_Item = item;
+ }
+
+ private:
+ Item* m_Item;
+
+ // friends
+ friend class NPT_List<T>;
+ };
+
+ // methods
+ NPT_List<T>();
+ NPT_List<T>(const NPT_List<T>& list);
+ ~NPT_List<T>();
+ NPT_Result Add(const T& data);
+ NPT_Result Insert(const Iterator where, const T& data);
+ NPT_Result Remove(const T& data, bool all=false);
+ NPT_Result Erase(const Iterator position);
+ NPT_Result PopHead(T& data);
+ bool Contains(const T& data) const;
+ NPT_Result Clear();
+ NPT_Result Get(NPT_Ordinal index, T& data) const;
+ NPT_Result Get(NPT_Ordinal index, T*& data) const;
+ NPT_Cardinal GetItemCount() const { return m_ItemCount; }
+ Iterator GetFirstItem() const { return Iterator(m_Head); }
+ Iterator GetLastItem() const { return Iterator(m_Tail); }
+ Iterator GetItem(NPT_Ordinal index) const;
+
+ // list manipulation
+ NPT_Result Add(NPT_List<T>& list);
+ NPT_Result Remove(const NPT_List<T>& list, bool all=false);
+ NPT_Result Cut(NPT_Cardinal keep, NPT_List<T>& cut);
+
+ // item manipulation
+ NPT_Result Add(Item& item);
+ NPT_Result Detach(Item& item);
+ NPT_Result Insert(const Iterator where, Item& item);
+
+ // list operations
+ // keep these template members defined here because MSV6 does not let
+ // us define them later
+ template <typename X>
+ NPT_Result Apply(const X& function) const
+ {
+ Item* item = m_Head;
+ while (item) {
+ function(item->m_Data);
+ item = item->m_Next;
+ }
+
+ return NPT_SUCCESS;
+ }
+
+ template <typename X, typename P>
+ NPT_Result ApplyUntil(const X& function, const P& predicate, bool* match = NULL) const
+ {
+ Item* item = m_Head;
+ while (item) {
+ NPT_Result return_value;
+ if (predicate(function(item->m_Data), return_value)) {
+ if (match) *match = true;
+ return return_value;
+ }
+ item = item->m_Next;
+ }
+
+ if (match) *match = false;
+ return NPT_SUCCESS;
+ }
+
+ template <typename P>
+ Iterator Find(const P& predicate, NPT_Ordinal n=0) const
+ {
+ Item* item = m_Head;
+ while (item) {
+ if (predicate(item->m_Data)) {
+ if (n == 0) {
+ return Iterator(item);
+ }
+ --n;
+ }
+ item = item->m_Next;
+ }
+
+ return Iterator(NULL);
+ }
+
+ // Merge sort algorithm
+ // http://en.wikipedia.org/wiki/Mergesort
+ template <typename X>
+ NPT_Result Sort(const X& function)
+ {
+ if (GetItemCount() <= 1) return NPT_SUCCESS;
+
+ NPT_List<T> right;
+ NPT_CHECK(Cut(GetItemCount() >> 1, right));
+
+ // sort the left side
+ Sort(function);
+
+ // sort the right side
+ right.Sort(function);
+
+ // merge the two back inline
+ if (function(m_Tail->m_Data, right.m_Head->m_Data) > 0) {
+ Merge(right, function);
+ } else {
+ // append right
+ right.m_Head->m_Prev = m_Tail;
+ m_Tail->m_Next = right.m_Head;
+ m_Tail = right.m_Tail;
+ m_ItemCount += right.m_ItemCount;
+
+ right.m_ItemCount = 0;
+ right.m_Head = right.m_Tail = NULL;
+ }
+
+ return NPT_SUCCESS;
+ }
+
+ template <typename X>
+ NPT_Result Merge(NPT_List<T>& other, const X& function)
+ {
+ Iterator left = GetFirstItem();
+ Iterator right;
+ while (left && other.m_Head) {
+ if (function(*left, other.m_Head->m_Data) <= 0) {
+ ++left;
+ } else {
+ // remove head and insert it
+ Item* head = other.m_Head;
+ other.Detach(*head);
+ Insert(left, *head);
+ }
+ }
+
+ // add what's left of other if any
+ if (other.m_Head) {
+ other.m_Head->m_Prev = m_Tail;
+ if (m_Tail) m_Tail->m_Next = other.m_Head;
+ m_Tail = other.m_Tail;
+ if (!m_Head) m_Head = other.m_Head;
+ other.m_Head = other.m_Tail = NULL;
+ }
+ m_ItemCount += other.m_ItemCount;
+ other.m_ItemCount = 0;
+ return NPT_SUCCESS;
+ }
+
+ // operators
+ void operator=(const NPT_List<T>& other);
+ bool operator==(const NPT_List<T>& other) const;
+ bool operator!=(const NPT_List<T>& other) const;
+
+protected:
+ // types
+ class Item
+ {
+ public:
+ // methods
+ Item(const T& data) : m_Next(0), m_Prev(0), m_Data(data) {}
+
+ // members
+ Item* m_Next;
+ Item* m_Prev;
+ T m_Data;
+
+ // friends
+ //friend class NPT_List<T>;
+ //friend class NPT_List<T>::Iterator;
+ };
+
+ // members
+ NPT_Cardinal m_ItemCount;
+ Item* m_Head;
+ Item* m_Tail;
+};
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::NPT_List
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_List<T>::NPT_List() : m_ItemCount(0), m_Head(0), m_Tail(0)
+{
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::NPT_List
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_List<T>::NPT_List(const NPT_List<T>& list) : m_ItemCount(0), m_Head(0), m_Tail(0)
+{
+ *this = list;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::~NPT_List<T>
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_List<T>::~NPT_List()
+{
+ Clear();
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::operator=
++---------------------------------------------------------------------*/
+template <typename T>
+void
+NPT_List<T>::operator=(const NPT_List<T>& list)
+{
+ // cleanup
+ Clear();
+
+ // copy the new list
+ Item* item = list.m_Head;
+ while (item) {
+ Add(item->m_Data);
+ item = item->m_Next;
+ }
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::operator==
++---------------------------------------------------------------------*/
+template <typename T>
+bool
+NPT_List<T>::operator==(const NPT_List<T>& other) const
+{
+ // quick test
+ if (m_ItemCount != other.m_ItemCount) return false;
+
+ // compare all elements one by one
+ Item* our_item = m_Head;
+ Item* their_item = other.m_Head;
+ while (our_item && their_item) {
+ if (our_item->m_Data != their_item->m_Data) return false;
+ our_item = our_item->m_Next;
+ their_item = their_item->m_Next;
+ }
+
+ return our_item == NULL && their_item == NULL;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::operator!=
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+bool
+NPT_List<T>::operator!=(const NPT_List<T>& other) const
+{
+ return !(*this == other);
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Clear
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Clear()
+{
+ // delete all items
+ Item* item = m_Head;
+ while (item) {
+ Item* next = item->m_Next;
+ delete item;
+ item = next;
+ }
+
+ m_ItemCount = 0;
+ m_Head = NULL;
+ m_Tail = NULL;
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Add
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Add(Item& item)
+{
+ // add element at the tail
+ if (m_Tail) {
+ item.m_Prev = m_Tail;
+ item.m_Next = NULL;
+ m_Tail->m_Next = &item;
+ m_Tail = &item;
+ } else {
+ m_Head = &item;
+ m_Tail = &item;
+ item.m_Next = NULL;
+ item.m_Prev = NULL;
+ }
+
+ // one more item in the list now
+ ++m_ItemCount;
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Add
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Add(NPT_List<T>& list)
+{
+ // copy the new list
+ Item* item = list.m_Head;
+ while (item) {
+ Add(item->m_Data);
+ item = item->m_Next;
+ }
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Add
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_Result
+NPT_List<T>::Add(const T& data)
+{
+ return Add(*new Item(data));
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::GetItem
++---------------------------------------------------------------------*/
+template <typename T>
+typename NPT_List<T>::Iterator
+NPT_List<T>::GetItem(NPT_Ordinal n) const
+{
+ Iterator result;
+ if (n >= m_ItemCount) return result;
+
+ result = m_Head;
+ for (unsigned int i=0; i<n; i++) {
+ ++result;
+ }
+
+ return result;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Insert
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_Result
+NPT_List<T>::Insert(Iterator where, const T&data)
+{
+ return Insert(where, *new Item(data));
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Insert
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Insert(Iterator where, Item& item)
+{
+ // insert the item in the list
+ Item* position = where.m_Item;
+ if (position) {
+ // insert at position
+ item.m_Next = position;
+ item.m_Prev = position->m_Prev;
+ position->m_Prev = &item;
+ if (item.m_Prev) {
+ item.m_Prev->m_Next = &item;
+ } else {
+ // this is the new head
+ m_Head = &item;
+ }
+
+ // one more item in the list now
+ ++m_ItemCount;
+ } else {
+ // insert at tail
+ return Add(item);
+ }
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Erase
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Erase(Iterator position)
+{
+ if (!position) return NPT_ERROR_NO_SUCH_ITEM;
+ Detach(*position.m_Item);
+ delete position.m_Item;
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Remove
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Remove(const T& data, bool all)
+{
+ Item* item = m_Head;
+ NPT_Cardinal matches = 0;
+
+ while (item) {
+ Item* next = item->m_Next;
+ if (item->m_Data == data) {
+ // we found a match
+ ++matches;
+
+ // detach item
+ Detach(*item);
+
+ // destroy the item
+ delete item;
+
+ if (!all) return NPT_SUCCESS;
+ }
+ item = next;
+ }
+
+ return matches?NPT_SUCCESS:NPT_ERROR_NO_SUCH_ITEM;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Remove
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Remove(const NPT_List<T>& list, bool all)
+{
+ Item* item = list.m_Head;
+ while (item) {
+ Remove(item->m_Data, all);
+ item = item->m_Next;
+ }
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Detach
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Detach(Item& item)
+{
+ // remove item
+ if (item.m_Prev) {
+ // item is not the head
+ if (item.m_Next) {
+ // item is not the tail
+ item.m_Next->m_Prev = item.m_Prev;
+ item.m_Prev->m_Next = item.m_Next;
+ } else {
+ // item is the tail
+ m_Tail = item.m_Prev;
+ m_Tail->m_Next = NULL;
+ }
+ } else {
+ // item is the head
+ m_Head = item.m_Next;
+ if (m_Head) {
+ // item is not the tail
+ m_Head->m_Prev = NULL;
+ } else {
+ // item is also the tail
+ m_Tail = NULL;
+ }
+ }
+
+ // one less item in the list now
+ --m_ItemCount;
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Get
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Get(NPT_Ordinal index, T& data) const
+{
+ T* data_pointer;
+ NPT_CHECK(Get(index, data_pointer));
+ data = *data_pointer;
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Get
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Get(NPT_Ordinal index, T*& data) const
+{
+ Item* item = m_Head;
+
+ if (index < m_ItemCount) {
+ while (index--) item = item->m_Next;
+ data = &item->m_Data;
+ return NPT_SUCCESS;
+ } else {
+ data = NULL;
+ return NPT_ERROR_NO_SUCH_ITEM;
+ }
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::PopHead
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::PopHead(T& data)
+{
+ // check that we have an element
+ if (m_Head == NULL) return NPT_ERROR_LIST_EMPTY;
+
+ // copy the head item's data
+ data = m_Head->m_Data;
+
+ // discard the head item
+ Item* head = m_Head;
+ m_Head = m_Head->m_Next;
+ if (m_Head) {
+ m_Head->m_Prev = NULL;
+ } else {
+ m_Tail = NULL;
+ }
+ delete head;
+
+ // update the count
+ --m_ItemCount;
+
+ return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Contains
++---------------------------------------------------------------------*/
+template <typename T>
+bool
+NPT_List<T>::Contains(const T& data) const
+{
+ Item* item = m_Head;
+ while (item) {
+ if (item->m_Data == data) return true;
+ item = item->m_Next;
+ }
+
+ return false;
+}
+
+/*----------------------------------------------------------------------
+| NPT_List<T>::Cut
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Cut(NPT_Cardinal keep, NPT_List<T>& cut)
+{
+ cut.Clear();
+
+ // shortcut
+ if (keep >= GetItemCount()) return NPT_SUCCESS;
+
+ // update new counts first
+ cut.m_ItemCount = m_ItemCount-keep;
+ m_ItemCount = keep;
+
+ // look for the cut-point item
+ Item* item = m_Head;
+ while (keep--) { item = item->m_Next;}
+
+ // the cut list goes from the cut-point item to the tail
+ cut.m_Head = item;
+ cut.m_Tail = m_Tail;
+
+ // update the portion of the list we keep
+ if (item == m_Head) m_Head = NULL;
+ m_Tail = item->m_Prev;
+
+ // update the cut list
+ if (item->m_Prev) item->m_Prev->m_Next = NULL;
+ item->m_Prev = NULL;
+
+ return NPT_SUCCESS;
+}
+
+#endif // _NPT_LIST_H_
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-02 17:46:49 +0000