[Issue 4021] [CTFE] AA rehash
d-bugmail at puremagic.com
d-bugmail at puremagic.com
Thu Apr 8 18:22:53 PDT 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4021
--- Comment #2 from Michael Rynn <y0uf00bar at 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: -------
More information about the Digitalmars-d-bugs
mailing list