////////////////////////////////////////////////////////////////////////////// // Banked List implementation #include "BankedList.h" #include // A page of items // (Internal class for internal use only..) template class CBankedListBank { public: CBankedListBank(); private: typedef CBankedList t_Parent; typedef CBankedListBank t_This; typedef T t_Type; friend t_Parent; friend t_Parent::t_Iter; // Is this bank currently full? LTBOOL IsFull(); // Is this bank currently empty? LTBOOL IsEmpty(); // Is this bank currently packed? (i.e. are the used items in contiguous usage?) LTBOOL IsPacked(); // Is this index in use? LTBOOL IsUsed(uint32 nIndex); // Get the index of pPtr (returns k_SizeOfBank if it isn't in this bank) uint32 GetIndexAtPtr(t_Type *pPtr); // Get object nIndex t_Type &GetRefAtIndex(uint32 nIndex); // How many items are currently in use? uint32 GetSize(); // What's your minimum in-use index? (returns k_SizeOfBank if empty) uint32 GetFirstUsed(); // What's your maximum in-use index? (returns k_SizeOfBank if empty) uint32 GetLastUsed(); // What's your minimum available index? (returns k_SizeOfBank if full) uint32 GetFirstOpen(); // What's your maximum in-use index? (returns k_SizeOfBank if full) uint32 GetLastOpen(); // Remove the item at index nIndex void Remove(uint32 nIndex); // Allocate an item T *New(typename t_Parent::t_NewOp eOp); // Read-only bank pointer access t_This *GetNext(); t_This *GetPrev(); // Remove this bank from the list void RemoveList(); // Insert this bank into the list after pTail void AppendList(t_This *pTail); // Insert this bank into the list before pHead void InsertList(t_This *pHead); private: // Intended for internal access only enum { k_DataPitch = ((sizeof(t_Type) + (sizeof(int) - 1)) / sizeof(int)) }; enum { k_SizeOfData = t_Parent::k_SizeOfBank * k_DataPitch }; // The usage flags for this bank uint32 m_nUsage; // Pointer to the next/prev banks in the list t_This *m_pNextBank, *m_pPrevBank; // The actual data (Note : This is an int array to avoid the ctor/dtor calls of the // actual type. Also, this conveniently provides word alignment to the allocations..) int m_aData[k_SizeOfData]; }; ////////////////////////////////////////////////////////////////////////////// // CBankedList::t_Iter implementation template CBankedListIter::CBankedListIter() : m_pCurBank(LTNULL), m_nIndex(0) { } template CBankedListIter::CBankedListIter(const t_This &iOther) : m_pCurBank(iOther.m_pCurBank), m_nIndex(iOther.m_nIndex) { } template CBankedListIter::CBankedListIter(t_Bank *pBank, uint32 nIndex) : m_pCurBank(pBank), m_nIndex(nIndex) { } template LTBOOL CBankedListIter::IsValid() { // Invalid bank? Not valid.. if (!m_pCurBank) return LTFALSE; // Invalid index? Not valid.. if (m_nIndex >= t_Parent::k_SizeOfBank) return LTFALSE; // You're valid, as long as the bank says you're in use return m_pCurBank->IsUsed(m_nIndex); } template T &CBankedListIter::DeRef() { // Not pointing at anything? Uh... Make something up... if (!m_pCurBank) { return *((T*)LTNULL); } return m_pCurBank->GetRefAtIndex(m_nIndex); } template void CBankedListIter::Next() { if (!m_pCurBank) return; do { if (m_nIndex < t_Parent::k_SizeOfBank) ++m_nIndex; else { m_pCurBank = m_pCurBank->GetNext(); m_nIndex = 0; } } while (m_pCurBank && (!m_pCurBank->IsUsed(m_nIndex))); } template void CBankedListIter::Prev() { if (!m_pCurBank) return; do { if (m_nIndex > 0) --m_nIndex; else { m_pCurBank = m_pCurBank->GetPrev(); if (m_pCurBank) m_nIndex = m_pCurBank->GetLastUsed(); } } while (m_pCurBank && (!m_pCurBank->IsUsed(m_nIndex))); } template void CBankedListIter::Copy(const t_This &iOther) { m_pCurBank = iOther.m_pCurBank; m_nIndex = iOther.m_nIndex; } template CBankedListBank *CBankedListIter::GetBank() { return m_pCurBank; } template uint32 CBankedListIter::GetIndex() { return m_nIndex; } ////////////////////////////////////////////////////////////////////////////// // CBankedList::t_Bank implementation template CBankedListBank::CBankedListBank() : m_nUsage(0), m_pNextBank(LTNULL), m_pPrevBank(LTNULL) { } template LTBOOL CBankedListBank::IsFull() { return m_nUsage == 0xFFFFFFFF; } template LTBOOL CBankedListBank::IsEmpty() { return m_nUsage == 0; } template LTBOOL CBankedListBank::IsPacked() { // Returns TRUE if the "used" bits are contiguous return (m_nUsage & (m_nUsage + 1)) == 0; } template LTBOOL CBankedListBank::IsUsed(uint32 nIndex) { return (m_nUsage & (1 << nIndex)) != 0; } template uint32 CBankedListBank::GetIndexAtPtr(T *pPtr) { if (((int*)pPtr >= m_aData) && ((int*)pPtr < &m_aData[k_SizeOfData])) return ((int*)pPtr - m_aData) / k_DataPitch; else return t_Parent::k_SizeOfBank; } template T &CBankedListBank::GetRefAtIndex(uint32 nIndex) { // Note : It is guaranteed that this won't be called with nIndex > k_SizeOfBank // due to the iterator being the only one to call this function return *((T*)(&m_aData[nIndex * k_DataPitch])); } // How many items are currently in use? template uint32 CBankedListBank::GetSize() { // This is a keen little trick I found in a Dr. Dobbs for counting bits without any branches.. uint32 nTemp; nTemp = ((m_nUsage & 0xAAAAAAAA) >> 1) + (m_nUsage & 0x55555555); nTemp = ((nTemp & 0xCCCCCCCC) >> 2) + (nTemp & 0x33333333); nTemp = ((nTemp & 0xF0F0F0F0) >> 4) + (nTemp & 0x0F0F0F0F); nTemp = ((nTemp & 0xFF00FF00) >> 8) + (nTemp & 0x00FF00FF); return ((nTemp & 0xFFFF0000) >> 16) + (nTemp & 0x0000FFFF); } template uint32 CBankedListBank::GetFirstUsed() { // Note : I'm sure there's a more clever way of doing this... uint32 nIndex = 0; uint32 nMask = 1; while (nIndex < t_Parent::k_SizeOfBank) { if ((m_nUsage & nMask) != 0) return nIndex; ++nIndex; nMask = nMask << 1; } // If it got here, it's empty return nIndex; } template uint32 CBankedListBank::GetLastUsed() { // Note : I'm sure there's a more clever way of doing this... uint32 nIndex = t_Parent::k_SizeOfBank - 1; uint32 nMask = 1 << nIndex; while (nIndex > 0) { if ((m_nUsage & nMask) != 0) return nIndex; --nIndex; nMask = nMask >> 1; } // If it got here, it's either 0 or empty return (m_nUsage == 1) ? 0 : t_Parent::k_SizeOfBank; } template uint32 CBankedListBank::GetFirstOpen() { // Note : I'm sure there's a more clever way of doing this... uint32 nIndex = 0; uint32 nMask = 1; while (nIndex < t_Parent::k_SizeOfBank) { if ((m_nUsage & nMask) == 0) return nIndex; ++nIndex; nMask = nMask << 1; } // If it got here, it's full return nIndex; } template uint32 CBankedListBank::GetLastOpen() { // Note : I'm sure there's a more clever way of doing this... uint32 nIndex = t_Parent::k_SizeOfBank - 1; uint32 nMask = 1 << nIndex; while (nIndex > 0) { if ((m_nUsage & nMask) == 0) return nIndex; --nIndex; nMask = nMask >> 1; } // If it got here, it's either 0 or empty return (m_nUsage == 1) ? 0 : t_Parent::k_SizeOfBank; } template void CBankedListBank::Remove(uint32 nIndex) { m_nUsage &= ~(1 << nIndex); } template T* CBankedListBank::New(typename t_Parent::t_NewOp eOp) { // Get our index uint32 nIndex = t_Parent::k_SizeOfBank; if (eOp == t_Parent::eNewOp_Pack) { // Fail if we're full if (IsFull()) return LTNULL; nIndex = GetFirstOpen(); } else if (eOp == t_Parent::eNewOp_Append) { // Fail if we can't append.. if (IsUsed(t_Parent::k_SizeOfBank - 1) || (GetNext() != LTNULL)) return LTNULL; if (IsEmpty()) nIndex = 0; else nIndex = GetLastUsed() + 1; } // Mark it as used m_nUsage |= (1 << nIndex); // Return the pointer.. return &GetRefAtIndex(nIndex); } template CBankedListBank *CBankedListBank::GetNext() { return m_pNextBank; } template CBankedListBank *CBankedListBank::GetPrev() { return m_pPrevBank; } template void CBankedListBank::RemoveList() { if (m_pPrevBank) m_pPrevBank->m_pNextBank = m_pNextBank; if (m_pNextBank) m_pNextBank->m_pPrevBank = m_pPrevBank; } template void CBankedListBank::AppendList(t_This *pTail) { if (pTail) { if (pTail->m_pNextBank) pTail->m_pNextBank->m_pPrevBank = this; m_pNextBank = pTail->m_pNextBank; m_pPrevBank = pTail; pTail->m_pNextBank = this; } else { m_pNextBank = LTNULL; m_pPrevBank = LTNULL; } } template void CBankedListBank::InsertList(t_This *pHead) { if (pHead) { if (pHead->m_pPrevBank) pHead->m_pPrevBank->m_pNextBank = this; m_pNextBank = pHead; m_pPrevBank = pHead->m_pPrevBank; pHead->m_pPrevBank = this; } else { m_pNextBank = LTNULL; m_pPrevBank = LTNULL; } } ////////////////////////////////////////////////////////////////////////////// // CBankedList implementation template CBankedList::CBankedList() : m_pBankHead(LTNULL), m_pBankTail(LTNULL), m_pEmptyHead(LTNULL), m_nSize(0) { } template CBankedList::~CBankedList() { Term(); } template void CBankedList::Init() { Term(); } template void CBankedList::Term() { if (m_pEmptyHead) { DeleteBankList(m_pEmptyHead); m_pEmptyHead = LTNULL; } if (m_pBankHead) { DeleteBankList(m_pBankHead); m_pBankHead = LTNULL; } m_pBankTail = LTNULL; m_nSize = 0; } template typename CBankedList::t_Iter CBankedList::GetHead() { return t_Iter(m_pBankHead, (m_pBankHead) ? m_pBankHead->GetFirstUsed() : 0); } template typename CBankedList::t_Iter CBankedList::GetTail() { return t_Iter(m_pBankTail, (m_pBankTail) ? m_pBankTail->GetLastUsed() : 0); } template typename CBankedList::t_Iter CBankedList::Remove(const t_Iter &iPos) { // Make sure we've got a valid position if (!iPos.IsValid()) return iPos; // Set up the return value t_Iter iRet(iPos); // Get the item we're pointing at t_Bank *pBank = iRet.GetBank(); uint32 nIndex = iRet.GetIndex(); // Move to the next item ++iRet; // Remove the item from the bank pBank->Remove(nIndex); // Remember that we removed one --m_nSize; // Remove the bank from the list if it's empty if (pBank->IsEmpty()) MoveToEmptyList(pBank); return iRet; } template typename CBankedList::t_Iter CBankedList::Find(T *pPtr) { // Start at the first bank t_Bank *pFinger = m_pBankHead; uint32 nIndex = 0; while (pFinger) { // Try to find it in this bank nIndex = pFinger->GetIndexAtPtr(pPtr); // Jump out of the loop if we found it if (nIndex < k_SizeOfBank) break; // Move to the next bank pFinger = pFinger->GetNext(); } // Return the result return t_Iter(pFinger, nIndex); } template void CBankedList::Remove(T *pPtr) { Remove(Find(pPtr)); } template void CBankedList::Append(const T &_Item) { new(this, eNewOp_Append) T(_Item); } template void CBankedList::Delete(t_Type *pPtr, bool bCallDtor) { if (!pPtr) return; // Find the pointer in the list t_Iter iPtr = Find(pPtr); // Jump out if we didn't find it if (!iPtr.IsValid()) { ASSERT(!"CBankedList::Delete was called on an unknown pointer"); return; } // Call the dtor if (bCallDtor) pPtr->~T(); // Delete it iPtr.GetBank()->Remove(iPtr.GetIndex()); // Remember that we removed one --m_nSize; // Remove the bank if it's empty if (iPtr.GetBank()->IsEmpty()) MoveToEmptyList(iPtr.GetBank()); // Report /* if (g_pLTClient) { g_pLTClient->CPrint("BankedList::Delete(%d) : %d", sizeof(t_Type), GetSize()); } */ } template void *operator new(size_t, CBankedList &, T* ptr) { return ptr; } // Internal ctor helper template void operator delete(void*, CBankedList &cBank, T* ptr) { cBank.Delete(ptr); } template T *CBankedList::New(t_NewOp eOp, bool bCallCtor) { // Get our bank t_Bank *pBank = LTNULL; if (eOp == eNewOp_Pack) { // Find the first available bank pBank = m_pBankHead; while (pBank && pBank->IsFull()) pBank = pBank->GetNext(); } else if (eOp == eNewOp_Append) { pBank = m_pBankTail; // Get a new bank if this one's been used all the way.. if (pBank && pBank->IsUsed(k_SizeOfBank - 1)) pBank = LTNULL; } // Get a new bank if we need to.. if (!pBank) { pBank = GetNewBank(); } // Fail if we just can't do it... if (!pBank) { ASSERT(!"Unable to allocate a bank in CBankedList::New"); return LTNULL; } // Get a new one from the bank T *pNewItem = pBank->New(eOp); // Remember that we added one... if (pNewItem) ++m_nSize; // Call the ctor ::new(*this, pNewItem) T; // Report /* if (g_pLTClient) { g_pLTClient->CPrint("BankedList::New(%d) : %d", sizeof(t_Type), GetSize()); } */ return pNewItem; } template LTBOOL CBankedList::IsEmpty() { return m_pBankHead == LTNULL; } template uint32 CBankedList::GetSize() { return m_nSize; } template uint32 CBankedList::GetFootprint() { // Start out with the size of the list... uint32 nSize = sizeof(*this); // Add in the active banks t_Bank *pFinger = m_pBankHead; while (pFinger) { nSize += sizeof(*pFinger); pFinger = pFinger->GetNext(); } // Add in the empty banks // PORT: the original re-declared `t_Bank *pFinger` here, a second // declaration of the same name in the same block scope. It survived only // because this is a template member that was never instantiated, so MSVC // never checked the body. Reuse the existing variable instead. pFinger = m_pEmptyHead; while (pFinger) { nSize += sizeof(*pFinger); pFinger = pFinger->GetNext(); } // PORT: the original had NO return statement despite the uint32 return // type -- undefined behaviour had it ever been called. Returning the // accumulated size is plainly what the function computes. return nSize; } template float CBankedList::GetUsage() { // Count the number of slots used/total uint32 nUsedSlots = 0; uint32 nTotalSlots = 0; // Only count the active banks t_Bank *pFinger = m_pBankHead; while (pFinger) { nTotalSlots += k_SizeOfBank; nUsedSlots += pFinger->GetSize(); pFinger = pFinger->GetNext(); } // Empty lists are considered entirely used if (!nTotalSlots) return 1.0f; else return (float)nUsedSlots / (float)nTotalSlots; } template void CBankedList::DeleteBankList(t_Bank *pHead) { t_Bank *pFinger = pHead; while (pFinger) { t_Bank *pDeleteMe = pFinger; pFinger = pFinger->GetNext(); debug_delete(pDeleteMe); } } template void CBankedList::MoveToEmptyList(t_Bank *pBank) { // Update the head pointer if (pBank == m_pBankHead) m_pBankHead = m_pBankHead->GetNext(); // Update the tail pointer if (pBank == m_pBankTail) m_pBankTail = m_pBankTail->GetPrev(); // Remove the bank from the active list pBank->RemoveList(); // Add it to the empty list pBank->InsertList(m_pEmptyHead); m_pEmptyHead = pBank; } template typename CBankedList::t_Bank *CBankedList::GetNewBank() { t_Bank *pResult; // If we've got an empty list available... if (m_pEmptyHead) { // Use the head of the empty list pResult = m_pEmptyHead; // Move the empty list forward m_pEmptyHead = m_pEmptyHead->GetNext(); // Remove it from the empty list pResult->RemoveList(); } // Otherwise make a new one else { pResult = debug_new(t_Bank); } // Add it to the end of the list pResult->AppendList(m_pBankTail); // Point the tail at it m_pBankTail = pResult; // Point the head at it if we're empty if (!m_pBankHead) m_pBankHead = pResult; // Here ya go... return pResult; } template LTBOOL CBankedList::PreAlloc(uint32 nMinItems) { // Calculate how many banks we'd need.. uint32 nBanksNeeded = (nMinItems + k_SizeOfBank - 1) / k_SizeOfBank; // Find out what we've currently got allocated t_Bank *pFinger = m_pEmptyHead; while (nBanksNeeded && pFinger) { --nBanksNeeded; pFinger = pFinger->GetNext(); } // Allocate new banks while (nBanksNeeded) { t_Bank *pNewBank = debug_new(t_Bank); // Add them to the empty list pNewBank->InsertList(m_pEmptyHead); m_pEmptyHead = pNewBank; } } template void CBankedList::Flush() { if (m_pEmptyHead) { DeleteBankList(m_pEmptyHead); m_pEmptyHead = LTNULL; } }