/* $Id: ccollection.cpp,v 1.8 2001年11月23日 18:07:37 phaller Exp $ */ /* * Collection class: * provides very fast object lookup by index number * * Copyright 2001 Patrick Haller * * * Project Odin Software License can be found in LICENSE.TXT * * */ #include static inline unsigned long _Optlink hashcode(int iRing, char *pszName) { unsigned long h; unsigned char *t = (unsigned char*)pszName; for (h = 0; *t; t++) { h = (h << 6); h += *t; h %= iRing; } return h; } CCollection::CCollection(int iInitialSize) { iSize = iInitialSize; } CCollection::~CCollection() { } CIndexLookup::CIndexLookup(int iInitialSize) { // iSize is expected to be set by parent constructor // allocate array with given size if (iInitialSize> 0) { pEntries = (PINDEXLOOKUPENTRY)malloc(iInitialSize * sizeof(INDEXLOOKUPENTRY)); memset(pEntries, 0, iInitialSize * sizeof(INDEXLOOKUPENTRY)); } else // no initial array provided pEntries = NULL; iOffset = INT_MAX; iHigh = INT_MIN; iUsedOffset = INT_MAX; iUsedHigh = INT_MIN; } CIndexLookup::~CIndexLookup() { free(pEntries); } int CIndexLookup::isValidIndex(int iIndex) { /* determine if the given index is within bounds */ return ( (iIndex>= iOffset) && (iIndex <= iHigh) ); } int CIndexLookup::shrink() { // shrink the index array to the absolutely necessary size only if (iInitialized == 0) { // if no elements were allocated, simple remove all data memory if (pEntries) { free(pEntries); pEntries = NULL; } return 1; } // verify if shrink can do anything good if ( (iOffset < iUsedOffset) || (iHigh> iUsedHigh) ) { // OK, reallocate the beast int iRequiredSize = iUsedHigh - iUsedOffset + 1; PINDEXLOOKUPENTRY pNewData = (PINDEXLOOKUPENTRY)malloc(iRequiredSize * sizeof(INDEXLOOKUPENTRY)); if (NULL == pNewData) { /* signal failure */ return 0; } // copy old data and write new boundary info if (NULL != pEntries) { int iRelative = iUsedOffset - iOffset; // Note: due to C++ pointer arithmetic, // (pEntries + iRelative) should automatically // increase pEntries by iRelative-times the // sizeof(INDEXLOOKUPENTRY) byte positions! memmove(pNewData, pEntries + iRelative, iRequiredSize * sizeof(INDEXLOOKUPENTRY)); // deferred delete ensures we've always got a valid array PINDEXLOOKUPENTRY pTemp = pEntries; pEntries = pNewData; free(pTemp); } else { // set new pointer and we're done memset(pNewData, 0, iRequiredSize * sizeof(INDEXLOOKUPENTRY)); pEntries = pNewData; } iSize = iRequiredSize; iOffset = iUsedOffset; iHigh = iUsedHigh; return 1; // shrunk } else return 0; // didn't do anything } PINDEXLOOKUPENTRY CIndexLookup::reallocateData(int iShift, int iRequiredSize) { // Note: assumption is iRequiredSize is> iSize! // if (iRequiredSize < iSize) // return NULL; PINDEXLOOKUPENTRY pNewData = (PINDEXLOOKUPENTRY)malloc(iRequiredSize * sizeof(INDEXLOOKUPENTRY)); if (NULL == pNewData) { /* signal failure */ return NULL; } // copy current data if (pEntries != NULL) { // copy the data, array cannot overlap memmove(pNewData + (iShift * sizeof(INDEXLOOKUPENTRY)), pEntries, iSize * sizeof(INDEXLOOKUPENTRY)); // zero out at the beginning or at the end if (iShift == 0) { // clear trailing memset(pNewData + sizeof(INDEXLOOKUPENTRY) * iSize, 0, sizeof(INDEXLOOKUPENTRY) * (iRequiredSize - iSize)); } else { // clear leading memset(pNewData, 0, sizeof(INDEXLOOKUPENTRY) * (iShift)); } } else // clear brand-new array memset(pNewData, 0, iRequiredSize * sizeof(INDEXLOOKUPENTRY)); return pNewData; } int CIndexLookup::ensureCapacity(int iIndex) { // we need to resize if the index is not valid if (!isValidIndex(iIndex)) { // calculate new array bounds, // copy original table, // swap table pointers // and free original pointer // check if new base offset is lower if (iIndex < iOffset) { // insert space at the front // calculate new size int iRequiredSize = iHigh - iIndex + 1; // reallocate the array int iShift = iOffset - iIndex; // for how many elements to shift left PINDEXLOOKUPENTRY pNewData = reallocateData(iShift, iRequiredSize); if (NULL == pNewData) // signal failure return 0; // deferred delete ensures we've always got a valid array PINDEXLOOKUPENTRY pTemp = pEntries; pEntries = pNewData; if (pTemp) free(pTemp); iSize = iRequiredSize; iOffset = iIndex; } else if (iIndex> iHigh) { // lengthen the array // calculate new size int iRequiredSize = iIndex - iOffset + 1; // reallocate the array PINDEXLOOKUPENTRY pNewData = reallocateData(0, iRequiredSize); if (NULL == pNewData) // signal failure return 0; // deferred delete ensures we've always got a valid array PINDEXLOOKUPENTRY pTemp = pEntries; pEntries = pNewData; if (pTemp) free(pTemp); iSize = iRequiredSize; iHigh = iIndex; } else // internal logic flaw! return 0; } return 1; /* OK */ } void* CIndexLookup::addElement(int iIndex, void* pObject) { // ensure the array can hold the entry if (ensureCapacity(iIndex)) { // update the used low and high marks if (iIndex < iUsedOffset) iUsedOffset = iIndex; if (iIndex> iUsedHigh) iUsedHigh = iIndex; // used limits are not initialized iInitialized = 1; // insert entry and quit pEntries[iIndex - iOffset].pObject = pObject; return pObject; } else { // signal failure return NULL; } } void* CIndexLookup::removeElement(int iIndex) { // check if index is within table if (isValidIndex(iIndex)) { // remove specified element from the array void *pOld = pEntries[iIndex - iOffset].pObject; pEntries[iIndex - iOffset].pObject = NULL; return pOld; } else { // signal failure return NULL; } } void CIndexLookup::clear(void) { free(pEntries); pEntries = NULL; iOffset = INT_MAX; iHigh = INT_MIN; iSize = 0; iUsedOffset = INT_MAX; iUsedHigh = INT_MIN; iInitialized = 0; } void* CIndexLookup::getElement(int iIndex) { if (isValidIndex(iIndex)) { // OK, return entry return pEntries[iIndex - iOffset].pObject; } else { // signal: not found return NULL; } } CIndexLookupLimit::CIndexLookupLimit(int iHardLimitLow, int iHardLimitHigh) : CIndexLookup(0) { // iSize is expected to be set by parent constructor // enable hard limits iLimitLow = min(iHardLimitLow, iHardLimitHigh); iLimitHigh = max (iHardLimitLow, iHardLimitHigh); // size the array iOffset = iLimitLow; iHigh = iLimitHigh; iSize = iHigh - iOffset + 1; pEntries = reallocateData(0, iSize); } CIndexLookupLimit::~CIndexLookupLimit() { } int CIndexLookupLimit::ensureCapacity(int iIndex) { // verify against hard limits if enabled // prevent growing under the low limit if (iIndex < iLimitLow) return 0; // prevent growing above the high limit if (iIndex> iLimitHigh) return 0; return CIndexLookup::ensureCapacity(iIndex); } CLinearList::CLinearList() : CCollection(0) { pFirst = NULL; pLast = NULL; } CLinearList::~CLinearList() { clear(); } PLINEARLISTENTRY CLinearList::addFirst(void* pObject) { if (pFirst) return addBefore(pFirst, pObject); else return add0(pObject); } PLINEARLISTENTRY CLinearList::addLast(void* pObject) { if (pLast) return addAfter(pLast, pObject); else return add0(pObject); } // special internal entry to add the 1st element PLINEARLISTENTRY CLinearList::add0 (void *pObject) { // allocate new entry PLINEARLISTENTRY pLLENew = (PLINEARLISTENTRY)malloc(sizeof(LINEARLISTENTRY)); if (NULL == pLLENew) // signal failure return NULL; // setup object pLLENew->pObject = pObject; pLLENew->pPrev = NULL; pLLENew->pNext = NULL; pFirst = pLLENew; pLast = pLLENew; // count items iSize = 1; return pLLENew; } PLINEARLISTENTRY CLinearList::addBefore (PLINEARLISTENTRY pLLE, void *pObject) { // allocate new entry PLINEARLISTENTRY pLLENew = (PLINEARLISTENTRY)malloc(sizeof(LINEARLISTENTRY)); if (NULL == pLLENew) // signal failure return NULL; // setup object pLLENew->pObject = pObject; pLLENew->pPrev = pLLE->pPrev; pLLENew->pNext = pLLE; pLLE->pPrev = pLLENew; // establish linking, append to end of list if (pFirst == pLLE) pFirst = pLLENew; // count items iSize++; return pLLENew; } PLINEARLISTENTRY CLinearList::addAfter(PLINEARLISTENTRY pLLE, void *pObject) { // allocate new entry PLINEARLISTENTRY pLLENew = (PLINEARLISTENTRY)malloc(sizeof(LINEARLISTENTRY)); if (NULL == pLLENew) // signal failure return NULL; // setup object pLLENew->pObject = pObject; pLLENew->pNext = pLLE->pNext; pLLENew->pPrev = pLLE; pLLE->pNext = pLLENew; // establish linking, append to end of list if (pLast == pLLE) pLast = pLLENew; // count items iSize++; return pLLENew; } PLINEARLISTENTRY CLinearList::findForward(void *pObject) { return findForward(pFirst, pObject); } PLINEARLISTENTRY CLinearList::findBackward(void *pObject) { return findBackward(pLast, pObject); } PLINEARLISTENTRY CLinearList::findForward(PLINEARLISTENTRY pLLECurrent, void *pObject) { while(pLLECurrent) { // check current item if (pLLECurrent->pObject == pObject) return pLLECurrent; pLLECurrent = pLLECurrent->pNext; } // signal not found return NULL; } PLINEARLISTENTRY CLinearList::findBackward(PLINEARLISTENTRY pLLECurrent, void *pObject) { while(pLLECurrent) { // check current item if (pLLECurrent->pObject == pObject) return pLLECurrent; pLLECurrent = pLLECurrent->pPrev; } // signal not found return NULL; } void CLinearList::removeElement(PLINEARLISTENTRY pLLE) { // check if we're removing from the head if (pLLE == pFirst) pFirst = pLLE->pNext; // check if we're removing from the tail if (pLLE == pLast) pLast = pLLE->pPrev; // remove from chain if (pLLE->pPrev != NULL) pLLE->pPrev->pNext = pLLE->pNext; if (pLLE->pNext != NULL) pLLE->pNext->pPrev = pLLE->pPrev; // free memory of the pLLE free(pLLE); // count elements iSize--; } int CLinearList::removeObject(void* pObject) { PLINEARLISTENTRY pLLE = findForward(pObject); if (pLLE == NULL) // signal not found return 0; else { removeElement(pLLE); return 1; } } void CLinearList::clear() { PLINEARLISTENTRY pLLE = pFirst; PLINEARLISTENTRY pLLENext; // Establish new head and tail pointers very quickly, // since new items can be added already while the old ones // are still being deleted without causing interference. pFirst = NULL; pLast = NULL; while (pLLE) { pLLENext = pLLE->pNext; free (pLLE); pLLE = pLLENext; } } CHashtableLookup::CHashtableLookup(int iInitialSize) : CCollection(iInitialSize) { // the parent constructor is expected to set iSize // to iInitialSize parrLists = new CLinearList* [iSize]; memset(parrLists, 0, iSize * sizeof(CLinearList*) ); iElements = 0; } CHashtableLookup::~CHashtableLookup() { // kill all the slot lists for (int i = 0; i < iSize; i++) { // check if slot was occupied if (parrLists[i] != NULL) { delete parrLists[i]; parrLists[i] = NULL; } } iSize = 0; iElements = 0; delete [] parrLists; } PHASHTABLEENTRY CHashtableLookup::addElement(char *pszName, void *pObject) { // get slot number unsigned long ulHash = hashcode(iSize, pszName); // create entry PHASHTABLEENTRY pHTE = (PHASHTABLEENTRY)malloc(sizeof(HASHTABLEENTRY)); pHTE->pszName = pszName; pHTE->pObject = pObject; // check if slot has a list object already if (parrLists[ulHash] == NULL) parrLists[ulHash] = new CLinearList(); parrLists[ulHash]->addLast(pHTE); // count allocated elements iElements++; return pHTE; } void* CHashtableLookup::removeElement(char *pszName) { // get slot number unsigned long ulHash = hashcode(iSize, pszName); // check if slot is occupied if (parrLists[ulHash] == NULL) // signal not found return NULL; // search the list PLINEARLISTENTRY pLLE = parrLists[ulHash]->getFirst(); if (pLLE == NULL) // signal not found return NULL; // iterate over the list while(pLLE) { PHASHTABLEENTRY pHTE = (PHASHTABLEENTRY)pLLE->pObject; // quickly compare 1st character for equality // before doing the strcmp call if (*pHTE->pszName == *pszName) if (strcmp(pHTE->pszName, pszName) == 0) { // save old object pointer void* pTemp = pHTE->pObject; free(pHTE); // found the correct entry parrLists[ulHash]->removeElement(pLLE); // count allocated elements iElements--; // return old object pointer to signal success return pTemp; } pLLE = pLLE->pNext; } // failed return NULL; } void* CHashtableLookup::getElement(char *pszName) { // get slot number unsigned long ulHash = hashcode(iSize, pszName); CLinearList *pLL = parrLists[ulHash]; // check if slot is occupied if (pLL == NULL) // signal not found return NULL; // search the list PLINEARLISTENTRY pLLE = pLL->getFirst(); if (pLLE == NULL) // signal not found return NULL; // even if this is the only element on the list, // we cannot save the strcmp, since the pszName-key // might still be different! (mismatch) // iterate over the list while(pLLE) { PHASHTABLEENTRY pHTE = (PHASHTABLEENTRY)pLLE->pObject; // quickly compare 1st character for equality // before doing the strcmp call if (*pHTE->pszName == *pszName) if (strcmp(pHTE->pszName, pszName) == 0) { // return result return pHTE->pObject; } pLLE = pLLE->pNext; } // failed return NULL; } void CHashtableLookup::clear() { // clear all the slot lists for (int i = 0; i < iSize; i++) { // check if slot was occupied if (parrLists[i] != NULL) parrLists[i]->clear(); } iSize = 0; iElements = 0; } void CHashtableLookup::rehash() { // if there are less slots than elements, // the blocking factor is expected to be high setSize(iElements); } void CHashtableLookup::setSize(int iNewSize) { // determine number of allocated elements // actually, we need the prime next to // the given number. if (iSize < iNewSize) setSize0(nextPrime(iNewSize)); } int CHashtableLookup::getElementMap(PHASHTABLEENTRY pBuffer) { int iIndex = 0; // iterate over all registered entries and dump them to the buffer // giving the caller direct access to the hashtable internals. for (int i = 0; i < iSize; i++) { // check if slot was occupied if (parrLists[i] != NULL) { // walk along any entry in that linear list PLINEARLISTENTRY pLLE = parrLists[i]->getFirst(); while (pLLE) { PHASHTABLEENTRY pHTE = (PHASHTABLEENTRY)pLLE->pObject; memcpy(&pBuffer[iIndex], pHTE, sizeof( HASHTABLEENTRY ) ); iIndex++; pLLE = parrLists[i]->getNext(pLLE); } } } // return number of elements copied return iIndex; } void CHashtableLookup::setSize0(int iNewSize) { // check if rehashing is necessary at all if (iSize == iNewSize) return; // save old array, allocate new array CLinearList** parrNew = new CLinearList* [iNewSize]; memset(parrNew, 0, sizeof(CLinearList*) * iNewSize); // convert all the slot lists for (int i = 0; i < iSize; i++) { // check if slot was occupied if (parrLists[i] != NULL) { // iterate over the slot PLINEARLISTENTRY pLLE = parrLists[i]->getFirst(); PHASHTABLEENTRY pHTE; unsigned long ulHash; while(pLLE) { // calculate new hashcode for the entry pHTE = (PHASHTABLEENTRY)pLLE->pObject; ulHash = hashcode(iNewSize, pHTE->pszName); // reinsert the pHTE into new slot if (parrNew[ulHash] == NULL) parrNew[ulHash] = new CLinearList(); parrNew[ulHash]->addLast( (void*)pHTE ); pLLE=pLLE->pNext; } // kill the slot delete parrLists[i]; parrLists[i] = NULL; } } // swap the tables iSize = iNewSize; delete [] parrLists; parrLists = parrNew; } unsigned long CHashtableLookup::nextPrime(unsigned long x) { // Return next prime number after x, unless x is a prime in which case // x is returned. if (x < 2) return 2; if (x == 3) return 3; if (x % 2 == 0) x++; unsigned long sqr = (unsigned long) sqrt((double)x) + 1; for (;;) { unsigned long n; for (n = 3; (n <= sqr) && ((x % n) != 0); n += 2) ; if (n> sqr) return x; x += 2; } } /* * The following code provides classes for special purposes, whereas * the above code is meant for general purposes. The above classes provide * excellent performance when looking up entries, whereas they're rather * slow when adding new elements to the collections. * * For the PELDR, it's more critical to have exceptionally fast adding * of the exports to the lists as this outweighs resolving imports. */

AltStyle によって変換されたページ (->オリジナル) /