summaryrefslogtreecommitdiff
path: root/src/misc
diff options
context:
space:
mode:
authoryexo <yexo@openttd.org>2010-02-18 14:23:18 +0000
committeryexo <yexo@openttd.org>2010-02-18 14:23:18 +0000
commit1abc0db336655f16fcc584fb8f5521beeb063234 (patch)
tree37cf4216c4ca8912fa2fed96f0ccbe86880f857e /src/misc
parente2e2310e169e87be1222de43fc5abf85cf18bc17 (diff)
downloadopenttd-1abc0db336655f16fcc584fb8f5521beeb063234.tar.xz
(svn r19160) -Codechange: Enlarge a CBinaryHeapT if the heap is full instead of dropping the added item
-Fix: CBinaryHeapT::CheckConsistency compared pointers instead of the actual items (skidd13)
Diffstat (limited to 'src/misc')
-rw-r--r--src/misc/binaryheap.hpp19
1 files changed, 10 insertions, 9 deletions
diff --git a/src/misc/binaryheap.hpp b/src/misc/binaryheap.hpp
index 6d8044c67..85dc202f0 100644
--- a/src/misc/binaryheap.hpp
+++ b/src/misc/binaryheap.hpp
@@ -44,13 +44,13 @@ public:
: m_size(0)
, m_max_size(max_items)
{
- m_items = new ItemPtr[max_items + 1];
+ m_items = MallocT<ItemPtr>(max_items + 1);
}
~CBinaryHeapT()
{
Clear();
- delete [] m_items;
+ free(m_items);
m_items = NULL;
}
@@ -71,9 +71,8 @@ public:
* Return the smallest item, or throw assert if empty. */
FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];}
- /** Insert new item into the priority queue, maintaining heap order.
- * @return false if the queue is full. */
- bool Push(Titem_& new_item);
+ /** Insert new item into the priority queue, maintaining heap order. */
+ void Push(Titem_& new_item);
/** Remove and return the smallest item from the priority queue. */
FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;};
@@ -97,9 +96,12 @@ public:
template <class Titem_>
-FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item)
+FORCEINLINE void CBinaryHeapT<Titem_>::Push(Titem_& new_item)
{
- if (IsFull()) return false;
+ if (IsFull()) {
+ m_max_size *= 2;
+ m_items = ReallocT<ItemPtr>(m_items, m_max_size + 1);
+ }
/* make place for new item */
int gap = ++m_size;
@@ -108,7 +110,6 @@ FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item)
m_items[gap] = m_items[parent];
m_items[gap] = &new_item;
CheckConsistency();
- return true;
}
template <class Titem_>
@@ -218,7 +219,7 @@ FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()
#if 0
for (int child = 2; child <= m_size; child++) {
int parent = child / 2;
- assert(!(m_items[child] < m_items[parent]));
+ assert(!(*m_items[child] < *m_items[parent]));
}
#endif
}