]>
Commit | Line | Data |
---|---|---|
b4c522fa | 1 | |
a3b38b77 | 2 | /* Copyright (C) 2010-2021 by The D Language Foundation, All Rights Reserved |
b4c522fa IB |
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 | ||
f9ab59ff | 14 | #include "dsystem.h" |
b4c522fa IB |
15 | #include "aav.h" |
16 | #include "rmem.h" | |
17 | ||
18 | ||
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 | ||
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 | ||
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 | ||
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 | ||
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 | } |