skiplist.hh

Motion JPEG编解码器源代码

	Node *a_pTraverse) const
{
	Node *pCurrentNode;
		// Where we're searching.
	int16_t nCurrentLevel;
		// The level we've searched so far.
	Node *pLastFinger;
		// A node that we know is <= the key.
	Node *pAlreadyChecked;
		// A node that we know is > the key.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// See how much of the previous search we can reuse.
	pCurrentNode = m_pHeader;
	pLastFinger = m_pHeader;
	pAlreadyChecked = m_pHeader;
	nCurrentLevel = m_nHeaderLevel;
	while (--nCurrentLevel >= 0)
	{
		Node *pCurrentFinger;
			// What's at this level.
		
		// See what's at this level.
		pCurrentFinger = a_pTraverse->m_apForward[nCurrentLevel];
		
		// If this is what we found before, OR if there's nothing here,
		// OR we haven't gone past what we're trying to find, then
		// there's a chance we can reuse the search at this level.
		if (pCurrentFinger == pLastFinger
		|| pCurrentFinger == m_pHeader
		|| !m_oPred (a_rKey, m_oKeyFn (pCurrentFinger->m_oValue)))
		{
			// Look at the item past the current search finger.
			Node *pNextFinger
				= pCurrentFinger->m_apForward[nCurrentLevel];
			
			// If there's nothing here, OR what's here is > what we're
			// looking for, then we can reuse all of this level's
			// search.
			if (pNextFinger == m_pHeader
			|| pNextFinger == pAlreadyChecked
			|| m_oPred (a_rKey, m_oKeyFn (pNextFinger->m_oValue)))
			{
				// We can reuse all of this level's search.
				pCurrentNode = pCurrentFinger;
				pLastFinger = pCurrentFinger;
				pAlreadyChecked = pNextFinger;
			}
			else
			{
				// We can reuse this level's search, but we have to
				// start looking here.
				pCurrentNode = pCurrentFinger;
				nCurrentLevel++;
				break;
			}
		}
		else
		{
			// We can't reuse this level.  Redo it.
			nCurrentLevel++;
			break;
		}
	}
	
	// Now search for the item in the list.
	while (--nCurrentLevel >= 0)
	{
		Node *pNextNode;
		while (pNextNode = pCurrentNode->m_apForward[nCurrentLevel],
			pNextNode != pAlreadyChecked && pNextNode != m_pHeader
			&& !m_oPred (a_rKey, m_oKeyFn (pNextNode->m_oValue)))
		{
			pCurrentNode = pNextNode;
		}
		pAlreadyChecked = pCurrentNode->m_apForward[nCurrentLevel];
		a_pTraverse->m_apForward[nCurrentLevel] = pCurrentNode;
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
}



// Point to the end of the list.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::SearchEnd (Node *a_pTraverse) const
{
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Point every level of the traverse array to the last node before
	// the end.
	Node *pLastNode = a_pTraverse->m_apForward[m_nHeaderLevel - 1];
	int16_t nCurrentLevel = m_nHeaderLevel;
	while (--nCurrentLevel >= 0)
	{
		Node *pNextNode;
		while (pNextNode = pLastNode->m_apForward[nCurrentLevel],
				pNextNode != m_pHeader)
		{
			pLastNode = pNextNode;
		}
		a_pTraverse->m_apForward[nCurrentLevel] = pLastNode;
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
}



// Insert a new node into the skip list.  Assume a_pTraverse is
// set up.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::InsertNode (Node *a_pNewNode,
	int16_t a_nNewLevel, Node *a_pTraverse)
{
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Set up the backward link of the new node.
	a_pNewNode->m_pBackward = a_pTraverse->m_apForward[0];
	
	// Modify all levels of pointers.
	while (--a_nNewLevel >= 0)
	{
		// Insert ourselves where the traverse array points.
		a_pNewNode->m_apForward[a_nNewLevel]
			= a_pTraverse->m_apForward[a_nNewLevel]
				->m_apForward[a_nNewLevel];
		a_pTraverse->m_apForward[a_nNewLevel]->m_apForward[a_nNewLevel]
			= a_pNewNode;
		
		// Point the traverse array at the new node.
		a_pTraverse->m_apForward[a_nNewLevel] = a_pNewNode;
	}
	
	// Set up the backward link of the node after the new one.
	a_pNewNode->m_apForward[0]->m_pBackward = a_pNewNode;
	
	// That's one more node in the list.
	m_nItems++;
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
}



// 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.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Node *
SkipList<KEY,VALUE,KEYFN,PRED>::RemoveNode (Node *a_pToRemove,
	Node *a_pTraverse, int16_t *a_rpLevel)
{
	int16_t nI;
		// Used to loop through skip-list levels.
	Node *pCurrentNode;
		// A node that's pointing to the node we're removing.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure this traversal array is set up to remove this node.
	assert (a_pTraverse->m_apForward[0]->m_apForward[0] == a_pToRemove);
	
	// Remove this node from all levels where it appears.
	for (nI = 0;
		 nI < m_nHeaderLevel
		 && (pCurrentNode = a_pTraverse->m_apForward[nI],
			pCurrentNode->m_apForward[nI] == a_pToRemove);
		 nI++)
	{
		pCurrentNode->m_apForward[nI] = a_pToRemove->m_apForward[nI];
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure the node had as many levels as we expected.
	assert (nI == a_pToRemove->m_nLevel);
#endif // DEBUG_SKIPLIST
	
	// Remove this node from the back-links.
	a_pTraverse->m_apForward[0]->m_apForward[0]->m_pBackward
		= a_pTraverse->m_apForward[0];
	
	// That's one less item in the list.
	m_nItems--;
	
	// Give them the level of this node, if they asked for it.
	if (a_rpLevel != NULL)
		*a_rpLevel = nI;
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Return the node we removed.
	return a_pToRemove;
}



// Allocate a new node with the given number of forward pointers.
// Returns NULL if something goes wrong.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Node *
SkipList<KEY,VALUE,KEYFN,PRED>::GetNewNode (int16_t a_nForwardPointers)
{
	int32_t nBytes;
		// The number of bytes this node needs.
	Node *pNode;
		// The node we allocate.
	
	// Calculate the number of bytes it takes to represent a node with
	// this many forward pointers.
	nBytes = sizeof (Node) + (a_nForwardPointers - 1) * sizeof (Node *);
	
	// Allocate space.
	pNode = (Node *) m_rNodeAllocator.Allocate (a_nForwardPointers - 1,
		nBytes);
	
#ifdef DEBUG_SKIPLIST
	// Set the number of forward pointers.
	pNode->m_nLevel = a_nForwardPointers;
#endif // DEBUG_SKIPLIST
	
	// Return what we allocated.
	return pNode;
}



// 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.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Node *
SkipList<KEY,VALUE,KEYFN,PRED>::GetNewNodeOfRandomLevel
	(int16_t &a_rnLevel)
{
	// Fix the dice (as described in the skip-list paper).
	int16_t nHighestLevel = (m_nHeaderLevel == HEADERCHUNK)
		? HEADERCHUNK : m_nHeaderLevel + 1;
	
	// Now generate a random level for the node.  (12055 / 32768 equals
	// our skip list's p, which is 1/e.)
	int16_t nNewLevel = 1;
	while (nNewLevel < nHighestLevel && Rand() < 12055)
		nNewLevel++;
	
	// Keep track of the new maximum.
	if (nNewLevel == nHighestLevel)
		m_nHeaderLevel = nHighestLevel;
	
	// Allocate a node of this size.
	a_rnLevel = nNewLevel;
	return GetNewNode (nNewLevel);
}



// Delete a node.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::DeleteNode (int16_t a_nForwardPointers,
	Node *a_pToDelete)
{
	// Make sure they gave us a node to delete.
	assert (a_pToDelete != NULL);
	
	// Delete the value we contain.
	a_pToDelete->m_oValue.~VALUE();
	
	// Deallocate the node's storage.
	DeallocateNode (a_nForwardPointers, a_pToDelete);
}



// Deallocate a node's storage.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::DeallocateNode
	(int16_t a_nForwardPointers, Node *a_pToDelete)
{
	// Make sure they gave us a node to deallocate.
	assert (a_pToDelete != NULL);
	
	// Return the memory to our node allocator.
	m_rNodeAllocator.Deallocate (a_nForwardPointers - 1,
		(void *)a_pToDelete);
}



// Get another random number.
template <class KEY, class VALUE, class KEYFN, class PRED>
int16_t
SkipList<KEY,VALUE,KEYFN,PRED>::Rand (void)
{
	// I'd use the normal rand() but it's WAAAY too slow.
	// Feel free to adjust this routine all you want.
	m_nRandSeed = m_nRandSeed * 42989 + 17891;
	return int16_t (m_nRandSeed & 32767);
}



#ifdef DEBUG_SKIPLIST

template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Invariant (void) const
{
	int32_t nI;
		// Used to loop through things.
	Node *pSearchFinger;
		// Used to verify the integrity of the forward pointers.
	Node *pCurrentNode;
		// The node whose integrity we are presently verifying.
	Node *pPreviousNode;
		// The node before the current one.
	uint32_t nItems;
		// The number of items we found.
	
	// Only check the invariant if they requested we do.
	if (!m_bDebug)
		return;
	
	// If the skip list is not fully initialized, we have less to check.
	if (m_pHeader == NULL)
	{
		assert (m_nHeaderLevel == 0);
		assert (m_pSearchFinger == NULL);
		assert (m_pSearchFinger2 == NULL);
		assert (m_nItems == 0);
		return;
	}
	
	// Make sure the skip list level isn't bigger than the compiled-in
	// maximum.
	assert (m_nHeaderLevel <= HEADERCHUNK);
	
	// We're going to run through the skip list and make sure all the
	// forward pointers are correct.  For that, we need a temporary
	// search finger to keep track of the traversal.
	pSearchFinger = (Node *) alloca (sizeof (Node)
		+ (HEADERCHUNK - 1) * sizeof (Node *));
	pSearchFinger->m_nLevel = 0;
	pSearchFinger->m_pBackward = NULL;
	for (nI = 0; nI < HEADERCHUNK; nI++)
		pSearchFinger->m_apForward[nI] = m_pHeader;
	
	// The backward link for the header node points to the last item in
	// the list.  So find the last item in the list.
	pPreviousNode = m_pHeader;
	while (pPreviousNode->m_apForward[0] != m_pHeader)
		pPreviousNode = pPreviousNode->m_apForward[0];
	
	// Run through the skip list, make sure the forward pointers and
	// backward pointers are intact.
	pCurrentNode = m_pHeader;
	nItems = 0;
	for (;;)
	{
		int32_t nLevel;
			// The level of the current node.
		
		// At least one forward pointer of the temporary search finger
		// points to the current node.  The number of forward pointers
		// that point to the current node, must be equal to its assigned
		// level.  So start by calculating what level this node must be.
		nLevel = 0;
		while (nLevel < HEADERCHUNK
				&& pSearchFinger->m_apForward[nLevel] == pCurrentNode)
			nLevel++;
		
		// Make sure the node has that many forward pointers.
		assert (pCurrentNode->m_nLevel == nLevel);
		
		// Make sure the backward pointer is intact.
		assert (pCurrentNode->m_pBackward == pPreviousNode);
		
		// Make sure that the nodes are in proper sorted order.
		if (pPreviousNode != m_pHeader && pCurrentNode != m_pHeader)
		{
			if (m_bAllowDuplicates)
			{
				// The current item has to be >= the previous item.
				assert (!m_oPred (m_oKeyFn (pCurrentNode->m_oValue),
					m_oKeyFn (pPreviousNode->m_oValue)));
			}
			else
			{
				// The current item has to be > the previous item.
				assert (m_oPred (m_oKeyFn (pPreviousNode->m_oValue),
					m_oKeyFn (pCurrentNode->m_oValue)));
			}
		}
		
		// If we're at the end of the list, stop.
		if (pCurrentNode->m_apForward[0] == m_pHeader)
			break;
		
		// That's one more item we found.  (We put this here in order to
		// avoid counting the header node as an item.)
		nItems++;
		
		// Move forward.
		pPreviousNode = pCurrentNode;
		pCurrentNode = pCurrentNode->m_apForward[0];
		for (nI = 0; nI < nLevel; nI++)
			pSearchFinger->m_apForward[nI]
				= pSearchFinger->m_apForward[nI]->m_apForward[nI];
	}
	
	// Make sure the list has the expected number of items.
	assert (m_nItems == nItems);
}

#endif // DEBUG_SKIPLIST



#endif // __SKIPLIST_H__