dmd/root/aav.d

/**
 * Associative array implementation.
 *
 * Copyright: Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
 * Authors:   Walter Bright, http://www.digitalmars.com
 * License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
 * Source:    $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/root/aav.d, root/_aav.d)
 * Documentation:  https://dlang.org/phobos/dmd_root_aav.html
 * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/root/aav.d
 */

module dmd.root.aav;

import core.stdc.string;
import dmd.root.rmem;

private size_t hash(size_t a) pure nothrow @nogc @safe
{
    a ^= (a >> 20) ^ (a >> 12);
    return a ^ (a >> 7) ^ (a >> 4);
}

struct KeyValueTemplate(K,V)
{
    K key;
    V value;
}

alias Key = void*;
alias Value = void*;

alias KeyValue = KeyValueTemplate!(Key, Value);

struct aaA
{
    aaA* next;
    KeyValue keyValue;
    alias keyValue this;
}

struct AA
{
    aaA** b;
    size_t b_length;
    size_t nodes; // total number of aaA nodes
    aaA*[4] binit; // initial value of b[]
    aaA aafirst; // a lot of these AA's have only one entry
}

/****************************************************
 * Determine number of entries in associative array.
 */
private size_t dmd_aaLen(const AA* aa) pure nothrow @nogc @safe
{
    return aa ? aa.nodes : 0;
}

/*************************************************
 * Get pointer to value in associative array indexed by key.
 * Add entry for key if it is not already there, returning a pointer to a null Value.
 * Create the associative array if it does not already exist.
 */
private Value* dmd_aaGet(AA** paa, Key key) pure nothrow
{
    //printf("paa = %p\n", paa);
    if (!*paa)
    {
        AA* a = cast(AA*)mem.xmalloc(AA.sizeof);
        a.b = cast(aaA**)a.binit;
        a.b_length = 4;
        a.nodes = 0;
        a.binit[0] = null;
        a.binit[1] = null;
        a.binit[2] = null;
        a.binit[3] = null;
        *paa = a;
        assert((*paa).b_length == 4);
    }
    //printf("paa = %p, *paa = %p\n", paa, *paa);
    assert((*paa).b_length);
    size_t i = hash(cast(size_t)key) & ((*paa).b_length - 1);
    aaA** pe = &(*paa).b[i];
    aaA* e;
    while ((e = *pe) !is null)
    {
        if (key == e.key)
            return &e.value;
        pe = &e.next;
    }
    // Not found, create new elem
    //printf("create new one\n");
    size_t nodes = ++(*paa).nodes;
    e = (nodes != 1) ? cast(aaA*)mem.xmalloc(aaA.sizeof) : &(*paa).aafirst;
    //e = new aaA();
    e.next = null;
    e.key = key;
    e.value = null;
    *pe = e;
    //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
    if (nodes > (*paa).b_length * 2)
    {
        //printf("rehash\n");
        dmd_aaRehash(paa);
    }
    return &e.value;
}

/*************************************************
 * Get value in associative array indexed by key.
 * Returns NULL if it is not already there.
 */
private Value dmd_aaGetRvalue(AA* aa, Key key) pure nothrow @nogc
{
    //printf("_aaGetRvalue(key = %p)\n", key);
    if (aa)
    {
        size_t i;
        size_t len = aa.b_length;
        i = hash(cast(size_t)key) & (len - 1);
        aaA* e = aa.b[i];
        while (e)
        {
            if (key == e.key)
                return e.value;
            e = e.next;
        }
    }
    return null; // not found
}

/**
Gets a range of key/values for `aa`.

Returns: a range of key/values for `aa`.
*/
@property auto asRange(AA* aa) pure nothrow @nogc
{
    return AARange!(Key, Value)(aa);
}

private struct AARange(K,V)
{
    AA* aa;
    // current index into bucket array `aa.b`
    size_t bIndex;
    aaA* current;

    this(AA* aa) pure nothrow @nogc
    {
        if (aa)
        {
            this.aa = aa;
            toNext();
        }
    }

    @property bool empty() const pure nothrow @nogc @safe
    {
        return current is null;
    }

    @property auto front() const pure nothrow @nogc
    {
        return cast(KeyValueTemplate!(K,V))current.keyValue;
    }

    void popFront() pure nothrow @nogc
    {
        if (current.next)
            current = current.next;
        else
        {
            bIndex++;
            toNext();
        }
    }

    private void toNext() pure nothrow @nogc
    {
        for (; bIndex < aa.b_length; bIndex++)
        {
            if (auto next = aa.b[bIndex])
            {
                current = next;
                return;
            }
        }
        current = null;
    }
}

unittest
{
    AA* aa = null;
    foreach(keyValue; aa.asRange)
        assert(0);

    enum totalKeyLength = 50;
    foreach (i; 1 .. totalKeyLength + 1)
    {
        auto key = cast(void*)i;
        {
            auto valuePtr = dmd_aaGet(&aa, key);
            assert(valuePtr);
            *valuePtr = key;
        }
        bool[totalKeyLength] found;
        size_t rangeCount = 0;
        foreach (keyValue; aa.asRange)
        {
            assert(keyValue.key <= key);
            assert(keyValue.key == keyValue.value);
            rangeCount++;
            assert(!found[cast(size_t)keyValue.key - 1]);
            found[cast(size_t)keyValue.key - 1] = true;
        }
        assert(rangeCount == i);
    }
}

/********************************************
 * Rehash an array.
 */
private void dmd_aaRehash(AA** paa) pure nothrow
{
    //printf("Rehash\n");
    if (*paa)
    {
        AA* aa = *paa;
        if (aa)
        {
            size_t len = aa.b_length;
            if (len == 4)
                len = 32;
            else
                len *= 4;
            aaA** newb = cast(aaA**)mem.xmalloc(aaA.sizeof * len);
            memset(newb, 0, len * (aaA*).sizeof);
            for (size_t k = 0; k < aa.b_length; k++)
            {
                aaA* e = aa.b[k];
                while (e)
                {
                    aaA* enext = e.next;
                    size_t j = hash(cast(size_t)e.key) & (len - 1);
                    e.next = newb[j];
                    newb[j] = e;
                    e = enext;
                }
            }
            if (aa.b != cast(aaA**)aa.binit)
                mem.xfree(aa.b);
            aa.b = newb;
            aa.b_length = len;
        }
    }
}

unittest
{
    AA* aa = null;
    Value v = dmd_aaGetRvalue(aa, null);
    assert(!v);
    Value* pv = dmd_aaGet(&aa, null);
    assert(pv);
    *pv = cast(void*)3;
    v = dmd_aaGetRvalue(aa, null);
    assert(v == cast(void*)3);
}

struct AssocArray(K,V)
{
    private AA* aa;

    /**
    Returns: The number of key/value pairs.
    */
    @property size_t length() const pure nothrow @nogc @safe
    {
        return dmd_aaLen(aa);
    }

    /**
    Lookup value associated with `key` and return the address to it. If the `key`
    has not been added, it adds it and returns the address to the new value.

    Params:
        key = key to lookup the value for

    Returns: the address to the value associated with `key`. If `key` does not exist, it
             is added and the address to the new value is returned.
    */
    V* getLvalue(const(K) key) pure nothrow
    {
        return cast(V*)dmd_aaGet(&aa, cast(void*)key);
    }

    /**
    Lookup and return the value associated with `key`, if the `key` has not been
    added, it returns null.

    Params:
        key = key to lookup the value for

    Returns: the value associated with `key` if present, otherwise, null.
    */
    V opIndex(const(K) key) pure nothrow @nogc
    {
        return cast(V)dmd_aaGetRvalue(aa, cast(void*)key);
    }

    /**
    Gets a range of key/values for `aa`.

    Returns: a range of key/values for `aa`.
    */
    @property auto asRange() pure nothrow @nogc
    {
        return AARange!(K,V)(aa);
    }
}

///
unittest
{
    auto foo = new Object();
    auto bar = new Object();

    AssocArray!(Object, Object) aa;

    assert(aa[foo] is null);
    assert(aa.length == 0);

    auto fooValuePtr = aa.getLvalue(foo);
    *fooValuePtr = bar;

    assert(aa[foo] is bar);
    assert(aa.length == 1);
}