aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/common/Utilities/IteratorPair.h22
-rw-r--r--src/server/game/AI/CoreAI/UnitAI.cpp92
-rw-r--r--src/server/game/AI/CoreAI/UnitAI.h96
-rw-r--r--src/server/game/AI/ScriptedAI/ScriptedCreature.cpp5
-rw-r--r--src/server/game/AI/ScriptedAI/ScriptedCreature.h8
-rw-r--r--src/server/game/Combat/ThreatManager.cpp89
-rw-r--r--src/server/game/Combat/ThreatManager.h49
-rw-r--r--src/server/game/Maps/Map.cpp38
-rw-r--r--src/server/game/Maps/Map.h7
-rw-r--r--tests/game/ThreatListIterator.cpp65
10 files changed, 309 insertions, 162 deletions
diff --git a/src/common/Utilities/IteratorPair.h b/src/common/Utilities/IteratorPair.h
index 5d24c931ef2..0782862d20d 100644
--- a/src/common/Utilities/IteratorPair.h
+++ b/src/common/Utilities/IteratorPair.h
@@ -27,39 +27,39 @@ namespace Trinity
*
* @brief Utility class to enable range for loop syntax for multimap.equal_range uses
*/
- template<class iterator>
+ template<class iterator, class end_iterator = iterator>
class IteratorPair
{
public:
constexpr IteratorPair() : _iterators() { }
- constexpr IteratorPair(iterator first, iterator second) : _iterators(first, second) { }
- constexpr IteratorPair(std::pair<iterator, iterator> iterators) : _iterators(iterators) { }
+ constexpr IteratorPair(iterator first, end_iterator second) : _iterators(first, second) { }
+ constexpr IteratorPair(std::pair<iterator, end_iterator> iterators) : _iterators(iterators) { }
constexpr iterator begin() const { return _iterators.first; }
- constexpr iterator end() const { return _iterators.second; }
+ constexpr end_iterator end() const { return _iterators.second; }
private:
- std::pair<iterator, iterator> _iterators;
+ std::pair<iterator, end_iterator> _iterators;
};
namespace Containers
{
- template<typename iterator>
- constexpr Trinity::IteratorPair<iterator> MakeIteratorPair(iterator first, iterator second)
+ template<typename iterator, class end_iterator = iterator>
+ constexpr IteratorPair<iterator, end_iterator> MakeIteratorPair(iterator first, end_iterator second)
{
return { first, second };
}
- template<typename iterator>
- constexpr Trinity::IteratorPair<iterator> MakeIteratorPair(std::pair<iterator, iterator> iterators)
+ template<typename iterator, class end_iterator = iterator>
+ constexpr IteratorPair<iterator, end_iterator> MakeIteratorPair(std::pair<iterator, end_iterator> iterators)
{
return iterators;
}
template<class M>
- inline auto MapEqualRange(M& map, typename M::key_type const& key) -> IteratorPair<decltype(map.begin())>
+ auto MapEqualRange(M& map, typename M::key_type const& key)
{
- return { map.equal_range(key) };
+ return MakeIteratorPair(map.equal_range(key));
}
}
//! namespace Containers
diff --git a/src/server/game/AI/CoreAI/UnitAI.cpp b/src/server/game/AI/CoreAI/UnitAI.cpp
index ee296611df1..a807a178acb 100644
--- a/src/server/game/AI/CoreAI/UnitAI.cpp
+++ b/src/server/game/AI/CoreAI/UnitAI.cpp
@@ -16,6 +16,7 @@
*/
#include "UnitAI.h"
+#include "Containers.h"
#include "Creature.h"
#include "CreatureAIImpl.h"
#include "Map.h"
@@ -322,14 +323,97 @@ void UnitAI::FillAISpellInfo()
});
}
-ThreatManager& UnitAI::GetThreatManager()
+Unit* UnitAI::FinalizeTargetSelection(std::list<Unit*>& targetList, SelectTargetMethod targetType)
{
- return me->GetThreatManager();
+ // maybe nothing fulfills the predicate
+ if (targetList.empty())
+ return nullptr;
+
+ switch (targetType)
+ {
+ case SelectTargetMethod::MaxThreat:
+ case SelectTargetMethod::MinThreat:
+ case SelectTargetMethod::MaxDistance:
+ case SelectTargetMethod::MinDistance:
+ return targetList.front();
+ case SelectTargetMethod::Random:
+ return Trinity::Containers::SelectRandomContainerElement(targetList);
+ default:
+ break;
+ }
+
+ return nullptr;
}
-void UnitAI::SortByDistance(std::list<Unit*>& list, bool ascending)
+bool UnitAI::PrepareTargetListSelection(std::list<Unit*>& targetList, SelectTargetMethod targetType, uint32 offset)
{
- list.sort(Trinity::ObjectDistanceOrderPred(me, ascending));
+ targetList.clear();
+ ThreatManager& mgr = me->GetThreatManager();
+ // shortcut: we're gonna ignore the first <offset> elements, and there's at most <offset> elements, so we ignore them all - nothing to do here
+ if (mgr.GetThreatListSize() <= offset)
+ return false;
+
+ if (targetType == SelectTargetMethod::MaxDistance || targetType == SelectTargetMethod::MinDistance)
+ {
+ for (ThreatReference const* ref : mgr.GetUnsortedThreatList())
+ {
+ if (ref->IsOffline())
+ continue;
+
+ targetList.push_back(ref->GetVictim());
+ }
+ }
+ else
+ {
+ Unit* currentVictim = mgr.GetCurrentVictim();
+ if (currentVictim)
+ targetList.push_back(currentVictim);
+
+ for (ThreatReference const* ref : mgr.GetSortedThreatList())
+ {
+ if (ref->IsOffline())
+ continue;
+
+ Unit* thisTarget = ref->GetVictim();
+ if (thisTarget != currentVictim)
+ targetList.push_back(thisTarget);
+ }
+ }
+
+ // shortcut: the list isn't gonna get any larger
+ if (targetList.size() <= offset)
+ {
+ targetList.clear();
+ return false;
+ }
+
+ // right now, list is unsorted for DISTANCE types - re-sort by SelectTargetMethod::MaxDistance
+ if (targetType == SelectTargetMethod::MaxDistance || targetType == SelectTargetMethod::MinDistance)
+ targetList.sort(Trinity::ObjectDistanceOrderPred(me, targetType == SelectTargetMethod::MinDistance));
+
+ // now the list is MAX sorted, reverse for MIN types
+ if (targetType == SelectTargetMethod::MinThreat)
+ targetList.reverse();
+
+ // ignore the first <offset> elements
+ while (offset)
+ {
+ targetList.pop_front();
+ --offset;
+ }
+
+ return true;
+}
+
+void UnitAI::FinalizeTargetListSelection(std::list<Unit*>& targetList, uint32 num, SelectTargetMethod targetType)
+{
+ if (targetList.size() <= num)
+ return;
+
+ if (targetType == SelectTargetMethod::Random)
+ Trinity::Containers::RandomResize(targetList, num);
+ else
+ targetList.resize(num);
}
std::string UnitAI::GetDebugInfo() const
diff --git a/src/server/game/AI/CoreAI/UnitAI.h b/src/server/game/AI/CoreAI/UnitAI.h
index 19f266ba45d..631f4f45ff6 100644
--- a/src/server/game/AI/CoreAI/UnitAI.h
+++ b/src/server/game/AI/CoreAI/UnitAI.h
@@ -18,11 +18,10 @@
#ifndef TRINITY_UNITAI_H
#define TRINITY_UNITAI_H
-#include "Containers.h"
#include "Errors.h"
#include "ObjectGuid.h"
+#include "SharedDefines.h"
#include "SpellDefines.h"
-#include "ThreatManager.h"
#include <unordered_map>
#define CAST_AI(a, b) (dynamic_cast<a*>(b))
@@ -176,30 +175,10 @@ class TC_GAME_API UnitAI
template<class PREDICATE>
Unit* SelectTarget(SelectTargetMethod targetType, uint32 offset, PREDICATE const& predicate)
{
- ThreatManager& mgr = GetThreatManager();
- // shortcut: if we ignore the first <offset> elements, and there are at most <offset> elements, then we ignore ALL elements
- if (mgr.GetThreatListSize() <= offset)
- return nullptr;
-
std::list<Unit*> targetList;
- SelectTargetList(targetList, mgr.GetThreatListSize(), targetType, offset, predicate);
-
- // maybe nothing fulfills the predicate
- if (targetList.empty())
- return nullptr;
-
- switch (targetType)
- {
- case SelectTargetMethod::MaxThreat:
- case SelectTargetMethod::MinThreat:
- case SelectTargetMethod::MaxDistance:
- case SelectTargetMethod::MinDistance:
- return targetList.front();
- case SelectTargetMethod::Random:
- return Trinity::Containers::SelectRandomContainerElement(targetList);
- default:
- return nullptr;
- }
+ SelectTargetList(targetList, std::numeric_limits<uint32>::max(), targetType, offset, predicate);
+
+ return FinalizeTargetSelection(targetList, targetType);
}
// Select the best (up to) <num> targets (in <targetType> order) from the threat list that fulfill the following:
@@ -220,71 +199,13 @@ class TC_GAME_API UnitAI
template <class PREDICATE>
void SelectTargetList(std::list<Unit*>& targetList, uint32 num, SelectTargetMethod targetType, uint32 offset, PREDICATE const& predicate)
{
- targetList.clear();
- ThreatManager& mgr = GetThreatManager();
- // shortcut: we're gonna ignore the first <offset> elements, and there's at most <offset> elements, so we ignore them all - nothing to do here
- if (mgr.GetThreatListSize() <= offset)
+ if (!PrepareTargetListSelection(targetList, targetType, offset))
return;
- if (targetType == SelectTargetMethod::MaxDistance || targetType == SelectTargetMethod::MinDistance)
- {
- for (ThreatReference const* ref : mgr.GetUnsortedThreatList())
- {
- if (ref->IsOffline())
- continue;
-
- targetList.push_back(ref->GetVictim());
- }
- }
- else
- {
- Unit* currentVictim = mgr.GetCurrentVictim();
- if (currentVictim)
- targetList.push_back(currentVictim);
-
- for (ThreatReference const* ref : mgr.GetSortedThreatList())
- {
- if (ref->IsOffline())
- continue;
-
- Unit* thisTarget = ref->GetVictim();
- if (thisTarget != currentVictim)
- targetList.push_back(thisTarget);
- }
- }
-
- // shortcut: the list isn't gonna get any larger
- if (targetList.size() <= offset)
- {
- targetList.clear();
- return;
- }
-
- // right now, list is unsorted for DISTANCE types - re-sort by SelectTargetMethod::MaxDistance
- if (targetType == SelectTargetMethod::MaxDistance || targetType == SelectTargetMethod::MinDistance)
- SortByDistance(targetList, targetType == SelectTargetMethod::MinDistance);
-
- // now the list is MAX sorted, reverse for MIN types
- if (targetType == SelectTargetMethod::MinThreat)
- targetList.reverse();
-
- // ignore the first <offset> elements
- while (offset)
- {
- targetList.pop_front();
- --offset;
- }
-
// then finally filter by predicate
targetList.remove_if([&predicate](Unit* target) { return !predicate(target); });
- if (targetList.size() <= num)
- return;
-
- if (targetType == SelectTargetMethod::Random)
- Trinity::Containers::RandomResize(targetList, num);
- else
- targetList.resize(num);
+ FinalizeTargetListSelection(targetList, num, targetType);
}
// Called when the unit enters combat
@@ -339,8 +260,9 @@ class TC_GAME_API UnitAI
UnitAI(UnitAI const& right) = delete;
UnitAI& operator=(UnitAI const& right) = delete;
- ThreatManager& GetThreatManager();
- void SortByDistance(std::list<Unit*>& list, bool ascending = true);
+ Unit* FinalizeTargetSelection(std::list<Unit*>& targetList, SelectTargetMethod targetType);
+ bool PrepareTargetListSelection(std::list<Unit*>& targetList, SelectTargetMethod targetType, uint32 offset);
+ void FinalizeTargetListSelection(std::list<Unit*>& targetList, uint32 num, SelectTargetMethod targetType);
};
#endif
diff --git a/src/server/game/AI/ScriptedAI/ScriptedCreature.cpp b/src/server/game/AI/ScriptedAI/ScriptedCreature.cpp
index c6c232f57eb..fd01ee4b423 100644
--- a/src/server/game/AI/ScriptedAI/ScriptedCreature.cpp
+++ b/src/server/game/AI/ScriptedAI/ScriptedCreature.cpp
@@ -109,8 +109,11 @@ bool SummonList::HasEntry(uint32 entry) const
return false;
}
-void SummonList::DoActionImpl(int32 action, StorageType const& summons)
+void SummonList::DoActionImpl(int32 action, StorageType& summons, uint16 max)
{
+ if (max)
+ Trinity::Containers::RandomResize(summons, max);
+
for (ObjectGuid const& guid : summons)
{
Creature* summon = ObjectAccessor::GetCreature(*_me, guid);
diff --git a/src/server/game/AI/ScriptedAI/ScriptedCreature.h b/src/server/game/AI/ScriptedAI/ScriptedCreature.h
index d8d3a356c06..bcb0496ec36 100644
--- a/src/server/game/AI/ScriptedAI/ScriptedCreature.h
+++ b/src/server/game/AI/ScriptedAI/ScriptedCreature.h
@@ -98,9 +98,9 @@ public:
void DoAction(int32 info, Predicate&& predicate, uint16 max = 0)
{
// We need to use a copy of SummonList here, otherwise original SummonList would be modified
- StorageType listCopy = _storage;
- Trinity::Containers::RandomResize<StorageType, Predicate>(listCopy, std::forward<Predicate>(predicate), max);
- DoActionImpl(info, listCopy);
+ StorageType listCopy;
+ std::copy_if(std::begin(_storage), std::end(_storage), std::inserter(listCopy, std::end(listCopy)), predicate);
+ DoActionImpl(info, listCopy, max);
}
void DoZoneInCombat(uint32 entry = 0);
@@ -108,7 +108,7 @@ public:
bool HasEntry(uint32 entry) const;
private:
- void DoActionImpl(int32 action, StorageType const& summons);
+ void DoActionImpl(int32 action, StorageType& summons, uint16 max);
Creature* _me;
StorageType _storage;
diff --git a/src/server/game/Combat/ThreatManager.cpp b/src/server/game/Combat/ThreatManager.cpp
index ea41b10e61e..81640f2eca3 100644
--- a/src/server/game/Combat/ThreatManager.cpp
+++ b/src/server/game/Combat/ThreatManager.cpp
@@ -26,12 +26,17 @@
#include "SpellAuraEffects.h"
#include "SpellMgr.h"
#include "TemporarySummon.h"
+#include <boost/heap/fibonacci_heap.hpp>
#include "Hacks/boost_1_74_fibonacci_heap.h"
BOOST_1_74_FIBONACCI_HEAP_MSVC_COMPILE_FIX(ThreatManager::threat_list_heap::value_type)
const CompareThreatLessThan ThreatManager::CompareThreat;
+class ThreatManager::Heap : public boost::heap::fibonacci_heap<ThreatReference const*, boost::heap::compare<CompareThreatLessThan>>
+{
+};
+
void ThreatReference::AddThreat(float amount)
{
if (amount == 0.0f)
@@ -148,6 +153,24 @@ void ThreatReference::UnregisterAndFree()
delete this;
}
+class ThreatReferenceImpl : public ThreatReference
+{
+public:
+ explicit ThreatReferenceImpl(ThreatManager* mgr, Unit* victim) : ThreatReference(mgr, victim) { }
+
+ ThreatManager::Heap::handle_type _handle;
+};
+
+void ThreatReference::HeapNotifyIncreased()
+{
+ _mgr._sortedThreatList->increase(static_cast<ThreatReferenceImpl*>(this)->_handle);
+}
+
+void ThreatReference::HeapNotifyDecreased()
+{
+ _mgr._sortedThreatList->decrease(static_cast<ThreatReferenceImpl*>(this)->_handle);
+}
+
/*static*/ bool ThreatManager::CanHaveThreatList(Unit const* who)
{
Creature const* cWho = who->ToCreature();
@@ -168,7 +191,8 @@ void ThreatReference::UnregisterAndFree()
return true;
}
-ThreatManager::ThreatManager(Unit* owner) : _owner(owner), _ownerCanHaveThreatList(false), _needClientUpdate(false), _updateTimer(THREAT_UPDATE_INTERVAL), _currentVictimRef(nullptr), _fixateRef(nullptr)
+ThreatManager::ThreatManager(Unit* owner) : _owner(owner), _ownerCanHaveThreatList(false), _needClientUpdate(false), _updateTimer(THREAT_UPDATE_INTERVAL),
+ _sortedThreatList(std::make_unique<Heap>()), _currentVictimRef(nullptr), _fixateRef(nullptr)
{
for (int8 i = 0; i < MAX_SPELL_SCHOOL; ++i)
_singleSchoolModifiers[i] = 1.0f;
@@ -177,7 +201,7 @@ ThreatManager::ThreatManager(Unit* owner) : _owner(owner), _ownerCanHaveThreatLi
ThreatManager::~ThreatManager()
{
ASSERT(_myThreatListEntries.empty(), "ThreatManager::~ThreatManager - %s: we still have %zu things threatening us, one of them is %s.", _owner->GetGUID().ToString().c_str(), _myThreatListEntries.size(), _myThreatListEntries.begin()->first.ToString().c_str());
- ASSERT(_sortedThreatList.empty(), "ThreatManager::~ThreatManager - %s: we still have %zu things threatening us, one of them is %s.", _owner->GetGUID().ToString().c_str(), _sortedThreatList.size(), (*_sortedThreatList.begin())->GetVictim()->GetGUID().ToString().c_str());
+ ASSERT(_sortedThreatList->empty(), "ThreatManager::~ThreatManager - %s: we still have %zu things threatening us, one of them is %s.", _owner->GetGUID().ToString().c_str(), _sortedThreatList->size(), (*_sortedThreatList->begin())->GetVictim()->GetGUID().ToString().c_str());
ASSERT(_threatenedByMe.empty(), "ThreatManager::~ThreatManager - %s: we are still threatening %zu things, one of them is %s.", _owner->GetGUID().ToString().c_str(), _threatenedByMe.size(), _threatenedByMe.begin()->first.ToString().c_str());
}
@@ -216,7 +240,7 @@ Unit* ThreatManager::GetLastVictim() const
Unit* ThreatManager::GetAnyTarget() const
{
- for (ThreatReference const* ref : _sortedThreatList)
+ for (ThreatReference const* ref : *_sortedThreatList)
if (!ref->IsOffline())
return ref->GetVictim();
return nullptr;
@@ -225,8 +249,8 @@ Unit* ThreatManager::GetAnyTarget() const
bool ThreatManager::IsThreatListEmpty(bool includeOffline) const
{
if (includeOffline)
- return _sortedThreatList.empty();
- for (ThreatReference const* ref : _sortedThreatList)
+ return _sortedThreatList->empty();
+ for (ThreatReference const* ref : *_sortedThreatList)
if (ref->IsAvailable())
return false;
return true;
@@ -249,11 +273,44 @@ float ThreatManager::GetThreat(Unit const* who, bool includeOffline) const
return (includeOffline || it->second->IsAvailable()) ? it->second->GetThreat() : 0.0f;
}
+size_t ThreatManager::GetThreatListSize() const
+{
+ return _sortedThreatList->size();
+}
+
+Trinity::IteratorPair<ThreatManager::ThreatListIterator, std::nullptr_t> ThreatManager::GetUnsortedThreatList() const
+{
+ auto itr = _myThreatListEntries.begin();
+ auto end = _myThreatListEntries.end();
+ std::function<ThreatReference const* ()> generator = [itr, end]() mutable -> ThreatReference const*
+ {
+ if (itr == end)
+ return nullptr;
+
+ return (itr++)->second;
+ };
+ return { ThreatListIterator{ std::move(generator) }, nullptr };
+}
+
+Trinity::IteratorPair<ThreatManager::ThreatListIterator, std::nullptr_t> ThreatManager::GetSortedThreatList() const
+{
+ auto itr = _sortedThreatList->ordered_begin();
+ auto end = _sortedThreatList->ordered_end();
+ std::function<ThreatReference const* ()> generator = [itr, end]() mutable -> ThreatReference const*
+ {
+ if (itr == end)
+ return nullptr;
+
+ return *(itr++);
+ };
+ return { ThreatListIterator{ std::move(generator) }, nullptr };
+}
+
std::vector<ThreatReference*> ThreatManager::GetModifiableThreatList()
{
std::vector<ThreatReference*> list;
list.reserve(_myThreatListEntries.size());
- for (auto it = _sortedThreatList.ordered_begin(), end = _sortedThreatList.ordered_end(); it != end; ++it)
+ for (auto it = _sortedThreatList->ordered_begin(), end = _sortedThreatList->ordered_end(); it != end; ++it)
list.push_back(const_cast<ThreatReference*>(*it));
return list;
}
@@ -395,7 +452,7 @@ void ThreatManager::AddThreat(Unit* target, float amount, SpellInfo const* spell
}
// ok, we're now in combat - create the threat list reference and push it to the respective managers
- ThreatReference* ref = new ThreatReference(this, target);
+ ThreatReference* ref = new ThreatReferenceImpl(this, target);
PutThreatListRef(target->GetGUID(), ref);
target->GetThreatManager().PutThreatenedByMeRef(_owner->GetGUID(), ref);
@@ -418,10 +475,10 @@ void ThreatManager::ScaleThreat(Unit* target, float factor)
void ThreatManager::MatchUnitThreatToHighestThreat(Unit* target)
{
- if (_sortedThreatList.empty())
+ if (_sortedThreatList->empty())
return;
- auto it = _sortedThreatList.ordered_begin(), end = _sortedThreatList.ordered_end();
+ auto it = _sortedThreatList->ordered_begin(), end = _sortedThreatList->ordered_end();
ThreatReference const* highest = *it;
if (!highest->IsAvailable())
return;
@@ -530,7 +587,7 @@ void ThreatManager::UpdateVictim()
ThreatReference const* ThreatManager::ReselectVictim()
{
- if (_sortedThreatList.empty())
+ if (_sortedThreatList->empty())
return nullptr;
for (auto const& pair : _myThreatListEntries)
@@ -544,7 +601,7 @@ ThreatReference const* ThreatManager::ReselectVictim()
if (oldVictimRef && oldVictimRef->IsOffline())
oldVictimRef = nullptr;
// in 99% of cases - we won't need to actually look at anything beyond the first element
- ThreatReference const* highest = _sortedThreatList.top();
+ ThreatReference const* highest = _sortedThreatList->top();
// if the highest reference is offline, the entire list is offline, and we indicate this
if (!highest->IsAvailable())
return nullptr;
@@ -562,7 +619,7 @@ ThreatReference const* ThreatManager::ReselectVictim()
return highest;
// If we get here, highest threat is ranged, but below 130% of current - there might be a melee that breaks 110% below us somewhere, so now we need to actually look at the next highest element
// luckily, this is a heap, so getting the next highest element is O(log n), and we're just gonna do that repeatedly until we've seen enough targets (or find a target)
- auto it = _sortedThreatList.ordered_begin(), end = _sortedThreatList.ordered_end();
+ auto it = _sortedThreatList->ordered_begin(), end = _sortedThreatList->ordered_end();
while (it != end)
{
ThreatReference const* next = *it;
@@ -772,8 +829,8 @@ void ThreatManager::SendThreatListToClients(bool newHighest) const
auto fillSharedPacketDataAndSend = [&](auto& packet)
{
packet.UnitGUID = _owner->GetGUID();
- packet.ThreatList.reserve(_sortedThreatList.size());
- for (ThreatReference const* ref : _sortedThreatList)
+ packet.ThreatList.reserve(_sortedThreatList->size());
+ for (ThreatReference const* ref : *_sortedThreatList)
{
if (!ref->IsAvailable())
continue;
@@ -805,7 +862,7 @@ void ThreatManager::PutThreatListRef(ObjectGuid const& guid, ThreatReference* re
auto& inMap = _myThreatListEntries[guid];
ASSERT(!inMap, "Duplicate threat reference at %p being inserted on %s for %s - memory leak!", ref, _owner->GetGUID().ToString().c_str(), guid.ToString().c_str());
inMap = ref;
- ref->_handle = _sortedThreatList.push(ref);
+ static_cast<ThreatReferenceImpl*>(ref)->_handle = _sortedThreatList->push(ref);
}
void ThreatManager::PurgeThreatListRef(ObjectGuid const& guid)
@@ -815,7 +872,7 @@ void ThreatManager::PurgeThreatListRef(ObjectGuid const& guid)
return;
ThreatReference* ref = it->second;
_myThreatListEntries.erase(it);
- _sortedThreatList.erase(ref->_handle);
+ _sortedThreatList->erase(static_cast<ThreatReferenceImpl*>(ref)->_handle);
if (_fixateRef == ref)
_fixateRef = nullptr;
diff --git a/src/server/game/Combat/ThreatManager.h b/src/server/game/Combat/ThreatManager.h
index 8e722707f91..36885802068 100644
--- a/src/server/game/Combat/ThreatManager.h
+++ b/src/server/game/Combat/ThreatManager.h
@@ -22,7 +22,6 @@
#include "IteratorPair.h"
#include "ObjectGuid.h"
#include "SharedDefines.h"
-#include <boost/heap/fibonacci_heap.hpp>
#include <array>
#include <unordered_map>
#include <vector>
@@ -81,7 +80,7 @@ struct CompareThreatLessThan
class TC_GAME_API ThreatManager
{
public:
- typedef boost::heap::fibonacci_heap<ThreatReference const*, boost::heap::compare<CompareThreatLessThan>> threat_list_heap;
+ class Heap;
class ThreatListIterator;
static const uint32 THREAT_UPDATE_INTERVAL = 1000u;
@@ -115,14 +114,14 @@ class TC_GAME_API ThreatManager
bool IsThreatenedBy(Unit const* who, bool includeOffline = false) const;
// returns ThreatReference amount if a ref exists, 0.0f otherwise
float GetThreat(Unit const* who, bool includeOffline = false) const;
- size_t GetThreatListSize() const { return _sortedThreatList.size(); }
+ size_t GetThreatListSize() const;
// fastest of the three threat list getters - gets the threat list in "arbitrary" order
// iterators will invalidate on adding/removing entries from the threat list; slightly less finicky than GetSorted.
- Trinity::IteratorPair<ThreatListIterator> GetUnsortedThreatList() const { return { _myThreatListEntries.begin(), _myThreatListEntries.end() }; }
+ Trinity::IteratorPair<ThreatListIterator, std::nullptr_t> GetUnsortedThreatList() const;
// slightly slower than GetUnsorted, but, well...sorted - only use it if you need the sorted property, of course
// this iterator pair will invalidate on any modification (even indirect) of the threat list; spell casts and similar can all induce this!
// note: current tank is NOT guaranteed to be the first entry in this list - check GetLastVictim separately if you want that!
- Trinity::IteratorPair<threat_list_heap::ordered_iterator> GetSortedThreatList() const { return { _sortedThreatList.ordered_begin(), _sortedThreatList.ordered_end() }; }
+ Trinity::IteratorPair<ThreatListIterator, std::nullptr_t> GetSortedThreatList() const;
// slowest of the three threat list getters (by far), but lets you modify the threat references - this is also sorted
std::vector<ThreatReference*> GetModifiableThreatList();
@@ -198,7 +197,7 @@ class TC_GAME_API ThreatManager
bool _needClientUpdate;
uint32 _updateTimer;
- threat_list_heap _sortedThreatList;
+ std::unique_ptr<Heap> _sortedThreatList;
std::unordered_map<ObjectGuid, ThreatReference*> _myThreatListEntries;
// AI notifies are delayed to ensure we are in a consistent state before we call out to arbitrary logic
@@ -231,19 +230,26 @@ class TC_GAME_API ThreatManager
class ThreatListIterator
{
- private:
- decltype(_myThreatListEntries)::const_iterator _it;
-
- public:
- ThreatReference const* operator*() const { return _it->second; }
- ThreatReference const* operator->() const { return _it->second; }
- ThreatListIterator& operator++() { ++_it; return *this; }
- bool operator==(ThreatListIterator const& o) const { return _it == o._it; }
- bool operator!=(ThreatListIterator const& o) const { return _it != o._it; }
- ThreatListIterator(decltype(_it) it) : _it(it) {}
+ private:
+ std::function<ThreatReference const* ()> _generator;
+ ThreatReference const* _current;
+
+ friend ThreatManager;
+ explicit ThreatListIterator(std::function<ThreatReference const* ()>&& generator)
+ : _generator(std::move(generator)), _current(_generator()) {}
+
+ public:
+ ThreatReference const* operator*() const { return _current; }
+ ThreatReference const* operator->() const { return _current; }
+ ThreatListIterator& operator++() { _current = _generator(); return *this; }
+ bool operator==(ThreatListIterator const& o) const { return _current == o._current; }
+ bool operator!=(ThreatListIterator const& o) const { return _current != o._current; }
+ bool operator==(std::nullptr_t) const { return _current == nullptr; }
+ bool operator!=(std::nullptr_t) const { return _current != nullptr; }
};
friend class ThreatReference;
+ friend class ThreatReferenceImpl;
friend struct CompareThreatLessThan;
friend class debug_commandscript;
};
@@ -274,16 +280,18 @@ class TC_GAME_API ThreatReference
void ClearThreat(); // dealloc's this
- private:
+ protected:
static bool FlagsAllowFighting(Unit const* a, Unit const* b);
- ThreatReference(ThreatManager* mgr, Unit* victim) :
+ explicit ThreatReference(ThreatManager* mgr, Unit* victim) :
_owner(reinterpret_cast<Creature*>(mgr->_owner)), _mgr(*mgr), _victim(victim),
_baseAmount(0.0f), _tempModifier(0), _taunted(TAUNT_STATE_NONE)
{
_online = ONLINE_STATE_OFFLINE;
}
+ virtual ~ThreatReference() = default;
+
void UnregisterAndFree();
bool ShouldBeOffline() const;
@@ -291,14 +299,13 @@ class TC_GAME_API ThreatReference
void UpdateTauntState(TauntState state = TAUNT_STATE_NONE);
Creature* const _owner;
ThreatManager& _mgr;
- void HeapNotifyIncreased() { _mgr._sortedThreatList.increase(_handle); }
- void HeapNotifyDecreased() { _mgr._sortedThreatList.decrease(_handle); }
+ void HeapNotifyIncreased();
+ void HeapNotifyDecreased();
Unit* const _victim;
OnlineState _online;
float _baseAmount;
int32 _tempModifier; // Temporary effects (auras with SPELL_AURA_MOD_TOTAL_THREAT) - set from victim's threatmanager in ThreatManager::UpdateMyTempModifiers
TauntState _taunted;
- ThreatManager::threat_list_heap::handle_type _handle;
public:
ThreatReference(ThreatReference const&) = delete;
diff --git a/src/server/game/Maps/Map.cpp b/src/server/game/Maps/Map.cpp
index 31c5193e7d8..fdec078db36 100644
--- a/src/server/game/Maps/Map.cpp
+++ b/src/server/game/Maps/Map.cpp
@@ -62,6 +62,7 @@
#include "WorldSession.h"
#include "WorldStateMgr.h"
#include "WorldStatePackets.h"
+#include <boost/heap/fibonacci_heap.hpp>
#include <sstream>
#include "Hacks/boost_1_74_fibonacci_heap.h"
@@ -76,6 +77,17 @@ GridState* si_GridStates[MAX_GRID_STATE];
ZoneDynamicInfo::ZoneDynamicInfo() : MusicId(0), DefaultWeather(nullptr), WeatherId(WEATHER_STATE_FINE),
Intensity(0.0f) { }
+struct RespawnInfoWithHandle;
+struct RespawnListContainer : boost::heap::fibonacci_heap<RespawnInfoWithHandle*, boost::heap::compare<CompareRespawnInfo>>
+{
+};
+struct RespawnInfoWithHandle : RespawnInfo
+{
+ explicit RespawnInfoWithHandle(RespawnInfo const& other) : RespawnInfo(other) { }
+
+ RespawnListContainer::handle_type handle;
+};
+
Map::~Map()
{
// UnloadAll must be called before deleting the map
@@ -134,7 +146,7 @@ m_unloadTimer(0), m_VisibleDistance(DEFAULT_VISIBILITY_DISTANCE),
m_VisibilityNotifyPeriod(DEFAULT_VISIBILITY_NOTIFY_PERIOD),
m_activeNonPlayersIter(m_activeNonPlayers.end()), _transportsUpdateIter(_transports.end()),
i_gridExpiry(expiry), m_terrain(sTerrainMgr.LoadTerrain(id)),
-i_scriptLock(false), _respawnCheckTimer(0)
+i_scriptLock(false), _respawnTimes(std::make_unique<RespawnListContainer>()), _respawnCheckTimer(0)
{
for (uint32 x = 0; x < MAX_NUMBER_OF_GRIDS; ++x)
{
@@ -2011,7 +2023,7 @@ void Map::Respawn(RespawnInfo* info, CharacterDatabaseTransaction dbTrans)
if (info->respawnTime <= GameTime::GetGameTime())
return;
info->respawnTime = GameTime::GetGameTime();
- _respawnTimes.increase(info->handle);
+ _respawnTimes->increase(static_cast<RespawnInfoWithHandle*>(info)->handle);
SaveRespawnInfoDB(*info, dbTrans);
}
@@ -2067,8 +2079,8 @@ bool Map::AddRespawnInfo(RespawnInfo const& info)
else
ABORT_MSG("Invalid respawn info for spawn id (%u," UI64FMTD ") being inserted", uint32(info.type), info.spawnId);
- RespawnInfo * ri = new RespawnInfo(info);
- ri->handle = _respawnTimes.push(ri);
+ RespawnInfoWithHandle* ri = new RespawnInfoWithHandle(info);
+ ri->handle = _respawnTimes->push(ri);
bySpawnIdMap->emplace(ri->spawnId, ri);
return true;
}
@@ -2101,9 +2113,9 @@ RespawnInfo* Map::GetRespawnInfo(SpawnObjectType type, ObjectGuid::LowType spawn
void Map::UnloadAllRespawnInfos() // delete everything from memory
{
- for (RespawnInfo* info : _respawnTimes)
+ for (RespawnInfo* info : *_respawnTimes)
delete info;
- _respawnTimes.clear();
+ _respawnTimes->clear();
_creatureRespawnTimesBySpawnId.clear();
_gameObjectRespawnTimesBySpawnId.clear();
}
@@ -2124,7 +2136,7 @@ void Map::DeleteRespawnInfo(RespawnInfo* info, CharacterDatabaseTransaction dbTr
spawnMap->erase(it);
// respawn heap
- _respawnTimes.erase(info->handle);
+ _respawnTimes->erase(static_cast<RespawnInfoWithHandle*>(info)->handle);
// database
DeleteRespawnInfoFromDB(info->type, info->spawnId, dbTrans);
@@ -2175,16 +2187,16 @@ void Map::DoRespawn(SpawnObjectType type, ObjectGuid::LowType spawnId, uint32 gr
void Map::ProcessRespawns()
{
time_t now = GameTime::GetGameTime();
- while (!_respawnTimes.empty())
+ while (!_respawnTimes->empty())
{
- RespawnInfo* next = _respawnTimes.top();
+ RespawnInfoWithHandle* next = _respawnTimes->top();
if (now < next->respawnTime) // done for this tick
break;
if (uint32 poolId = sPoolMgr->IsPartOfAPool(next->type, next->spawnId)) // is this part of a pool?
{ // if yes, respawn will be handled by (external) pooling logic, just delete the respawn time
// step 1: remove entry from maps to avoid it being reachable by outside logic
- _respawnTimes.pop();
+ _respawnTimes->pop();
ASSERT_NOTNULL(GetRespawnMapForType(next->type))->erase(next->spawnId);
// step 2: tell pooling logic to do its thing
@@ -2197,7 +2209,7 @@ void Map::ProcessRespawns()
else if (CheckRespawn(next)) // see if we're allowed to respawn
{ // ok, respawn
// step 1: remove entry from maps to avoid it being reachable by outside logic
- _respawnTimes.pop();
+ _respawnTimes->pop();
ASSERT_NOTNULL(GetRespawnMapForType(next->type))->erase(next->spawnId);
// step 2: do the respawn, which involves external logic
@@ -2209,7 +2221,7 @@ void Map::ProcessRespawns()
}
else if (!next->respawnTime)
{ // just remove this respawn entry without rescheduling
- _respawnTimes.pop();
+ _respawnTimes->pop();
ASSERT_NOTNULL(GetRespawnMapForType(next->type))->erase(next->spawnId);
RemoveRespawnTime(next->type, next->spawnId, nullptr, true);
delete next;
@@ -2217,7 +2229,7 @@ void Map::ProcessRespawns()
else
{ // new respawn time, update heap position
ASSERT(now < next->respawnTime); // infinite loop guard
- _respawnTimes.decrease(next->handle);
+ _respawnTimes->decrease(next->handle);
SaveRespawnInfoDB(*next);
}
}
diff --git a/src/server/game/Maps/Map.h b/src/server/game/Maps/Map.h
index 92740108dbb..a3061418e4a 100644
--- a/src/server/game/Maps/Map.h
+++ b/src/server/game/Maps/Map.h
@@ -36,7 +36,6 @@
#include "SpawnData.h"
#include "Timer.h"
#include "WorldStateDefines.h"
-#include <boost/heap/fibonacci_heap.hpp>
#include <bitset>
#include <list>
#include <map>
@@ -157,8 +156,7 @@ struct CompareRespawnInfo
bool operator()(RespawnInfo const* a, RespawnInfo const* b) const;
};
using ZoneDynamicInfoMap = std::unordered_map<uint32 /*zoneId*/, ZoneDynamicInfo>;
-using RespawnListContainer = boost::heap::fibonacci_heap<RespawnInfo*, boost::heap::compare<CompareRespawnInfo>>;
-using RespawnListHandle = RespawnListContainer::handle_type;
+struct RespawnListContainer;
using RespawnInfoMap = std::unordered_map<ObjectGuid::LowType, RespawnInfo*>;
struct RespawnInfo
{
@@ -167,7 +165,6 @@ struct RespawnInfo
uint32 entry;
time_t respawnTime;
uint32 gridId;
- RespawnListHandle handle;
};
inline bool CompareRespawnInfo::operator()(RespawnInfo const* a, RespawnInfo const* b) const
{
@@ -724,7 +721,7 @@ class TC_GAME_API Map : public GridRefManager<NGridType>
m_activeNonPlayers.erase(obj);
}
- RespawnListContainer _respawnTimes;
+ std::unique_ptr<RespawnListContainer> _respawnTimes;
RespawnInfoMap _creatureRespawnTimesBySpawnId;
RespawnInfoMap _gameObjectRespawnTimesBySpawnId;
RespawnInfoMap* GetRespawnMapForType(SpawnObjectType type)
diff --git a/tests/game/ThreatListIterator.cpp b/tests/game/ThreatListIterator.cpp
new file mode 100644
index 00000000000..7121b783579
--- /dev/null
+++ b/tests/game/ThreatListIterator.cpp
@@ -0,0 +1,65 @@
+/*
+ * This file is part of the TrinityCore Project. See AUTHORS file for Copyright information
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "tc_catch2.h"
+
+#include "IteratorPair.h"
+
+class ThreatListIterator
+{
+private:
+ std::function<int const* ()> _generator;
+ int const* _current;
+
+public:
+ explicit ThreatListIterator(std::function<int const* ()>&& generator)
+ : _generator(std::move(generator)), _current(_generator())
+ { }
+
+ int const* operator*() const { return _current; }
+ int const* operator->() const { return _current; }
+ ThreatListIterator& operator++() { _current = _generator(); return *this; }
+ bool operator==(ThreatListIterator const& o) const { return _current == o._current; }
+ bool operator!=(ThreatListIterator const& o) const { return _current != o._current; }
+ bool operator==(std::nullptr_t) const { return _current == nullptr; }
+ bool operator!=(std::nullptr_t) const { return _current != nullptr; }
+};
+
+std::vector<int> ints{ 1, 2, 3, 4 };
+
+Trinity::IteratorPair<ThreatListIterator, std::nullptr_t> GetUnsortedThreatList()
+{
+ auto itr = ints.begin();
+ auto end = ints.end();
+ std::function<int const* ()> generator = [itr, end]() mutable -> int const*
+ {
+ if (itr == end)
+ return nullptr;
+
+ return &*(itr++);
+ };
+ return { ThreatListIterator{ std::move(generator) }, nullptr };
+}
+
+TEST_CASE("Check generator logic", "[ThreatListIterator]")
+{
+ std::vector<int> iterated;
+ for (int const* i : GetUnsortedThreatList())
+ iterated.push_back(*i);
+
+ REQUIRE(iterated == ints);
+}