summaryrefslogtreecommitdiff
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
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)
-rw-r--r--src/misc/binaryheap.hpp19
-rw-r--r--src/pathfinder/yapf/nodelist.hpp2
2 files changed, 10 insertions, 11 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
}
diff --git a/src/pathfinder/yapf/nodelist.hpp b/src/pathfinder/yapf/nodelist.hpp
index 75b459a54..e88085b61 100644
--- a/src/pathfinder/yapf/nodelist.hpp
+++ b/src/pathfinder/yapf/nodelist.hpp
@@ -93,8 +93,6 @@ public:
{
assert(m_closed.Find(item.GetKey()) == NULL);
m_open.Push(item);
- /* TODO: check if m_open_queue is not full */
- assert(!m_open_queue.IsFull());
m_open_queue.Push(item);
if (&item == m_new_node) {
m_new_node = NULL;