1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Copyright:   Copyright (C) 2000-2020 by The D Language Foundation, All Rights Reserved
6  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright), Dave Fladebo
7  * License:     Distributed under the Boost Software License, Version 1.0.
8  *              http://www.boost.org/LICENSE_1_0.txt
9  * Source:      https://github.com/dlang/dmd/blob/master/src/dmd/backend/aarray.d
10  */
11 
12 module dmd.backend.aarray;
13 
14 import core.stdc.stdio;
15 import core.stdc.stdlib;
16 import core.stdc..string;
17 
18 alias hash_t = size_t;
19 
20 nothrow:
21 
22 /*********************
23  * This is the "bucket" used by the AArray.
24  */
25 private struct aaA
26 {
27     aaA *next;
28     hash_t hash;        // hash of the key
29     /* key   */         // key value goes here
30     /* value */         // value value goes here
31 }
32 
33 /**************************
34  * Associative Array type.
35  * Params:
36  *      TKey = type that has members Key, getHash(), and equals()
37  *      Value = value type
38  */
39 
40 struct AArray(TKey, Value)
41 {
42 nothrow:
43     alias Key = TKey.Key;       // key type
44 
45     ~this()
46     {
47         destroy();
48     }
49 
50     /****
51      * Frees all the data used by AArray
52      */
53     void destroy()
54     {
55         if (buckets)
56         {
57             foreach (e; buckets)
58             {
59                 while (e)
60                 {
61                     auto en = e;
62                     e = e.next;
63                     free(en);
64                 }
65             }
66             free(buckets.ptr);
67             buckets = null;
68             nodes = 0;
69         }
70     }
71 
72     /********
73      * Returns:
74      *   Number of entries in the AArray
75      */
76     size_t length()
77     {
78         return nodes;
79     }
80 
81     /*************************************************
82      * Get pointer to value in associative array indexed by key.
83      * Add entry for key if it is not already there.
84      * Params:
85      *  pKey = pointer to key
86      * Returns:
87      *  pointer to Value
88      */
89 
90     Value* get(Key* pkey)
91     {
92         //printf("AArray::get()\n");
93         const aligned_keysize = aligntsize(Key.sizeof);
94 
95         if (!buckets.length)
96         {
97             alias aaAp = aaA*;
98             const len = prime_list[0];
99             auto p = cast(aaAp*)calloc(len, aaAp.sizeof);
100             assert(p);
101             buckets = p[0 .. len];
102         }
103 
104         hash_t key_hash = tkey.getHash(pkey);
105         const i = key_hash % buckets.length;
106         //printf("key_hash = %x, buckets.length = %d, i = %d\n", key_hash, buckets.length, i);
107         aaA* e;
108         auto pe = &buckets[i];
109         while ((e = *pe) != null)
110         {
111             if (key_hash == e.hash &&
112                 tkey.equals(pkey, cast(Key*)(e + 1)))
113             {
114                 goto Lret;
115             }
116             pe = &e.next;
117         }
118 
119         // Not found, create new elem
120         //printf("create new one\n");
121         e = cast(aaA *) malloc(aaA.sizeof + aligned_keysize + Value.sizeof);
122         assert(e);
123         memcpy(e + 1, pkey, Key.sizeof);
124         memset(cast(void *)(e + 1) + aligned_keysize, 0, Value.sizeof);
125         e.hash = key_hash;
126         e.next = null;
127         *pe = e;
128 
129         ++nodes;
130         //printf("length = %d, nodes = %d\n", buckets_length, nodes);
131         if (nodes > buckets.length * 4)
132         {
133             //printf("rehash()\n");
134             rehash();
135         }
136 
137     Lret:
138         return cast(Value*)(cast(void*)(e + 1) + aligned_keysize);
139     }
140 
141     /*************************************************
142      * Determine if key is in aa.
143      * Params:
144      *  pKey = pointer to key
145      * Returns:
146      *  null    not in aa
147      *  !=null  in aa, return pointer to value
148      */
149 
150     Value* isIn(Key* pkey)
151     {
152         //printf("AArray.isIn(), .length = %d, .ptr = %p\n", nodes, buckets.ptr);
153         if (!nodes)
154             return null;
155 
156         const key_hash = tkey.getHash(pkey);
157         //printf("hash = %d\n", key_hash);
158         const i = key_hash % buckets.length;
159         auto e = buckets[i];
160         while (e != null)
161         {
162             if (key_hash == e.hash &&
163                 tkey.equals(pkey, cast(Key*)(e + 1)))
164             {
165                 return cast(Value*)(cast(void*)(e + 1) + aligntsize(Key.sizeof));
166             }
167 
168             e = e.next;
169         }
170 
171         // Not found
172         return null;
173     }
174 
175 
176     /*************************************************
177      * Delete key entry in aa[].
178      * If key is not in aa[], do nothing.
179      * Params:
180      *  pKey = pointer to key
181      */
182 
183     void del(Key *pkey)
184     {
185         if (!nodes)
186             return;
187 
188         const key_hash = tkey.getHash(pkey);
189         //printf("hash = %d\n", key_hash);
190         const i = key_hash % buckets.length;
191         auto pe = &buckets[i];
192         aaA* e;
193         while ((e = *pe) != null)       // null means not found
194         {
195             if (key_hash == e.hash &&
196                 tkey.equals(pkey, cast(Key*)(e + 1)))
197             {
198                 *pe = e.next;
199                 --nodes;
200                 free(e);
201                 break;
202             }
203             pe = &e.next;
204         }
205     }
206 
207 
208     /********************************************
209      * Produce array of keys from aa.
210      * Returns:
211      *  malloc'd array of keys
212      */
213 
214     Key[] keys()
215     {
216         if (!nodes)
217             return null;
218 
219         auto p = cast(Key *)malloc(nodes * Key.sizeof);
220         assert(p);
221         auto q = p;
222         foreach (e; buckets)
223         {
224             while (e)
225             {
226                 memcpy(q, e + 1, Key.sizeof);
227                 ++q;
228                 e = e.next;
229             }
230         }
231         return p[0 .. nodes];
232     }
233 
234     /********************************************
235      * Produce array of values from aa.
236      * Returns:
237      *  malloc'd array of values
238      */
239 
240     Value[] values()
241     {
242         if (!nodes)
243             return null;
244 
245         const aligned_keysize = aligntsize(Key.sizeof);
246         auto p = cast(Value *)malloc(nodes * Value.sizeof);
247         assert(p);
248         auto q = p;
249         foreach (e; buckets)
250         {
251             while (e)
252             {
253                 memcpy(q, cast(void*)(e + 1) + aligned_keysize, Value.sizeof);
254                 ++q;
255                 e = e.next;
256             }
257         }
258         return p[0 .. nodes];
259     }
260 
261     /********************************************
262      * Rehash an array.
263      */
264 
265     void rehash()
266     {
267         //printf("Rehash\n");
268         if (!nodes)
269             return;
270 
271         size_t newbuckets_length = prime_list[$ - 1];
272 
273         foreach (prime; prime_list[0 .. $ - 1])
274         {
275             if (nodes <= prime)
276             {
277                 newbuckets_length = prime;
278                 break;
279             }
280         }
281         auto newbuckets = cast(aaA**)calloc(newbuckets_length, (aaA*).sizeof);
282         assert(newbuckets);
283 
284         foreach (e; buckets)
285         {
286             while (e)
287             {
288                 auto en = e.next;
289                 auto b = &newbuckets[e.hash % newbuckets_length];
290                 e.next = *b;
291                 *b = e;
292                 e = en;
293             }
294         }
295 
296         free(buckets.ptr);
297         buckets = null;
298         buckets = newbuckets[0 .. newbuckets_length];
299     }
300 
301     alias applyDg = nothrow int delegate(Key*, Value*);
302     /*********************************************
303      * For each element in the AArray,
304      * call dg(Key* pkey, Value* pvalue)
305      * If dg returns !=0, stop and return that value.
306      * Params:
307      *  dg = delegate to call for each key/value pair
308      * Returns:
309      *  !=0 : value returned by first dg() call that returned non-zero
310      *  0   : no entries in aa, or all dg() calls returned 0
311      */
312 
313     int apply(applyDg dg)
314     {
315         if (!nodes)
316             return 0;
317 
318         //printf("AArray.apply(aa = %p, keysize = %d, dg = %p)\n", &this, Key.sizeof, dg);
319 
320         const aligned_keysize = aligntsize(Key.sizeof);
321 
322         foreach (e; buckets)
323         {
324             while (e)
325             {
326                 auto result = dg(cast(Key*)(e + 1), cast(Value*)(e + 1) + aligned_keysize);
327                 if (result)
328                     return result;
329                 e = e.next;
330             }
331         }
332 
333         return 0;
334     }
335 
336   private:
337 
338     aaA*[] buckets;
339     size_t nodes;               // number of nodes
340     TKey tkey;
341 }
342 
343 private:
344 
345 /**********************************
346  * Align to next pointer boundary, so value
347  * will be aligned.
348  * Params:
349  *      tsize = offset to be aligned
350  * Returns:
351  *      aligned offset
352  */
353 
354 size_t aligntsize(size_t tsize)
355 {
356     // Is pointer alignment on the x64 4 bytes or 8?
357     return (tsize + size_t.sizeof - 1) & ~(size_t.sizeof - 1);
358 }
359 
360 immutable uint[14] prime_list =
361 [
362     97U,         389U,
363     1543U,       6151U,
364     24593U,      98317U,
365     393241U,     1572869U,
366     6291469U,    25165843U,
367     100663319U,  402653189U,
368     1610612741U, 4294967291U
369 ];
370 
371 /***************************************************************/
372 
373 /***
374  * A TKey for basic types
375  * Params:
376  *      K = a basic type
377  */
378 public struct Tinfo(K)
379 {
380 nothrow:
381     alias Key = K;
382 
383     static hash_t getHash(Key* pk)
384     {
385         return cast(hash_t)*pk;
386     }
387 
388     static bool equals(Key* pk1, Key* pk2)
389     {
390         return *pk1 == *pk2;
391     }
392 }
393 
394 /***************************************************************/
395 
396 /****
397  * A TKey that is a string
398  */
399 public struct TinfoChars
400 {
401 nothrow:
402     alias Key = const(char)[];
403 
404     static hash_t getHash(Key* pk)
405     {
406         auto buf = *pk;
407         hash_t hash = 0;
408         foreach (v; buf)
409             hash = hash * 11 + v;
410         return hash;
411     }
412 
413     static bool equals(Key* pk1, Key* pk2)
414     {
415         auto buf1 = *pk1;
416         auto buf2 = *pk2;
417         return buf1.length == buf2.length &&
418                memcmp(buf1.ptr, buf2.ptr, buf1.length) == 0;
419     }
420 }
421 
422 // Interface for C++ code
423 public extern (C++) struct AAchars
424 {
425 nothrow:
426     alias AA = AArray!(TinfoChars, uint);
427     AA aa;
428 
429     static AAchars* create()
430     {
431         auto a = cast(AAchars*)calloc(1, AAchars.sizeof);
432         assert(a);
433         return a;
434     }
435 
436     static void destroy(AAchars* aac)
437     {
438         aac.aa.destroy();
439         free(aac);
440     }
441 
442     extern(D) uint* get(const(char)[] buf)
443     {
444         return aa.get(&buf);
445     }
446 
447     uint length()
448     {
449         return cast(uint)aa.length();
450     }
451 }
452 
453 /***************************************************************/
454 
455 // Key is the slice specified by (*TinfoPair.pbase)[Pair.start .. Pair.end]
456 
457 struct Pair { uint start, end; }
458 
459 public struct TinfoPair
460 {
461 nothrow:
462     alias Key = Pair;
463 
464     ubyte** pbase;
465 
466     hash_t getHash(Key* pk)
467     {
468         auto buf = (*pbase)[pk.start .. pk.end];
469         hash_t hash = 0;
470         foreach (v; buf)
471             hash = hash * 11 + v;
472         return hash;
473     }
474 
475     bool equals(Key* pk1, Key* pk2)
476     {
477         const len1 = pk1.end - pk1.start;
478         const len2 = pk2.end - pk2.start;
479 
480         auto buf1 = *pk1;
481         auto buf2 = *pk2;
482         return len1 == len2 &&
483                memcmp(*pbase + pk1.start, *pbase + pk2.start, len1) == 0;
484     }
485 }
486 
487 // Interface for C++ code
488 public extern (C++) struct AApair
489 {
490 nothrow:
491     alias AA = AArray!(TinfoPair, uint);
492     AA aa;
493 
494     static AApair* create(ubyte** pbase)
495     {
496         auto a = cast(AApair*)calloc(1, AApair.sizeof);
497         assert(a);
498         a.aa.tkey.pbase = pbase;
499         return a;
500     }
501 
502     static void destroy(AApair* aap)
503     {
504         aap.aa.destroy();
505         free(aap);
506     }
507 
508     uint* get(uint start, uint end)
509     {
510         auto p = Pair(start, end);
511         return aa.get(&p);
512     }
513 
514     uint length()
515     {
516         return cast(uint)aa.length();
517     }
518 }
519 
520 /*************************************************************/
521 
522 version (none)
523 {
524 
525 /* Since -betterC doesn't support unittests, do it this way
526  * for the time being.
527  * This is a stand-alone file anyway.
528  */
529 
530 int main()
531 {
532     testAArray();
533     testAApair();
534 
535     return 0;
536 }
537 
538 void testAArray()
539 {
540     int dg(int* pk, bool* pv) { return 3; }
541     int dgz(int* pk, bool* pv) { return 0; }
542 
543     AArray!(Tinfo!int, bool) aa;
544     aa.rehash();
545     assert(aa.keys() == null);
546     assert(aa.values() == null);
547     assert(aa.apply(&dg) == 0);
548 
549     assert(aa.length == 0);
550     int k = 8;
551     aa.del(&k);
552     bool v = true;
553     assert(!aa.isIn(&k));
554     bool *pv = aa.get(&k);
555     *pv = true;
556     int j = 9;
557     pv = aa.get(&j);
558     *pv = false;
559     aa.rehash();
560 
561     assert(aa.length() == 2);
562     assert(*aa.get(&k) == true);
563     assert(*aa.get(&j) == false);
564 
565     assert(aa.apply(&dg) == 3);
566     assert(aa.apply(&dgz) == 0);
567 
568     aa.del(&k);
569     assert(aa.length() == 1);
570     assert(!aa.isIn(&k));
571     assert(*aa.isIn(&j) == false);
572 
573     auto keys = aa.keys();
574     assert(keys.length == 1);
575     assert(keys[0] == 9);
576 
577     auto values = aa.values();
578     assert(values.length == 1);
579     assert(values[0] == false);
580 }
581 
582 void testAApair()
583 {
584     const(char)* buf = "abcb";
585     auto aap = AApair.create(cast(ubyte**)&buf);
586     auto pu = aap.get(1,2);
587     *pu = 10;
588     assert(aap.length == 1);
589     pu = aap.get(3,4);
590     assert(*pu == 10);
591     AApair.destroy(aap);
592 }
593 
594 }