Internal optimization in traversal of BlockMetadata_Generic::m_Suballocations
diff --git a/README.md b/README.md
index 572958e..9cbb89f 100644
--- a/README.md
+++ b/README.md
@@ -40,7 +40,7 @@
# Prerequisites
-- Self-contained C++ library in single pair of H + CPP files. No external dependencies other than standard C, C++ library and Windows SDK. Some features of C++11 used. STL containers, C++ exceptions, and RTTI are not used.
+- Self-contained C++ library in single pair of H + CPP files. No external dependencies other than standard C, C++ library and Windows SDK. Some features of C++14 used. STL containers, C++ exceptions, and RTTI are not used.
- Object-oriented interface in a convention similar to D3D12.
- Error handling implemented by returning `HRESULT` error codes - same way as in D3D12.
- Interface documented using Doxygen-style comments.
diff --git a/src/D3D12MemAlloc.cpp b/src/D3D12MemAlloc.cpp
index 7075fcb..04ddd44 100644
--- a/src/D3D12MemAlloc.cpp
+++ b/src/D3D12MemAlloc.cpp
@@ -1561,6 +1561,7 @@
void Remove(Item* pItem);
+ class reverse_iterator;
class iterator
{
public:
@@ -1570,6 +1571,12 @@
{
}
+ iterator(const reverse_iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
T& operator*() const
{
D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
@@ -1636,8 +1643,93 @@
}
friend class List<T>;
+ friend class const_iterator;
};
+
+ class reverse_iterator
+ {
+ public:
+ reverse_iterator() :
+ m_pList(NULL),
+ m_pItem(NULL)
+ {
+ }
+ reverse_iterator(const iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
+ T& operator*() const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
+ return m_pItem->Value;
+ }
+ T* operator->() const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
+ return &m_pItem->Value;
+ }
+
+ reverse_iterator& operator++()
+ {
+ D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
+ m_pItem = m_pItem->pPrev;
+ return *this;
+ }
+ reverse_iterator& operator--()
+ {
+ if(m_pItem != NULL)
+ {
+ m_pItem = m_pItem->pNext;
+ }
+ else
+ {
+ D3D12MA_HEAVY_ASSERT(!m_pList->IsEmpty());
+ m_pItem = m_pList->Front();
+ }
+ return *this;
+ }
+
+ reverse_iterator operator++(int)
+ {
+ reverse_iterator result = *this;
+ ++*this;
+ return result;
+ }
+ reverse_iterator operator--(int)
+ {
+ reverse_iterator result = *this;
+ --*this;
+ return result;
+ }
+
+ bool operator==(const reverse_iterator& rhs) const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
+ return m_pItem == rhs.m_pItem;
+ }
+ bool operator!=(const reverse_iterator& rhs) const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
+ return m_pItem != rhs.m_pItem;
+ }
+
+ private:
+ List<T>* m_pList;
+ Item* m_pItem;
+
+ reverse_iterator(List<T>* pList, Item* pItem) :
+ m_pList(pList),
+ m_pItem(pItem)
+ {
+ }
+
+ friend class List<T>;
+ friend class const_reverse_iterator;
+ };
+
class const_iterator
{
public:
@@ -1653,6 +1745,23 @@
{
}
+ const_iterator(const reverse_iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
+ const_iterator(const const_reverse_iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
+ iterator dropConst() const
+ {
+ return iterator(const_cast<List<T>*>(m_pList), const_cast<Item*>(m_pItem));
+ }
+
const T& operator*() const
{
D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
@@ -1721,6 +1830,106 @@
friend class List<T>;
};
+ class const_reverse_iterator
+ {
+ public:
+ const_reverse_iterator() :
+ m_pList(NULL),
+ m_pItem(NULL)
+ {
+ }
+
+ const_reverse_iterator(const iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
+ const_reverse_iterator(const reverse_iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
+ const_reverse_iterator(const const_iterator& src) :
+ m_pList(src.m_pList),
+ m_pItem(src.m_pItem)
+ {
+ }
+
+ reverse_iterator dropConst() const
+ {
+ return reverse_iterator(const_cast<List<T>*>(m_pList), const_cast<Item*>(m_pItem));
+ }
+
+ const T& operator*() const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
+ return m_pItem->Value;
+ }
+ const T* operator->() const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
+ return &m_pItem->Value;
+ }
+
+ const_reverse_iterator& operator++()
+ {
+ D3D12MA_HEAVY_ASSERT(m_pItem != NULL);
+ m_pItem = m_pItem->pPrev;
+ return *this;
+ }
+ const_reverse_iterator& operator--()
+ {
+ if(m_pItem != NULL)
+ {
+ m_pItem = m_pItem->pNext;
+ }
+ else
+ {
+ D3D12MA_HEAVY_ASSERT(!m_pList->IsEmpty());
+ m_pItem = m_pList->Front();
+ }
+ return *this;
+ }
+
+ const_reverse_iterator operator++(int)
+ {
+ const_reverse_iterator result = *this;
+ ++*this;
+ return result;
+ }
+ const_reverse_iterator operator--(int)
+ {
+ const_reverse_iterator result = *this;
+ --*this;
+ return result;
+ }
+
+ bool operator==(const const_reverse_iterator& rhs) const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
+ return m_pItem == rhs.m_pItem;
+ }
+ bool operator!=(const const_reverse_iterator& rhs) const
+ {
+ D3D12MA_HEAVY_ASSERT(m_pList == rhs.m_pList);
+ return m_pItem != rhs.m_pItem;
+ }
+
+ private:
+ const_reverse_iterator(const List<T>* pList, const Item* pItem) :
+ m_pList(pList),
+ m_pItem(pItem)
+ {
+ }
+
+ const List<T>* m_pList;
+ const Item* m_pItem;
+
+ friend class List<T>;
+ };
+
bool empty() const { return IsEmpty(); }
size_t size() const { return GetCount(); }
@@ -1733,6 +1942,15 @@
const_iterator begin() const { return cbegin(); }
const_iterator end() const { return cend(); }
+ reverse_iterator rbegin() { return reverse_iterator(this, Back()); }
+ reverse_iterator rend() { return reverse_iterator(this, NULL); }
+
+ const_reverse_iterator crbegin() const { return const_reverse_iterator(this, Back()); }
+ const_reverse_iterator crend() const { return const_reverse_iterator(this, NULL); }
+
+ const_reverse_iterator rbegin() const { return crbegin(); }
+ const_reverse_iterator rend() const { return crend(); }
+
void clear() { Clear(); }
void push_back(const T& value) { PushBack(value); }
void erase(iterator it) { Remove(it.m_pItem); }
@@ -2420,6 +2638,7 @@
Vector<SuballocationList::iterator> m_FreeSuballocationsBySize;
ZeroInitializedRange m_ZeroInitializedRange;
+ SuballocationList::const_iterator FindAtOffset(UINT64 offset) const;
bool ValidateFreeSuballocationList() const;
// Checks if requested suballocation with given parameters can be placed in given pFreeSuballocItem.
@@ -3194,16 +3413,9 @@
void BlockMetadata_Generic::GetAllocationInfo(UINT64 offset, VIRTUAL_ALLOCATION_INFO& outInfo) const
{
- for(const auto& suballoc : m_Suballocations)
- {
- if(suballoc.offset == offset)
- {
- outInfo.size = suballoc.size;
- outInfo.pUserData = suballoc.userData;
- return;
- }
- }
- D3D12MA_ASSERT(0 && "Not found!");
+ Suballocation& suballoc = *FindAtOffset(offset).dropConst();
+ outInfo.size = suballoc.size;
+ outInfo.pUserData = suballoc.userData;
}
bool BlockMetadata_Generic::CreateAllocationRequest(
@@ -3319,18 +3531,7 @@
void BlockMetadata_Generic::FreeAtOffset(UINT64 offset)
{
- for(SuballocationList::iterator suballocItem = m_Suballocations.begin();
- suballocItem != m_Suballocations.end();
- ++suballocItem)
- {
- Suballocation& suballoc = *suballocItem;
- if(suballoc.offset == offset)
- {
- FreeSuballocation(suballocItem);
- return;
- }
- }
- D3D12MA_ASSERT(0 && "Not found!");
+ FreeSuballocation(FindAtOffset(offset).dropConst());
}
void BlockMetadata_Generic::Clear()
@@ -3349,6 +3550,38 @@
m_FreeSuballocationsBySize.push_back(m_Suballocations.begin());
}
+SuballocationList::const_iterator BlockMetadata_Generic::FindAtOffset(UINT64 offset) const
+{
+ const UINT64 last = m_Suballocations.crbegin()->offset;
+ if (last == offset)
+ return m_Suballocations.crbegin();
+ const UINT64 first = m_Suballocations.cbegin()->offset;
+ if (first == offset)
+ return m_Suballocations.cbegin();
+
+ const size_t suballocCount = m_Suballocations.size();
+ const UINT64 step = (last - first + m_Suballocations.cbegin()->size) / suballocCount;
+ auto findSuballocation = [&](auto begin, auto end) -> SuballocationList::const_iterator
+ {
+ for (auto suballocItem = begin;
+ suballocItem != end;
+ ++suballocItem)
+ {
+ const Suballocation& suballoc = *suballocItem;
+ if (suballoc.offset == offset)
+ return suballocItem;
+ }
+ D3D12MA_ASSERT(false && "Not found!");
+ return m_Suballocations.end();
+ };
+ // If requested offset is closer to the end of range, search from the end
+ if ((offset - first) > suballocCount * step / 2)
+ {
+ return findSuballocation(m_Suballocations.crbegin(), m_Suballocations.crend());
+ }
+ return findSuballocation(m_Suballocations.cbegin(), m_Suballocations.cend());
+}
+
bool BlockMetadata_Generic::ValidateFreeSuballocationList() const
{
UINT64 lastSize = 0;
@@ -3548,15 +3781,8 @@
void BlockMetadata_Generic::SetAllocationUserData(UINT64 offset, void* userData)
{
- for(auto& suballoc : m_Suballocations)
- {
- if(suballoc.offset == offset)
- {
- suballoc.userData = userData;
- return;
- }
- }
- D3D12MA_ASSERT(0 && "Not found!");
+ Suballocation& suballoc = *FindAtOffset(offset).dropConst();
+ suballoc.userData = userData;
}
void BlockMetadata_Generic::CalcAllocationStatInfo(StatInfo& outInfo) const
