From ab350d1e43edef1a39f48d2771a9f136b3c4ae5f Mon Sep 17 00:00:00 2001 From: peterbell10 Date: Sun, 21 Jan 2018 18:45:13 +0000 Subject: cItemGrid: Allocate storage lazily (#4083) * cItemGrid: Allocate storage lazily * cItemGrid: Fix spelling, Prioritary -> Priority --- src/CMakeLists.txt | 1 + src/ItemGrid.cpp | 188 ++++++++++++++++++++++++++++++++--------------------- src/ItemGrid.h | 21 +++--- src/LazyArray.h | 134 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 257 insertions(+), 87 deletions(-) create mode 100644 src/LazyArray.h (limited to 'src') diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index b5daedfaa..f2732bf8f 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -118,6 +118,7 @@ SET (HDRS Inventory.h Item.h ItemGrid.h + LazyArray.h LightingThread.h LineBlockTracer.h LinearInterpolation.h diff --git a/src/ItemGrid.cpp b/src/ItemGrid.cpp index 69aa976c6..045f083c8 100644 --- a/src/ItemGrid.cpp +++ b/src/ItemGrid.cpp @@ -12,11 +12,10 @@ -cItemGrid::cItemGrid(int a_Width, int a_Height) : +cItemGrid::cItemGrid(int a_Width, int a_Height): m_Width(a_Width), m_Height(a_Height), - m_NumSlots(a_Width * a_Height), - m_Slots(new cItem[a_Width * a_Height]), + m_Slots(a_Width * a_Height), m_IsInTriggerListeners(false) { } @@ -25,19 +24,9 @@ cItemGrid::cItemGrid(int a_Width, int a_Height) : -cItemGrid::~cItemGrid() -{ - delete[] m_Slots; - m_Slots = nullptr; -} - - - - - bool cItemGrid::IsValidSlotNum(int a_SlotNum) const { - return ((a_SlotNum >= 0) && (a_SlotNum < m_NumSlots)); + return ((a_SlotNum >= 0) && (a_SlotNum < m_Slots.size())); } @@ -77,7 +66,7 @@ void cItemGrid::GetSlotCoords(int a_SlotNum, int & a_X, int & a_Y) const if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: SlotNum out of range: %d in grid of range %d", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); a_X = -1; a_Y = -1; @@ -93,12 +82,9 @@ void cItemGrid::GetSlotCoords(int a_SlotNum, int & a_X, int & a_Y) const void cItemGrid::CopyFrom(const cItemGrid & a_Src) { - ASSERT(m_Width == a_Src.m_Width); - ASSERT(m_Height == a_Src.m_Height); - for (int i = m_NumSlots - 1; i >= 0; --i) - { - m_Slots[i] = a_Src.m_Slots[i]; - } + m_Width = a_Src.m_Width; + m_Height = a_Src.m_Height; + m_Slots = a_Src.m_Slots; // The listeners are not copied } @@ -121,11 +107,11 @@ const cItem & cItemGrid::GetSlot(int a_SlotNum) const if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: Invalid slot number, %d out of %d slots", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); - return m_Slots[0]; + a_SlotNum = 0; } - return m_Slots[a_SlotNum]; + return m_Slots.GetAt(a_SlotNum); } @@ -155,11 +141,15 @@ void cItemGrid::SetSlot(int a_SlotNum, const cItem & a_Item) if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); return; } - m_Slots[a_SlotNum] = a_Item; + + if (!a_Item.IsEmpty() || m_Slots.IsStorageAllocated()) + { + m_Slots[a_SlotNum] = a_Item; + } TriggerListeners(a_SlotNum); } @@ -190,13 +180,13 @@ void cItemGrid::EmptySlot(int a_SlotNum) if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); return; } // Check if already empty: - if (m_Slots[a_SlotNum].IsEmpty()) + if (m_Slots.GetAt(a_SlotNum).IsEmpty()) { return; } @@ -215,11 +205,11 @@ bool cItemGrid::IsSlotEmpty(int a_SlotNum) const if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); return true; } - return m_Slots[a_SlotNum].IsEmpty(); + return m_Slots.GetAt(a_SlotNum).IsEmpty(); } @@ -237,7 +227,12 @@ bool cItemGrid::IsSlotEmpty(int a_X, int a_Y) const void cItemGrid::Clear(void) { - for (int i = 0; i < m_NumSlots; i++) + if (!m_Slots.IsStorageAllocated()) + { + return; // Already clear + } + + for (int i = 0; i < m_Slots.size(); i++) { m_Slots[i].Empty(); TriggerListeners(i); @@ -250,27 +245,34 @@ void cItemGrid::Clear(void) int cItemGrid::HowManyCanFit(const cItem & a_ItemStack, bool a_AllowNewStacks) { - char NumLeft = a_ItemStack.m_ItemCount; + int NumLeft = a_ItemStack.m_ItemCount; int MaxStack = ItemHandler(a_ItemStack.m_ItemType)->GetMaxStackSize(); - for (int i = m_NumSlots - 1; i >= 0; i--) + + if (!m_Slots.IsStorageAllocated()) { - if (m_Slots[i].IsEmpty()) + // Grid is empty, all slots are available + return a_AllowNewStacks ? std::min(NumLeft, m_Slots.size() * MaxStack) : 0; + } + + for (const auto & Slot : m_Slots) + { + if (Slot.IsEmpty()) { if (a_AllowNewStacks) { NumLeft -= MaxStack; } } - else if (m_Slots[i].IsEqual(a_ItemStack)) + else if (Slot.IsEqual(a_ItemStack)) { - NumLeft -= MaxStack - m_Slots[i].m_ItemCount; + NumLeft -= MaxStack - Slot.m_ItemCount; } if (NumLeft <= 0) { // All items fit return a_ItemStack.m_ItemCount; } - } // for i - m_Slots[] + } // for Slot - m_Slots[] return a_ItemStack.m_ItemCount - NumLeft; } @@ -283,7 +285,7 @@ int cItemGrid::AddItemToSlot(const cItem & a_ItemStack, int a_Slot, int a_Num, i if (!IsValidSlotNum(a_Slot)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_Slot, m_NumSlots + __FUNCTION__, a_Slot, m_Slots.size() ); return 0; } @@ -308,33 +310,38 @@ int cItemGrid::AddItemToSlot(const cItem & a_ItemStack, int a_Slot, int a_Num, i -int cItemGrid::AddItem(cItem & a_ItemStack, bool a_AllowNewStacks, int a_PrioritarySlot) +int cItemGrid::AddItem(cItem & a_ItemStack, bool a_AllowNewStacks, int a_PrioritySlot) { int NumLeft = a_ItemStack.m_ItemCount; int MaxStack = a_ItemStack.GetMaxStackSize(); - if ((a_PrioritarySlot != -1) && !IsValidSlotNum(a_PrioritarySlot)) + if ((a_PrioritySlot != -1) && !IsValidSlotNum(a_PrioritySlot)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_PrioritarySlot, m_NumSlots + __FUNCTION__, a_PrioritySlot, m_Slots.size() ); - a_PrioritarySlot = -1; + a_PrioritySlot = -1; + } + + if (!a_AllowNewStacks && !m_Slots.IsStorageAllocated()) + { + return 0; // No existing stacks to add to } - // Try prioritarySlot first: + // Try prioritySlot first: if ( - (a_PrioritarySlot != -1) && + (a_PrioritySlot != -1) && ( - m_Slots[a_PrioritarySlot].IsEmpty() || - m_Slots[a_PrioritarySlot].IsEqual(a_ItemStack) + m_Slots[a_PrioritySlot].IsEmpty() || + m_Slots[a_PrioritySlot].IsEqual(a_ItemStack) ) ) { - NumLeft -= AddItemToSlot(a_ItemStack, a_PrioritarySlot, NumLeft, MaxStack); + NumLeft -= AddItemToSlot(a_ItemStack, a_PrioritySlot, NumLeft, MaxStack); } // Scan existing stacks: - for (int i = 0; i < m_NumSlots; i++) + for (int i = 0; i < m_Slots.size(); i++) { if (m_Slots[i].IsEqual(a_ItemStack)) { @@ -352,7 +359,7 @@ int cItemGrid::AddItem(cItem & a_ItemStack, bool a_AllowNewStacks, int a_Priorit return (a_ItemStack.m_ItemCount - NumLeft); } - for (int i = 0; i < m_NumSlots; i++) + for (int i = 0; i < m_Slots.size(); i++) { if (m_Slots[i].IsEmpty()) { @@ -371,12 +378,12 @@ int cItemGrid::AddItem(cItem & a_ItemStack, bool a_AllowNewStacks, int a_Priorit -int cItemGrid::AddItems(cItems & a_ItemStackList, bool a_AllowNewStacks, int a_PrioritarySlot) +int cItemGrid::AddItems(cItems & a_ItemStackList, bool a_AllowNewStacks, int a_PrioritySlot) { int TotalAdded = 0; for (cItems::iterator itr = a_ItemStackList.begin(); itr != a_ItemStackList.end();) { - int NumAdded = AddItem(*itr, a_AllowNewStacks, a_PrioritarySlot); + int NumAdded = AddItem(*itr, a_AllowNewStacks, a_PrioritySlot); if (itr->m_ItemCount == NumAdded) { itr = a_ItemStackList.erase(itr); @@ -399,7 +406,12 @@ int cItemGrid::RemoveItem(const cItem & a_ItemStack) { int NumLeft = a_ItemStack.m_ItemCount; - for (int i = 0; i < m_NumSlots; i++) + if (!m_Slots.IsStorageAllocated()) + { + return 0; // No items to remove + } + + for (int i = 0; i < m_Slots.size(); i++) { if (NumLeft <= 0) { @@ -433,12 +445,12 @@ int cItemGrid::ChangeSlotCount(int a_SlotNum, int a_AddToCount) if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: Invalid slot number %d out of %d slots, ignoring the call, returning -1", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); return -1; } - if (m_Slots[a_SlotNum].IsEmpty()) + if (m_Slots.GetAt(a_SlotNum).IsEmpty()) { // The item is empty, it's not gonna change return 0; @@ -482,13 +494,13 @@ cItem cItemGrid::RemoveOneItem(int a_SlotNum) if (!IsValidSlotNum(a_SlotNum)) { LOGWARNING("%s: Invalid slot number %d out of %d slots, ignoring the call, returning empty item", - __FUNCTION__, a_SlotNum, m_NumSlots + __FUNCTION__, a_SlotNum, m_Slots.size() ); return cItem(); } // If the slot is empty, return an empty item - if (m_Slots[a_SlotNum].IsEmpty()) + if (m_Slots.GetAt(a_SlotNum).IsEmpty()) { return cItem(); } @@ -526,12 +538,17 @@ cItem cItemGrid::RemoveOneItem(int a_X, int a_Y) int cItemGrid::HowManyItems(const cItem & a_Item) { + if (!m_Slots.IsStorageAllocated()) + { + return 0; + } + int res = 0; - for (int i = 0; i < m_NumSlots; i++) + for (auto & Slot : m_Slots) { - if (m_Slots[i].IsEqual(a_Item)) + if (Slot.IsEqual(a_Item)) { - res += m_Slots[i].m_ItemCount; + res += Slot.m_ItemCount; } } return res; @@ -571,9 +588,9 @@ int cItemGrid::GetFirstUsedSlot(void) const int cItemGrid::GetLastEmptySlot(void) const { - for (int i = m_NumSlots - 1; i >= 0; i--) + for (int i = m_Slots.size() - 1; i >= 0; i--) { - if (m_Slots[i].IsEmpty()) + if (m_Slots.GetAt(i).IsEmpty()) { return i; } @@ -587,9 +604,14 @@ int cItemGrid::GetLastEmptySlot(void) const int cItemGrid::GetLastUsedSlot(void) const { - for (int i = m_NumSlots - 1; i >= 0; i--) + if (!m_Slots.IsStorageAllocated()) + { + return -1; // No slots are used + } + + for (int i = m_Slots.size() - 1; i >= 0; i--) { - if (!m_Slots[i].IsEmpty()) + if (!m_Slots.GetAt(i).IsEmpty()) { return i; } @@ -606,14 +628,14 @@ int cItemGrid::GetNextEmptySlot(int a_StartFrom) const if ((a_StartFrom != -1) && !IsValidSlotNum(a_StartFrom)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_StartFrom, m_NumSlots + __FUNCTION__, a_StartFrom, m_Slots.size() ); a_StartFrom = -1; } - for (int i = a_StartFrom + 1; i < m_NumSlots; i++) + for (int i = a_StartFrom + 1; i < m_Slots.size(); i++) { - if (m_Slots[i].IsEmpty()) + if (m_Slots.GetAt(i).IsEmpty()) { return i; } @@ -630,14 +652,19 @@ int cItemGrid::GetNextUsedSlot(int a_StartFrom) const if ((a_StartFrom != -1) && !IsValidSlotNum(a_StartFrom)) { LOGWARNING("%s: Invalid slot number %d out of %d slots", - __FUNCTION__, a_StartFrom, m_NumSlots + __FUNCTION__, a_StartFrom, m_Slots.size() ); a_StartFrom = -1; } - for (int i = a_StartFrom + 1; i < m_NumSlots; i++) + if (!m_Slots.IsStorageAllocated()) + { + return -1; // No slots are used + } + + for (int i = a_StartFrom + 1; i < m_Slots.size(); i++) { - if (!m_Slots[i].IsEmpty()) + if (!m_Slots.GetAt(i).IsEmpty()) { return i; } @@ -651,13 +678,18 @@ int cItemGrid::GetNextUsedSlot(int a_StartFrom) const void cItemGrid::CopyToItems(cItems & a_Items) const { - for (int i = 0; i < m_NumSlots; i++) + if (!m_Slots.IsStorageAllocated()) + { + return; // Nothing to copy + } + + for (const auto & Slot : m_Slots) { - if (!m_Slots[i].IsEmpty()) + if (!Slot.IsEmpty()) { - a_Items.push_back(m_Slots[i]); + a_Items.push_back(Slot); } - } // for i - m_Slots[] + } // for Slot - m_Slots[] } @@ -668,9 +700,15 @@ bool cItemGrid::DamageItem(int a_SlotNum, short a_Amount) { if (!IsValidSlotNum(a_SlotNum)) { - LOGWARNING("%s: invalid slot number %d out of %d slots, ignoring.", __FUNCTION__, a_SlotNum, m_NumSlots); + LOGWARNING("%s: invalid slot number %d out of %d slots, ignoring.", __FUNCTION__, a_SlotNum, m_Slots.size()); return false; } + + if (!m_Slots.IsStorageAllocated()) + { + return false; // Nothing to damage + } + return m_Slots[a_SlotNum].DamageItem(a_Amount); } @@ -736,7 +774,7 @@ void cItemGrid::GenerateRandomLootWithBooks(const cLootProbab * a_LootProbabs, s break; } } // for j - a_LootProbabs[] - SetSlot(Rnd % m_NumSlots, CurrentLoot); + SetSlot(Rnd % m_Slots.size(), CurrentLoot); } // for i - NumSlots } diff --git a/src/ItemGrid.h b/src/ItemGrid.h index e744afd87..ee2dc79f3 100644 --- a/src/ItemGrid.h +++ b/src/ItemGrid.h @@ -9,6 +9,7 @@ #pragma once #include "Item.h" +#include "LazyArray.h" @@ -33,12 +34,10 @@ public: cItemGrid(int a_Width, int a_Height); - ~cItemGrid(); - // tolua_begin int GetWidth (void) const { return m_Width; } int GetHeight (void) const { return m_Height; } - int GetNumSlots(void) const { return m_NumSlots; } + int GetNumSlots(void) const { return m_Slots.size(); } /** Converts XY coords into slot number; returns -1 on invalid coords */ int GetSlotNum(int a_X, int a_Y) const; @@ -49,7 +48,6 @@ public: void GetSlotCoords(int a_SlotNum, int & a_X, int & a_Y) const; /** Copies all items from a_Src to this grid. - Both grids must be the same size (asserts). Doesn't copy the listeners. */ void CopyFrom(const cItemGrid & a_Src); @@ -84,21 +82,21 @@ public: /** Adds as many items out of a_ItemStack as can fit. If a_AllowNewStacks is set to false, only existing stacks can be topped up; If a_AllowNewStacks is set to true, empty slots can be used for the rest. - If a_PrioritarySlot is set to a positive value, then the corresponding slot will be used first (if empty or compatible with added items). - If a_PrioritarySlot is set to -1, regular order applies. + If a_PrioritySlot is set to a positive value, then the corresponding slot will be used first (if empty or compatible with added items). + If a_PrioritySlot is set to -1, regular order applies. Returns the number of items that fit. */ - int AddItem(cItem & a_ItemStack, bool a_AllowNewStacks = true, int a_PrioritarySlot = -1); + int AddItem(cItem & a_ItemStack, bool a_AllowNewStacks = true, int a_PrioritySlot = -1); /** Same as AddItem, but works on an entire list of item stacks. The a_ItemStackList is modified to reflect the leftover items. If a_AllowNewStacks is set to false, only existing stacks can be topped up; If a_AllowNewStacks is set to true, empty slots can be used for the rest. - If a_PrioritarySlot is set to a positive value, then the corresponding slot will be used first (if empty or compatible with added items). - If a_PrioritarySlot is set to -1, regular order applies. + If a_PrioritySlot is set to a positive value, then the corresponding slot will be used first (if empty or compatible with added items). + If a_PrioritySlot is set to -1, regular order applies. Returns the total number of items that fit. */ - int AddItems(cItems & a_ItemStackList, bool a_AllowNewStacks = true, int a_PrioritarySlot = -1); + int AddItems(cItems & a_ItemStackList, bool a_AllowNewStacks = true, int a_PrioritySlot = -1); /** Removes the specified item from the grid, as many as possible, up to a_ItemStack.m_ItemCount. Returns the number of items that were removed. */ @@ -185,8 +183,7 @@ public: protected: int m_Width; int m_Height; - int m_NumSlots; // m_Width * m_Height, for easier validity checking in the access functions - cItem * m_Slots; // x + m_Width * y + cLazyArray m_Slots; cListeners m_Listeners; ///< Listeners which should be notified on slot changes; the pointers are not owned by this object cCriticalSection m_CSListeners; ///< CS that guards the m_Listeners against multi-thread access diff --git a/src/LazyArray.h b/src/LazyArray.h new file mode 100644 index 000000000..7015d6c47 --- /dev/null +++ b/src/LazyArray.h @@ -0,0 +1,134 @@ + +#pragma once + +/** A dynamic array that defers allocation to the first modifying access. +Const references from the array before allocation will all be to the same default constructed value. +It is therefore important that default constructed values are indistinguishable from each other. */ +template +class cLazyArray +{ + static_assert((!std::is_reference::value && !std::is_array::value), + "cLazyArray: T must be a value type"); + static_assert(std::is_default_constructible::value, + "cLazyArray: T must be default constructible"); +public: + using value_type = T; + using pointer = T *; + using const_pointer = const T *; + using reference = T &; + using const_reference = const T &; + using size_type = int; + using iterator = pointer; + using const_iterator = const_pointer; + + cLazyArray(size_type a_Size) NOEXCEPT: + m_Size{ a_Size } + { + ASSERT(a_Size > 0); + } + + cLazyArray(const cLazyArray & a_Other): + m_Size{ a_Other.m_Size } + { + if (a_Other.IsStorageAllocated()) + { + // Note that begin() will allocate the array to copy into + std::copy(a_Other.begin(), a_Other.end(), begin()); + } + } + + cLazyArray(cLazyArray && a_Other) NOEXCEPT: + m_Array{ std::move(a_Other.m_Array) }, + m_Size{ a_Other.m_Size } + { + } + + cLazyArray & operator = (const cLazyArray & a_Other) + { + cLazyArray(a_Other).swap(*this); + return *this; + } + + cLazyArray & operator = (cLazyArray && a_Other) NOEXCEPT + { + m_Array = std::move(a_Other.m_Array); + m_Size = a_Other.m_Size; + return *this; + } + + T & operator [] (size_type a_Idx) + { + ASSERT((0 <= a_Idx) && (a_Idx < m_Size)); + return data()[a_Idx]; + } + + const T & operator [] (size_type a_Idx) const + { + return GetAt(a_Idx); + } + + // STL style interface + + const_iterator cbegin() const { return data(); } + iterator begin() { return data(); } + const_iterator begin() const { return cbegin(); } + + const_iterator cend() const { return data() + m_Size; } + iterator end() { return data() + m_Size; } + const_iterator end() const { return cend(); } + + size_type size() const NOEXCEPT { return m_Size; } + + const T * data() const + { + if (m_Array == nullptr) + { + m_Array.reset(new T[m_Size]); + } + return m_Array.get(); + } + + T * data() + { + static_assert(!std::is_const::value, ""); + const cLazyArray * const_this = this; + return const_cast(const_this->data()); + } + + void swap(cLazyArray & a_Other) NOEXCEPT + { + std::swap(m_Array, a_Other.m_Array); + std::swap(m_Size, a_Other.m_Size); + } + + friend void swap(cLazyArray & a_Lhs, cLazyArray & a_Rhs) NOEXCEPT + { + a_Lhs.swap(a_Rhs); + } + + // Extra functions to help avoid allocation + + /** A const view of an element of the array. Never causes the array to allocate. */ + const T & GetAt(size_type a_Idx) const + { + ASSERT((0 <= a_Idx) && (a_Idx < m_Size)); + if (IsStorageAllocated()) + { + return data()[a_Idx]; + } + else + { + static const T DefaultValue; + return DefaultValue; + } + } + + /** Returns true if the array has already been allocated. */ + bool IsStorageAllocated() const NOEXCEPT { return (m_Array != nullptr); } + +private: + // Mutable so const data() can allocate the array + mutable std::unique_ptr m_Array; + size_type m_Size; +}; + -- cgit v1.2.3