ddmd.root.aav source code

1 /**
2  * Compiler implementation of the D programming language
3  * http://dlang.org
4  *
5  * Copyright: Copyright (c) 1999-2016 by Digital Mars, All Rights Reserved
6  * Authors:   Walter Bright, http://www.digitalmars.com
7  * License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
8  * Source:    $(DMDSRC root/_aav.d)
9  */
10 
11 module ddmd.root.aav;
12 
13 import core.stdc..string;
14 import ddmd.root.rmem;
15 
16 extern (C++) size_t hash(size_t a)
17 {
18     a ^= (a >> 20) ^ (a >> 12);
19     return a ^ (a >> 7) ^ (a >> 4);
20 }
21 
22 alias Key = void*;
23 alias Value = void*;
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*[4] binit; // initial value of b[]
38     aaA aafirst; // a lot of these AA's have only one entry
39 }
40 
41 /****************************************************
42  * Determine number of entries in associative array.
43  */
44 extern (C++) size_t dmd_aaLen(const AA* aa) pure
45 {
46     return aa ? aa.nodes : 0;
47 }
48 
49 /*************************************************
50  * Get pointer to value in associative array indexed by key.
51  * Add entry for key if it is not already there, returning a pointer to a null Value.
52  * Create the associative array if it does not already exist.
53  */
54 extern (C++) Value* dmd_aaGet(AA** paa, Key key)
55 {
56     //printf("paa = %p\n", paa);
57     if (!*paa)
58     {
59         AA* a = cast(AA*)mem.xmalloc(AA.sizeof);
60         a.b = cast(aaA**)a.binit;
61         a.b_length = 4;
62         a.nodes = 0;
63         a.binit[0] = null;
64         a.binit[1] = null;
65         a.binit[2] = null;
66         a.binit[3] = null;
67         *paa = a;
68         assert((*paa).b_length == 4);
69     }
70     //printf("paa = %p, *paa = %p\n", paa, *paa);
71     assert((*paa).b_length);
72     size_t i = hash(cast(size_t)key) & ((*paa).b_length - 1);
73     aaA** pe = &(*paa).b[i];
74     aaA* e;
75     while ((e = *pe) !is null)
76     {
77         if (key == e.key)
78             return &e.value;
79         pe = &e.next;
80     }
81     // Not found, create new elem
82     //printf("create new one\n");
83     size_t nodes = ++(*paa).nodes;
84     e = (nodes != 1) ? cast(aaA*)mem.xmalloc(aaA.sizeof) : &(*paa).aafirst;
85     //e = new aaA();
86     e.next = null;
87     e.key = key;
88     e.value = null;
89     *pe = e;
90     //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
91     if (nodes > (*paa).b_length * 2)
92     {
93         //printf("rehash\n");
94         dmd_aaRehash(paa);
95     }
96     return &e.value;
97 }
98 
99 /*************************************************
100  * Get value in associative array indexed by key.
101  * Returns NULL if it is not already there.
102  */
103 extern (C++) Value dmd_aaGetRvalue(AA* aa, Key key)
104 {
105     //printf("_aaGetRvalue(key = %p)\n", key);
106     if (aa)
107     {
108         size_t i;
109         size_t len = aa.b_length;
110         i = hash(cast(size_t)key) & (len - 1);
111         aaA* e = aa.b[i];
112         while (e)
113         {
114             if (key == e.key)
115                 return e.value;
116             e = e.next;
117         }
118     }
119     return null; // not found
120 }
121 
122 /********************************************
123  * Rehash an array.
124  */
125 extern (C++) void dmd_aaRehash(AA** paa)
126 {
127     //printf("Rehash\n");
128     if (*paa)
129     {
130         AA* aa = *paa;
131         if (aa)
132         {
133             size_t len = aa.b_length;
134             if (len == 4)
135                 len = 32;
136             else
137                 len *= 4;
138             aaA** newb = cast(aaA**)mem.xmalloc(aaA.sizeof * len);
139             memset(newb, 0, len * (aaA*).sizeof);
140             for (size_t k = 0; k < aa.b_length; k++)
141             {
142                 aaA* e = aa.b[k];
143                 while (e)
144                 {
145                     aaA* enext = e.next;
146                     size_t j = hash(cast(size_t)e.key) & (len - 1);
147                     e.next = newb[j];
148                     newb[j] = e;
149                     e = enext;
150                 }
151             }
152             if (aa.b != cast(aaA**)aa.binit)
153                 mem.xfree(aa.b);
154             aa.b = newb;
155             aa.b_length = len;
156         }
157     }
158 }
159 
160 unittest
161 {
162     AA* aa = null;
163     Value v = dmd_aaGetRvalue(aa, null);
164     assert(!v);
165     Value* pv = dmd_aaGet(&aa, null);
166     assert(pv);
167     *pv = cast(void*)3;
168     v = dmd_aaGetRvalue(aa, null);
169     assert(v == cast(void*)3);
170 }