License
BSD-3-Clause
ddn.columnar.bitmap
The bitmap layer of ddn.df: one representation for validity bitmaps and bit-packed boolean values (D7, ADR-2026-10-18-08).
A bitmap is immutable(ulong)[] words plus a bit offset below 64 and a length in bits. slice re-bases the words so bitOffset < 64 always holds and no copy is made. After re-basing, logical bit i is wordAt(i >> 6) >> (i & 63) — never (bitOffset + i), which double-counts the offset (fact 6). The empty bitmap is the "all valid" sentinel.
Copyright
Copyright (c) 2026, DDN (D Developer Network) Members
Types 2
structBitmap
A packed bitmap: one bit per slot, LSB-first within each word, 1 set. One type serves both chunk validity ("absent means no nulls"; the empty bitmap is the all-valid sentinel) and BOOLEAN values (BooleanArray.bits is never the sentinel, so an all-false boolean column keeps its storage).
Instances are values: slice shares the immutable storage and re-bases the offset; and, or and not produce fresh offset-0 bitmaps with the last word tail-masked, so countSet and equality are exact. opEquals is logical: it depends only on the visible bits, never on the offset or the storage.
Fields
immutable(ulong)[] wordsStorage, possibly shared with a parent bitmap.size_t bitOffsetBit of `words[0]` where the visible range starts; always `< 64`.size_t lengthNumber of visible bits.Methods
bool isSentinel() const @safe pure nothrowReturns: `true` when this bitmap is empty — the "all valid" sentinel for validity bitmaps (an identity operand for `and`).ulong wordAt(size_t w) const @safe pure nothrowThe `w`-th word of the logical bitstream: the bits of the visible range starting at `w * 64`, assembled from one or two storage words. The `r != 0` guard is mandatory — a runtime shift by 64 is n...ulong window(size_t start, size_t n) const @safe pure nothrowThe packed window word of `n` visible bits starting at `start`, LSB-first; the bits past `n` in the result are cleared. The empty sentinel reads as all-ones, its meaning for validity bitmaps ("no n...size_t countSet() const @safe pure nothrowCounts the set bits in the visible range. The count of an empty bitmap is `0`; the owner of a sentinel validity bitmap takes its valid count from its own length instead (the sentinel means "all val...Bitmap slice(size_t start, size_t len) const @safe pure nothrowZero-copy slice: re-bases the storage so the result's `bitOffset` is again below 64, without copying a word.Bitmap and(const Bitmap other) constWord-wise conjunction with tail masking. A sentinel on either side short-circuits and returns the other side unchanged (the all-valid sentinel is the identity of `and`).Bitmap or(const Bitmap other) constWord-wise disjunction with tail masking. A sentinel on either side short-circuits and returns the other side unchanged.Bitmap not() constWord-wise negation with tail masking. Not defined on the sentinel, which has no length of its own; the owner of a sentinel validity bitmap materialises an all-set bitmap of its own length instead.bool[] toBools() const @safe pure nothrowReturns: the visible bits materialised as a fresh `bool[]`.structBitmapBuilder
Builds a Bitmap from individual bits. Fresh words are zeroed by allocAligned (GC.calloc), so bits can be OR-ed in safely (fact 5). Single-use: after finish the builder holds nothing and further use asserts (the plan requires throwing or asserting; the assert surfaces the bug at the earliest point).
Fields
private ulong[] _wordsprivate size_t _lengthprivate bool _sealedMethods
void appendWord(ulong word, size_t n) @safe pure nothrowAppends `n` bits from one packed word, LSB-first; the bits of `word` at or above `n` are ignored. This is the bulk path the packed-bit kernels of `ddn.columnar.vector` write through.void appendWords(const(ulong)[] words, size_t bits) @safe pure nothrowAppends `bits` packed bits from whole words, LSB-first; the bits of the last word at or above `bits` are ignored.void appendBitmap(const Bitmap other) @safe pure nothrowAppends every visible bit of another bitmap, word-wise through `wordAt` (offsets re-based on the fly).Bitmap finish() @safe pure nothrowSeals the bitmap, trimming over-allocated capacity so the storage holds exactly the words in use.