[Issue 4021] [CTFE] AA rehash

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4021



--- Comment #2 from Michael Rynn <y0uf00...@gmail.com> 2010-04-08 18:22:50 PDT 
---
// I feel obliged to submit a version of function _aaRehash that ignores the
TypeInfo passed to it, to make the keyti argument redundent. (
druntime/src/rt/aaA.d).

void* _aaRehash(AA* paa, TypeInfo keyti)
{
    BB newb;

    TypeInfo origti;

    void _aaRehash_x(aaA* olde)
    {
        while (1)
        {
            auto left = olde.left;
            auto right = olde.right;
            olde.left = null;
            olde.right = null;

            aaA *e;

            //printf("rehash %p\n", olde);
            auto key_hash = olde.hash;
            size_t i = key_hash % newb.b.length;
            auto pe = &newb.b[i];
            while ((e = *pe) !is null)
            {
                //printf("\te = %p, e.left = %p, e.right = %p\n", e, e.left,
e.right);
                assert(e.left != e);
                assert(e.right != e);
                if (key_hash == e.hash)
                {
                    auto c = origti.compare(olde + 1, e + 1);
                    assert(c != 0);
                    pe = (c < 0) ? &e.left : &e.right;
                }
                else
                    pe = (key_hash < e.hash) ? &e.left : &e.right;
            }
            *pe = olde;

            if (right)
            {
                if (!left)
                {   olde = right;
                    continue;
                }
                _aaRehash_x(right);
            }
            if (!left)
                break;
            olde = left;
        }
    }

    //printf("Rehash\n");
    if (paa.a)
    {
        auto aa = paa.a;
        auto len = _aaLen(*paa);

        if (len)
        {
            size_t i;

            origti = aa.keyti;
            for (i = 0; i < prime_list.length - 1; i++)
            {
                if (len <= prime_list[i])
                    break;
            }
            len = prime_list[i];
            newb.b = new aaA*[len];

            foreach (e; aa.b)
            {
                if (e)
                    _aaRehash_x(e);
            }
            delete aa.b;

            newb.nodes = aa.nodes;
            newb.keyti = aa.keyti;
        }

        *paa.a = newb;
        _aaBalance(paa);
    }
    return (*paa).a;
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------