Wrong result of advance(it, -1)

[Quuxplusone]

#include "plf_hive.h"
#include <cassert>

int main()
{
    plf::hive<char> h(plf::hive_limits(4, 4));
    h.insert(6, 'x');
    auto it = h.end();
    advance(it, -1);
    advance(it, -1);
    assert(it != h.end());
}

It looks like advance with a negative offset can sometimes move forward instead of backward, when it's right at the edge of a block. I think the culprit is here:

    else if (group_pointer->free_list_head == std::numeric_limits<skipfield_type>::max()) // ie. no erased elements in this group
    {
        element_pointer = reinterpret_cast<aligned_pointer_type>(group_pointer->skipfield) - distance;
        skipfield_pointer = (group_pointer->skipfield + group_pointer->capacity) - distance;
        return;
    }

I think this is assuming that "no erasures in the group" means "the group is full," so we're computing things with capacity, but actually the group might be only incompletely full, and we should be using size instead. So the middle two lines should be more like

        element_pointer = group_pointer->elements + group_pointer->size - distance;
        skipfield_pointer = group_pointer->skipfield + group_pointer->size - distance;

[mattreecebentley]

Good spotting - fixed in beta, there is a slightly faster solution for the element_pointer line though

[mattreecebentley]

Good spotting! fixed in beta, there is a slightly faster solution for the element_pointer line

On 25/04/2022 12:46 pm, Quuxplusone wrote:

|#include "plf_hive.h" #include int main() { plf::hive h(plf::hive_limits(4, 4)); h.insert(6, 'x'); auto it = h.end(); advance(it, -1); advance(it, -1); assert(it != h.end()); }|