1package trie23// node is a single position in the trie tree4type node struct {5 char byte // node's char, unused in the root node6 value any // node's value, stored when isKey is true7 isKey bool // whether a key terminates at this node8 children []*node // child nodes, kept sorted ascending by char9}1011// childIndex returns the index of the child reached by byte c and whether such12// a child exists. When it does not exist, the returned index is the position at13// which a child with byte c must be inserted to keep children sorted.14func (n *node) childIndex(c byte) (int, bool) {15 lo := 016 hi := len(n.children)17 for lo < hi {18 mid := (lo + hi) / 21920 switch {21 case n.children[mid].char < c:22 lo = mid + 123 case n.children[mid].char > c:24 hi = mid25 default:26 return mid, true27 }28 }29 return lo, false30}3132// get retrieves the value stored under key in the subtree rooted at n.33func (n *node) get(key string) (value any, exists bool) {34 cur := n35 for i := 0; i < len(key); i++ {36 idx, ok := cur.childIndex(key[i])37 if !ok {38 return nil, false39 }4041 cur = cur.children[idx]42 }4344 if !cur.isKey {45 return nil, false46 }47 return cur.value, true48}4950// set inserts or updates key with value. It returns true when the key already51// existed and its value updated, and false when it was newly inserted.52func (n *node) set(key string, value any) (updated bool) {53 cur := n54 for i := 0; i < len(key); i++ {55 c := key[i]56 idx, ok := cur.childIndex(c)57 if ok {58 cur = cur.children[idx]59 continue60 }6162 child := &node{char: c}63 cur.children = append(cur.children, nil)64 copy(cur.children[idx+1:], cur.children[idx:])65 cur.children[idx] = child66 cur = child67 }6869 if cur.isKey {70 cur.value = value71 return true72 }7374 cur.isKey = true75 cur.value = value76 return false77}7879// remove deletes key from the subtree rooted at n, pruning any nodes that no80// longer terminate a key and have no children. It returns the removed value and81// whether the key was found.82func (n *node) remove(key string) (value any, removed bool) {83 if key == "" {84 if !n.isKey {85 return nil, false86 }8788 value = n.value89 n.isKey = false90 n.value = nil91 return value, true92 }9394 idx, ok := n.childIndex(key[0])95 if !ok {96 return nil, false97 }9899 child := n.children[idx]100 value, removed = child.remove(key[1:])101 if removed && !child.isKey && len(child.children) == 0 {102 n.children = append(n.children[:idx], n.children[idx+1:]...)103 }104 return value, removed105}106107// inorder visits this node (when it terminates a key) and its whole subtree.108// key is the full key spelled from the root to this node. When ascending is109// true keys are produced in lexicographic order, otherwise in reverse. Because110// a key always sorts before any key that extends it, the terminal value is111// emitted before the children when ascending and after them when descending.112// It returns true as soon as cb requests the walk to stop.113func (n *node) inorder(key string, ascending bool, cb func(key string, value any) bool) (stop bool) {114 if ascending {115 if n.isKey && cb(key, n.value) {116 return true117 }118119 for _, c := range n.children {120 if c.inorder(key+string([]byte{c.char}), ascending, cb) {121 return true122 }123 }124 return false125 }126127 for i := len(n.children) - 1; i >= 0; i-- {128 c := n.children[i]129 if c.inorder(key+string([]byte{c.char}), ascending, cb) {130 return true131 }132 }133134 if n.isKey && cb(key, n.value) {135 return true136 }137 return false138}139Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.