1
2/* Copyright (C) 2010-2019 by The D Language Foundation, All Rights Reserved
3 * http://www.digitalmars.com
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
6 * https://github.com/D-Programming-Language/dmd/blob/master/src/root/aav.c
7 */
8
9/**
10 * Implementation of associative arrays.
11 *
12 */
13
14#include "dsystem.h"
15#include "aav.h"
16#include "rmem.h"
17
18
19inline size_t hash(size_t a)
20{
21    a ^= (a >> 20) ^ (a >> 12);
22    return a ^ (a >> 7) ^ (a >> 4);
23}
24
25struct aaA
26{
27    aaA *next;
28    Key key;
29    Value value;
30};
31
32struct AA
33{
34    aaA* *b;
35    size_t b_length;
36    size_t nodes;       // total number of aaA nodes
37    aaA* binit[4];      // initial value of b[]
38
39    aaA aafirst;        // a lot of these AA's have only one entry
40};
41
42/****************************************************
43 * Determine number of entries in associative array.
44 */
45
46size_t dmd_aaLen(AA* aa)
47{
48    return aa ? aa->nodes : 0;
49}
50
51
52/*************************************************
53 * Get pointer to value in associative array indexed by key.
54 * Add entry for key if it is not already there, returning a pointer to a null Value.
55 * Create the associative array if it does not already exist.
56 */
57
58Value* dmd_aaGet(AA** paa, Key key)
59{
60    //printf("paa = %p\n", paa);
61
62    if (!*paa)
63    {   AA *a = (AA *)mem.xmalloc(sizeof(AA));
64        a->b = (aaA**)a->binit;
65        a->b_length = 4;
66        a->nodes = 0;
67        a->binit[0] = NULL;
68        a->binit[1] = NULL;
69        a->binit[2] = NULL;
70        a->binit[3] = NULL;
71        *paa = a;
72        assert((*paa)->b_length == 4);
73    }
74    //printf("paa = %p, *paa = %p\n", paa, *paa);
75
76    assert((*paa)->b_length);
77    size_t i = hash((size_t)key) & ((*paa)->b_length - 1);
78    aaA** pe = &(*paa)->b[i];
79    aaA *e;
80    while ((e = *pe) != NULL)
81    {
82        if (key == e->key)
83            return &e->value;
84        pe = &e->next;
85    }
86
87    // Not found, create new elem
88    //printf("create new one\n");
89
90    size_t nodes = ++(*paa)->nodes;
91    e = (nodes != 1) ? (aaA *)mem.xmalloc(sizeof(aaA)) : &(*paa)->aafirst;
92    //e = new aaA();
93    e->next = NULL;
94    e->key = key;
95    e->value = NULL;
96    *pe = e;
97
98    //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
99    if (nodes > (*paa)->b_length * 2)
100    {
101        //printf("rehash\n");
102        dmd_aaRehash(paa);
103    }
104
105    return &e->value;
106}
107
108
109/*************************************************
110 * Get value in associative array indexed by key.
111 * Returns NULL if it is not already there.
112 */
113
114Value dmd_aaGetRvalue(AA* aa, Key key)
115{
116    //printf("_aaGetRvalue(key = %p)\n", key);
117    if (aa)
118    {
119        size_t i;
120        size_t len = aa->b_length;
121        i = hash((size_t)key) & (len-1);
122        aaA* e = aa->b[i];
123        while (e)
124        {
125            if (key == e->key)
126                return e->value;
127            e = e->next;
128        }
129    }
130    return NULL;    // not found
131}
132
133
134/********************************************
135 * Rehash an array.
136 */
137
138void dmd_aaRehash(AA** paa)
139{
140    //printf("Rehash\n");
141    if (*paa)
142    {
143        AA *aa = *paa;
144        if (aa)
145        {
146            size_t len = aa->b_length;
147            if (len == 4)
148                len = 32;
149            else
150                len *= 4;
151            aaA** newb = (aaA**)mem.xmalloc(sizeof(aaA)*len);
152            memset(newb, 0, len * sizeof(aaA*));
153
154            for (size_t k = 0; k < aa->b_length; k++)
155            {   aaA *e = aa->b[k];
156                while (e)
157                {   aaA* enext = e->next;
158                    size_t j = hash((size_t)e->key) & (len-1);
159                    e->next = newb[j];
160                    newb[j] = e;
161                    e = enext;
162                }
163            }
164            if (aa->b != (aaA**)aa->binit)
165                mem.xfree(aa->b);
166
167            aa->b = newb;
168            aa->b_length = len;
169        }
170    }
171}
172