nxt.bitarray_algorithm source code

1 /** Algorithms for dynamic and static bitarrays based with integral blocks.
2  *
3  * Algorithms are qualified as `package` because they should only be used by
4  * bit-array containers.
5  */
6 module nxt.bitarray_algorithm;
7 
8 pure nothrow @safe @nogc:
9 
10 size_t countOnes(Blocks, bool blockAlignedLength = false)(const scope auto ref Blocks blocks, size_t length) @trusted
11 if (isBlocks!Blocks) {
12 	alias Block = typeof(Blocks.init[0]);
13 	enum bitsPerBlock = 8*Block.sizeof;
14 
15 	typeof(return) result = 0;
16 
17 	import core.bitop : popcnt;
18 	const fullBlockCount = length / bitsPerBlock;
19 	foreach (const block; blocks.ptr[0 .. fullBlockCount]) {
20 		result += cast(typeof(result))popcnt(block);
21 	}
22 
23 	// dbg("bitsPerBlock:", bitsPerBlock,
24 	//	 " length:", length,
25 	//	 " fullBlockCount:", fullBlockCount);,
26 
27 	static if (!blockAlignedLength) {
28 		const restBitCount = length % bitsPerBlock;
29 		if (restBitCount) {
30 			result += cast(typeof(result))popcnt(blocks.ptr[fullBlockCount] & ((1UL << restBitCount)-1));
31 		}
32 
33 		// dbg(" restBitCount:", restBitCount);
34 	}
35 
36 	return typeof(return)(result);
37 }
38 
39 /// Test `countOnes` with full blocks.
40 pure nothrow @safe @nogc unittest {
41 	alias Block = size_t;
42 	enum bitsPerBlock = 8*Block.sizeof;
43 
44 	enum blockCount = 3;
45 	Block[blockCount] x;
46 	const length = 8*x.sizeof;
47 	assert(countOnes(x, length) == 0);
48 
49 	x[0] = 1;
50 	assert(countOnes(x, length) == 1);
51 
52 	x[0] = 1+2;
53 	assert(countOnes(x, length) == 2);
54 
55 	x[0] = 1+2;
56 	x[1] = 1+2;
57 	assert(countOnes(x, length) == 4);
58 
59 	x[0] = 1+2;
60 	x[1] = 1+2;
61 	x[2] = 1+2;
62 	assert(countOnes(x, length) == 6);
63 }
64 
65 /// Test `countOnes` with partial blocks.
66 pure nothrow @safe @nogc unittest {
67 	alias Block = size_t;
68 	static void test(uint blockCount)() {
69 		Block[blockCount] x;
70 		foreach (const length; 1 .. 8*x.sizeof) {
71 			assert(countOnes(x, length) == 0);
72 
73 			x[0] |= 1UL << (length-1);
74 			assert(countOnes(x, length) == 1);
75 			x[0] = 0;
76 		}
77 	}
78 	test!1();
79 	test!2();
80 	test!3();
81 }
82 
83 /** Find index of first cleared (zero) bit or `length` if no bit cleared.
84  *
85  * Optimized for zeros-sparsity.
86  */
87 size_t indexOfFirstZero(Blocks, bool blockAlignedLength = false)(const scope auto ref Blocks blocks, size_t length)
88 if (isBlocks!Blocks) {
89 	static if (blockAlignedLength) {
90 		foreach (const blockIndex, block; blocks) {
91 			if (block != block.max) // optimize for zeros-sparsity
92 			{
93 				import core.bitop : bsf;
94 				const hitIndex = blockIndex*8*block.sizeof + bsf(~block); /+ TODO: is there a builtin for `bsf(~block)`? +/
95 				return hitIndex < length ? hitIndex : length; // if hit beyond end miss
96 			}
97 		}
98 	}
99 	else
100 	{
101 		/+ TODO: handle blocks with garbage in the rest block +/
102 		foreach (const blockIndex, block; blocks) {
103 			if (block != block.max) // optimize for zeros-sparsity
104 			{
105 				import core.bitop : bsf;
106 				const hitIndex = blockIndex*8*block.sizeof + bsf(~block); /+ TODO: is there a builtin for `bsf(~block)`? +/
107 				return hitIndex < length ? hitIndex : length; // if hit beyond end miss
108 			}
109 		}
110 	}
111 	return length;			  // miss
112 }
113 
114 /** Find index of first set (one) bit or `length` if no bit cleared.
115  *
116  * Optimized for ones-sparsity.
117  */
118 size_t indexOfFirstOne(Blocks, bool blockAlignedLength = false)(const scope auto ref Blocks blocks, size_t length)
119 if (isBlocks!Blocks) {
120 	static if (blockAlignedLength) {
121 		foreach (const blockIndex, const block; blocks) {
122 			if (block != block.min) // optimize for ones-sparsity
123 			{
124 				import core.bitop : bsf;
125 				const hitIndex = blockIndex*8*block.sizeof + bsf(block);
126 				return hitIndex < length ? hitIndex : length; // if hit beyond end miss
127 			}
128 		}
129 	}
130 	else
131 	{
132 		/+ TODO: handle blocks with garbage in the rest block +/
133 		foreach (const blockIndex, const block; blocks) {
134 			if (block != block.min) // optimize for ones-sparsity
135 			{
136 				import core.bitop : bsf;
137 				const hitIndex = blockIndex*8*block.sizeof + bsf(block);
138 				return hitIndex < length ? hitIndex : length; // if hit beyond end miss
139 			}
140 		}
141 	}
142 	return length;			  // miss
143 }
144 
145 private enum isBlocks(Blocks) = (is(typeof(Blocks.init[0]) : uint) ||
146 								 is(typeof(Blocks.init[0]) : ulong));