Unofficial Dub Package Documentation 
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  * Set bit b in vector v.
258  */
259 
260 pure
261 void vec_setbit(size_t b, vec_t v)
262 {
263     debug
264     {
265         if (!(v && b < vec_numbits(v)))
266             printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n",
267                 v, cast(int) b, cast(int) (v ? vec_numbits(v) : 0), cast(int) (v ? vec_dim(v) : 0));
268     }
269     assert(v && b < vec_numbits(v));
270     core.bitop.bts(v, b);
271 }
272 
273 /**************************
274  * Clear bit b in vector v.
275  */
276 
277 pure
278 void vec_clearbit(size_t b, vec_t v)
279 {
280     assert(v && b < vec_numbits(v));
281     core.bitop.btr(v, b);
282 }
283 
284 /**************************
285  * Test bit b in vector v.
286  */
287 
288 pure
289 size_t vec_testbit(size_t b, const vec_t v)
290 {
291     if (!v)
292         return 0;
293     debug
294     {
295         if (!(v && b < vec_numbits(v)))
296             printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n",
297                 v, cast(int) b, cast(int) (v ? vec_numbits(v) : 0), cast(int) (v ? vec_dim(v) : 0));
298     }
299     assert(v && b < vec_numbits(v));
300     return core.bitop.bt(v, b);
301 }
302 
303 /********************************
304  * Find first set bit starting from b in vector v.
305  * If no bit is found, return vec_numbits(v).
306  */
307 
308 pure
309 size_t vec_index(size_t b, const vec_t vec)
310 {
311     if (!vec)
312         return 0;
313     const(vec_base_t)* v = vec;
314     if (b < vec_numbits(v))
315     {
316         const vtop = &vec[vec_dim(v)];
317         const bit = b & VECMASK;
318         if (bit != b)                   // if not starting in first word
319             v += b >> VECSHIFT;
320         size_t starv = *v >> bit;
321         while (1)
322         {
323             while (starv)
324             {
325                 if (starv & 1)
326                     return b;
327                 b++;
328                 starv >>= 1;
329             }
330             b = (b + VECBITS) & ~VECMASK;   // round up to next word
331             if (++v >= vtop)
332                 break;
333             starv = *v;
334         }
335     }
336     return vec_numbits(vec);
337 }
338 
339 /********************************
340  * Compute v1 &= v2.
341  */
342 
343 pure
344 void vec_andass(vec_t v1, const(vec_base_t)* v2)
345 {
346     if (v1)
347     {
348         assert(v2);
349         assert(vec_numbits(v1)==vec_numbits(v2));
350         const vtop = &v1[vec_dim(v1)];
351         for (; v1 < vtop; v1++,v2++)
352             *v1 &= *v2;
353     }
354     else
355         assert(!v2);
356 }
357 
358 /********************************
359  * Compute v1 = v2 & v3.
360  */
361 
362 pure
363 void vec_and(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3)
364 {
365     if (v1)
366     {
367         assert(v2 && v3);
368         assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
369         const vtop = &v1[vec_dim(v1)];
370         for (; v1 < vtop; v1++,v2++,v3++)
371             *v1 = *v2 & *v3;
372     }
373     else
374         assert(!v2 && !v3);
375 }
376 
377 /********************************
378  * Compute v1 ^= v2.
379  */
380 
381 pure
382 void vec_xorass(vec_t v1, const(vec_base_t)* v2)
383 {
384     if (v1)
385     {
386         assert(v2);
387         assert(vec_numbits(v1)==vec_numbits(v2));
388         const vtop = &v1[vec_dim(v1)];
389         for (; v1 < vtop; v1++,v2++)
390             *v1 ^= *v2;
391     }
392     else
393         assert(!v2);
394 }
395 
396 /********************************
397  * Compute v1 = v2 ^ v3.
398  */
399 
400 pure
401 void vec_xor(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3)
402 {
403     if (v1)
404     {
405         assert(v2 && v3);
406         assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
407         const vtop = &v1[vec_dim(v1)];
408         for (; v1 < vtop; v1++,v2++,v3++)
409             *v1 = *v2 ^ *v3;
410     }
411     else
412         assert(!v2 && !v3);
413 }
414 
415 /********************************
416  * Compute v1 |= v2.
417  */
418 
419 pure
420 void vec_orass(vec_t v1, const(vec_base_t)* v2)
421 {
422     if (v1)
423     {
424         debug assert(v2);
425         debug assert(vec_numbits(v1)==vec_numbits(v2));
426         const vtop = &v1[vec_dim(v1)];
427         for (; v1 < vtop; v1++,v2++)
428             *v1 |= *v2;
429     }
430     else
431         assert(!v2);
432 }
433 
434 /********************************
435  * Compute v1 = v2 | v3.
436  */
437 
438 pure
439 void vec_or(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3)
440 {
441     if (v1)
442     {
443         assert(v2 && v3);
444         assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
445         const vtop = &v1[vec_dim(v1)];
446         for (; v1 < vtop; v1++,v2++,v3++)
447                 *v1 = *v2 | *v3;
448     }
449     else
450         assert(!v2 && !v3);
451 }
452 
453 /********************************
454  * Compute v1 -= v2.
455  */
456 
457 pure
458 void vec_subass(vec_t v1, const(vec_base_t)* v2)
459 {
460     if (v1)
461     {
462         assert(v2);
463         assert(vec_numbits(v1)==vec_numbits(v2));
464         const vtop = &v1[vec_dim(v1)];
465         for (; v1 < vtop; v1++,v2++)
466             *v1 &= ~*v2;
467     }
468     else
469         assert(!v2);
470 }
471 
472 /********************************
473  * Compute v1 = v2 - v3.
474  */
475 
476 pure
477 void vec_sub(vec_t v1, const(vec_base_t)* v2, const(vec_base_t)* v3)
478 {
479     if (v1)
480     {
481         assert(v2 && v3);
482         assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
483         const vtop = &v1[vec_dim(v1)];
484         for (; v1 < vtop; v1++,v2++,v3++)
485             *v1 = *v2 & ~*v3;
486     }
487     else
488         assert(!v2 && !v3);
489 }
490 
491 /****************
492  * Clear vector.
493  */
494 
495 pure
496 void vec_clear(vec_t v)
497 {
498     if (v)
499         memset(v, 0, v[0].sizeof * vec_dim(v));
500 }
501 
502 /****************
503  * Set vector.
504  */
505 
506 pure
507 void vec_set(vec_t v)
508 {
509     if (v)
510     {
511         memset(v, ~0, v[0].sizeof * vec_dim(v));
512         vec_clearextrabits(v);
513     }
514 }
515 
516 /***************
517  * Copy vector.
518  */
519 
520 pure
521 void vec_copy(vec_t to, const vec_t from)
522 {
523     if (to != from)
524     {
525         debug
526         {
527             if (!(to && from && vec_numbits(to) == vec_numbits(from)))
528                 printf("to = x%p, from = x%p, numbits(to) = %d, numbits(from) = %d\n",
529                     to, from, cast(int) (to ? vec_numbits(to) : 0),
530                     cast(int) (from ? vec_numbits(from): 0));
531         }
532         assert(to && from && vec_numbits(to) == vec_numbits(from));
533         memcpy(to, from, to[0].sizeof * vec_dim(to));
534     }
535 }
536 
537 /****************
538  * Return 1 if vectors are equal.
539  */
540 
541 pure
542 int vec_equal(const vec_t v1, const vec_t v2)
543 {
544     if (v1 == v2)
545         return 1;
546     assert(v1 && v2 && vec_numbits(v1) == vec_numbits(v2));
547     return !memcmp(v1, v2, v1[0].sizeof * vec_dim(v1));
548 }
549 
550 /********************************
551  * Return 1 if (v1 & v2) == 0
552  */
553 
554 pure
555 int vec_disjoint(const(vec_base_t)* v1, const(vec_base_t)* v2)
556 {
557     assert(v1 && v2);
558     assert(vec_numbits(v1) == vec_numbits(v2));
559     const vtop = &v1[vec_dim(v1)];
560     for (; v1 < vtop; v1++,v2++)
561         if (*v1 & *v2)
562             return 0;
563     return 1;
564 }
565 
566 /*********************
567  * Clear any extra bits in vector.
568  */
569 
570 pure
571 void vec_clearextrabits(vec_t v)
572 {
573     assert(v);
574     const n = vec_numbits(v);
575     if (n & VECMASK)
576         v[vec_dim(v) - 1] &= MASK(cast(uint)n) - 1;
577 }
578 
579 /******************
580  * Write out vector.
581  */
582 
583 pure
584 void vec_println(const vec_t v)
585 {
586     debug
587     {
588         vec_print(v);
589         fputc('\n',stdout);
590     }
591 }
592 
593 pure
594 void vec_print(const vec_t v)
595 {
596     debug
597     {
598         printf(" Vec %p, numbits %d dim %d", v, cast(int) vec_numbits(v), cast(int) vec_dim(v));
599         if (v)
600         {
601             fputc('\t',stdout);
602             for (size_t i = 0; i < vec_numbits(v); i++)
603                 fputc((vec_testbit(i,v)) ? '1' : '0',stdout);
604         }
605     }
606 }
607 
608

Page generated by adrdox