1 /** 2 * Compiler implementation of the 3 * $(LINK2 http://www.dlang.org, D programming language). 4 * 5 * Simple bit vector implementation. 6 * 7 * Copyright: Copyright (C) 2013-2020 by The D Language Foundation, All Rights Reserved 8 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 9 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 10 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/dvec.d, backend/dvec.d) 11 */ 12 13 module dmd.backend.dvec; 14 15 import core.stdc.stdio; 16 import core.stdc.stdlib; 17 import core.stdc.string; 18 19 import core.bitop; 20 21 extern (C): 22 23 nothrow: 24 @nogc: 25 26 alias vec_base_t = size_t; // base type of vector 27 alias vec_t = vec_base_t*; 28 29 enum VECBITS = vec_base_t.sizeof * 8; // # of bits per entry 30 enum VECMASK = VECBITS - 1; // mask for bit position 31 enum VECSHIFT = (VECBITS == 16) ? 4 : (VECBITS == 32 ? 5 : 6); // # of bits in VECMASK 32 33 static assert(vec_base_t.sizeof == 2 && VECSHIFT == 4 || 34 vec_base_t.sizeof == 4 && VECSHIFT == 5 || 35 vec_base_t.sizeof == 8 && VECSHIFT == 6); 36 37 struct VecGlobal 38 { 39 int count; // # of vectors allocated 40 int initcount; // # of times package is initialized 41 vec_t[30] freelist; // free lists indexed by dim 42 43 nothrow: 44 @nogc: 45 46 void initialize() 47 { 48 if (initcount++ == 0) 49 count = 0; 50 } 51 52 void terminate() 53 { 54 if (--initcount == 0) 55 { 56 debug 57 { 58 if (count != 0) 59 { 60 printf("vecGlobal.count = %d\n", count); 61 assert(0); 62 } 63 } 64 else 65 assert(count == 0); 66 67 foreach (size_t i; 0 .. freelist.length) 68 { 69 void **vn; 70 for (void** v = cast(void **)freelist[i]; v; v = vn) 71 { 72 vn = cast(void **)(*v); 73 //mem_free(v); 74 .free(v); 75 } 76 freelist[i] = null; 77 } 78 } 79 } 80 81 vec_t allocate(size_t numbits) 82 { 83 if (numbits == 0) 84 return cast(vec_t) null; 85 const dim = (numbits + (VECBITS - 1)) >> VECSHIFT; 86 vec_t v; 87 if (dim < freelist.length && (v = freelist[dim]) != null) 88 { 89 freelist[dim] = *cast(vec_t *)v; 90 v += 2; 91 switch (dim) 92 { 93 case 5: v[4] = 0; goto case 4; 94 case 4: v[3] = 0; goto case 3; 95 case 3: v[2] = 0; goto case 2; 96 case 2: v[1] = 0; goto case 1; 97 case 1: v[0] = 0; 98 break; 99 default: memset(v,0,dim * vec_base_t.sizeof); 100 break; 101 } 102 goto L1; 103 } 104 else 105 { 106 v = cast(vec_t) calloc(dim + 2, vec_base_t.sizeof); 107 assert(v); 108 } 109 if (v) 110 { 111 v += 2; 112 L1: 113 vec_dim(v) = dim; 114 vec_numbits(v) = numbits; 115 /*printf("vec_calloc(%d): v = %p vec_numbits = %d vec_dim = %d\n", 116 numbits,v,vec_numbits(v),vec_dim(v));*/ 117 count++; 118 } 119 return v; 120 } 121 122 vec_t dup(const vec_t v) 123 { 124 if (!v) 125 return null; 126 127 const dim = vec_dim(v); 128 const nbytes = (dim + 2) * vec_base_t.sizeof; 129 vec_t vc; 130 vec_t result; 131 if (dim < freelist.length && (vc = freelist[dim]) != null) 132 { 133 freelist[dim] = *cast(vec_t *)vc; 134 goto L1; 135 } 136 else 137 { 138 vc = cast(vec_t) calloc(nbytes, 1); 139 assert(vc); 140 } 141 if (vc) 142 { 143 L1: 144 memcpy(vc,v - 2,nbytes); 145 count++; 146 result = vc + 2; 147 } 148 else 149 result = null; 150 return result; 151 } 152 153 void free(vec_t v) 154 { 155 /*printf("vec_free(%p)\n",v);*/ 156 if (v) 157 { 158 const dim = vec_dim(v); 159 v -= 2; 160 if (dim < freelist.length) 161 { 162 *cast(vec_t *)v = freelist[dim]; 163 freelist[dim] = v; 164 } 165 else 166 .free(v); 167 count--; 168 } 169 } 170 171 } 172 173 __gshared VecGlobal vecGlobal; 174 175 private pure vec_base_t MASK(uint b) { return cast(vec_base_t)1 << (b & VECMASK); } 176 177 pure ref inout(vec_base_t) vec_numbits(inout vec_t v) { return v[-1]; } 178 pure ref inout(vec_base_t) vec_dim(inout vec_t v) { return v[-2]; } 179 180 /************************** 181 * Initialize package. 182 */ 183 184 void vec_init() 185 { 186 vecGlobal.initialize(); 187 } 188 189 190 /************************** 191 * Terminate package. 192 */ 193 194 void vec_term() 195 { 196 vecGlobal.terminate(); 197 } 198 199 /******************************** 200 * Allocate a vector given # of bits in it. 201 * Clear the vector. 202 */ 203 204 vec_t vec_calloc(size_t numbits) 205 { 206 return vecGlobal.allocate(numbits); 207 } 208 209 /******************************** 210 * Allocate copy of existing vector. 211 */ 212 213 vec_t vec_clone(const vec_t v) 214 { 215 return vecGlobal.dup(v); 216 } 217 218 /************************** 219 * Free a vector. 220 */ 221 222 void vec_free(vec_t v) 223 { 224 /*printf("vec_free(%p)\n",v);*/ 225 return vecGlobal.free(v); 226 } 227 228 /************************** 229 * Realloc a vector to have numbits bits in it. 230 * Extra bits are set to 0. 231 */ 232 233 vec_t vec_realloc(vec_t v, size_t numbits) 234 { 235 /*printf("vec_realloc(%p,%d)\n",v,numbits);*/ 236 if (!v) 237 return vec_calloc(numbits); 238 if (!numbits) 239 { vec_free(v); 240 return null; 241 } 242 const vbits = vec_numbits(v); 243 if (numbits == vbits) 244 return v; 245 vec_t newv = vec_calloc(numbits); 246 if (newv) 247 { 248 const nbytes = (vec_dim(v) < vec_dim(newv)) ? vec_dim(v) : vec_dim(newv); 249 memcpy(newv,v,nbytes * vec_base_t.sizeof); 250 vec_clearextrabits(newv); 251 } 252 vec_free(v); 253 return newv; 254 } 255 256 /******************************** 257 * Recycle a vector `v` to a new size `numbits`, clear all bits. 258 * Re-uses original if possible. 259 */ 260 void vec_recycle(ref vec_t v, size_t numbits) 261 { 262 vec_free(v); 263 v = vec_calloc(numbits); 264 } 265 266 267 /************************** 268 * Set bit b in vector v. 269 */ 270 271 pure 272 void vec_setbit(size_t b, vec_t v) 273 { 274 debug 275 { 276 if (!(v && b < vec_numbits(v))) 277 printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n", 278 v, cast(int) b, cast(int) (v ? vec_numbits(v) : 0), cast(int) (v ? vec_dim(v) : 0)); 279 } 280 assert(v && b < vec_numbits(v)); 281 core.bitop.bts(v, b); 282 } 283 284 /************************** 285 * Clear bit b in vector v. 286 */ 287 288 pure 289 void vec_clearbit(size_t b, vec_t v) 290 { 291 assert(v && b < vec_numbits(v)); 292 core.bitop.btr(v, b); 293 } 294 295 /************************** 296 * Test bit b in vector v. 297 */ 298 299 pure 300 size_t vec_testbit(size_t b, const vec_t v) 301 { 302 if (!v) 303 return 0; 304 debug 305 { 306 if (!(v && b < vec_numbits(v))) 307 printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n", 308 v, cast(int) b, cast(int) (v ? vec_numbits(v) : 0), cast(int) (v ? vec_dim(v) : 0)); 309 } 310 assert(v && b < vec_numbits(v)); 311 return core.bitop.bt(v, b); 312 } 313 314 /******************************** 315 * Find first set bit starting from b in vector v. 316 * If no bit is found, return vec_numbits(v). 317 */ 318 319 pure 320 size_t vec_index(size_t b, const vec_t vec) 321 { 322 if (!vec) 323 return 0; 324 const(vec_base_t)* v = vec; 325 if (b < vec_numbits(v)) 326 { 327 const vtop = &vec[vec_dim(v)]; 328 const bit = b & VECMASK; 329 if (bit != b) // if not starting in first word 330 v += b >> VECSHIFT; 331 size_t starv = *v >> bit; 332 while (1) 333 { 334 while (starv) 335 { 336 if (starv & 1) 337 return b; 338 b++; 339 starv >>= 1; 340 } 341 b = (b + VECBITS) & ~VECMASK; // round up to next word 342 if (++v >= vtop) 343 break; 344 starv = *v; 345 } 346 } 347 return vec_numbits(vec); 348 } 349 350 /******************************** 351 * Compute v1 &= v2. 352 */ 353 354 pure 355 void vec_andass(vec_t v1, const(vec_base_t)* v2) 356 { 357 if (v1) 358 { 359 assert(v2); 360 assert(vec_numbits(v1)==vec_numbits(v2)); 361 const vtop = &v1[vec_dim(v1)]; 362 for (; v1 < vtop; v1++,v2++) 363 *v1 &= *v2; 364 } 365 else 366 assert(!v2); 367 } 368 369 /******************************** 370 * Compute v1 = v2 & v3. 371 */ 372 373 pure 374 void vec_and(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 375 { 376 if (v1) 377 { 378 assert(v2 && v3); 379 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 380 const vtop = &v1[vec_dim(v1)]; 381 for (; v1 < vtop; v1++,v2++,v3++) 382 *v1 = *v2 & *v3; 383 } 384 else 385 assert(!v2 && !v3); 386 } 387 388 /******************************** 389 * Compute v1 ^= v2. 390 */ 391 392 pure 393 void vec_xorass(vec_t v1, const(vec_base_t)* v2) 394 { 395 if (v1) 396 { 397 assert(v2); 398 assert(vec_numbits(v1)==vec_numbits(v2)); 399 const vtop = &v1[vec_dim(v1)]; 400 for (; v1 < vtop; v1++,v2++) 401 *v1 ^= *v2; 402 } 403 else 404 assert(!v2); 405 } 406 407 /******************************** 408 * Compute v1 = v2 ^ v3. 409 */ 410 411 pure 412 void vec_xor(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 413 { 414 if (v1) 415 { 416 assert(v2 && v3); 417 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 418 const vtop = &v1[vec_dim(v1)]; 419 for (; v1 < vtop; v1++,v2++,v3++) 420 *v1 = *v2 ^ *v3; 421 } 422 else 423 assert(!v2 && !v3); 424 } 425 426 /******************************** 427 * Compute v1 |= v2. 428 */ 429 430 pure 431 void vec_orass(vec_t v1, const(vec_base_t)* v2) 432 { 433 if (v1) 434 { 435 debug assert(v2); 436 debug assert(vec_numbits(v1)==vec_numbits(v2)); 437 const vtop = &v1[vec_dim(v1)]; 438 for (; v1 < vtop; v1++,v2++) 439 *v1 |= *v2; 440 } 441 else 442 assert(!v2); 443 } 444 445 /******************************** 446 * Compute v1 = v2 | v3. 447 */ 448 449 pure 450 void vec_or(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 451 { 452 if (v1) 453 { 454 assert(v2 && v3); 455 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 456 const vtop = &v1[vec_dim(v1)]; 457 for (; v1 < vtop; v1++,v2++,v3++) 458 *v1 = *v2 | *v3; 459 } 460 else 461 assert(!v2 && !v3); 462 } 463 464 /******************************** 465 * Compute v1 -= v2. 466 */ 467 468 pure 469 void vec_subass(vec_t v1, const(vec_base_t)* v2) 470 { 471 if (v1) 472 { 473 assert(v2); 474 assert(vec_numbits(v1)==vec_numbits(v2)); 475 const vtop = &v1[vec_dim(v1)]; 476 for (; v1 < vtop; v1++,v2++) 477 *v1 &= ~*v2; 478 } 479 else 480 assert(!v2); 481 } 482 483 /******************************** 484 * Compute v1 = v2 - v3. 485 */ 486 487 pure 488 void vec_sub(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3) 489 { 490 if (v1) 491 { 492 assert(v2 && v3); 493 assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 494 const vtop = &v1[vec_dim(v1)]; 495 for (; v1 < vtop; v1++,v2++,v3++) 496 *v1 = *v2 & ~*v3; 497 } 498 else 499 assert(!v2 && !v3); 500 } 501 502 /**************** 503 * Clear vector. 504 */ 505 506 pure 507 void vec_clear(vec_t v) 508 { 509 if (v) 510 memset(v, 0, v[0].sizeof * vec_dim(v)); 511 } 512 513 /**************** 514 * Set vector. 515 */ 516 517 pure 518 void vec_set(vec_t v) 519 { 520 if (v) 521 { 522 memset(v, ~0, v[0].sizeof * vec_dim(v)); 523 vec_clearextrabits(v); 524 } 525 } 526 527 /*************** 528 * Copy vector. 529 */ 530 531 pure 532 void vec_copy(vec_t to, const vec_t from) 533 { 534 if (to != from) 535 { 536 debug 537 { 538 if (!(to && from && vec_numbits(to) == vec_numbits(from))) 539 printf("to = x%p, from = x%p, numbits(to) = %d, numbits(from) = %d\n", 540 to, from, cast(int) (to ? vec_numbits(to) : 0), 541 cast(int) (from ? vec_numbits(from): 0)); 542 } 543 assert(to && from && vec_numbits(to) == vec_numbits(from)); 544 memcpy(to, from, to[0].sizeof * vec_dim(to)); 545 } 546 } 547 548 /**************** 549 * Return 1 if vectors are equal. 550 */ 551 552 pure 553 int vec_equal(const vec_t v1, const vec_t v2) 554 { 555 if (v1 == v2) 556 return 1; 557 assert(v1 && v2 && vec_numbits(v1) == vec_numbits(v2)); 558 return !memcmp(v1, v2, v1[0].sizeof * vec_dim(v1)); 559 } 560 561 /******************************** 562 * Return 1 if (v1 & v2) == 0 563 */ 564 565 pure 566 int vec_disjoint(const(vec_base_t)* v1, const(vec_base_t)* v2) 567 { 568 assert(v1 && v2); 569 assert(vec_numbits(v1) == vec_numbits(v2)); 570 const vtop = &v1[vec_dim(v1)]; 571 for (; v1 < vtop; v1++,v2++) 572 if (*v1 & *v2) 573 return 0; 574 return 1; 575 } 576 577 /********************* 578 * Clear any extra bits in vector. 579 */ 580 581 pure 582 void vec_clearextrabits(vec_t v) 583 { 584 assert(v); 585 const n = vec_numbits(v); 586 if (n & VECMASK) 587 v[vec_dim(v) - 1] &= MASK(cast(uint)n) - 1; 588 } 589 590 /****************** 591 * Write out vector. 592 */ 593 594 pure 595 void vec_println(const vec_t v) 596 { 597 debug 598 { 599 vec_print(v); 600 fputc('\n',stdout); 601 } 602 } 603 604 pure 605 void vec_print(const vec_t v) 606 { 607 debug 608 { 609 printf(" Vec %p, numbits %d dim %d", v, cast(int) vec_numbits(v), cast(int) vec_dim(v)); 610 if (v) 611 { 612 fputc('\t',stdout); 613 for (size_t i = 0; i < vec_numbits(v); i++) 614 fputc((vec_testbit(i,v)) ? '1' : '0',stdout); 615 } 616 } 617 } 618 619