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 }