CHashPage Class Reference

#include <svdhash.h>

Collaboration diagram for CHashPage:

Collaboration graph
[legend]

Public Member Functions

 CHashPage (void)
bool Allocate (unsigned int nPageSize)
 ~CHashPage (void)
void Empty (HP_DIRINDEX arg_nDepth, UINT32 arg_nHashGroup, HP_DIRINDEX arg_nDirSize)
int Insert (HP_HEAPLENGTH nRecord, UINT32 nHash, void *pRecord)
HP_DIRINDEX FindFirstKey (UINT32 nHash, unsigned int *numchecks)
HP_DIRINDEX FindNextKey (HP_DIRINDEX i, UINT32 nHash, unsigned int *numchecks)
HP_DIRINDEX FindFirst (HP_PHEAPLENGTH pnRecord, void *pRecord)
HP_DIRINDEX FindNext (HP_PHEAPLENGTH pnRecord, void *pRecord)
void HeapCopy (HP_DIRINDEX iDir, HP_PHEAPLENGTH pnRecord, void *pRecord)
void HeapFree (HP_DIRINDEX iDir)
void HeapUpdate (HP_DIRINDEX iDir, HP_HEAPLENGTH nRecord, void *pRecord)
bool WritePage (HANDLE hFile, HF_FILEOFFSET oWhere)
bool ReadPage (HANDLE hFile, HF_FILEOFFSET oWhere)
HP_DIRINDEX GetDepth (void)
bool Split (CHashPage &hp0, CHashPage &hp1)
bool Defrag (HP_HEAPLENGTH nExtra)
void GetRange (UINT32 arg_nDirDepth, UINT32 &nStart, UINT32 &nEnd)

Private Member Functions

bool HeapAlloc (HP_DIRINDEX iDir, HP_HEAPLENGTH nRecord, UINT32 nHash, void *pRecord)
void SetVariablePointers (void)
void SetFixedPointers (void)
void GetStats (HP_HEAPLENGTH nExtra, int *pnRecords, HP_HEAPLENGTH *pnAllocatedSize, int *pnGoodDirSize)

Private Attributes

unsigned char * m_pPage
unsigned int m_nPageSize
HP_PHEADER m_pHeader
HP_PHEAPOFFSET m_pDirectory
unsigned char * m_pHeapStart
unsigned char * m_pHeapEnd
HP_PTRAILER m_pTrailer
int m_iDir
int m_nProbesLeft
UINT32 m_nDirEmptyTrigger

Detailed Description

Definition at line 118 of file svdhash.h.

Constructor & Destructor Documentation

CHashPage::CHashPage ( void   ) 

Definition at line 382 of file svdhash.cpp.

References m_nPageSize, and m_pPage.

00383 {
00384     m_nPageSize = 0;
00385     m_pPage = 0;
00386 }

CHashPage::~CHashPage ( void   ) 

Definition at line 388 of file svdhash.cpp.

References m_pPage.

00389 {
00390     if (m_pPage)
00391     {
00392         delete [] m_pPage;
00393         m_pPage = 0;
00394     }
00395 }

Member Function Documentation

bool CHashPage::Allocate ( unsigned int  nPageSize  ) 

Definition at line 369 of file svdhash.cpp.

References m_nPageSize, and m_pPage.

Referenced by Defrag(), and CHashTable::Insert().

00370 {
00371     if (m_nPageSize) return false;
00372 
00373     m_nPageSize = nPageSize;
00374     m_pPage = new unsigned char[nPageSize];
00375     if (m_pPage)
00376     {
00377         return true;
00378     }
00379     return false;
00380 }

bool CHashPage::Defrag ( HP_HEAPLENGTH  nExtra  ) 

Definition at line 1194 of file svdhash.cpp.

References Allocate(), Empty(), GetStats(), HP_DIR_DELETED, HP_INSERT_SUCCESS, Insert(), IS_HP_SUCCESS, tagHPHeader::m_nDepth, tagHPHeader::m_nDirSize, tagHPHeader::m_nHashGroup, m_nPageSize, m_pHeader, m_pHeapStart, m_pPage, tagHPHeapNode::s, SetFixedPointers(), SetVariablePointers(), and tagHPHeapNode::u.

Referenced by Insert().

01195 {
01196     CHashPage *hpNew = new CHashPage;
01197     if (!hpNew) return false;
01198     if (!hpNew->Allocate(m_nPageSize))
01199     {
01200         delete hpNew;
01201         return false;
01202     }
01203 
01204     // Figure out what a good directory size is given the actual records in this page.
01205     //
01206     int   nRecords;
01207     HP_HEAPLENGTH nAllocatedSize;
01208     int   nGoodDirSize;
01209     GetStats(nExtra, &nRecords, &nAllocatedSize, &nGoodDirSize);
01210 
01211     // Initialize that type of HashPage and copy records over.
01212     //
01213     hpNew->Empty(m_pHeader->m_nDepth, m_pHeader->m_nHashGroup, nGoodDirSize);
01214     int errInserted = HP_INSERT_SUCCESS;
01215     for (int iDir = 0; iDir < m_pHeader->m_nDirSize && IS_HP_SUCCESS(errInserted); iDir++)
01216     {
01217         if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
01218         {
01219             HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[iDir]);
01220             errInserted = hpNew->Insert(pNode->u.s.nRecordSize, pNode->u.s.nHash, pNode+1);
01221         }
01222     }
01223     if (IS_HP_SUCCESS(errInserted))
01224     {
01225         // Swap buffers.
01226         //
01227         unsigned char *tmp;
01228         tmp = hpNew->m_pPage;
01229         hpNew->m_pPage = m_pPage;
01230         m_pPage = tmp;
01231 
01232         SetFixedPointers();
01233         SetVariablePointers();
01234         delete hpNew;
01235         return true;
01236     }
01237     delete hpNew;
01238     return false;
01239 }

void CHashPage::Empty ( HP_DIRINDEX  arg_nDepth,
UINT32  arg_nHashGroup,
HP_DIRINDEX  arg_nDirSize 
)

Definition at line 486 of file svdhash.cpp.

References ChoosePrimes(), HP_DIR_EMPTY, HP_NIL_OFFSET, tagHPHeader::m_nDepth, tagHPHeader::m_nDirEmptyLeft, tagHPHeader::m_nDirSize, tagHPHeader::m_nHashGroup, m_nPageSize, tagHPHeader::m_nTotalInsert, tagHPHeader::m_oFreeList, m_pDirectory, m_pHeader, m_pHeapEnd, m_pHeapStart, m_pPage, tagHPHeader::m_Primes, tagHPHeapNode::nBlockSize, tagHPHeapNode::oNext, SetFixedPointers(), SetVariablePointers(), and tagHPHeapNode::u.

Referenced by CHashFile::CreateFileSet(), Defrag(), CHashTable::Init(), and Split().

00487 {
00488     memset(m_pPage, 0, m_nPageSize);
00489 
00490     SetFixedPointers();
00491 
00492     m_pHeader->m_nDepth = arg_nDepth;
00493     m_pHeader->m_nDirSize = arg_nDirSize;
00494     m_pHeader->m_nHashGroup = arg_nHashGroup;
00495     m_pHeader->m_nTotalInsert = 0;
00496     m_pHeader->m_nDirEmptyLeft = arg_nDirSize;  // Number of entries marked HP_DIR_EMPTY.
00497     if (arg_nDirSize > 0)
00498     {
00499         ChoosePrimes(arg_nDirSize, m_pHeader->m_Primes);
00500         for (UINT32 iDir = 0; iDir < arg_nDirSize; iDir++)
00501         {
00502             m_pDirectory[iDir] = HP_DIR_EMPTY;
00503         }
00504     }
00505     SetVariablePointers();
00506 
00507     // Setup initial free list.
00508     //
00509     HP_PHEAPNODE pNode = (HP_PHEAPNODE)m_pHeapStart;
00510     pNode->nBlockSize = (HP_HEAPLENGTH)(m_pHeapEnd - m_pHeapStart);
00511     pNode->u.oNext = HP_NIL_OFFSET;
00512     m_pHeader->m_oFreeList = 0; // This is intentionally zero (i.e., m_pHeapStart - m_pHeapStart).
00513 }

HP_DIRINDEX CHashPage::FindFirst ( HP_PHEAPLENGTH  pnRecord,
void *  pRecord 
)

Definition at line 1251 of file svdhash.cpp.

References HP_DIR_DELETED, HP_DIR_EMPTY, m_iDir, tagHPHeader::m_nDirSize, m_pHeader, and m_pHeapStart.

Referenced by CHashTable::FindFirst(), and CHashTable::FindNext().

01252 {
01253     for (m_iDir = 0; m_iDir < m_pHeader->m_nDirSize; m_iDir++)
01254     {
01255         if (m_pDirectory[m_iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
01256         {
01257             HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[m_iDir]);
01258             *pnRecord = pNode->u.s.nRecordSize;
01259             memcpy(pRecord, pNode+1, pNode->u.s.nRecordSize);
01260             return m_iDir;
01261         }
01262     }
01263     return HP_DIR_EMPTY;
01264 }

HP_DIRINDEX CHashPage::FindFirstKey ( UINT32  nHash,
unsigned int *  numchecks 
)

Definition at line 709 of file svdhash.cpp.

References HP_DIR_DELETED, HP_DIR_EMPTY, tagHPHeader::m_nDepth, tagHPHeader::m_nDirSize, tagHPHeader::m_nHashGroup, m_nProbesLeft, m_pHeader, m_pHeapStart, tagHPHeader::m_Primes, tagHPHeapNode::s, and tagHPHeapNode::u.

Referenced by CHashTable::FindFirstKey(), and CHashFile::FindFirstKey().

00710 {
00711 #ifdef HP_PROTECTION
00712     // First, is this page dealing with keys like this at all?
00713     //
00714     HP_DIRINDEX nDepth = m_pHeader->m_nDepth;
00715     if ((nHash & anGroupMask[nDepth]) != m_pHeader->m_nHashGroup)
00716         return HP_DIR_EMPTY;
00717 #endif // HP_PROTECTION
00718 
00719     const int nDirSize = m_pHeader->m_nDirSize;
00720 
00721     // Where do we begin our first probe?
00722     //
00723     int iDir = (nHash >> 4) % nDirSize;
00724     int sOffset = m_pDirectory[iDir];
00725     if ((unsigned int)sOffset < HP_DIR_DELETED)
00726     {
00727         HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + sOffset);
00728         if (pNode->u.s.nHash == nHash)
00729         {
00730             m_nProbesLeft = nDirSize - 1;
00731             *numchecks = 1;
00732             return iDir;
00733         }
00734     }
00735     else if (HP_DIR_EMPTY == sOffset)
00736     {
00737         m_nProbesLeft = nDirSize;
00738         *numchecks = 0;
00739         return HP_DIR_EMPTY;
00740     }
00741 
00742     //    HP_DIR_DELETED == sOffset
00743     // || pNode->u.s.nHash != nHash
00744 
00745     m_nProbesLeft = nDirSize - 1;
00746     int di = m_pHeader->m_Primes[nHash & 15];
00747 
00748     iDir += di;
00749     if (iDir >= nDirSize)
00750     {
00751         iDir -= nDirSize;
00752     }
00753     sOffset = m_pDirectory[iDir];
00754 
00755     while (sOffset != HP_DIR_EMPTY)
00756     {
00757         m_nProbesLeft--;
00758         if (sOffset != HP_DIR_DELETED)
00759         {
00760             HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + sOffset);
00761             if (pNode->u.s.nHash == nHash)
00762             {
00763                 *numchecks = nDirSize - m_nProbesLeft;
00764                 return iDir;
00765             }
00766         }
00767 
00768         if (!m_nProbesLeft) break;
00769 
00770         iDir += di;
00771         if (iDir >= nDirSize)
00772         {
00773             iDir -= nDirSize;
00774         }
00775         sOffset = m_pDirectory[iDir];
00776     }
00777     *numchecks = nDirSize - m_nProbesLeft;
00778     return HP_DIR_EMPTY;
00779 }

HP_DIRINDEX CHashPage::FindNext ( HP_PHEAPLENGTH  pnRecord,
void *  pRecord 
)

Definition at line 1266 of file svdhash.cpp.

References HP_DIR_DELETED, HP_DIR_EMPTY, m_iDir, tagHPHeader::m_nDirSize, m_pHeader, and m_pHeapStart.

Referenced by CHashTable::FindNext().

01267 {
01268     for ( m_iDir++; m_iDir < m_pHeader->m_nDirSize; m_iDir++)
01269     {
01270         if (m_pDirectory[m_iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
01271         {
01272             HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[m_iDir]);
01273             *pnRecord = pNode->u.s.nRecordSize;
01274             memcpy(pRecord, pNode+1, pNode->u.s.nRecordSize);
01275             return m_iDir;
01276         }
01277     }
01278     return HP_DIR_EMPTY;
01279 }

HP_DIRINDEX CHashPage::FindNextKey ( HP_DIRINDEX  i,
UINT32  nHash,
unsigned int *  numchecks 
)

Definition at line 785 of file svdhash.cpp.

References HP_DIR_DELETED, HP_DIR_EMPTY, tagHPHeader::m_nDepth, tagHPHeader::m_nDirSize, tagHPHeader::m_nHashGroup, m_nProbesLeft, m_pHeader, m_pHeapStart, tagHPHeader::m_Primes, tagHPHeapNode::s, and tagHPHeapNode::u.

Referenced by CHashTable::FindNextKey(), and CHashFile::FindNextKey().

00786 {
00787     *numchecks = 0;
00788 
00789 #ifdef HP_PROTECTION
00790     // First, is this page dealing with keys like this at all?
00791     //
00792     HP_DIRINDEX nDepth = m_pHeader->m_nDepth;
00793     if ((nHash & anGroupMask[nDepth]) != m_pHeader->m_nHashGroup)
00794         return HP_DIR_EMPTY;
00795 #endif // HP_PROTECTION
00796 
00797     int nDirSize = m_pHeader->m_nDirSize;
00798 
00799     // Where do we begin our first probe? If this is the first call, i will be HP_DIR_EMPTY.
00800     // On calls after that, it will be what we returned on the previous call.
00801     //
00802     int di = m_pHeader->m_Primes[nHash & 15];
00803     iDir += di;
00804     if (iDir >= nDirSize)
00805     {
00806         iDir -= nDirSize;
00807     }
00808     while (m_nProbesLeft && (m_pDirectory[iDir] != HP_DIR_EMPTY))
00809     {
00810         m_nProbesLeft--;
00811         (*numchecks)++;
00812         if (m_pDirectory[iDir] != HP_DIR_DELETED)
00813         {
00814             if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
00815             {
00816                 HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[iDir]);
00817                 if (pNode->u.s.nHash == nHash) return iDir;
00818             }
00819         }
00820         iDir += di;
00821         if (iDir >= nDirSize)
00822         {
00823             iDir -= nDirSize;
00824         }
00825     }
00826     return HP_DIR_EMPTY;
00827 }

HP_DIRINDEX CHashPage::GetDepth ( void   ) 

Definition at line 1185 of file svdhash.cpp.

References tagHPHeader::m_nDepth, and m_pHeader.

Referenced by CHashTable::Insert(), and CHashFile::RebuildDirectory().

01186 {
01187     return m_pHeader->m_nDepth;
01188 }

void CHashPage::GetRange ( UINT32  arg_nDirDepth,
UINT32 &  nStart,
UINT32 &  nEnd 
)

Definition at line 1035 of file svdhash.cpp.

Referenced by CHashFile::AllocateEmptyPage(), CHashTable::FindFirstKey(), CHashFile::FindFirstKey(), CHashTable::Insert(), CHashFile::Insert(), CHashFile::ReadCache(), and CHashFile::RebuildDirectory().

01040 {
01041     UINT32 nBase = 0;
01042     int nShift = 32 - arg_nDirDepth;
01043     if (arg_nDirDepth > 0)
01044     {
01045         nBase = m_pHeader->m_nHashGroup >> nShift;
01046     }
01047     UINT32 ulMask = anGroupMask[nShift + m_pHeader->m_nDepth];
01048     nStart = nBase & ulMask;
01049     nEnd   = nBase | ~ulMask;
01050 }

void CHashPage::GetStats ( HP_HEAPLENGTH  nExtra,
int *  pnRecords,
HP_HEAPLENGTH *  pnAllocatedSize,
int *  pnGoodDirSize 
) [private]

Definition at line 407 of file svdhash.cpp.

References EXPAND_TO_BOUNDARY, FILL_FACTOR, HP_DIR_DELETED, HP_MIN_HEAP_ALLOC, HP_SIZEOF_HEAPNODE, tagHPHeapNode::s, and tagHPHeapNode::u.

Referenced by Defrag(), and Split().

00413 {
00414     unsigned nSize = 0;
00415     unsigned nCount = 0;
00416     unsigned nGoodDirSize = 100;
00417 
00418     // Count and measure all the records in this page.
00419     //
00420     for (UINT32 iDir = 0; iDir < m_pHeader->m_nDirSize; iDir++)
00421     {
00422         if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
00423         {
00424             nCount++;
00425             HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[iDir]);
00426             HP_HEAPLENGTH nRequired = EXPAND_TO_BOUNDARY(
00427                 HP_SIZEOF_HEAPNODE + pNode->u.s.nRecordSize);
00428 
00429             if (nRequired < HP_MIN_HEAP_ALLOC)
00430             {
00431                 nRequired = HP_MIN_HEAP_ALLOC;
00432             }
00433             nSize += nRequired;
00434         }
00435     }
00436     *pnRecords = nCount;
00437     *pnAllocatedSize = nSize;
00438 
00439     // If we have records to talk about, or even if we are trying to reserve
00440     // space, then do the math.
00441     //
00442     if (  nExtra != 0
00443        || nCount != 0)
00444     {
00445         UINT32 nSpace = (UINT32)( ((unsigned char *)m_pTrailer)
00446                                 - ((unsigned char *)m_pDirectory));
00447         UINT32 nMinDirSize = nCount;
00448         UINT32 nMaxDirSize = (nSpace - nSize)/sizeof(HP_HEAPOFFSET);
00449 
00450         if (nExtra)
00451         {
00452             nExtra += HP_SIZEOF_HEAPNODE;
00453             if (nExtra < HP_MIN_HEAP_ALLOC)
00454             {
00455                 nExtra = HP_MIN_HEAP_ALLOC;
00456             }
00457             nExtra = EXPAND_TO_BOUNDARY(nExtra);
00458             nCount++;
00459             nSize += nExtra;
00460         }
00461 
00462 #define FILL_FACTOR 1
00463         UINT32 nAverageSize = (nSize + nCount/2)/nCount;
00464         UINT32 nHeapGoal = (nSpace * nAverageSize)/(nAverageSize + sizeof(HP_HEAPOFFSET) + FILL_FACTOR);
00465         nGoodDirSize = (UINT32)((nSpace - nHeapGoal + sizeof(HP_HEAPOFFSET)/2)/sizeof(HP_HEAPOFFSET));
00466         if (nGoodDirSize < nMinDirSize)
00467         {
00468             nGoodDirSize = nMinDirSize;
00469         }
00470         else if (nGoodDirSize > nMaxDirSize)
00471         {
00472             nGoodDirSize = nMaxDirSize;
00473         }
00474     }
00475     *pnGoodDirSize = nGoodDirSize;
00476 }

bool CHashPage::HeapAlloc ( HP_DIRINDEX  iDir,
HP_HEAPLENGTH  nRecord,
UINT32  nHash,
void *  pRecord 
) [private]

Definition at line 832 of file svdhash.cpp.

References EXPAND_TO_BOUNDARY, HP_DIR_DELETED, HP_DIR_EMPTY, HP_NIL_OFFSET, HP_SIZEOF_HEAPNODE, tagHPHeader::m_nDirEmptyLeft, tagHPHeader::m_oFreeList, m_pHeader, m_pHeapStart, tagHPHeapNode::nBlockSize, tagHPHeapNode::oNext, tagHPHeapNode::s, and tagHPHeapNode::u.

Referenced by Insert().

00833 {
00834     //ValidateFreeList();
00835     if (m_pDirectory[iDir] < HP_DIR_DELETED)
00836     {
00837         return false;
00838     }
00839 
00840     // How much space do we need?
00841     //
00842     HP_HEAPLENGTH nRequired = EXPAND_TO_BOUNDARY(HP_SIZEOF_HEAPNODE + nRecord);
00843     if (nRequired < HP_MIN_HEAP_ALLOC)
00844     {
00845         nRequired = HP_MIN_HEAP_ALLOC;
00846     }
00847 
00848     // Search through the free list for something of the right size.
00849     //
00850     HP_HEAPOFFSET oNext = m_pHeader->m_oFreeList;
00851     HP_PHEAPOFFSET poPrev = &(m_pHeader->m_oFreeList);
00852     while (oNext != HP_NIL_OFFSET)
00853     {
00854 #if 0
00855         if (!ValidateFreeBlock(oPrevious))
00856         {
00857             ValidateFreeList();
00858             return false;
00859         }
00860 #endif // 0
00861         unsigned char *pBlockStart = m_pHeapStart + oNext;
00862         HP_PHEAPNODE pNode = (HP_PHEAPNODE)pBlockStart;
00863         if (pNode->nBlockSize >= nRequired)
00864         {
00865             // We found something of the correct size.
00866             //
00867             // Do we cut it into two blocks or take the whole thing?
00868             //
00869             HP_HEAPLENGTH nNewBlockSize = pNode->nBlockSize - nRequired;
00870             if (nNewBlockSize >= EXPAND_TO_BOUNDARY(HP_MIN_HEAP_ALLOC+1))
00871             {
00872                 // There is enough for leftovers, split it.
00873                 //
00874                 HP_PHEAPNODE pNewNode = (HP_PHEAPNODE)(pBlockStart + nRequired);
00875                 pNewNode->nBlockSize = nNewBlockSize;
00876                 pNewNode->u.oNext = pNode->u.oNext;
00877 
00878                 // Update current node.
00879                 //
00880                 pNode->nBlockSize = nRequired;
00881                 pNode->u.s.nHash = nHash;
00882                 pNode->u.s.nRecordSize = nRecord;
00883 
00884                 // Update Free list pointer.
00885                 //
00886                 *poPrev += nRequired;
00887             }
00888             else
00889             {
00890                 // Take the whole thing.
00891                 //
00892                 *poPrev = pNode->u.oNext;
00893                 pNode->u.s.nHash = nHash;
00894                 pNode->u.s.nRecordSize = nRecord;
00895             }
00896             memcpy(pNode+1, pRecord, nRecord);
00897             if (m_pDirectory[iDir] == HP_DIR_EMPTY)
00898             {
00899                 m_pHeader->m_nDirEmptyLeft--;
00900             }
00901             m_pDirectory[iDir] = (HP_HEAPOFFSET)(pBlockStart - m_pHeapStart);
00902             return true;
00903         }
00904         poPrev = &(pNode->u.oNext);
00905         oNext = pNode->u.oNext;
00906     }
00907     return false;
00908 }

void CHashPage::HeapCopy ( HP_DIRINDEX  iDir,
HP_PHEAPLENGTH  pnRecord,
void *  pRecord 
)

Definition at line 937 of file svdhash.cpp.

References HP_DIR_DELETED, m_pHeapStart, tagHPHeapNode::s, and tagHPHeapNode::u.

Referenced by CHashTable::Copy(), and CHashFile::Copy().

00938 {
00939     if (pnRecord == 0 || pRecord == 0) return;
00940 
00941     if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
00942     {
00943         HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[iDir]);
00944 
00945         // Copy the record.
00946         //
00947         *pnRecord = pNode->u.s.nRecordSize;
00948         memcpy(pRecord, pNode+1, pNode->u.s.nRecordSize);
00949     }
00950 }

void CHashPage::HeapFree ( HP_DIRINDEX  iDir  ) 

Definition at line 913 of file svdhash.cpp.

References HP_DIR_DELETED, tagHPHeader::m_oFreeList, m_pHeader, m_pHeapStart, tagHPHeapNode::nBlockSize, tagHPHeapNode::oNext, and tagHPHeapNode::u.

Referenced by CHashTable::Remove(), and CHashFile::Remove().

00914 {
00915     //ValidateFreeList();
00916     if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
00917     {
00918         HP_HEAPOFFSET oBlock = m_pDirectory[iDir];
00919         HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + oBlock);
00920 
00921         // Clear it. The reason for clearing is that it makes debugging easier,
00922         // and also, if the file is compressed by the file system, a string
00923         // of zeros will yield a smaller result.
00924         //
00925         HP_HEAPLENGTH nBlockSize = pNode->nBlockSize;
00926         memset(pNode, 0, nBlockSize);
00927         pNode->nBlockSize = nBlockSize;
00928 
00929         // Push it onto the free list.
00930         //
00931         pNode->u.oNext = m_pHeader->m_oFreeList;
00932         m_pHeader->m_oFreeList = oBlock;
00933         m_pDirectory[iDir] = HP_DIR_DELETED;
00934     }
00935 }

void CHashPage::HeapUpdate ( HP_DIRINDEX  iDir,
HP_HEAPLENGTH  nRecord,
void *  pRecord 
)

Definition at line 952 of file svdhash.cpp.

References HP_DIR_DELETED, m_pHeapStart, tagHPHeapNode::s, and tagHPHeapNode::u.

Referenced by CHashTable::Update().

00953 {
00954     if (nRecord == 0 || pRecord == 0) return;
00955 
00956     if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
00957     {
00958         HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[iDir]);
00959 
00960         if (pNode->u.s.nRecordSize != nRecord) return;
00961         memcpy(pNode+1, pRecord, nRecord);
00962     }
00963 }

int CHashPage::Insert ( HP_HEAPLENGTH  nRecord,
UINT32  nHash,
void *  pRecord 
)

Definition at line 646 of file svdhash.cpp.

References Defrag(), ENDLINE, HeapAlloc(), HP_DIR_DELETED, HP_INSERT_ERROR_FULL, HP_INSERT_ERROR_ILLEGAL, HP_INSERT_SUCCESS, HP_INSERT_SUCCESS_DEFRAG, Log, tagHPHeader::m_nDepth, tagHPHeader::m_nDirEmptyLeft, m_nDirEmptyTrigger, tagHPHeader::m_nDirSize, tagHPHeader::m_nHashGroup, m_nProbesLeft, tagHPHeader::m_nTotalInsert, m_pHeader, tagHPHeader::m_Primes, and CLogFile::WriteString().

Referenced by Defrag(), CHashTable::Insert(), CHashFile::Insert(), and Split().

00647 {
00648     int ret = HP_INSERT_SUCCESS;
00649     m_pHeader->m_nTotalInsert++;
00650     for (int nTries = 0; nTries < 2; nTries++)
00651     {
00652 #ifdef HP_PROTECTION
00653         // First, is this page dealing with keys like this at all?
00654         //
00655         HP_DIRINDEX nDepth = m_pHeader->m_nDepth;
00656         if ((nHash & anGroupMask[nDepth]) != m_pHeader->m_nHashGroup)
00657         {
00658             Log.WriteString("CHashPage::Insert - Inserting into the wrong page." ENDLINE);
00659             return HP_INSERT_ERROR_ILLEGAL;
00660         }
00661 #endif // HP_PROTECTION
00662 
00663         // Where do we begin our first probe?
00664         //
00665         int di   = m_pHeader->m_Primes[nHash & 15];
00666         int iDir = (nHash >> 4) % (m_pHeader->m_nDirSize);
00667         m_nProbesLeft = m_pHeader->m_nDirSize;
00668         while (m_nProbesLeft-- && (m_pDirectory[iDir] < HP_DIR_DELETED))
00669         {
00670             iDir += di;
00671             if (iDir >= (m_pHeader->m_nDirSize))
00672             {
00673                 iDir -= (m_pHeader->m_nDirSize);
00674             }
00675         }
00676         if (m_nProbesLeft >= 0)
00677         {
00678             if (m_pHeader->m_nDirEmptyLeft < m_nDirEmptyTrigger)
00679             {
00680                 if (!Defrag(nRecord))
00681                 {
00682                     return HP_INSERT_ERROR_FULL;
00683                 }
00684                 ret = HP_INSERT_SUCCESS_DEFRAG;
00685                 continue;
00686             }
00687             if (HeapAlloc(iDir, nRecord, nHash, pRecord))
00688             {
00689                 return ret;
00690             }
00691         }
00692         if (!Defrag(nRecord))
00693         {
00694             return HP_INSERT_ERROR_FULL;
00695         }
00696         ret = HP_INSERT_SUCCESS_DEFRAG;
00697     }
00698     return HP_INSERT_ERROR_FULL;
00699 }

bool CHashPage::ReadPage ( HANDLE  hFile,
HF_FILEOFFSET  oWhere 
)

Definition at line 1143 of file svdhash.cpp.

References cnt, cs_dbreads, Log, m_nPageSize, m_pPage, mudstate, MuxAlarm, SetFixedPointers(), SetVariablePointers(), statedata::shutdown_flag, CMuxAlarm::Sleep(), time_1s, and CLogFile::tinyprintf().

01144 {
01145     cs_dbreads++;
01146     SetFixedPointers();
01147     int cnt = 60;
01148     for ( ; cnt; MuxAlarm.Sleep(time_1s), cnt--)
01149     {
01150 #ifdef HAVE_PREAD
01151         int cc = pread(hFile, m_pPage, m_nPageSize, oWhere);
01152 #else
01153         if (lseek(hFile, oWhere, SEEK_SET) == (off_t)-1)
01154         {
01155             Log.tinyprintf("CHashPage::Read - lseek error %u." ENDLINE, errno);
01156             continue;
01157         }
01158         int cc = read(hFile, m_pPage, m_nPageSize);
01159 #endif // HAVE_PREAD
01160         if ((int)m_nPageSize != cc)
01161         {
01162             if (cc == -1)
01163             {
01164                 Log.tinyprintf("CHashPage::Read - read error %u." ENDLINE, errno);
01165             }
01166             else
01167             {
01168                 // Our read request was only partially filled. Surrender.
01169                 //
01170                 Log.tinyprintf("CHashPage::Read - partial read." ENDLINE);
01171             }
01172             continue;
01173         }
01174         SetVariablePointers();
01175         return true;
01176     }
01177 
01178     // Don't struggle further.  You'll just make it worse.
01179     //
01180     mudstate.shutdown_flag = true;
01181     return false;
01182 }

void CHashPage::SetFixedPointers ( void   )  [private]

Definition at line 479 of file svdhash.cpp.

References m_nPageSize, m_pDirectory, m_pHeader, m_pPage, and m_pTrailer.

Referenced by Defrag(), Empty(), and ReadPage().

00480 {
00481     m_pHeader = (HP_PHEADER)m_pPage;
00482     m_pDirectory = (HP_PHEAPOFFSET)(m_pHeader+1);
00483     m_pTrailer = (HP_PTRAILER)(m_pPage + m_nPageSize - sizeof(HP_TRAILER));
00484 }

void CHashPage::SetVariablePointers ( void   )  [private]

Definition at line 1241 of file svdhash.cpp.

References m_nDirEmptyTrigger, tagHPHeader::m_nDirSize, m_pHeader, m_pHeapEnd, m_pHeapStart, and m_pTrailer.

Referenced by Defrag(), Empty(), and ReadPage().

01242 {
01243     m_pHeapStart = (unsigned char *)(m_pDirectory + m_pHeader->m_nDirSize);
01244     m_pHeapEnd = (unsigned char *)(m_pTrailer);
01245 
01246     // If less than 14.29% of the entries are empty, then do another Defrag.
01247     //
01248     m_nDirEmptyTrigger = (m_pHeader->m_nDirSize)/7;
01249 }

bool CHashPage::Split ( CHashPage &  hp0,
CHashPage &  hp1 
)

Definition at line 965 of file svdhash.cpp.

References Empty(), ENDLINE, GetStats(), HP_DIR_DELETED, Insert(), IS_HP_SUCCESS, Log, tagHPHeader::m_nDepth, tagHPHeader::m_nDirSize, tagHPHeader::m_nHashGroup, m_pHeader, m_pHeapStart, CLogFile::tinyprintf(), and CLogFile::WriteString().

Referenced by CHashTable::Insert().

00966 {
00967     // Figure out what a good directory size is given the actual records in this page.
00968     //
00969     int   nRecords;
00970     HP_HEAPLENGTH nAllocatedSize;
00971     int   nGoodDirSize;
00972     GetStats(0, &nRecords, &nAllocatedSize, &nGoodDirSize);
00973     if (nRecords == 0)
00974     {
00975         Log.WriteString("Why are we splitting a page with no records in it?" ENDLINE);
00976         return false;
00977     }
00978 
00979     // Initialize that type of HashPage and copy records over.
00980     //
00981     int   nNewDepth = m_pHeader->m_nDepth + 1;
00982     UINT32 nBitMask = 1 << (32-nNewDepth);
00983     UINT32 nHashGroup0 = m_pHeader->m_nHashGroup & (~nBitMask);
00984     UINT32 nHashGroup1 = nHashGroup0 | nBitMask;
00985     hp0.Empty(nNewDepth, nHashGroup0, nGoodDirSize);
00986     hp1.Empty(nNewDepth, nHashGroup1, nGoodDirSize);
00987     for (int iDir = 0; iDir < m_pHeader->m_nDirSize; iDir++)
00988     {
00989         if (m_pDirectory[iDir] < HP_DIR_DELETED) // ValidateAllocatedBlock(iDir))
00990         {
00991             HP_PHEAPNODE pNode = (HP_PHEAPNODE)(m_pHeapStart + m_pDirectory[iDir]);
00992             UINT32 nHash = pNode->u.s.nHash;
00993             if ((nHash & anGroupMask[nNewDepth]) == (nHashGroup0 & anGroupMask[nNewDepth]))
00994             {
00995                 if (!IS_HP_SUCCESS(hp0.Insert(pNode->u.s.nRecordSize, nHash, pNode+1)))
00996                 {
00997                     Log.WriteString("CHashPage::Split - Ran out of room." ENDLINE);
00998                     return false;
00999                 }
01000             }
01001             else if ((nHash & anGroupMask[nNewDepth]) == (nHashGroup1 & anGroupMask[nNewDepth]))
01002             {
01003                 if (!IS_HP_SUCCESS(hp1.Insert(pNode->u.s.nRecordSize, nHash, pNode+1)))
01004                 {
01005                     Log.WriteString("CHashPage::Split - Ran out of room." ENDLINE);
01006                     return false;
01007                 }
01008             }
01009             else
01010             {
01011                 Log.WriteString("CHashPage::Split - This record fits in neither page...lost." ENDLINE);
01012                 return false;
01013             }
01014         }
01015     }
01016 #if 0
01017     int nRecords0, nRecords1;
01018     HP_HEAPLENGTH nAllocatedSize0, nAllocatedSize1;
01019     int    temp;
01020     hp0.GetStats(0, &nRecords0, &nAllocatedSize0, &temp);
01021     hp1.GetStats(0, &nRecords1, &nAllocatedSize1, &temp);
01022     Log.tinyprintf("Split (%d %d) page into (%d %d) and (%d %d)" ENDLINE,
01023         nRecords, nAllocatedSize, nRecords0, nAllocatedSize0, nRecords1,
01024         nAllocatedSize1);
01025     if (nRecords0 + nRecords1 != nRecords)
01026     {
01027         Log.WriteString("Lost something" ENDLINE);
01028         return false;
01029     }
01030 #endif // 0
01031     return true;
01032 }

bool CHashPage::WritePage ( HANDLE  hFile,
HF_FILEOFFSET  oWhere 
)

Definition at line 1104 of file svdhash.cpp.

References cnt, cs_dbwrites, Log, m_nPageSize, m_pPage, mudstate, MuxAlarm, statedata::shutdown_flag, CMuxAlarm::Sleep(), time_1s, and CLogFile::tinyprintf().

01105 {
01106     cs_dbwrites++;
01107     int cnt = 60;
01108     for ( ; cnt; MuxAlarm.Sleep(time_1s), cnt--)
01109     {
01110 #ifdef HAVE_PWRITE
01111         int cc = pwrite(hFile, m_pPage, m_nPageSize, oWhere);
01112 #else
01113         if (lseek(hFile, oWhere, SEEK_SET) == (off_t)-1)
01114         {
01115             Log.tinyprintf("CHashPage::Write - lseek error %u." ENDLINE, errno);
01116             continue;
01117         }
01118         int cc = write(hFile, m_pPage, m_nPageSize);
01119 #endif // HAVE_PWRITE
01120         if ((int)m_nPageSize != cc)
01121         {
01122             if (cc == -1)
01123             {
01124                 Log.tinyprintf("CHashPage::Write - write error %u." ENDLINE, errno);
01125             }
01126             else
01127             {
01128                 // Our write request was only partially filled. The disk is
01129                 // probably full.
01130                 //
01131                 Log.tinyprintf("CHashPage::Write - partial write." ENDLINE);
01132             }
01133         }
01134         return true;
01135     }
01136 
01137     // Don't struggle further.  You'll just make it worse.
01138     //
01139     mudstate.shutdown_flag = true;
01140     return false;
01141 }

Field Documentation

int CHashPage::m_iDir [private]

Definition at line 129 of file svdhash.h.

Referenced by FindFirst(), and FindNext().

UINT32 CHashPage::m_nDirEmptyTrigger [private]

Definition at line 131 of file svdhash.h.

Referenced by Insert(), and SetVariablePointers().

unsigned int CHashPage::m_nPageSize [private]

Definition at line 122 of file svdhash.h.

Referenced by Allocate(), CHashPage(), Defrag(), Empty(), ReadPage(), SetFixedPointers(), and WritePage().

int CHashPage::m_nProbesLeft [private]

Definition at line 130 of file svdhash.h.

Referenced by FindFirstKey(), FindNextKey(), and Insert().

HP_PHEAPOFFSET CHashPage::m_pDirectory [private]

Definition at line 124 of file svdhash.h.

Referenced by Empty(), and SetFixedPointers().

HP_PHEADER CHashPage::m_pHeader [private]

Definition at line 123 of file svdhash.h.

Referenced by Defrag(), Empty(), FindFirst(), FindFirstKey(), FindNext(), FindNextKey(), GetDepth(), HeapAlloc(), HeapFree(), Insert(), SetFixedPointers(), SetVariablePointers(), and Split().

unsigned char* CHashPage::m_pHeapEnd [private]

Definition at line 126 of file svdhash.h.

Referenced by Empty(), and SetVariablePointers().

unsigned char* CHashPage::m_pHeapStart [private]

Definition at line 125 of file svdhash.h.

Referenced by Defrag(), Empty(), FindFirst(), FindFirstKey(), FindNext(), FindNextKey(), HeapAlloc(), HeapCopy(), HeapFree(), HeapUpdate(), SetVariablePointers(), and Split().

unsigned char* CHashPage::m_pPage [private]

Definition at line 121 of file svdhash.h.

Referenced by Allocate(), CHashPage(), Defrag(), Empty(), ReadPage(), SetFixedPointers(), WritePage(), and ~CHashPage().

HP_PTRAILER CHashPage::m_pTrailer [private]

Definition at line 127 of file svdhash.h.

Referenced by SetFixedPointers(), and SetVariablePointers().

The documentation for this class was generated from the following files:
Generated on Mon May 28 04:40:24 2007 for MUX by  doxygen 1.4.7