skiplist.hh

Motion JPEG编解码器源代码

template <class KEY, class VALUE, class KEYFN, class PRED>
SkipList<KEY,VALUE,KEYFN,PRED>::~SkipList (void)
{
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// If we have anything to delete, delete it.
	if (m_pHeader != NULL)
	{
		// Delete everything in the list.
		Erase (Begin(), End());

		// Free up our extra nodes.
		DeallocateNode (HEADERCHUNK, m_pSearchFinger2);
		DeallocateNode (HEADERCHUNK, m_pSearchFinger);
		DeallocateNode (HEADERCHUNK, m_pHeader);
	}
}



#ifdef DEBUG_SKIPLIST

// Set whether to run the skip-list invariant before and after methods.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::SetDebug (bool a_bDebug)
{
	// Easy enough.
	m_bDebug = a_bDebug;
}

#endif // DEBUG_SKIPLIST



// Insert an item into the list.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::InsertResult
SkipList<KEY,VALUE,KEYFN,PRED>::Insert (Status_t &a_reStatus,
	const VALUE &a_rValue)
{
	Node *pNewNode;
		// The new node being inserted.
	int16_t nNewLevel;
		// The level of the new node.
	InsertResult oInsertResult;
		// The result of the insertion.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Find where to put this key.  (Put equal keys at the upper bound.)
	SearchUpper (m_oKeyFn (a_rValue), m_pSearchFinger);
	
	// Insert this node if there's no duplicate already in here.
	if (m_bAllowDuplicates
	|| (pNewNode = m_pSearchFinger->m_apForward[0],
		pNewNode == m_pHeader
		|| m_oPred (m_oKeyFn (pNewNode->m_oValue),
			m_oKeyFn (a_rValue))))
	{
		// Generate a node of random level.
		pNewNode = GetNewNodeOfRandomLevel (nNewLevel);
		if (pNewNode == NULL)
		{
			// We couldn't allocate space.
			a_reStatus = g_kOutOfMemory;
			oInsertResult.m_itPosition = End();
			oInsertResult.m_bInserted = false;
			return oInsertResult;
		}

		// Install the value.
		new ((void *)(&(pNewNode->m_oValue))) VALUE (a_rValue);

		// Put it into the skip list here.
		InsertNode (pNewNode, nNewLevel, m_pSearchFinger);

		// Let them know where we put it, and that we did insert it.
		oInsertResult.m_itPosition = Iterator (pNewNode);
		oInsertResult.m_bInserted = true;
	}
	else
	{
		// We didn't insert it.  Show them the equal item.
		oInsertResult.m_itPosition = Iterator (pNewNode);
		oInsertResult.m_bInserted = false;
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Let them know what happened.
	return oInsertResult;
}



// Insert an item into the list, at this exact location, if it's safe.
// Returns where it was really inserted.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Iterator
SkipList<KEY,VALUE,KEYFN,PRED>::Insert (Status_t &a_reStatus,
	Iterator a_oPosition, const VALUE &a_rValue)
{
	const KEY &rKey = m_oKeyFn (a_rValue);
		// The key of what they're inserting.
	Node *pNewNode;
		// The node we're inserting.
	int16_t nNewLevel;
		// The level it's at.
	Iterator oHere;
		// Where it gets inserted.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// According to STL semantics, the insertion point must immediately
	// follow a_oPosition.  To fit more naturally with skip-list
	// semantics, the insertion point needs to precede a_oPosition.
	if (a_oPosition != End())
		++a_oPosition;
	
	// The new item has to fit where this iterator points, and we must
	// be able to find this iterator's node in the list.
	Iterator oBefore = a_oPosition; --oBefore;
	if ((a_oPosition.m_pNode != m_pHeader
		&& m_oPred (m_oKeyFn (a_oPosition.m_pNode->m_oValue), rKey))
	|| (oBefore.m_pNode != m_pHeader
		&& m_oPred (rKey, m_oKeyFn (oBefore.m_pNode->m_oValue)))
	|| !SearchExact (a_oPosition.m_pNode, m_pSearchFinger))
	{
		// Don't use their iterator.
		oHere = Insert (a_reStatus, a_rValue).m_itPosition;
	}
	
	// Insert this node if we always insert, or if there's no duplicate
	// already.
	else if (m_bAllowDuplicates
	|| (pNewNode = m_pSearchFinger->m_apForward[0]->m_apForward[0],
		pNewNode == m_pHeader
		|| m_oPred (rKey, m_oKeyFn (pNewNode->m_oValue))))
	{
		// Generate a node of random level.
		pNewNode = GetNewNodeOfRandomLevel (nNewLevel);
		if (pNewNode == NULL)
		{
			// We couldn't allocate space.
			a_reStatus = g_kOutOfMemory;
			oHere = End();
		}
		else
		{
			// Install the value.
			new ((void *)(&(pNewNode->m_oValue))) VALUE (a_rValue);
	
			// Put it into the skip list here.
			InsertNode (pNewNode, nNewLevel, m_pSearchFinger);
	
			// Let them know where we put it.
			oHere = Iterator (pNewNode);
		}
	}
	
	// We didn't insert it.  Show them the equal item.
	else
		oHere = Iterator (pNewNode);
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Let our caller know what happened.
	return oHere;
}



// Insert a range of items from another skip-list.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Insert (Status_t &a_reStatus,
	ConstIterator a_oFirst, ConstIterator a_oLast)
{
	ConstIterator oHere;
		// The next item to insert.
	
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Try to insert every item they gave us.
	for (oHere = a_oFirst; oHere != a_oLast; oHere++)
	{
		Insert (a_reStatus, *oHere);
		if (a_reStatus != g_kNoError)
		{
			// BUG: this is messy.  If we can't insert the entire range,
			// we shouldn't insert any of it.  Fix this by preallocating
			// all necessary nodes.
			return;
		}
	}
}



// Erase the item here.  Return the item following the one removed.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Iterator
SkipList<KEY,VALUE,KEYFN,PRED>::Erase (Iterator a_oHere)
{
	Node *pToRemove;
	int16_t nLevel;
		// The node being deleted, and its level.

	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Don't let them erase End().
	if (a_oHere.m_pNode == m_pHeader)
		return Begin();
	
	// If this iterator does not point to a current node, leave.
	// (This check also sets up the search finger for RemoveNode().)
	if (!SearchExact (a_oHere.m_pNode, m_pSearchFinger))
		return Begin();
	
	// Erase it.
	pToRemove = RemoveNode (m_pSearchFinger->m_apForward[0]
		->m_apForward[0], m_pSearchFinger, &nLevel);
	DeleteNode (nLevel, pToRemove);
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Return an iterator that points past the deleted node.
	return Iterator (m_pSearchFinger->m_apForward[0]->m_apForward[0]);
}



// Erase a range of items in this list.  Return the item following the
// last one removed.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Iterator
SkipList<KEY,VALUE,KEYFN,PRED>::Erase (Iterator a_oFirst,
	Iterator a_oLast)
{
	int16_t nI;
		// Used to loop through things.
	Node *pNode, *pToRemove;
		// Nodes we're examining and deleting.
	int16_t nLevel;
		// The level of each removed node.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Make sure these iterators are in the right order.
	assert (a_oFirst == Begin()
		|| a_oLast == End()
		|| !m_oPred (m_oKeyFn (a_oLast.m_pNode->m_oValue),
			m_oKeyFn (a_oFirst.m_pNode->m_oValue)));
	
	// A skip-list's range-delete doesn't involve a rebalancing for
	// every node deleted, like a tree structure's range-delete would.
	// Here, we just generate search fingers for each end of the
	// range, and fix the forward/backward pointers in one shot.
	// We still have to loop through the deleted range in order to
	// delete the nodes, but that's nowhere near the cost of a
	// rebalance per node.  Spiffy, huh?
	
	// First, search for the beginning of the range to delete.
	// Abort if we can't find it.
	if (!SearchExact (a_oFirst.m_pNode, m_pSearchFinger))
		return End();
	
	// Use that as a base for the second search.
	for (nI = 0; nI < m_nHeaderLevel; nI++)
		m_pSearchFinger2->m_apForward[nI]
			= m_pSearchFinger->m_apForward[nI];
	
	// Now search for the end of the range to delete.
	// Abort if we can't find it.
	if (!SearchExact (a_oLast.m_pNode, m_pSearchFinger2))
		return End();
	
	// Loop through the removed nodes, destroy the values inside,
	// and deallocate the nodes.
	pNode = a_oFirst.m_pNode;
	while (pNode != a_oLast.m_pNode)
	{
		// Get the node to destroy.
		pToRemove = pNode;
		pNode = pNode->m_apForward[0];

		// Destroy it.
		pToRemove = RemoveNode (pToRemove, m_pSearchFinger, &nLevel);
		DeleteNode (nLevel, pToRemove);
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Return the end of the removed range.
	return a_oLast;
}



// Empty the list.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Clear (void)
{
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);

	// Easy enough.
	Erase (Begin(), End());
}



// 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.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::InsertResult
SkipList<KEY,VALUE,KEYFN,PRED>::Move
	(SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther, Iterator a_oHere)
{
	Node *pNode;
		// The node we're moving.
	int16_t nLevel;
		// The level of the node we're moving.
	InsertResult oInsertResult;
		// The result of the insertion.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);

	// Make sure the skip-lists can move items between themselves.
	assert (CanMove (a_rOther));
	
	// Don't let them move End().
	assert (a_oHere.m_pNode != a_rOther.m_pHeader);
	
	// Get a reference to the key of the value being moved.
	const KEY &rKey = m_oKeyFn (a_oHere.m_pNode->m_oValue);
	
	// Find where to put this key.  (Put equal keys at the upper bound.)
	SearchUpper (rKey, m_pSearchFinger);
	
	// Move this node if there's no duplicate already in here.
	if (m_bAllowDuplicates
	|| (pNode = m_pSearchFinger->m_apForward[0],
		pNode == m_pHeader
			|| m_oPred (m_oKeyFn (pNode->m_oValue), rKey)))
	{
		bool bFound;
		// true if this node was found in the other skip list.
		
#ifdef DEBUG_SKIPLIST
		// Make sure the other list is intact.
		a_rOther.Invariant();
#endif // DEBUG_SKIPLIST
		
		// Find this node in the other skip list.
		bFound = a_rOther.SearchExact (a_oHere.m_pNode,
			a_rOther.m_pSearchFinger);
		
		// Make sure this iterator points to a current node.
		assert (bFound);
		
#ifdef DEBUG_SKIPLIST
		// Make sure the other list is intact.
		a_rOther.Invariant();
#endif // DEBUG_SKIPLIST
		
		// Remove it from that skip list.
		pNode = a_rOther.RemoveNode (a_oHere.m_pNode,
			a_rOther.m_pSearchFinger, &nLevel);
		
#ifdef DEBUG_SKIPLIST
		// Make sure the other list is intact.
		a_rOther.Invariant();
#endif // DEBUG_SKIPLIST
		
		// If the node we're about to add is a higher level than any
		// node we've seen so far, keep track of the new maximum.
		if (m_nHeaderLevel < nLevel)
			m_nHeaderLevel = nLevel;
		
		// Put it into the skip list here.
		InsertNode (pNode, nLevel, m_pSearchFinger);
		
		// Let them know where we put it, and that we did insert it.
		oInsertResult.m_itPosition = Iterator (pNode);
		oInsertResult.m_bInserted = true;
	}
	else
	{
		// We didn't insert it.  Show them the equal item.
		oInsertResult.m_itPosition = Iterator (pNode);
		oInsertResult.m_bInserted = false;
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST