Contents

dankogai/swift-critbittree

[Crit-bit tree] in Swift — CBTSet and CBTDictionary, drop-in analogues of Set and Dictionary that keep their elements in sorted order.

Synopsis

import CritBitTree

var set: CBTSet<String> = ["swift", "critbit", "tree"]
set.insert("banana")
set.contains("swift")   // true
Array(set)              // ["banana", "critbit", "swift", "tree"] — always sorted
set.prefix("cr")        // ["critbit"] — prefix search in O(len(prefix))

var freq = CBTDictionary<Substring, Int>()
for word in "to be or not to be".split(separator: " ") {
    freq[word, default: 0] += 1
}
print(freq)             // ["be": 2, "not": 1, "or": 1, "to": 2]

Description

A crit-bit tree is a binary trie in which every internal node records only the position of the critical bit — the first bit at which its two subtrees differ — and every key lives in a leaf. It was popularized by [D. J. Bernstein][Crit-bit tree]; see also [Adam Langley's annotated implementation][critbit.pdf] and [Nim's critbits module][nim-critbits].

[critbit.pdf]: https://www.imperialviolet.org/binary/critbit.pdf [nim-critbits]: https://nim-lang.org/docs/critbits.html

Properties that fall out of the structure:

  • Fast, comparison-free operations — membership, insertion, and removal walk one node per critical bit, testing a single bit at each step: O(k) where k is the key length in bits, independent of the number of elements.
  • Sorted iteration — in-order traversal yields keys in ascending bit-lexicographic order, for free.
  • Canonical shape — the tree's structure depends only on the set of keys, never on insertion order, which makes equality a simple parallel traversal.
  • Compact — n keys need exactly n − 1 internal nodes.

This package implements the tree as a persistent (path-copying) data structure, so CBTSet and CBTDictionary are value types with the same copy-on-assignment behavior as Set and Dictionary, sharing structure between copies.

Types

| Type | Analogue of | |------|-------------| | CBTSet<Element> / CBASet<Element> | Set | | CBTDictionary<Key, Value> / CBADictionary<Key, Value> | Dictionary |

All four conform to all protocols of their built-in analogues except the Objective-C/Foundation bridging machinery (CVarArg, _ObjectiveCBridgeable, custom AnyHashable representations), which only applies to types bridged to NSSet/NSDictionary. That is: Sequence, Collection, SetAlgebra or ExpressibleByDictionaryLiteral, Equatable, Hashable, Encodable/Decodable, Sendable, CustomReflectable, CustomStringConvertible, and CustomDebugStringConvertible (* conditionally, like the built-ins).

The method-level API matches too: firstIndex(of:) / index(forKey:) in O(k), remove(at:), popFirst(), Set-style filter returning Self, Keys/Values dictionary views (values supports in-place mutation), init(minimumCapacity:), reserveCapacity(_:), and Dictionary(grouping:by:).

The CBT types store the tree as individually allocated nodes; mutations copy only the path from root to leaf, so copies share almost all structure — and prefix(_:) can return a view that shares its subtree outright. The CBA types store the same tree in two flat arrays (branches as (critbit, left, right) index triples, elements alongside), so an n-element container owns two array buffers instead of 2n − 1 heap nodes: substantially faster in practice (roughly 4× on insertion and iteration, more on removal), at the cost of whole-array copy-on-write when a shared copy mutates, and tombstones left behind by removals until the container empties. Same semantics, same API — pick CBA for speed, CBT for cheap structural sharing. The append-only storage gives the CBA types one extra ability: insertionOrder(), a lazy view of the elements in insertion order (updates keep an element's position; remove-then-insert moves it to the end). See Benchmark.md for measurements against the built-in Set and Dictionary.

Set elements and dictionary keys must conform to CritBitAvailable:

public protocol CritBitAvailable: Equatable {
    /// Position of the first differing bit, MSB-first, or nil if equal.
    static func critbitAt(_ lhs: Self, _ rhs: Self) -> Int?
    /// Whether the bit at `position` is set, in the same numbering.
    func critbit(at position: Int) -> Bool
    /// The number of bits in the value's representation.
    var critbitWidth: Int { get }
}

Conformances are provided for String, Substring, all ten standard fixed-width integer types, and — conditionally and recursively — Array of any conforming element, so CBTSet<[String]> or CBTDictionary<[UInt8], Value> just work. Arrays are encoded with a leading element count, so they order shortlex (shorter arrays first) and [1, 2], [1, 2, 0], and ["1", "2"] vs ["12"] are all distinct keys. Default implementations cover any StringProtocol or FixedWidthInteger type, so conforming another such type is one line:

extension UInt128: CritBitAvailable {}

Prefix search

The signature capability of a crit-bit tree: all keys sharing a prefix occupy one contiguous subtree, so prefix(_:) — available on both containers when elements/keys are strings — locates it in O(k) in the length of the prefix, independent of the number of elements, and returns a set/dictionary that shares the subtree:

let s: CBTSet<String> = ["app", "apple", "applesauce", "banana"]
s.prefix("app")         // ["app", "apple", "applesauce"]

let d: CBTDictionary<String, Int> = ["app": 1, "apple": 2, "banana": 3]
d.prefix("app")         // ["app": 1, "apple": 2]

Differences from Set and Dictionary

Both are inherent to the data structure and can be a feature:

  • Iteration order is deterministic: ascending bit-lexicographic order. For strings this is UTF-8 byte order; for unsigned integers, numeric order; for signed integers, negative values follow non-negative ones (bit 0 is the sign bit).
  • Identity is bitwise: two String keys are the same key iff their UTF-8 bytes are equal, so canonically equivalent but differently composed strings (e.g. precomposed vs. decomposed "é") are distinct. Relatedly, strings containing U+0000 are not distinguishable from their truncations — the same limitation as the C original's NUL-terminated keys.

Usage

Swift Package Manager

Add to your Package.swift:

dependencies: [
    .package(url: "https://github.com/dankogai/swift-critbittree.git", branch: "main"),
],

and "CritBitTree" to your target's dependencies. In Xcode: File → Add Package Dependencies… with the URL above.

Build and test

swift build
swift test

Playground

Open macOS.playground in Xcode (with the package checked out) to try the API interactively.

License

MIT. © 2026 Dan Kogai.

Package Metadata

Repository: dankogai/swift-critbittree

Default branch: main

README: README.md