www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 17314] New: BinaryHeap crashes upon insertion if heapified

https://issues.dlang.org/show_bug.cgi?id=17314

          Issue ID: 17314
           Summary: BinaryHeap crashes upon insertion if heapified with an
                    array of length 1
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P1
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: kirsybuu gmail.com

Bug report for:
https://forum.dlang.org/post/cavtukhpddgoilredilk forum.dlang.org

This code throws a Range violation:

import std.stdio, std.container;
void main() {
  auto pq = heapify([5]);
  pq.insert(8);
}

because the insert method fails to increases length in the case of length == 1:

static if (isDynamicArray!Store)
{
    if (_store.length == 0)
        _store.length = 8;
    else if (length == _store.length)
        _store.length = length * 3 / 2; // problem: 1 * 3 / 2 = 3 / 2 = 1
    _store[_length] = value; // out-of-bounds!
}

--
Apr 09