1
2 /* Copyright (C) 2010-2021 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
hash(size_t a)19 inline size_t hash(size_t a)
20 {
21 a ^= (a >> 20) ^ (a >> 12);
22 return a ^ (a >> 7) ^ (a >> 4);
23 }
24
25 struct aaA
26 {
27 aaA *next;
28 Key key;
29 Value value;
30 };
31
32 struct 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
dmd_aaLen(AA * aa)46 size_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
dmd_aaGet(AA ** paa,Key key)58 Value* 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
dmd_aaGetRvalue(AA * aa,Key key)114 Value 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
dmd_aaRehash(AA ** paa)138 void 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