Table of contents
Some lookups are not “does this key exist” but “what is the most specific rule that applies to this key”. Telephone routing is the canonical example: a dialled number matches the longest stored prefix, so +1 212 555 0100 should resolve to a New York rule (1212) if one exists, and fall back to a broader North American rule (1) if it does not. A hash map answers only exact-key questions, so longest-prefix matching would need a separate probe for every shrinking prefix; a linear scan over a sorted list degrades as the table grows. The numtrie
package in nurago
is a small generic trie built for exactly this question:
import "github.com/tecnickcom/nurago/pkg/numtrie"
root := numtrie.New[Route]()
root.Add("1", &defaultUSRoute)
root.Add("1212", &newYorkRoute)
root.Add("44", &ukRoute)
root.Add("44207", &londonRoute)
val, status := root.Get("+1-212-555-0100")
// val == &newYorkRoute (longest matching prefix: "1212")
A structure this small is really a bundle of design decisions, so this post walks through it as six questions, each answered from the code.
Why a fixed 10-slot child array instead of a map per node?
Because the alphabet is known and tiny. Keys are digit sequences, so every node carries exactly ten child slots:
const indexSize = 10 // digits from 0 to 9
type Node[T any] struct {
value *T
numChildren int
children [indexSize]*Node[T]
}
A map[rune]*Node would give each interior node its own hash table and pay a hash-and-probe on every step of every traversal. The fixed array makes a node a single allocation, and descending to the next digit is one array index. The allocation profile follows directly from the layout: insertion allocates one node per new digit position, re-inserting at an existing position allocates nothing, and lookups (Get and GetExact) do not allocate. The package’s BenchmarkAdd deliberately inserts a thousand distinct keys into a fresh trie per iteration so it reports that real insertion cost; re-adding a single key would show a misleading zero allocations per operation, because after the first iteration every node already exists.
The trade is memory: ten pointer slots per node even where only one is occupied. For a routing table with a small fixed alphabet, that is a modest, predictable price for hash-free descent.
What does the packed int8 status encode, and why should one traversal return it all?
Longest-prefix matching does not have a binary result, and a routing engine often needs the full picture without a second query. Get therefore returns, alongside the value, an int8 documented as a compact bit field:
Bit 7 (sign): set → no digits matched at all (empty input or no root child)
Bit 1: set → input extends beyond the matched trie path (prefix match)
Bit 0: set → matched node has children (partial match)
Six named constants cover every meaningful combination:
StatusMatchEmpty (-127): no digit characters in input
StatusMatchNo (-125): first digit not in trie
StatusMatchFull ( 0): exact match, leaf node
StatusMatchPartial ( 1): exact match, non-leaf node
StatusMatchPrefix ( 2): stored key is prefix of input, leaf node
StatusMatchPartialPrefix ( 3): stored key is prefix of input, non-leaf node
One traversal, one byte, and the caller learns not just what matched but whether the dialled number is complete, whether a more specific rule could exist further down, and whether the input overshot a terminal entry. When bit 7 is set, the status is a standalone sentinel: only the sign is significant and the low bits carry no meaning. For callers that only want “the best match for this input exactly as stored”, GetExact skips all of this and returns the value at the precise key position, with no longest-prefix fallback.
How is the status computed without branching over cases?
The two informative bits are not selected by a four-way switch. They fall out of two boolean facts about where the walk ended, converted to bits and OR-ed together:
return typeutil.BoolToNum[int8](digit > match)<<1 |
typeutil.BoolToNum[int8](t.numChildren > 0)
match counts the digits followed into the trie; digit is either equal to match or exactly one more, when the input carried a further digit whose child was absent. So digit > match is precisely the prefix bit, and numChildren > 0 (a counter maintained during insertion, so leaf detection costs nothing at lookup time) is the partial bit. The typeutil.BoolToNum helper is documented to compile, for integer instantiations, to a branch-free byte move rather than a jump. The only branch in the status path handles match == 0, which returns the named negative sentinels directly so the result is well defined even for an empty trie.
How does 1-800-FLOWERS become a numeric key?
Real numbers arrive formatted (+1-212-555-0100) and occasionally as vanity spellings. Rather than push sanitisation onto the caller, the trie normalises during the walk itself. Every rune passes through phonekeypad.KeypadDigit from nurago’s phonekeypad
package: digits map to themselves, ASCII letters fold case-insensitively to their International Telecommunication Union (ITU) E.161 keypad digits, and everything else (hyphens, spaces, parentheses, the leading +, non-ASCII characters) reports “not a keypad character” and is skipped. So FLOWERS becomes 3569377 and matches transparently against a numeric key. Add, Get, and GetExact all apply the same fold, so what you store and what you look up normalise identically; the package’s tests confirm that adding "1B3" after "123" overwrites the same slot.
This mapping is also why the child array is exactly ten wide: KeypadDigit always returns a result in [0, 10), and that result indexes the array directly. The source marks the two as a pair that must stay in sync.
Who owns an inserted value, and what does nil mean?
Values are stored as pointers, and the contract is aliasing, not copying: the trie keeps the supplied pointer, so mutating the pointed-to value after Add is visible through the trie, and one pointer stored under several keys is shared by all of them. A nil value is rejected as a no-op (Add returns false and creates no nodes), because the trie cannot distinguish a stored nil from an absent entry. Storing at the empty key, Add("", v), sets a default that acts as the longest-prefix fallback for any input that matches at least one digit.
On the way out, nil is more subtle than “negative status means nil”. The two negative sentinels do return nil, even when a root default is present: if nothing matched, no value leaks. But a non-negative status does not by itself guarantee a value. StatusMatchFull and StatusMatchPrefix, the two leaf outcomes, always carry one; StatusMatchPartial and StatusMatchPartialPrefix return the last non-nil value found along the path, which is nil when the walk ended inside the structure without passing any stored value. The rule is short: always nil-check the returned pointer, whatever the status says.
Ownership also settles concurrency. Add mutates the trie in place, so it must not run concurrently with anything; once the trie is fully built, any number of goroutines may call Get and GetExact in parallel without locks.
What does O(k) cover, and what does it not?
The package documents lookup as O(k) in the number of digits k, and the code supports it: the walk visits at most one node per digit and does not revisit, independent of how many keys the trie holds, and it allocates nothing. Two caveats keep the claim precise. First, every rune of the input is examined once to classify it, so a heavily formatted string costs time proportional to its full length, not just its digit count; the bound is on node hops. Second, O(k) says nothing about memory or insertion: each node spends ten pointer slots regardless of occupancy, and building the trie allocates a node per new digit position, which is exactly what the insertion benchmark measures.
The lesson travels beyond telephony: when keys come from a small fixed alphabet and the question is “longest prefix”, a fixed-fan-out trie returning a bit-packed status answers it more directly, and tells you more, than the map or the scan you would otherwise reach for.