skiplist.hh

Motion JPEG编解码器源代码

#ifndef __SKIPLIST_H__
#define __SKIPLIST_H__

// This file (C) 2004 Steven Boswell.  All rights reserved.
// Released to the public under the GNU General Public License.
// See the file COPYING for more information.

/* A skip list is a sorted data structure with probabilistic balancing
   that performs the same functions as balanced-binary-tree sorts of
   data structures, but skip lists have lots of unusual avenues for
   optimizations not available to binary trees. */

#include "config.h"
#include <assert.h>
#include <stdlib.h>
#include <new>
#include "mjpeg_types.h"
#include "Status_t.h"
#include "Allocator.hh"



// Define this to compile in code to double-check and debug the skip
// list.
#ifndef NDEBUG
//	#define DEBUG_SKIPLIST
#endif // NDEBUG



template <class KEY, class VALUE, class KEYFN, class PRED>
class SkipList
{
private:
	// The type of a node in the skip list.
	struct Node
	{
		VALUE m_oValue;
			// The data held by this node.
#ifdef DEBUG_SKIPLIST
		int32_t m_nLevel;
			// The number of forward pointers in this node.
#endif // DEBUG_SKIPLIST
		Node *m_pBackward;
			// The node before this one.
		Node *m_apForward[1];
			// The nodes after this one, at all the levels we exist.
	};
	
	SkipList (const SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther);
	const SkipList<KEY,VALUE,KEYFN,PRED> &operator =
			(const SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther);
		// Disallow copying and assignment.
	
	enum { HEADERCHUNK = 10 };
		// The number of forward pointers in the header.
		// Will give good sorting for up to e^10 items.
	
public:
	typedef Allocator<Node,HEADERCHUNK> Allocator;
		// The type of node allocator to use.

	static Allocator sm_oNodeAllocator;
		// The default node allocator.

	SkipList (const PRED &a_rPred = PRED(),
			Allocator &a_rAlloc = sm_oNodeAllocator);
		// Default constructor.  Must be followed by Init().

	SkipList (Status_t &a_reStatus, bool a_bAllowDuplicates,
			uint32_t a_nRandSeed, const PRED &a_rPred = PRED(),
			Allocator &a_rAlloc = sm_oNodeAllocator);
		// Constructor.  Specify whether or not duplicates are allowed,
		// and provide a random number seed.

	void Init (Status_t &a_reStatus, bool a_bAllowDuplicates,
			uint32_t a_nRandSeed);
		// Construction method.  Specify whether or not duplicates are
		// allowed, and provide a random number seed.

	virtual ~SkipList (void);
		// Destructor.

#ifdef DEBUG_SKIPLIST

	void Invariant (void) const;
		// Thoroughly analyze the skip list for structural integrity.

	void SetDebug (bool a_bDebug);
		// Set whether to run the skip-list invariant before and after
		// methods.

#endif // DEBUG_SKIPLIST

	//
	// Iterator classes.
	//
	
	class Iterator;
	class ConstIterator;
	friend class ConstIterator;
	class ConstIterator
	{
		protected:
			friend class SkipList<KEY,VALUE,KEYFN,PRED>;
				// Let SkipList access m_pNode.
			Node *m_pNode;
				// The node we represent.
		public:
			ConstIterator() { m_pNode = NULL; }
			ConstIterator (Node *a_pNode) : m_pNode (a_pNode) {}
			ConstIterator (const Iterator &a_rOther)
				: m_pNode (a_rOther.m_pNode) {}
			const VALUE &operator*() const {return m_pNode->m_oValue; }
			ConstIterator& operator++()
				{ m_pNode = m_pNode->m_apForward[0];
					return *this; }
			ConstIterator operator++(int) { ConstIterator oTmp = *this;
				++*this; return oTmp; }
			ConstIterator& operator--()
				{ m_pNode = m_pNode->m_pBackward;
					return *this; }
			ConstIterator operator--(int) { ConstIterator oTmp = *this;
				--*this; return oTmp; }
			bool operator== (const ConstIterator &a_rOther) const
				{ return (m_pNode == a_rOther.m_pNode) ? true : false; }
			bool operator!= (const ConstIterator &a_rOther) const
				{ return (m_pNode != a_rOther.m_pNode) ? true : false; }
	};
	friend class Iterator;
	class Iterator : public ConstIterator
	{
		public:
			Iterator() : ConstIterator() {}
			Iterator (Node *a_pNode) : ConstIterator (a_pNode) {}
			VALUE &operator*() {return ConstIterator::m_pNode->m_oValue; }
			Iterator& operator++() { ConstIterator::m_pNode = ConstIterator::m_pNode->m_apForward[0];
				return *this; }
			Iterator operator++(int) { Iterator oTmp = *this; ++*this;
				return oTmp; }
			Iterator& operator--() { ConstIterator::m_pNode = ConstIterator::m_pNode->m_pBackward;
				return *this; }
			Iterator operator--(int) { Iterator oTmp = *this; --*this;
				return oTmp; }
			bool operator== (const Iterator &a_rOther) const
				{ return (ConstIterator::m_pNode == a_rOther.m_pNode) ? true : false; }
			bool operator!= (const Iterator &a_rOther) const
				{ return (ConstIterator::m_pNode != a_rOther.m_pNode) ? true : false; }
	};
	
	//
	// Skip list methods.
	//
	
	Iterator Begin (void)
			{ return Iterator (m_pHeader->m_apForward[0]); }
		// Return an iterator to the beginning of the list.
	
	ConstIterator Begin (void) const
			{ return ConstIterator (m_pHeader->m_apForward[0]); }
		// Return an iterator to the beginning of the list.
	
	Iterator End (void) { return Iterator (m_pHeader); }
		// Return an iterator to the end of the list.
	
	ConstIterator End (void) const { return ConstIterator (m_pHeader); }
		// Return an iterator to the end of the list.
	
	uint32_t Size (void) const { return m_nItems; }
		// Return the number of items in the list.
		// (May be called on a default-constructed object, making it
		// possible for default-constructed subclasses/owners to destroy
		// themselves safely.)
	
	bool Empty (void) const { return (m_nItems == 0) ? true : false; }
		// Return whether the list is empty.
	
	// A structure used to return the result of an insertion.
	struct InsertResult
	{
		Iterator m_itPosition;
			// Where the item was inserted, or where the duplicate was
			// found.

		bool m_bInserted;
			// true if the item was inserted into the list.
	};
	
	InsertResult Insert (Status_t &a_reStatus, const VALUE &a_rValue);
		// Insert an item into the list.
	
	Iterator Insert (Status_t &a_reStatus, Iterator a_oPosition,
			const VALUE &a_rValue);
		// Insert an item into the list, at this exact location, if it's
		// safe.  Returns where it was really inserted.
	
	void Insert (Status_t &a_reStatus, ConstIterator a_oFirst,
			ConstIterator a_oLast);
		// Insert a range of items from another skip-list.
	
	Iterator Erase (Iterator a_oHere);
		// Erase the item here.  Return the item following the one
		// removed.
	
	Iterator Erase (Iterator a_oFirst, Iterator a_oLast);
		// Erase a range of items in this list.  Return the item
		// following the last one removed.
	
	void Clear (void);
		// Empty the list.
	
	InsertResult Move (SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther,
			Iterator a_oHere);
		// Remove an item from another skip list and insert it into
		// ourselves.
		// Just like an Erase() followed by an Insert(), except that
		// there's no possibility of the operation failing.
	
	void Move (SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther,
			Iterator a_oFirst, Iterator a_oLast);
		// Remove a range of items from another skip-list and insert
		// them into ourselves.
		// Just like an Erase() followed by an Insert(), except that
		// there's no possibility of the operation failing.
	
	void Move (SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther);
		// Move all items from the other skip-list to ourself.
		// The current skip-list must be empty.
	
	bool CanMove (const SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther) const;
		// Returns true if the two skip lists can move items between
		// each other.

	void Assign (Status_t &a_reStatus,
			const SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther);
		// Assign the contents of the other skip list to ourselves.
	
	Iterator Find (const KEY &a_rKey);
		// Find the given item in the list.  Returns End() if not found.
	
	ConstIterator Find (const KEY &a_rKey) const;
		// Find the given item in the list.  Returns End() if not found.
	
	Iterator LowerBound (const KEY &a_rKey);
		// Return the position of the first item that's >= the key.
	
	ConstIterator LowerBound (const KEY &a_rKey) const;
		// Return the position of the first item that's >= the key.
	
	Iterator UpperBound (const KEY &a_rKey);
		// Return the position of the first item that's > the key.
	
	ConstIterator UpperBound (const KEY &a_rKey) const;
		// Return the position of the first item that's > the key.

private:
	
	Allocator &m_rNodeAllocator;
		// Where we get memory to allocate nodes.

	bool m_bAllowDuplicates;
		// true if we allow duplicate elements.
	
	int16_t m_nHeaderLevel;
		// How many valid pointers m_pHeader[] is holding.
	
	Node *m_pHeader;
		// The beginning of the list.
	
	Node *m_pSearchFinger, *m_pSearchFinger2;
		// Used to speed up searches, by caching the results of
		// previous searches.
	
	uint32_t m_nItems;
		// The number of items in this list.

	uint32_t m_nRandSeed;
		// The random-number seed.

	KEYFN m_oKeyFn;
		// How we extract a key from a value.

	PRED m_oPred;
		// How we compare keys to each other.
	
	void SearchLower (const KEY &a_rKey, Node *a_pTraverse) const;
		// Search for an item greater than or equal to a_rKey.
	
	bool SearchExact (Node *a_pKey, Node *a_pTraverse) const;
		// Search for this exact item.  Returns true if it's found.
	
	void SearchUpper (const KEY &a_rKey, Node *a_pTraverse) const;
		// Search for an item greater than a_rKey.

	void SearchEnd (Node *a_pTraverse) const;
		// Point to the end of the list.
	
	void InsertNode (Node *a_pNewNode, int16_t a_nNewLevel,
			Node *a_pTraverse);
		// Insert a new node into the skip list.  Assume a_pTraverse is
		// set up.

	Node *RemoveNode (Node *a_pToRemove, Node *a_pTraverse,
			int16_t *a_rpLevel = NULL);
		// Remove the given node from the skip list.  Assume a_pTraverse
		// is set up.
		// Returns the node that got removed, and optionally backpatches
		// its level.

	Node *GetNewNode (int16_t a_nForwardPointers);
		// Allocate a new node with the given number of forward
		// pointers.  Returns NULL if something goes wrong.

	Node *GetNewNodeOfRandomLevel (int16_t &a_rnLevel);
		// Allocate a new node with a random number of forward pointers.
		// Returns NULL if something goes wrong; otherwise, a_rnLevel
		// gets backpatched with the number of levels.

	void DeleteNode (int16_t a_nForwardPointers, Node *a_pToDelete);
		// Delete a node.

	void DeallocateNode (int16_t a_nForwardPointers, Node *a_pToDelete);
		// Deallocate a node's storage.

	int16_t Rand (void);
		// Get another random number.

#ifdef DEBUG_SKIPLIST

	bool m_bDebug;
		// true if the invariant should be checked.

#endif // DEBUG_SKIPLIST
};



// The default node allocator.  Allocates 64K at a time.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Allocator
	SkipList<KEY,VALUE,KEYFN,PRED>::sm_oNodeAllocator (65536);



// Default constructor.  Must be followed by Init().
template <class KEY, class VALUE, class KEYFN, class PRED>
SkipList<KEY,VALUE,KEYFN,PRED>::SkipList (const PRED &a_rPred,
		Allocator &a_rAlloc)
	: m_rNodeAllocator (a_rAlloc), m_oPred (a_rPred)
{
	// Set up some defaults.
	m_bAllowDuplicates = false;
	m_nHeaderLevel = 0;
	m_pHeader = NULL;
	m_pSearchFinger = NULL;
	m_pSearchFinger2 = NULL;
	m_nItems = 0;
	m_nRandSeed = 0;
#ifdef DEBUG_SKIPLIST
	m_bDebug = false;
	
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
}



// Constructor.  Specify whether or not duplicates are allowed, and
// provide a random number seed.
template <class KEY, class VALUE, class KEYFN, class PRED>
SkipList<KEY,VALUE,KEYFN,PRED>::SkipList (Status_t &a_reStatus,
		bool a_bAllowDuplicates, uint32_t a_nRandSeed,
		const PRED &a_rPred, Allocator &a_rAlloc)
	: m_rNodeAllocator (a_rAlloc), m_oPred (a_rPred)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);
	
	// Set up some defaults.
	m_bAllowDuplicates = false;
	m_nHeaderLevel = 0;
	m_pHeader = NULL;
	m_pSearchFinger = NULL;
	m_pSearchFinger2 = NULL;
	m_nItems = 0;
	m_nRandSeed = 0;
#ifdef DEBUG_SKIPLIST
	m_bDebug = false;
#endif // DEBUG_SKIPLIST
	
	// Init() does all the work.
	Init (a_reStatus, a_bAllowDuplicates, a_nRandSeed);
}



// Construction method.  Specify whether or not duplicates are allowed,
// and provide a random number seed.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Init (Status_t &a_reStatus,
	bool a_bAllowDuplicates, uint32_t a_nRandSeed)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);
	
	// Make sure we haven't been initialized already.
	assert (m_pHeader == NULL);
	
	// Fill in the blanks.
	m_bAllowDuplicates = a_bAllowDuplicates;
	m_nHeaderLevel = 0;
	m_nItems = 0;
	m_nRandSeed = a_nRandSeed;
	
	// Allocate our necessary nodes.
	m_pHeader = GetNewNode (HEADERCHUNK);
	m_pSearchFinger = GetNewNode (HEADERCHUNK);
	m_pSearchFinger2 = GetNewNode (HEADERCHUNK);
	if (m_pHeader == NULL || m_pSearchFinger == NULL
		|| m_pSearchFinger2 == NULL)
	{
		delete m_pHeader;
		m_pHeader = NULL;
		delete m_pSearchFinger;
		m_pSearchFinger = NULL;
		delete m_pSearchFinger2;
		m_pSearchFinger2 = NULL;
		a_reStatus = g_kOutOfMemory;
		return;
	}
	
	// Set up our nodes.
	//
	// The way we work, incrementing End() gets you Begin(), and
	// decrementing Begin() gets you End().  We implement that by using
	// our header node as a NULL-like sentinel node.
	m_pHeader->m_pBackward = m_pHeader;
	m_pSearchFinger->m_pBackward = m_pHeader;
	m_pSearchFinger2->m_pBackward = m_pHeader;
	for (int16_t nI = 0; nI < HEADERCHUNK; nI++)
	{
		m_pHeader->m_apForward[nI] = m_pHeader;
		m_pSearchFinger->m_apForward[nI] = m_pHeader;
		m_pSearchFinger2->m_apForward[nI] = m_pHeader;
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
}



// Destructor.