/*++ Microsoft Windows NT RPC Name Service Copyright (c) 1995 Microsoft Corporation Module Name: skiplist.cxx Abstract: This module contains definitions of non inline member functions for the CSkipList class, which implements skiplists with reference counted links. Author: Satish Thatte (SatishT) 08/16/95 Created all the code below except where otherwise indicated. --*/ #if DBG char * CSListName = "CSkipList"; char * CSLinkName = "CSkipLink"; #endif #include // the regular constructor CSkipList::CSkipLink::CSkipLink(IOrderedItem * d, short l) : data(d) { next = new CSkipLink* [levels = l]; for (short i = 0; i < l; i++ ) next[i] = NULL; fDeleteData = FALSE; } // resizing constructor CSkipList::CSkipLink::CSkipLink(CSkipLink * old, short newSize) { next = new CSkipLink* [levels = newSize]; data = old->data; fDeleteData = old->fDeleteData; ASSERT(levels > old->levels, "Skip List Levels Incorrect\n"); for (short i = 0; i < old->levels; i++ ) next[i] = old->next[i]; // if we are resizing, there had better be a next ASSERT(next[0], "Resizing a single-item Skip List\n"); next[0]->hold(); // to counteract the release in old for ( i = old->levels; i < levels; i++ ) next[i] = NULL; old->release(); } CSkipList::CSkipLink::~CSkipLink() { if (next[0]) next[0]->release(); delete [] next; if (fDeleteData) delete data; } CSkipList::CSkipList() { count = 0; maxlevel = 1; // initial max level maxcount = 2; pLnkFirst = NULL; } void CSkipList::wipeOut() /*++ Routine Description: release all SkipLinks and all data and reinitialize to empty list --*/ { if (pLnkFirst) { CSkipLink *pLnkCurr = pLnkFirst; do { pLnkCurr->fDeleteData = TRUE; pLnkCurr = pLnkCurr->next[0]; } while (pLnkCurr); releaseAll(pLnkFirst); // release as many links as you can, // and do it iteratively for robustness pLnkFirst = NULL; count = 0; } } IOrderedItem *CSkipList::find(IOrderedItem * d) /*++ Routine Description: Find a matching item in the CSkipList and return it An IOrderedItem given as argument is the key, and the item returned may be an object of a class derived from the key type. This routine uses a goto and uses the raw compare function, because the performance of this routine is important, and it is especially important to avoid unnecessary comparisons --*/ { CSkipLink *temp = NULL, *pLink = pLnkFirst; if (!pLnkFirst) return NULL; // empty list int comparison = pLnkFirst->data->compare(*d); if (comparison > 0) return NULL; // no chance if (comparison == 0) return pLnkFirst->data; for (short cLvl = maxlevel-1 ; cLvl >= 0 ; cLvl-- ) { while(temp = pLink->next[cLvl]) { int comparison = temp->data->compare(*d); if (comparison == 0) return temp->data; if (comparison > 0) goto cont; else pLink = temp; // comparison < 0 } cont:; } return NULL; } IOrderedItem *CSkipList::pop() /*++ Routine Description: Remove and return the first item in the CSkipList Returns: the removed item if any, NULL, otherwise. --*/ { short cLvl; if (!pLnkFirst) return NULL; IOrderedItem *lpRetval = pLnkFirst->data; CSkipLink *temp = NULL; /* If there is a second item, we copy the second into the first so as to preserve the max size of the first node, as well as its links at higher levels which the second link may lack */ if (temp = pLnkFirst->next[0]) { pLnkFirst->data = temp->data; ASSERT(pLnkFirst->levels >= temp->levels, "First node in skip list not largest\n"); /* the next pointers of the second link need to be copied into the first as well, along with the data pointer */ for ( cLvl = temp->levels - 1; cLvl >= 0; cLvl-- ) { pLnkFirst->next[cLvl] = temp->next[cLvl]; } if (temp->next[0]) // this hold counteracts the following release temp->next[0]->hold(); temp->release(); } else { // we are removing the only item in the list pLnkFirst->release(); pLnkFirst = NULL; } count--; return lpRetval; } IOrderedItem *CSkipList::remove(IOrderedItem * d) /*++ Routine Description: Remove and return a matching item in the CSkipList. An IOrderedItem given as argument is the key, and the item to be removed may be an object of a class derived from the key type. This routine uses ordinary relational operators. It is not as efficient as it could be if it used the raw compare function, but relational operators make it more readable. Since remove operations are infrequent, the small extra cost in performance does not matter. RETURNS: the removed item if any, NULL, otherwise --*/ { ASSERT(d, "Attempt to remove a null object in skip list\n"); if (!pLnkFirst || (*(pLnkFirst->data) > *d)) return NULL; // no chance ASSERT(pLnkFirst->levels == maxlevel, "Wrong size for first skiplist node\n"); // always holds /* Is this a special case: remove the first item? */ if (*(pLnkFirst->data) == *d) return pop(); /* Otherwise our first task is to find the item to be removed. pLink will track the link prior to the one being removed */ CSkipLink *temp = NULL, *pLink = pLnkFirst; short cLvl; IOrderedItem *lpRetval = NULL; for ( cLvl = maxlevel-1 ; cLvl >= 0 ; cLvl-- ) { while ((temp = pLink->next[cLvl]) && (*(temp->data) < *d)) pLink = temp; if (temp && (*(temp->data) == *d)) { lpRetval = temp->data; break; } } /* Check if we found something, or came to the end of the rope */ if (cLvl < 0) return NULL; // end of the rope, nothing found /* now we can allocate the threading array */ CSkipLink **ppSLthreads = new CSkipLink* [maxlevel]; ppSLthreads[cLvl] = pLink; short findLvl = cLvl; CSkipLink * pFindLink = temp; /* Now that we found the link to be removed, we need to find its predecessors at every level, so that they can be relinked */ for ( cLvl-- ; cLvl >= 0 ; cLvl-- ) { while ((temp = pLink->next[cLvl]) && *(temp->data) < *d) pLink = temp; ppSLthreads[cLvl] = pLink; } /* relink, release, and be done */ for ( cLvl = findLvl; cLvl >= 0; cLvl-- ) { ppSLthreads[cLvl]->next[cLvl] = pFindLink->next[cLvl]; } if (pFindLink->next[0]) pFindLink->next[0]->hold(); // the preceding hold counteracts the following release pFindLink->release(); delete [] ppSLthreads; count--; return lpRetval; } SkipStatus CSkipList::insert(IOrderedItem * d) /*++ Routine Description: Insert the IOrderedItem into the CSkipList. The CSkipList will adjust its maxlevels member as necessary. The algorithm is probabilistic -- the size of the new CSkipLink is decided by using a random number. This routine uses ordinary relational operators. It is not as efficient as it could be if it used the raw compare function, but relational operators make it more readable. Since remove operations are infrequent, the small extra cost in performance does not matter. The routine assumes that srand has been called to initialize the random number generator. --*/ { if (!pLnkFirst) { /* if this is the only data item in the list then we must use maxlevel for node size which may be greater than 1 if the list had stuff which got removed */ pLnkFirst = new CSkipLink(d,maxlevel); } else { ASSERT(pLnkFirst->levels == maxlevel, "Wrong size for first skiplist node\n"); // must always hold if (*(pLnkFirst->data) > *d) /* new data is smallest -- swap with first and pretend we are inserting previous first. This is not the most efficient way, but for this special case, the extra code isn't worth it */ swapThem(pLnkFirst->data,d); CSkipLink *pLink = pLnkFirst, *temp = NULL; /* The array below is used to hold the nodes that need to be threaded with the new CSkipLink */ CSkipLink **ppSLthreads = new CSkipLink* [maxlevel]; short cLvl; /* We now find the threading points by a process very similar to the search process in find */ for ( cLvl = maxlevel - 1 ; cLvl >= 0 ; cLvl-- ) { while((temp = pLink->next[cLvl]) && *(temp->data) <= *d) pLink = temp; if (*(pLink->data) == *d) { delete [] ppSLthreads; return Duplicate; } else ppSLthreads[cLvl] = pLink; } /* now create the new link */ short size; ULONG dwRandState = GetTickCount(); for (size = 1 ; size < maxlevel ; size++ ) if (RandomBit(&dwRandState)) break; /* We get a CSkipLink of the randomly chosen size -- the probability of choosing each larger size is half that of the previous size. Maxlevel has the residual probability, equal to that for the next smaller size. This is not quite ideal, but good enough for us. */ CSkipLink *pNewLink = new CSkipLink(d,size); /* now thread the new link in */ for ( cLvl = size-1 ; cLvl >= 0 ; cLvl-- ) { temp = ppSLthreads[cLvl]->next[cLvl]; ppSLthreads[cLvl]->next[cLvl] = pNewLink; pNewLink->next[cLvl] = temp; } delete [] ppSLthreads; } /* bump up count and also maxlevel if necessary */ if ( ++count > maxcount) { maxlevel++; maxcount <<= 1; // double the maxcount /* now we need to resize the first node to max size */ pLnkFirst = new CSkipLink(pLnkFirst,maxlevel); } return OK; } // void printStats(); void CSkipList::releaseAll(CSkipLink * pCurr) /* The reason why this method doesn't just release pLnkFirst is because we must avoid stack overflow caused by a runaway recursive release effect. So we do this iteratively. We must, however, make sure to stop if we hit a link that would not be deleted if released because we are releasing the next one only to simulate the release that would happen due to deletion of the current link. */ { CSkipLink *pPrev = NULL; /* The invariant for the loop below is that pCurr->ulRefCount is 1 higher than it should be. */ while (pCurr && pCurr->willBeDeletedIfReleased()) { pPrev = pCurr; pCurr = pCurr->next[0]; if (pCurr) pCurr->hold(); pPrev->release(); } if (pCurr) pCurr->release(); // printStats(); } IOrderedItem* CSkipListIterator::next() { // advance the iterator and return next IDataItem // continue to hold the link we expect to return next if (!ptr) return NULL; CSkipList::CSkipLink* tl = ptr; IOrderedItem* result = ptr->data; ptr = ptr->next[0]; if (ptr) ptr->hold(); tl->release(); return result; }