/* This file is part of limb                           https://lila.oss/limb
 * Copyright (C) 2023 Olivier Brunel                          jjk@jjacky.com */
/* SPDX-License-Identifier: GPL-2.0-only */
#include "hmap.h"

static void
relocate(u32 idx, u32 min, u32 max, u32 *left, u32 relocated[], hmap *hmap)
{
    /* keep in sync w/ item in hmap.h */
    struct fullitem {
        u32 key;
        u8 data[DLEN(hmap)];
    } * it;

    it = ITEM(idx, hmap);

    u32 n = idx / 32;
    u32 b = 1 << (idx - n);
    if ((relocated[n] & b) || !it->key)
        return;

    struct fullitem itmp, *new;

    /* remove item from current spot */
    itmp = *it;
    memset(it, 0, sizeof(*it));

    /* and look for its natural spot, or first available collision spot
     * if needed */
    u32 i, j;
    for (i = itmp.key, j = 1; ; i += j++) {
        /* get item's wanted spot */
        new = ITEM(i & hmap->sa.a, hmap);

        /* put it back if it's where it was */
        if (new == it)
            break;

        /* make sure its wanted spot has been relocated if needed */
        relocate(i & hmap->sa.a, min, max, left, relocated, hmap);

        /* settle there if it's now available */
        if (!new->key)
            break;
    }
    /* put item in its (new) spot */
    *new = itmp;
    n = (i & hmap->sa.a) / 32;
    b = 1 << ((i & hmap->sa.a) - n);
    relocated[n] |= b;
    /* decrease left iif it was within [min,max] */
    if (idx >= min && idx <= max)
        --*left;
}

int
grow(size_t n, hmap *hmap)
{
    u32 oldsize, newsize;

    if (n > MAXSIZE)
        n = MAXSIZE;

    for (newsize = MINSIZE; newsize < n; newsize <<= 1)
        ;

    /* if sa.a was turned into the mask.. */
    if (hmap->sa.a) {
        /* ..make it the (currently) allocated size again */
        ++hmap->sa.a;
        hmap->sa.a *= hmap->ilen;
    }
    oldsize = hmap->sa.a / hmap->ilen;

    if (!stralloc_ready_tuned(&hmap->sa, newsize * hmap->ilen, 0, 0, 1)) {
        hmap->sa.a /= hmap->ilen;
        --hmap->sa.a;
        return 0;
    }

    /* empty the new items */
    memset(hmap->sa.s + oldsize * hmap->ilen, 0, (newsize - oldsize) * hmap->ilen);

    /* make sa.a the new mask */
    hmap->sa.a /= hmap->ilen;
    --hmap->sa.a;

    /* we'll (try to) relocate all items to their (new) "natural" spots, or
     * a new collision/alternate spot if one got freed */
    u32 left = hmap->sa.len;
    u32 relocated[((hmap->sa.a + 1) / 32) + 1];
    memset(relocated, 0, sizeof(relocated));
    for (u32 i = 0; left; ++i) {
        struct item *it = ITEM(i, hmap);
        if (it->key)
            relocate(i, i, oldsize, &left, relocated, hmap);
    }

    return 1;
}