problem.d

struct InvBoneBindInfo
{
    char[64] id = 0;
    float sss;
}


HashMapTest!(void*, InvBoneBindInfo[32]) nodePartBones;


extern(C) void main()
{
}

struct HashMapTest(Key, Value)
{
    enum MIN_HASH_TABLE_POWER = 3;
    enum RELATIONSHIP = 8;
    static struct Pair
    {
        Key key;
        Value value;
    }

    static struct Element
    {
        uint hash = 0;
        Element* next = null;
        Pair pair;
    }

    Element** hash_table = null;
    size_t allocatedSize = 0;
    ubyte hash_table_power = 0;
    uint elements = 0;

    void dispose()
    {
        clear();
    }

    private:
    void make_hash_table()
    {

    }

    void erase_hash_table()
    {
        //ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside.");
        //memdelete_arr(hash_table);


    }

    void check_hash_table()
    {
        int new_hash_table_power = -1;

        if (cast(int) elements > ((1 << hash_table_power) * RELATIONSHIP))
        {
            /* rehash up */
            new_hash_table_power = hash_table_power + 1;

            while (cast(int) elements > ((1 << new_hash_table_power) * RELATIONSHIP))
            {
                new_hash_table_power++;
            }

        }
        else if ((hash_table_power > cast(int) MIN_HASH_TABLE_POWER) && (
                cast(int) elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP)))
        {
            /* rehash down */
            new_hash_table_power = hash_table_power - 1;

            while (cast(int) elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP))
            {
                new_hash_table_power--;
            }

            if (new_hash_table_power < cast(int) MIN_HASH_TABLE_POWER)
            {
                new_hash_table_power = MIN_HASH_TABLE_POWER;
            }
        }

        if (new_hash_table_power == -1)
        {
            return;
        }

        //Element **new_hash_table = memnew_arr(Element*, (cast(ulong)1 << new_hash_table_power));
        auto newSize = (Element*).sizeof * (cast(size_t) 1 << new_hash_table_power);
        Element** new_hash_table = null;
        //ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory.");

        for (int i = 0; i < (1 << new_hash_table_power); i++)
        {
            new_hash_table[i] = null;
        }

        if (hash_table)
        {
            for (int i = 0; i < (1 << hash_table_power); i++)
            {
                while (hash_table[i])
                {
                    Element* se = hash_table[i];
                    hash_table[i] = se.next;
                    int new_pos = se.hash & ((1 << new_hash_table_power) - 1);
                    se.next = new_hash_table[new_pos];
                    new_hash_table[new_pos] = se;
                }
            }
            //memdelete_arr(hash_table);
            
            auto bytes = (cast(ubyte*) hash_table)[0 .. allocatedSize];
        }
        hash_table = new_hash_table;
        allocatedSize = newSize;
        hash_table_power = cast(ubyte) new_hash_table_power;
    }

    const Element* get_element(const ref Key p_key)
    {

        if (!hash_table)
            return null;
        uint hash = hash(p_key);
        uint index = hash & ((1 << hash_table_power) - 1);

        Element* e = cast(Element*) hash_table[index];

        while (e)
        {
            /* checking hash first avoids comparing key, which may take longer */
            if (e.hash == hash && compare(e.pair.key, p_key))
            {
                /* the pair exists in this hashtable, so just update data */
                return e;
            }
            e = e.next;
        }

        return null;
    }

    Element* create_element(const ref Key p_key)
    {
        /* if element doesn't exist, create it */
        Element* e = null;
        //ERR_FAIL_COND_V_MSG(!e, nullptr, "Out of memory.");
        uint hash = hash(p_key);
        uint index = hash & ((1 << hash_table_power) - 1);
        e.next = hash_table[index];
        e.hash = hash;
        e.pair.key = cast(Key)p_key; // TODO: when i use pointer as key, i need this
        e.pair.value = Value.init;

        hash_table[index] = e;
        elements++;
        return e;
    }

    public:
    Element* set(const ref Key key, const ref Value value)
    {
        Element* e = null;
        if (!hash_table)
        {
            make_hash_table(); // if no table, make one
        }
        else
        {
            e = cast(Element*)(get_element(key));
        }

        /* if we made it up to here, the pair doesn't exist, create and assign */

        if (!e)
        {
            e = create_element(key);
            if (!e)
            {
                return null;
            }
            check_hash_table(); // perform mantenience routine
        }

        e.pair.value = cast(Value) value;
        return e;
    }

    ref Value get(const ref Key p_key)
    {
        Value* res = getptr(p_key);
        //CRASH_COND_MSG(!res, "Map key not found.");
        return *res;
    }

    Value* getptr(const ref Key p_key)
    {
        if (!hash_table)
        {
            return null;
        }

        Element* e = cast(Element*)(get_element(p_key));

        if (e)
        {
            return &e.pair.value;
        }

        return null;
    }

    bool erase(const ref Key p_key)
    {
        if (!hash_table)
        {
            return false;
        }

        uint hash = hash(p_key);
        uint index = hash & ((1 << hash_table_power) - 1);

        Element* e = hash_table[index];
        Element* p = null;
        while (e)
        {
            /* checking hash first avoids comparing key, which may take longer */
            if (e.hash == hash && compare(e.pair.key, p_key))
            {
                if (p)
                {
                    p.next = e.next;
                }
                else
                {
                    //begin of list
                    hash_table[index] = e.next;
                }

                elements--;

                if (elements == 0)
                {
                    erase_hash_table();
                }
                else
                {
                    check_hash_table();
                }
                return true;
            }

            p = e;
            e = e.next;
        }

        return false;
    }

    bool remove(const ref Key key)
    {
        return erase(key);
    }

    bool has(const ref Key p_key)
    {
        return getptr(p_key) != null;
    }

    uint count() const {
        return elements;
    }

    bool is_empty() const {
        return elements == 0;
    }

    void clear()
    {
        /* clean up */
        if (hash_table) {
            for (int i = 0; i < (1 << hash_table_power); i++) {
                while (hash_table[i]) {
                    Element *e = hash_table[i];
                    hash_table[i] = e.next;
                }
            }

            auto bytes = (cast(ubyte*) hash_table)[0 .. allocatedSize];
        }

        hash_table = null;
        hash_table_power = 0;
        elements = 0;
    }

    int opApply(int delegate(Pair*) dg)
    {
        if(!hash_table) return 0;

        int result;
        for (int i = 0; i < (1 << hash_table_power); i++) {
            Element* e = hash_table[i];
            while(e) {
                if ((result = dg(&e.pair)) != 0)
                    break;
                e = e.next;
            }
        }
        return result;
    }

    int opApply(int delegate(Key, Value) dg)
    {
        if(!hash_table) return 0;

        int result;
        for (int i = 0; i < (1 << hash_table_power); i++) {
            Element* e = hash_table[i];
            while(e) {
                if ((result = dg(e.pair.key, e.pair.value)) != 0)
                    break;
                e = e.next;
            }
        }
        return result;
    }

    void opIndexAssign(const ref Value value, const ref Key key) {
        set(key, value);
    }

    // TODO: how to handle error
    ref Value opIndex(const ref Key key) {
        if(!has(key)) panic("key not found");
        return get(key);
    }

}

noreturn panic(Char, A...)(in Char[] fmt, A args, string file = __MODULE__, int line = __LINE__)
{
    import core.stdc.stdlib: abort;
    abort();
}

uint hash(T)(inout ref T v)
{
    static if(is(T == U*, U) && __traits(isScalar, T)) 
    {
        return hash_one_uint64(cast(ulong) v);
    }
    else static if( is(T == int) || is(T == uint)) 
    {
        return hash_one_uint64(cast(ulong) v);
    }
    else static if( is(T == short) || is(T == ushort)) 
    {
        return hash_one_uint64(cast(ulong) v);
    }
    else static if( is(T == long) || is(T == ulong) ) 
    {
        return hash_one_uint64(cast(ulong) v);
    }
    else static if( is(T == float) || is(T == double) ) 
    {
        return hash_djb2_one_float(v);
    }
    else static if ( is (T == string) )
    {
        return cast(int) string_hash(v);
    }
    else static if ( is (T == const(char)[]) )
    {
        return cast(int) string_hash(v);
    }
    else {
        static assert(0, "not supported: " ~ T.stringof);
    }
}

bool compare(T)(inout ref T p_lhs, inout ref T p_rhs)
{
    static if(is(T == U*, U) && __traits(isScalar, T)) 
    {
        return p_lhs == p_rhs;
    }
    else static if( is(T == int) || is(T == uint)) 
    {
        return p_lhs == p_rhs;
    }
    else static if( is(T == short) || is(T == ushort)) 
    {
        return p_lhs == p_rhs;
    }
    else static if( is(T == long) || is(T == ulong)) 
    {
        return p_lhs == p_rhs;
    }
    else static if( is(T == float) || is(T == double) ) 
    {
        return (p_lhs == p_rhs) || (is_nan(p_lhs) && is_nan(p_rhs));
    } 
    else static if ( is (T == string) )
    {
        //auto len = p_lhs.length;
        //auto same = !strncmp(p_lhs.ptr, p_rhs.ptr, len);
        //return same;
        return (p_lhs == p_rhs);
    }
    else static if ( is (T == const(char)[]) )
    {
        auto len = strlen(p_lhs.ptr);
        auto same = !strncmp(p_lhs.ptr, p_rhs.ptr, len);
        return same;
        // return (p_lhs == p_rhs);
    }
    else {
        static assert(0, "not supported " ~ T.stringof);
    }
}

ulong string_hash(const(char)[] name)
{
    return hash_fast(cast(ubyte[]) name);

    //size_t length = name.length;
    //ulong hash = 0xcbf29ce484222325;
    //ulong prime = 0x00000100000001b3;

    //for (size_t i = 0; i < length; i++)
    //{
    //    ubyte value = name[i];
    //    hash = hash ^ value;
    //    hash *= prime;
    //}
    //return hash;
}

uint get_16(ubyte* a_data)
{
    return (cast(uint) a_data[0]) | ((cast(uint) a_data[1]) << 8);
}

uint hash_fast(ubyte[] a_data)
{
    ubyte* data = a_data.ptr;
    auto hash = cast(uint) a_data.length;
    auto left = cast(uint) a_data.length;

    if (left == 0)
    {
        return 0;
    }

    for (; left > 3; left -= 4)
    {
        uint value;
        hash += get_16(data);
        value = (get_16(data + 2) << 11);
        hash = (hash << 16) ^ hash ^ value;
        data += 4;
        hash += hash >> 11;
    }

    final switch (left)
    {
    case 3:
        hash += get_16(data);
        hash ^= hash << 16;
        hash ^= (cast(uint) data[2]) << 18;
        hash += hash >> 11;
        break;
    case 2:
        hash += get_16(data);
        hash ^= hash << 11;
        hash += hash >> 17;
        break;
    case 1:
        hash += cast(uint) data[0];
        hash ^= hash << 10;
        hash += hash >> 1;
        break;
    case 0:
        break;
    }

    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
}

uint hash_one_uint64(const ulong p_int)
{
    ulong v = p_int;
    v = (~v) + (v << 18); // v = (v << 18) - v - 1;
    v = v ^ (v >> 31);
    v = v * 21; // v = (v + (v << 2)) + (v << 4);
    v = v ^ (v >> 11);
    v = v + (v << 6);
    v = v ^ (v >> 22);
    return cast(int) v;
}