skiplist.hh

Motion JPEG编解码器源代码

	// Let them know what happened.
	return oInsertResult;
}



// 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.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Move
	(SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther, Iterator a_oFirst,
	Iterator a_oLast)
{
	Iterator oHere, oNext;
		// The item we're moving.
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Loop through all the items, move each one.
	oHere = a_oFirst;
	while (oHere != a_oLast)
	{
		// Keep track of the next item to move.
		oNext = oHere;
		oNext++;
		
		// Move this item.
		Move (a_rOther, oHere);
		
		// Loop back and move the next one.
		oHere = oNext;
	}
}



// Move all items from the other skip-list to ourself.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Move
	(SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther)
{
	Node *p;
		// Used to swap structures.

	// Make sure the skip-lists can move items between themselves.
	assert (CanMove (a_rOther));
	
	// Make sure we're empty.
	assert (m_nItems == 0);

	// Swap the header & search fingers.
	p = m_pHeader;
	m_pHeader = a_rOther.m_pHeader;
	a_rOther.m_pHeader = p;
	p = m_pSearchFinger;
	m_pSearchFinger = a_rOther.m_pSearchFinger;
	a_rOther.m_pSearchFinger = p;
	p = m_pSearchFinger2;
	m_pSearchFinger2 = a_rOther.m_pSearchFinger2;
	a_rOther.m_pSearchFinger2 = p;

	// Use their header level, if it's bigger than ours.
	if (m_nHeaderLevel < a_rOther.m_nHeaderLevel)
		m_nHeaderLevel = a_rOther.m_nHeaderLevel;
	a_rOther.m_nHeaderLevel = 0;

	// Now we have all their items.
	m_nItems = a_rOther.m_nItems;
	a_rOther.m_nItems = 0;

#ifdef DEBUG_SKIPLIST
	// Make sure we're all intact.
	Invariant();
	a_rOther.Invariant();
#endif // DEBUG_SKIPLIST
}



// Returns true if the two skip lists can move items between
// each other.
template <class KEY, class VALUE, class KEYFN, class PRED>
bool
SkipList<KEY,VALUE,KEYFN,PRED>::CanMove
	(const SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther) const
{
	// They can if they have the same allocator.
	return (&m_rNodeAllocator == &a_rOther.m_rNodeAllocator);
}



// Assign the contents of the other skip list to ourselves.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::Assign (Status_t &a_reStatus,
	const SkipList<KEY,VALUE,KEYFN,PRED> &a_rOther)
{
	Node *pBegin, *pEnd;
		// Where we're looking in the other list.
	Node *pHere;
		// Where we're looking in our list.
	
#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);
	
	// Get the range of items from the other list.
	pBegin = a_rOther.Begin().m_pNode;
	pEnd = a_rOther.End().m_pNode;
	
	// First, if we have more nodes than they do, erase enough of ours
	// so that we have the same amount.
	if (Size() > a_rOther.Size())
	{
		// Calculate the number of nodes to delete.
		int32_t nToDelete = Size() - a_rOther.Size();
		
		// Move forward that many items.
		Iterator oToDelete = Begin();
		while (--nToDelete >= 0)
			oToDelete++;
		
		// Delete those items.
		Erase (Begin(), oToDelete);
	}
	
	// Start modifying our items here.
	pHere = Begin().m_pNode;
	
	// Next, insert as many items as we can, using the nodes already
	// allocated in the list.
	while (pHere != m_pHeader && pBegin != pEnd)
	{
		// Store the new item over the old one.
		pHere->m_oValue = pBegin->m_oValue;
		
		// Move forward.
		pHere = pHere->m_apForward[0];
		pBegin = pBegin->m_apForward[0];
	}
	
	// If we ran out of nodes, insert the rest in the normal way.
	if (pBegin != pEnd)
		Insert (a_reStatus, ConstIterator (pBegin),
			ConstIterator (pEnd));
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
}



// Find the given item in the list.  Returns End() if not found.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Iterator
SkipList<KEY,VALUE,KEYFN,PRED>::Find (const KEY &a_rKey)
{
	Iterator oHere;
		// What we found.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Look for the item.
	oHere = LowerBound (a_rKey);
	
	// LowerBound() returns the first item >= the key.  So if this item
	// is greater than what they were asking for, that means we didn't
	// find it.
	if (oHere == End()
	|| m_oPred (a_rKey, m_oKeyFn (oHere.m_pNode->m_oValue)))
		return End();
	else
		return oHere;
}



// Find the given item in the list.  Returns End() if not found.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::ConstIterator
SkipList<KEY,VALUE,KEYFN,PRED>::Find (const KEY &a_rKey) const
{
	ConstIterator oHere;
		// What we found.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Look for the item.
	oHere = LowerBound (a_rKey);
	
	// LowerBound() returns the first item >= the key.  So if this item
	// is greater than what they were asking for, that means we didn't
	// find it.
	if (oHere == End()
	|| m_oPred (a_rKey, m_oKeyFn (oHere.m_pNode->m_oValue)))
		return End();
	else
		return oHere;
}



// Return the position of the first item that's >= the key.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Iterator
SkipList<KEY,VALUE,KEYFN,PRED>::LowerBound (const KEY &a_rKey)
{
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Search for the first item >= the key.
	SearchLower (a_rKey, m_pSearchFinger);
	
	// Return what we found.
	return Iterator (m_pSearchFinger->m_apForward[0]->m_apForward[0]);
}



// Return the position of the first item that's >= the key.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::ConstIterator
SkipList<KEY,VALUE,KEYFN,PRED>::LowerBound (const KEY &a_rKey) const
{
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Search for the first item >= the key.
	SearchLower (a_rKey, m_pSearchFinger);
	
	// Return what we found.
	return ConstIterator (m_pSearchFinger->m_apForward[0]
		->m_apForward[0]);
}



// Return the position of the first item that's > the key.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::Iterator
SkipList<KEY,VALUE,KEYFN,PRED>::UpperBound (const KEY &a_rKey)
{
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Search for the first item > the key.
	SearchUpper (a_rKey, m_pSearchFinger);
	
	// Return what we found.
	return Iterator (m_pSearchFinger->m_apForward[0]->m_apForward[0]);
}



// Return the position of the first item that's > the key.
template <class KEY, class VALUE, class KEYFN, class PRED>
typename SkipList<KEY,VALUE,KEYFN,PRED>::ConstIterator
SkipList<KEY,VALUE,KEYFN,PRED>::UpperBound (const KEY &a_rKey) const
{
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// Search for the first item > the key.
	SearchUpper (a_rKey, m_pSearchFinger);
	
	// Return what we found.
	return ConstIterator (m_pSearchFinger->m_apForward[0]
		->m_apForward[0]);
}



// Search for an item greater than or equal to a_rKey.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::SearchLower (const KEY &a_rKey,
	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 (m_oKeyFn (pCurrentFinger->m_oValue), a_rKey))
		{
			// 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 (m_oKeyFn (pNextFinger->m_oValue), a_rKey))
			{
				// 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 (m_oKeyFn (pNextNode->m_oValue), a_rKey))
		{
			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
}



// Search for this exact item.  Returns true if it's found.
template <class KEY, class VALUE, class KEYFN, class PRED>
bool
SkipList<KEY,VALUE,KEYFN,PRED>::SearchExact (Node *a_pKey,
	Node *a_pTraverse) const
{
	Node *pFound;
		// What we found.
	int16_t nI;
		// Used to iterate through levels.
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Make sure we have been initialized properly.
	assert (m_pHeader != NULL);
	
	// If they passed us End(), just search to the end and succeed.
	if (a_pKey == m_pHeader)
	{
		SearchEnd (a_pTraverse);
		return true;
	}
	
	// Find the lower bound.
	SearchLower (m_oKeyFn (a_pKey->m_oValue), a_pTraverse);
	
	// Run through the equal range, look for this exact item.
	for (pFound = a_pTraverse->m_apForward[0]->m_apForward[0];
		 pFound != m_pHeader && pFound != a_pKey;
		 pFound = pFound->m_apForward[0])
	{
		// Advance the search finger.
		for (nI = 0;
			 nI < m_nHeaderLevel
			 	&& a_pTraverse->m_apForward[nI]->m_apForward[nI]
					== pFound;
			 nI++)
		{
			a_pTraverse->m_apForward[nI] = pFound;
		}
	}
	
#ifdef DEBUG_SKIPLIST
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SKIPLIST
	
	// Let them know if we succeeded.
	return (pFound == a_pKey);
}



// Search for an item greater than a_rKey.
template <class KEY, class VALUE, class KEYFN, class PRED>
void
SkipList<KEY,VALUE,KEYFN,PRED>::SearchUpper (const KEY &a_rKey,