18794565666

Committed 24 Oct 2025 11:24PM UTC coverage: 71.139% (+2.6%) from 68.56%

Build # 18794565666

Build Type

push

github

Committed by

ghettovoice

Commit Message

Memory allocation optimizations

- disable by default error wrapping and provide methods to enable it;
- new method to check node cache stats;
- minor fixes and refactoring.

Run Details

88 of 113 new or added lines in 3 files covered. (77.88%)

2 existing lines in 2 files now uncovered.

1612 of 2266 relevant lines covered (71.14%)

54.67 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

63.56

/node.go

package abnf

import (
        "bytes"
        "encoding/binary"
        "hash"
        "hash/fnv"
        "sync"
        "sync/atomic"
        "unsafe"

        lru "github.com/hashicorp/golang-lru/v2"
)

// Node represents a single node in a tree generated by [Operator].
type Node struct {
        Key      string
        Pos      uint
        Value    []byte
        Children Nodes
}

// String returns the node's value as string.
func (n *Node) String() string {
        if n == nil {
                return ""
        }
        return string(n.Value)
}

// Len returns length of the node's value.
func (n *Node) Len() int {
        if n == nil {
                return 0
        }
        return len(n.Value)
}

// IsEmpty returns true if the node's value length = 0.
func (n *Node) IsEmpty() bool { return n == nil || len(n.Value) == 0 }

// Contains returns whether the subtree contains the given key.
func (n *Node) Contains(key string) bool {
        if n == nil {
                return false
        }
        _, ok := n.GetNode(key)
        return ok
}

// GetNode recursively searches a node with the given key starting from itself.
// Returns found node or nil if not found.
func (n *Node) GetNode(key string) (*Node, bool) {
        if n == nil {
                return nil, false
        }
        if n.Key == key {
                return n, true
        }
        return n.Children.Get(key)
}

// GetNodes recursively searches all nodes with the given key starting from itself.
func (n *Node) GetNodes(key string) Nodes {
        if n == nil {
                return nil
        }

        var ns Nodes
        if n.Key == key {
                ns = append(ns, n)
        }
        ns = append(ns, n.Children.AllByKey(key)...)
        return ns
}

// Compare compares node values via [bytes.Compare].
// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
func (n *Node) Compare(other *Node) int {
        if n == other {
                return 0
        } else if n == nil {
                return -1
        } else if other == nil {
                return 1
        }
        return bytes.Compare(n.Value, other.Value)
}

var (
        nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]
        cacheHit,
        cacheMiss atomic.Uint64
)

// EnableNodeCache initializes the node cache.
// If size is 0, it will be set to 1024.
// By default, the cache is disabled.
// It does nothing if the cache is already enabled.
// Call this function before using any [Operator], usually in the [init].
func EnableNodeCache(size uint) {
        if nodeCache.Load() != nil {
                return
        }

        if size == 0 {
                size = 1024
        }

        cache, _ := lru.New[uint64, *Node](int(size))
        nodeCache.Store(cache)
}

// ResizeNodeCache resizes the node cache.
// If size is 0, it will be set to 1024.
// It does nothing if the cache is disabled.
// It is safe to call this function from multiple goroutines.
func ResizeNodeCache(size uint) {
        if size == 0 {
                size = 1024
        }

        if cache := nodeCache.Load(); cache != nil {
                cache.Resize(int(size))
        }
}

// DisableNodeCache disables the node cache and purges all cached nodes.
// It does nothing if the cache is already disabled.
// It is safe to call this function from multiple goroutines.
func DisableNodeCache() {
        if cache := nodeCache.Swap(nil); cache != nil {
                cache.Purge()
                cacheHit.Store(0)
                cacheMiss.Store(0)
        }
}

func NodeCacheStats() struct{ hit, miss, size uint64 } {
        var size uint64
        if cache := nodeCache.Load(); cache != nil {
                size = uint64(cache.Len())
        }
        return struct{ hit, miss, size uint64 }{cacheHit.Load(), cacheMiss.Load(), size}
}

type nodeCacheKey struct {
        hash.Hash64
        buf [8]byte
}

var nodeCacheKeyPool = sync.Pool{
        New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },
}

func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...*Node) *nodeCacheKey {
        ck := nodeCacheKeyPool.Get().(*nodeCacheKey)
        ck.writeBase(key, pos, len, input)
        ck.writeChildKeys(0, ns...)
        return ck
}

func (ck *nodeCacheKey) free() {
        if ck == nil {
                return
        }

        ck.Reset()
        nodeCacheKeyPool.Put(ck)
}

func (ck *nodeCacheKey) writeBase(key string, pos, length uint, input []byte) {
        ck.Write(unsafeStringToBytes(key))

        binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))
        ck.Write(ck.buf[:])

        binary.BigEndian.PutUint64(ck.buf[:], uint64(length))
        ck.Write(ck.buf[:])

        if len(input) == 0 || length == 0 {
                return
        }

        start := int(pos)
        if start >= len(input) {
                return
        }
        end := min(start+int(length), len(input))
        ck.Write(input[start:end])
}

func (ck *nodeCacheKey) writeChildKeys(depth uint, ns ...*Node) {
        for _, n := range ns {
                binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))
                ck.Write(ck.buf[:])
                ck.Write(unsafeStringToBytes(n.Key))
                ck.writeChildKeys(depth+1, n.Children...)
        }
}

func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }

// unsafeStringToBytes converts string to []byte without allocation
// WARNING: The returned byte slice must not be modified
func unsafeStringToBytes(s string) []byte {
        return *(*[]byte)(unsafe.Pointer(&struct {
                string
                int
        }{s, len(s)}))
}

func loadNode(k *nodeCacheKey) (*Node, bool) {
        cache := nodeCache.Load()
        if cache == nil {
                return nil, false
        }

        n, ok := cache.Get(k.hash())
        if !ok {
                cacheMiss.Add(1)
                return nil, false
        }
        cacheHit.Add(1)
        return n, true
}

func storeNode(k *nodeCacheKey, n *Node) {
        cache := nodeCache.Load()
        if cache == nil {
                return
        }

        cache.Add(k.hash(), n)
}

func loadOrStoreNode(k *nodeCacheKey, newNode func() *Node) *Node {
        defer k.free()

        cache := nodeCache.Load()
        if cache == nil {
                return newNode()
        }

        if n, ok := loadNode(k); ok {
                return n
        }

        n := newNode()
        storeNode(k, n)
        return n
}

// Nodes represents a list of nodes.
type Nodes []*Node

func (ns *Nodes) Len() int {
        if ns == nil {
                return 0
        }
        return len(*ns)
}

// Contains returns whether the subtree contains the given key.
func (ns *Nodes) Contains(key string) bool {
        if ns == nil {
                return false
        }

        for _, n := range *ns {
                if n.Key == key || n.Children.Contains(key) {
                        return true
                }
        }
        return false
}

// Get recursively searches a node with the given key.
func (ns *Nodes) Get(key string) (*Node, bool) {
        if ns == nil {
                return nil, false
        }

        for _, n := range *ns {
                if n.Key == key {
                        return n, true
                }
                if n, ok := n.Children.Get(key); ok {
                        return n, true
                }
        }
        return nil, false
}

// All returns all nodes in the list.
func (ns *Nodes) All() Nodes {
        if ns == nil {
                return nil
        }
        return *ns
}

// GetAll recursively searches all nodes with the given key.
func (ns *Nodes) AllByKey(key string) Nodes {
        if ns == nil {
                return nil
        }

        var nodes Nodes
        for _, n := range *ns {
                if n.Key == key {
                        nodes = append(nodes, n)
                }
                nodes = append(nodes, n.Children.AllByKey(key)...)
        }
        return nodes
}

// Best returns a node with the longest value or nil if the list is empty.
func (ns *Nodes) Best() *Node {
        if ns == nil || len(*ns) == 0 {
                return nil
        }

        best := (*ns)[0]
        for _, n := range (*ns)[1:] {
                if n.Len() > best.Len() {
                        best = n
                }
        }
        return best
}

// Compare compares two best nodes.
// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
func (ns *Nodes) Compare(other *Nodes) int {
        if ns == nil || other == nil {
                return 0
        }
        return ns.Best().Compare(other.Best())
}

func (ns *Nodes) Append(n ...*Node) {
        *ns = append(*ns, n...)
}

// NodesCap is a initial capacity of a new nodes list.
var NodesCap = 10

var nodesPool = &sync.Pool{
        New: func() any {
                ns := make(Nodes, 0, NodesCap)
                return &ns
        },
}

// NewNodes returns a new nodes list from the pool.
func NewNodes() *Nodes {
        return nodesPool.Get().(*Nodes)
}

// Clear clears the nodes list.
func (ns *Nodes) Clear() {
        if ns == nil {
                return
        }

        clear(*ns)
        *ns = (*ns)[:0]
}

// Free returns the nodes list to the pool.
func (ns *Nodes) Free() {
        ns.Clear()

        if ns == nil || cap(*ns) == 0 || cap(*ns) > 10*NodesCap {
                return
        }

        nodesPool.Put(ns)
}

type nodesSorter Nodes

func (ns *nodesSorter) Len() int { return len(*ns) }

func (ns *nodesSorter) Less(i, j int) bool {
        return len((*ns)[i].Value) > len((*ns)[j].Value) ||
                len((*ns)[i].Children) > len((*ns)[j].Children) ||
                (*ns)[i].Pos < (*ns)[j].Pos ||
                (*ns)[i].Key < (*ns)[j].Key
}

func (ns *nodesSorter) Swap(i, j int) { (*ns)[i], (*ns)[j] = (*ns)[j], (*ns)[i] }

1	package abnf
2
3	import (
4	"bytes"
5	"encoding/binary"
6	"hash"
7	"hash/fnv"
8	"sync"
9	"sync/atomic"
10	"unsafe"
11
12	lru "github.com/hashicorp/golang-lru/v2"
13	)
14
15	// Node represents a single node in a tree generated by [Operator].
16	type Node struct {
17	Key string
18	Pos uint
19	Value []byte
20	Children Nodes
21	}
22
23	// String returns the node's value as string.
24	func (n *Node) String() string {	3✔
25	if n == nil {	3✔
26	return ""	×
27	}	×
28	return string(n.Value)	3✔
29	}
30
31	// Len returns length of the node's value.
32	func (n *Node) Len() int {	48✔
33	if n == nil {	48✔
34	return 0	×
35	}	×
36	return len(n.Value)	48✔
37	}
38
39	// IsEmpty returns true if the node's value length = 0.
40	func (n *Node) IsEmpty() bool { return n == nil \|\| len(n.Value) == 0 }	×
41
42	// Contains returns whether the subtree contains the given key.
43	func (n *Node) Contains(key string) bool {	×
44	if n == nil {	×
45	return false	×
46	}	×
47	_, ok := n.GetNode(key)	×
48	return ok	×
49	}
50
51	// GetNode recursively searches a node with the given key starting from itself.
52	// Returns found node or nil if not found.
53	func (n Node) GetNode(key string) (Node, bool) {	3✔
54	if n == nil {	3✔
55	return nil, false	×
56	}	×
57	if n.Key == key {	4✔
58	return n, true	1✔
59	}	1✔
60	return n.Children.Get(key)	2✔
61	}
62
63	// GetNodes recursively searches all nodes with the given key starting from itself.
64	func (n *Node) GetNodes(key string) Nodes {	×
65	if n == nil {	×
66	return nil	×
67	}	×
68
69	var ns Nodes	×
70	if n.Key == key {	×
71	ns = append(ns, n)	×
72	}	×
73	ns = append(ns, n.Children.AllByKey(key)...)	×
74	return ns	×
75	}
76
77	// Compare compares node values via [bytes.Compare].
78	// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
79	func (n Node) Compare(other Node) int {	35✔
80	if n == other {	35✔
81	return 0	×
82	} else if n == nil {	35✔
83	return -1	×
84	} else if other == nil {	35✔
85	return 1	×
86	}	×
87	return bytes.Compare(n.Value, other.Value)	35✔
88	}
89
90	var (
91	nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]
92	cacheHit,
93	cacheMiss atomic.Uint64
94	)
95
96	// EnableNodeCache initializes the node cache.
97	// If size is 0, it will be set to 1024.
98	// By default, the cache is disabled.
99	// It does nothing if the cache is already enabled.
100	// Call this function before using any [Operator], usually in the [init].
101	func EnableNodeCache(size uint) {	1✔
102	if nodeCache.Load() != nil {	1✔
103	return	×
104	}	×
105
106	if size == 0 {	2✔
107	size = 1024	1✔
108	}	1✔
109
110	cache, _ := lru.New[uint64, *Node](int(size))	1✔
111	nodeCache.Store(cache)	1✔
112	}
113
114	// ResizeNodeCache resizes the node cache.
115	// If size is 0, it will be set to 1024.
116	// It does nothing if the cache is disabled.
117	// It is safe to call this function from multiple goroutines.
118	func ResizeNodeCache(size uint) {	×
119	if size == 0 {	×
120	size = 1024	×
121	}	×
122
123	if cache := nodeCache.Load(); cache != nil {	×
124	cache.Resize(int(size))	×
125	}	×
126	}
127
128	// DisableNodeCache disables the node cache and purges all cached nodes.
129	// It does nothing if the cache is already disabled.
130	// It is safe to call this function from multiple goroutines.
131	func DisableNodeCache() {	1✔
132	if cache := nodeCache.Swap(nil); cache != nil {	2✔
133	cache.Purge()	1✔
134	cacheHit.Store(0)	1✔
135	cacheMiss.Store(0)	1✔
136	}	1✔
137	}
138
NEW 139	func NodeCacheStats() struct{ hit, miss, size uint64 } {	×
NEW 140	var size uint64	×
NEW 141	if cache := nodeCache.Load(); cache != nil {	×
NEW 142	size = uint64(cache.Len())	×
UNCOV 143	}	×
NEW 144	return struct{ hit, miss, size uint64 }{cacheHit.Load(), cacheMiss.Load(), size}	×
145	}
146
147	type nodeCacheKey struct {
148	hash.Hash64
149	buf [8]byte
150	}
151
152	var nodeCacheKeyPool = sync.Pool{
153	New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },	54✔
154	}
155
156	func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...Node) nodeCacheKey {	285✔
157	ck := nodeCacheKeyPool.Get().(*nodeCacheKey)	285✔
158	ck.writeBase(key, pos, len, input)	285✔
159	ck.writeChildKeys(0, ns...)	285✔
160	return ck	285✔
161	}	285✔
162
163	func (ck *nodeCacheKey) free() {	285✔
164	if ck == nil {	285✔
165	return	×
166	}	×
167
168	ck.Reset()	285✔
169	nodeCacheKeyPool.Put(ck)	285✔
170	}
171
172	func (ck *nodeCacheKey) writeBase(key string, pos, length uint, input []byte) {	285✔
173	ck.Write(unsafeStringToBytes(key))	285✔
174		285✔
175	binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))	285✔
176	ck.Write(ck.buf[:])	285✔
177		285✔
178	binary.BigEndian.PutUint64(ck.buf[:], uint64(length))	285✔
179	ck.Write(ck.buf[:])	285✔
180		285✔
181	if len(input) == 0 \|\| length == 0 {	359✔
182	return	74✔
183	}	74✔
184
185	start := int(pos)	211✔
186	if start >= len(input) {	211✔
187	return	×
188	}	×
189	end := min(start+int(length), len(input))	211✔
190	ck.Write(input[start:end])	211✔
191	}
192
193	func (ck nodeCacheKey) writeChildKeys(depth uint, ns ...Node) {	727✔
194	for _, n := range ns {	1,046✔
195	binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))	319✔
196	ck.Write(ck.buf[:])	319✔
197	ck.Write(unsafeStringToBytes(n.Key))	319✔
198	ck.writeChildKeys(depth+1, n.Children...)	319✔
199	}	319✔
200	}
201
202	func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }	43✔
203
204	// unsafeStringToBytes converts string to []byte without allocation
205	// WARNING: The returned byte slice must not be modified
206	func unsafeStringToBytes(s string) []byte {	604✔
207	return ([]byte)(unsafe.Pointer(&struct {	604✔
208	string	604✔
209	int	604✔
210	}{s, len(s)}))	604✔
211	}	604✔
212
213	func loadNode(k nodeCacheKey) (Node, bool) {	30✔
214	cache := nodeCache.Load()	30✔
215	if cache == nil {	30✔
216	return nil, false	×
217	}	×
218
219	n, ok := cache.Get(k.hash())	30✔
220	if !ok {	43✔
221	cacheMiss.Add(1)	13✔
222	return nil, false	13✔
223	}	13✔
224	cacheHit.Add(1)	17✔
225	return n, true	17✔
226	}
227
228	func storeNode(k nodeCacheKey, n Node) {	13✔
229	cache := nodeCache.Load()	13✔
230	if cache == nil {	13✔
231	return	×
232	}	×
233
234	cache.Add(k.hash(), n)	13✔
235	}
236
237	func loadOrStoreNode(k nodeCacheKey, newNode func() Node) *Node {	285✔
238	defer k.free()	285✔
239		285✔
240	cache := nodeCache.Load()	285✔
241	if cache == nil {	540✔
242	return newNode()	255✔
243	}	255✔
244
245	if n, ok := loadNode(k); ok {	47✔
246	return n	17✔
247	}	17✔
248
249	n := newNode()	13✔
250	storeNode(k, n)	13✔
251	return n	13✔
252	}
253
254	// Nodes represents a list of nodes.
255	type Nodes []*Node
256
257	func (ns *Nodes) Len() int {	225✔
258	if ns == nil {	225✔
259	return 0	×
260	}	×
261	return len(*ns)	225✔
262	}
263
264	// Contains returns whether the subtree contains the given key.
265	func (ns *Nodes) Contains(key string) bool {	×
266	if ns == nil {	×
267	return false	×
268	}	×
269
270	for _, n := range *ns {	×
271	if n.Key == key \|\| n.Children.Contains(key) {	×
272	return true	×
273	}	×
274	}
275	return false	×
276	}
277
278	// Get recursively searches a node with the given key.
279	func (ns Nodes) Get(key string) (Node, bool) {	6✔
280	if ns == nil {	6✔
281	return nil, false	×
282	}	×
283
284	for _, n := range *ns {	11✔
285	if n.Key == key {	6✔
286	return n, true	1✔
287	}	1✔
288	if n, ok := n.Children.Get(key); ok {	4✔
289	return n, true	×
290	}	×
291	}
292	return nil, false	5✔
293	}
294
295	// All returns all nodes in the list.
296	func (ns *Nodes) All() Nodes {	357✔
297	if ns == nil {	357✔
298	return nil	×
299	}	×
300	return *ns	357✔
301	}
302
303	// GetAll recursively searches all nodes with the given key.
304	func (ns *Nodes) AllByKey(key string) Nodes {	×
305	if ns == nil {	×
306	return nil	×
307	}	×
308
309	var nodes Nodes	×
310	for _, n := range *ns {	×
311	if n.Key == key {	×
312	nodes = append(nodes, n)	×
313	}	×
314	nodes = append(nodes, n.Children.AllByKey(key)...)	×
315	}
316	return nodes	×
317	}
318
319	// Best returns a node with the longest value or nil if the list is empty.
320	func (ns Nodes) Best() Node {	81✔
321	if ns == nil \|\| len(*ns) == 0 {	81✔
322	return nil	×
323	}	×
324
325	best := (*ns)[0]	81✔
326	for _, n := range (*ns)[1:] {	105✔
327	if n.Len() > best.Len() {	25✔
328	best = n	1✔
329	}	1✔
330	}
331	return best	81✔
332	}
333
334	// Compare compares two best nodes.
335	// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
336	func (ns Nodes) Compare(other Nodes) int {	35✔
337	if ns == nil \|\| other == nil {	35✔
338	return 0	×
339	}	×
340	return ns.Best().Compare(other.Best())	35✔
341	}
342
343	func (ns Nodes) Append(n ...Node) {	423✔
344	ns = append(ns, n...)	423✔
345	}	423✔
346
347	// NodesCap is a initial capacity of a new nodes list.
348	var NodesCap = 10
349
350	var nodesPool = &sync.Pool{
351	New: func() any {	72✔
352	ns := make(Nodes, 0, NodesCap)	72✔
353	return &ns	72✔
354	},	72✔
355	}
356
357	// NewNodes returns a new nodes list from the pool.
358	func NewNodes() *Nodes {	262✔
359	return nodesPool.Get().(*Nodes)	262✔
360	}	262✔
361
362	// Clear clears the nodes list.
363	func (ns *Nodes) Clear() {	593✔
364	if ns == nil {	593✔
365	return	×
366	}	×
367
368	clear(*ns)	593✔
369	ns = (ns)[:0]	593✔
370	}
371
372	// Free returns the nodes list to the pool.
373	func (ns *Nodes) Free() {	262✔
374	ns.Clear()	262✔
375		262✔
376	if ns == nil \|\| cap(ns) == 0 \|\| cap(ns) > 10*NodesCap {	262✔
377	return	×
378	}	×
379
380	nodesPool.Put(ns)	262✔
381	}
382
383	type nodesSorter Nodes
384
385	func (ns nodesSorter) Len() int { return len(ns) }	27✔
386
387	func (ns *nodesSorter) Less(i, j int) bool {	65✔
388	return len((ns)[i].Value) > len((ns)[j].Value) \|\|	65✔
389	len((ns)[i].Children) > len((ns)[j].Children) \|\|	65✔
390	(ns)[i].Pos < (ns)[j].Pos \|\|	65✔
391	(ns)[i].Key < (ns)[j].Key	65✔
392	}	65✔
393
394	func (ns nodesSorter) Swap(i, j int) { (ns)[i], (ns)[j] = (ns)[j], (*ns)[i] }	56✔

ghettovoice / abnf / 18794565666

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous