1 files changed, 79 insertions, 2 deletions

diff --git a/CommonLibs/LinkedLists.h b/CommonLibs/LinkedLists.h
index 2cb83ee..31fb9c5 100644
--- a/CommonLibs/LinkedLists.h
+++ b/CommonLibs/LinkedLists.h
@@ -1,6 +1,8 @@
 /*
 * Copyright 2008 Free Software Foundation, Inc.
 *
+* This software is distributed under multiple licenses; see the COPYING file in the main directory for licensing information for this specific distribuion.
+*
 * This software is distributed under the terms of the GNU Affero Public License.
 * See the COPYING file in the main directory for details.
 *
@@ -28,6 +30,7 @@
 #define LINKEDLISTS_H
 
 #include <stdlib.h>
+#include <assert.h>
 
 
 
@@ -54,7 +57,7 @@ class ListNode {
 /** A fast FIFO for pointer-based storage. */
 class PointerFIFO {
 
-	private:
+	protected:
 
 	ListNode* mHead;		///< points to next item out
 	ListNode* mTail;		///< points to last item in
@@ -69,9 +72,12 @@ class PointerFIFO {
 	{}
 
 	unsigned size() const { return mSize; }
+	unsigned totalSize() const { return 0; }	// Not used in this version.
 
-	/** Put an item into the FIFO. */
+	/** Put an item into the FIFO at the back of the queue. */
 	void put(void* val);
+	/** Push an item on the front of the FIFO. */
+	void push_front(void*val);			// pat added.
 
 	/**
 		Take an item from the FIFO.
@@ -79,6 +85,9 @@ class PointerFIFO {
 	*/
 	void* get();
 
+	/** Peek at front item without removal. */
+	void *front() { return mHead ? mHead->data() : 0; }	// pat added
+
 
 	private:
 
@@ -90,6 +99,74 @@ class PointerFIFO {
 
 };
 
+// This is the default type for SingleLinkList Node element;
+// You can derive your class directly from this, but then you must add type casts
+// all over the place.
+class SingleLinkListNode
+{	public:
+	SingleLinkListNode *mNext;
+	SingleLinkListNode *next() {return mNext;}
+	void setNext(SingleLinkListNode *item) {mNext=item;}
+	SingleLinkListNode() : mNext(0) {}
+	virtual unsigned size() { return 0; }
+};
+
+// A single-linked lists of elements with internal pointers.
+// The methods must match those from SingleLinkListNode.
+// This class also assumes the Node has a size() method, and accumulates
+// the total size of elements in the list in totalSize().
+template<class Node=SingleLinkListNode>
+class SingleLinkList
+{
+	Node *mHead, *mTail;
+	unsigned mSize;			// Number of elements in list.
+	unsigned mTotalSize;	// Total of size() method of elements in list.
+
+	public:
+	SingleLinkList() : mHead(0), mTail(0), mSize(0), mTotalSize(0) {}
+	unsigned size() const { return mSize; }
+	unsigned totalSize() const { return mTotalSize; }
+
+	Node *pop_back() { assert(0); } // Not efficient with this type of list.
+
+	Node *pop_front()
+	{
+		if (!mHead) return NULL;
+		Node *result = mHead;
+		mHead = mHead->next();
+		if (mTail == result) { mTail = NULL; assert(mHead == NULL); }
+		result->setNext(NULL);	// be neat
+		mSize--;
+		mTotalSize -= result->size();
+		return result;
+	}
+
+	void push_front(Node *item)
+	{
+		item->setNext(mHead);
+		mHead = item;
+		if (!mTail) { mTail = item; }
+		mSize++;
+		mTotalSize += item->size();
+	}
+
+	void push_back(Node *item)
+	{
+		item->setNext(NULL);
+		if (mTail) { mTail->setNext(item); }
+		mTail = item;
+		if (!mHead) mHead = item;
+		mSize++;
+		mTotalSize += item->size();
+	}
+	Node *front() { return mHead; }
+	Node *back() { return mTail; }
+
+	// Interface to InterthreadQueue so it can used SingleLinkList as the Fifo.
+	void put(void *val) { push_back((Node*)val); }
+	void *get() { return pop_front(); }
+};
+