--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/d/dmd/root/aav.c	Thu Feb 13 11:34:05 2020 +0900
@@ -0,0 +1,171 @@
+
+/* Copyright (C) 2010-2019 by The D Language Foundation, All Rights Reserved
+ * http://www.digitalmars.com
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
+ * https://github.com/D-Programming-Language/dmd/blob/master/src/root/aav.c
+ */
+
+/**
+ * Implementation of associative arrays.
+ *
+ */
+
+#include "dsystem.h"
+#include "aav.h"
+#include "rmem.h"
+
+
+inline size_t hash(size_t a)
+{
+    a ^= (a >> 20) ^ (a >> 12);
+    return a ^ (a >> 7) ^ (a >> 4);
+}
+
+struct aaA
+{
+    aaA *next;
+    Key key;
+    Value value;
+};
+
+struct AA
+{
+    aaA* *b;
+    size_t b_length;
+    size_t nodes;       // total number of aaA nodes
+    aaA* binit[4];      // initial value of b[]
+
+    aaA aafirst;        // a lot of these AA's have only one entry
+};
+
+/****************************************************
+ * Determine number of entries in associative array.
+ */
+
+size_t dmd_aaLen(AA* aa)
+{
+    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.
+ */
+
+Value* dmd_aaGet(AA** paa, Key key)
+{
+    //printf("paa = %p\n", paa);
+
+    if (!*paa)
+    {   AA *a = (AA *)mem.xmalloc(sizeof(AA));
+        a->b = (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((size_t)key) & ((*paa)->b_length - 1);
+    aaA** pe = &(*paa)->b[i];
+    aaA *e;
+    while ((e = *pe) != 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) ? (aaA *)mem.xmalloc(sizeof(aaA)) : &(*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.
+ */
+
+Value dmd_aaGetRvalue(AA* aa, Key key)
+{
+    //printf("_aaGetRvalue(key = %p)\n", key);
+    if (aa)
+    {
+        size_t i;
+        size_t len = aa->b_length;
+        i = hash((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
+}
+
+
+/********************************************
+ * Rehash an array.
+ */
+
+void dmd_aaRehash(AA** paa)
+{
+    //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 = (aaA**)mem.xmalloc(sizeof(aaA)*len);
+            memset(newb, 0, len * sizeof(aaA*));
+
+            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((size_t)e->key) & (len-1);
+                    e->next = newb[j];
+                    newb[j] = e;
+                    e = enext;
+                }
+            }
+            if (aa->b != (aaA**)aa->binit)
+                mem.xfree(aa->b);
+
+            aa->b = newb;
+            aa->b_length = len;
+        }
+    }
+}