dmd.backend.dvec source code

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-2021 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