// Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. //***************************************************************************** // RecordPool.cpp -- Implementation of record heaps. // // //***************************************************************************** #include "stdafx.h" #include #define RECORDPOOL_GROW_FACTOR 8 #define RECORDPOOL_GROW_MAX 2048 #define RECORDPOOL_GROW_MINROWS 2 #define RECORDPOOL_GROW_DEFAULTROWS 16 HRESULT RecordPool::InitNew( UINT32 cbRec, // Record size. UINT32 cRecsInit) // Initial guess of count of record. { HRESULT hr; S_UINT32 cbGrow; // Initial grow size of the pool. // Size of each record is fixed. m_cbRec = cbRec; if (cRecsInit > 0) { cbGrow = S_UINT32(cbRec) * S_UINT32(cRecsInit); } else { cbGrow = S_UINT32(cbRec) * S_UINT32(RECORDPOOL_GROW_DEFAULTROWS); } if (cbGrow.IsOverflow()) { Debug_ReportInternalError("Growing record pool overflowed."); return CLDB_E_INTERNALERROR; } m_ulGrowInc = cbGrow.Value(); IfFailRet(StgPool::InitNew()); // If there is an initial size for the record pool, grow to that now. if (cRecsInit > 0) { if (!Grow(cbGrow.Value())) return E_OUTOFMEMORY; } return S_OK; } // RecordPool::InitNew //***************************************************************************** // Load a Record heap from persisted memory. If a copy of the data is made // (so that it may be updated), then a new hash table is generated which can // be used to elminate duplicates with new Records. //***************************************************************************** HRESULT RecordPool::InitOnMem( ULONG cbRec, // Record size. void *pData, // Predefined data. ULONG iSize, // Size of data. BOOL fReadOnly) // true if append is forbidden. { HRESULT hr; m_cbRec = cbRec; // Let base class init our memory structure. IfFailRet(StgPool::InitOnMem(pData, iSize, fReadOnly)); // For init on existing mem case. if ((pData != NULL) && (iSize != 0)) { // If we are doing an update in place don't make a copy // If we cannot update, then we don't need a hash table. if (fReadOnly) return S_OK; // Other wise copy the memory to do the update IfFailRet(TakeOwnershipOfInitMem()); } return S_OK; } // RecordPool::InitOnMem //***************************************************************************** // Allocate memory if we don't have any, or grow what we have. If successful, // then at least iRequired bytes will be allocated. //***************************************************************************** bool RecordPool::Grow( // true if successful. ULONG iRequired) // Min required bytes to allocate. { // Allocate the memory. if (!StgPool::Grow(iRequired)) return false; // Zero the new memory. memset(GetNextLocation(), 0, GetCbSegAvailable()); return true; } // bool RecordProol::Grow() //***************************************************************************** // The Record will be added to the pool. The index of the Record in the pool // is returned in *piIndex. If the Record is already in the pool, then the // index will be to the existing copy of the Record. //***************************************************************************** HRESULT RecordPool::AddRecord( BYTE **ppRecord, UINT32 *pnIndex) // Return 1-based index of Record here. { _ASSERTE(pnIndex != NULL); // Space on heap for new Record? if (m_cbRec > GetCbSegAvailable()) { if (!Grow(m_cbRec)) { *ppRecord = NULL; return E_OUTOFMEMORY; } } // Records should be aligned on record boundaries. _ASSERTE((GetNextOffset() % m_cbRec) == 0); // Copy the Record to the heap. *ppRecord = GetNextLocation(); // Give the 1-based index back to caller. *pnIndex = (GetNextOffset() / m_cbRec) + 1; // Update heap counters. SegAllocate(m_cbRec); return S_OK; } // RecordPool::AddRecord //***************************************************************************** // Insert a Record into the pool. The index of the Record before which to // insert is specified. Shifts all records down. Return a pointer to the // new record. //***************************************************************************** HRESULT RecordPool::InsertRecord( UINT32 nIndex, // [IN] Insert record before this. BYTE **ppRecord) { HRESULT hr; StgPoolSeg *pCurSeg; // Current segment. StgPoolSeg *pPrevSeg; // Previous segment. BYTE *pSegEnd; // Last record in a segment. BYTE *pFrom; // A copy/move source. ULONG cbMove; // Bytes to move. BYTE *pNew; // New record. // Notice the case of appending. if (nIndex == (Count() + 1)) { UINT32 nNewIndex_Ignore; return AddRecord(ppRecord, &nNewIndex_Ignore); } // If past end or before beginning, invalid. if ((nIndex > Count()) || (nIndex == 0)) { Debug_ReportError("Invalid index passed for inserting record."); return CLDB_E_INDEX_NOTFOUND; } // This code works by allocating a new record at the end. // The last record is moved to the new end record. // Working backwards through the chained segments, // shift the segment by one record, so the empty record // is at the start of the segment instead of the end. // copy the last record of the previous segment to the // newly emptied first record of the current segment. // When the segment containing the insert point is finally // reached, its last record is empty (from above loop), so // shift from the insertion point to the end-1 by one record. // Current last record. pCurSeg = m_pCurSeg; IfFailRet(GetRecord(Count(), &pSegEnd)); _ASSERTE(hr == S_OK); // Add an empty record to the end of the heap. { UINT32 nLastRecordIndex_Ignore; IfFailRet(AddRecord(&pNew, &nLastRecordIndex_Ignore)); } // Copy the current last record to the new record. memcpy(pNew, pSegEnd, m_cbRec); // While the insert location is prior to the current segment, while (nIndex < GetIndexForRecord(pCurSeg->m_pSegData)) { // Shift the segment up by one record. cbMove = (ULONG)(pSegEnd - pCurSeg->m_pSegData); memmove(pCurSeg->m_pSegData + m_cbRec, pCurSeg->m_pSegData, cbMove); // Find the previous segment. pPrevSeg = this; while (pPrevSeg->m_pNextSeg != pCurSeg) { pPrevSeg = pPrevSeg->m_pNextSeg; } // Copy the final record of the previous segment to the start of this one. pSegEnd = pPrevSeg->m_pSegData+pPrevSeg->m_cbSegNext-m_cbRec; memcpy(pCurSeg->m_pSegData, pSegEnd, m_cbRec); // Make the previous segment the current segment. pCurSeg = pPrevSeg; } // Shift at the insert location, forward by one. IfFailRet(GetRecord(nIndex, &pFrom)); _ASSERTE(hr == S_OK); cbMove = (ULONG)(pSegEnd - pFrom); memmove(pFrom + m_cbRec, pFrom, cbMove); *ppRecord = pFrom; return S_OK; } // RecordPool::InsertRecord //***************************************************************************** // Return a pointer to a Record given an index previously handed out by // AddRecord or FindRecord. //***************************************************************************** HRESULT RecordPool::GetRecord( UINT32 nIndex, // 1-based index of Record in pool. BYTE **ppRecord) { MetaData::DataBlob record; if (nIndex == 0) { Debug_ReportError("Invalid index 0 passed."); *ppRecord = NULL; return CLDB_E_INDEX_NOTFOUND; } // Convert to 0-based internal form, defer to implementation. HRESULT hr = GetData((nIndex - 1) * m_cbRec, &record); if (FAILED(hr)) { *ppRecord = NULL; return hr; } _ASSERTE(record.ContainsData(m_cbRec)); *ppRecord = record.GetDataPointer(); return hr; } // RecordPool::GetRecord //***************************************************************************** // Return the first record in a pool, and set up a context for fast // iterating through the pool. Note that this scheme does pretty minimal // error checking. //***************************************************************************** void *RecordPool::GetFirstRecord( // Pointer to Record in pool. void **pContext) // Store context here. { StgPoolSeg **ppSeg = reinterpret_cast(pContext); *ppSeg = static_cast(this); return (*ppSeg)->m_pSegData; } // void *RecordPool::GetFirstRecord() //***************************************************************************** // Given a pointer to a record, return a pointer to the next record. // Note that this scheme does pretty minimal error checking. In particular, // this will let the caller walk off of the end of valid data in the last // segment. //***************************************************************************** void *RecordPool::GetNextRecord( // Pointer to Record in pool. void *pRecord, // Current record. void **pContext) // Stored context here. { BYTE *pbRec = reinterpret_cast(pRecord); StgPoolSeg **ppSeg = reinterpret_cast(pContext); // Get the next record. pbRec += m_cbRec; // Is the next record outside of the current segment? if (static_cast(pbRec - (*ppSeg)->m_pSegData) >= (*ppSeg)->m_cbSegSize) { // Better be exactly one past current segment. _ASSERTE(static_cast(pbRec - (*ppSeg)->m_pSegData) == (*ppSeg)->m_cbSegSize); // Switch the context pointer. *ppSeg = (*ppSeg)->m_pNextSeg; // Next record is start of next segment. if (*ppSeg) return (*ppSeg)->m_pSegData; else return 0; } return pbRec; } // void *RecordPool::GetNextRecord() //***************************************************************************** // Given a pointer to a record, determine the index corresponding to the // record. //***************************************************************************** ULONG RecordPool::GetIndexForRecord( // 1-based index of Record in pool. const void *pvRecord) // Pointer to Record in pool. { ULONG iPrev = 0; // cumulative index of previous segments. const StgPoolSeg *pSeg = this; const BYTE *pRecord = reinterpret_cast(pvRecord); const BYTE *pSegData = NULL; ULONG ulSegSize; for (;;) { // Does the current segment contain the record? pSegData = pSeg->GetSegData(); ulSegSize = pSeg->GetSegSize(); if (pRecord >= pSegData && pRecord < pSegData + ulSegSize) { // The pointer should be to the start of a record. _ASSERTE(((pRecord - pSegData) % m_cbRec) == 0); return (ULONG)(1 + iPrev + (pRecord - pSegData) / m_cbRec); } _ASSERTE((ulSegSize % m_cbRec) == 0); iPrev += ulSegSize / m_cbRec; pSeg = pSeg->GetNextSeg(); // If out of data, didn't find the record. if (pSeg == 0) return 0; } } // ULONG RecordPool::GetIndexForRecord() //***************************************************************************** // Given a purported pointer to a record, determine if the pointer is valid. //***************************************************************************** int RecordPool::IsValidPointerForRecord(// true or false. const void *pvRecord) // Pointer to Record in pool. { const StgPoolSeg *pSeg; const BYTE *pRecord = reinterpret_cast(pvRecord); const BYTE *pSegData = NULL; for (pSeg = this; (pSeg); pSeg = pSeg->GetNextSeg()) { // Does the current segment contain the record? pSegData = pSeg->GetSegData(); if ((pRecord >= pSegData) && (pRecord < pSegData + pSeg->GetSegSize())) { // The pointer should be to the start of a record. return (((pRecord - pSegData) % m_cbRec) == 0); } _ASSERTE((pSeg->GetSegSize() % m_cbRec) == 0); } return 0; } // int RecordPool::IsValidPointerForRecord() //***************************************************************************** // Replace the contents of this pool with those from another pool. The other // pool loses ownership of the memory. //***************************************************************************** HRESULT RecordPool::ReplaceContents( RecordPool *pOther) // The other record pool. { // Release any memory currently held. Uninit(); // Grab the new data. *this = *pOther; // If the other pool's curseg pointed to itself, make this pool point to itself. if (pOther->m_pCurSeg == pOther) m_pCurSeg = this; // Fix the other pool so it won't free the memory that this one // just hijacked. pOther->m_pSegData = (BYTE*)m_zeros; pOther->m_pNextSeg = 0; pOther->Uninit(); return S_OK; } // HRESULT RecordPool::ReplaceContents()