18682945889

Committed 21 Oct 2025 11:54AM UTC coverage: 70.692% (+1.2%) from 69.501%

Build # 18682945889

Build Type

Pull #52

github

Committed by

ghettovoice

Commit Message

Provide a glob function to init node cache

Pull Request Pull Request #52: Optimize

Run Details

367 of 428 new or added lines in 7 files covered. (85.75%)

27 existing lines in 4 files now uncovered.

1522 of 2153 relevant lines covered (70.69%)

52.18 hits per line

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

63.76

/node.go

package abnf

import (
        "bytes"
        "hash/fnv"
        "strconv"
        "sync"

        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.GetAll(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 *lru.Cache[uint64, *Node]

// InitNodeCache initializes the node cache.
// If size is 0, it will be set to 512.
// Call this function before using any [Operator], usually in the [init].
func InitNodeCache(size uint) {
        if size == 0 {
                size = 512
        }
        nodeCache, _ = lru.New[uint64, *Node](int(size))
}

func init() {
        InitNodeCache(512)
}

type nodeCacheKey struct {
        key   string
        pos   uint
        len   uint
        input []byte
        child []byte
}

func (key *nodeCacheKey) hash() uint64 {
        h := fnv.New64a()
        h.Write([]byte(key.key))
        h.Write([]byte(strconv.FormatUint(uint64(key.pos), 10)))
        h.Write([]byte(strconv.FormatUint(uint64(key.len), 10)))
        h.Write(key.input)
        h.Write(key.child)
        return h.Sum64()
}

func hashKeys(nn *Nodes) []byte {
        h := fnv.New64a()
        for _, n := range *nn {
                h.Write([]byte(n.Key))
                h.Write(hashKeys(&n.Children))
        }
        return h.Sum(nil)
}

func hashString(s []byte) []byte {
        h := fnv.New64a()
        h.Write(s)
        return h.Sum(nil)
}

func loadNode(k nodeCacheKey) (*Node, bool) {
        n, ok := nodeCache.Get(k.hash())
        if !ok {
                return nil, false
        }
        return n, true
}

func storeNode(k nodeCacheKey, n *Node) {
        nodeCache.Add(k.hash(), n)
}

func loadOrStoreNode(k nodeCacheKey, newNode func() *Node) *Node {
        if n, ok := loadNode(k); ok {
                return n
        }

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

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

// Contains returns whether the subtree contains the given key.
func (ns Nodes) Contains(key string) bool {
        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) {
        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
}

// GetAll recursively searches all nodes with the given key.
func (ns Nodes) GetAll(key string) Nodes {
        var nodes Nodes
        for _, n := range ns {
                if n.Key == key {
                        nodes = append(nodes, n)
                }
                nodes = append(nodes, n.Children.GetAll(key)...)
        }
        return nodes
}

// Best returns a node with the longest value or nil if the list is empty.
func (ns Nodes) Best() *Node {
        if 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 {
        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 = 100

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

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

// 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) > 2*NodesCap {
                return
        }

        nsPool.Put(ns)
}

1	package abnf
2
3	import (
4	"bytes"
5	"hash/fnv"
6	"strconv"
7	"sync"
8
9	lru "github.com/hashicorp/golang-lru/v2"
10	)
11
12	// Node represents a single node in a tree generated by [Operator].
13	type Node struct {
14	Key string
15	Pos uint
16	Value []byte
17	Children Nodes
18	}
19
20	// String returns the node's value as string.
21	func (n *Node) String() string {	×
22	if n == nil {	×
23	return ""	×
24	}	×
25	return string(n.Value)	×
26	}
27
28	// Len returns length of the node's value.
29	func (n *Node) Len() int {	42✔
30	if n == nil {	42✔
31	return 0	×
32	}	×
33	return len(n.Value)	42✔
34	}
35
36	// IsEmpty returns true if the node's value length = 0.
37	func (n *Node) IsEmpty() bool { return n == nil \|\| len(n.Value) == 0 }	×
38
39	// Contains returns whether the subtree contains the given key.
40	func (n *Node) Contains(key string) bool {	×
41	if n == nil {	×
42	return false	×
43	}	×
NEW 44	_, ok := n.GetNode(key)	×
NEW 45	return ok	×
46	}
47
48	// GetNode recursively searches a node with the given key starting from itself.
49	// Returns found node or nil if not found.
50	func (n Node) GetNode(key string) (Node, bool) {	3✔
51	if n == nil {	3✔
NEW 52	return nil, false	×
NEW 53	}	×
54	if n.Key == key {	4✔
55	return n, true	1✔
56	}	1✔
57	return n.Children.Get(key)	2✔
58	}
59
60	// GetNodes recursively searches all nodes with the given key starting from itself.
61	func (n *Node) GetNodes(key string) Nodes {	×
62	if n == nil {	×
63	return nil	×
64	}	×
65
66	var ns Nodes	×
67	if n.Key == key {	×
68	ns = append(ns, n)	×
69	}	×
70	ns = append(ns, n.Children.GetAll(key)...)	×
71	return ns	×
72	}
73
74	// Compare compares node values via [bytes.Compare].
75	// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
76	func (n Node) Compare(other Node) int {	32✔
77	if n == other {	32✔
78	return 0	×
79	} else if n == nil {	32✔
80	return -1	×
81	} else if other == nil {	32✔
82	return 1	×
83	}	×
84	return bytes.Compare(n.Value, other.Value)	32✔
85	}
86
87	var nodeCache lru.Cache[uint64, Node]
88
89	// InitNodeCache initializes the node cache.
90	// If size is 0, it will be set to 512.
91	// Call this function before using any [Operator], usually in the [init].
92	func InitNodeCache(size uint) {	1✔
93	if size == 0 {	1✔
NEW 94	size = 512	×
NEW 95	}	×
96	nodeCache, _ = lru.New[uint64, *Node](int(size))	1✔
97	}
98
99	func init() {	1✔
100	InitNodeCache(512)	1✔
101	}	1✔
102
103	type nodeCacheKey struct {
104	key string
105	pos uint
106	len uint
107	input []byte
108	child []byte
109	}
110
111	func (key *nodeCacheKey) hash() uint64 {	396✔
112	h := fnv.New64a()	396✔
113	h.Write([]byte(key.key))	396✔
114	h.Write([]byte(strconv.FormatUint(uint64(key.pos), 10)))	396✔
115	h.Write([]byte(strconv.FormatUint(uint64(key.len), 10)))	396✔
116	h.Write(key.input)	396✔
117	h.Write(key.child)	396✔
118	return h.Sum64()	396✔
119	}	396✔
120
121	func hashKeys(nn *Nodes) []byte {	204✔
122	h := fnv.New64a()	204✔
123	for _, n := range *nn {	303✔
124	h.Write([]byte(n.Key))	99✔
125	h.Write(hashKeys(&n.Children))	99✔
126	}	99✔
127	return h.Sum(nil)	204✔
128	}
129
130	func hashString(s []byte) []byte {	123✔
131	h := fnv.New64a()	123✔
132	h.Write(s)	123✔
133	return h.Sum(nil)	123✔
134	}	123✔
135
136	func loadNode(k nodeCacheKey) (*Node, bool) {	246✔
137	n, ok := nodeCache.Get(k.hash())	246✔
138	if !ok {	396✔
139	return nil, false	150✔
140	}	150✔
141	return n, true	96✔
142	}
143
144	func storeNode(k nodeCacheKey, n *Node) {	150✔
145	nodeCache.Add(k.hash(), n)	150✔
146	}	150✔
147
148	func loadOrStoreNode(k nodeCacheKey, newNode func() Node) Node {	246✔
149	if n, ok := loadNode(k); ok {	342✔
150	return n	96✔
151	}	96✔
152
153	n := newNode()	150✔
154	storeNode(k, n)	150✔
155	return n	150✔
156	}
157
158	// Nodes represents a list of nodes.
159	type Nodes []*Node
160
161	// Contains returns whether the subtree contains the given key.
162	func (ns Nodes) Contains(key string) bool {	×
163	for _, n := range ns {	×
164	if n.Key == key \|\| n.Children.Contains(key) {	×
165	return true	×
166	}	×
167	}
168	return false	×
169	}
170
171	// Get recursively searches a node with the given key.
172	func (ns Nodes) Get(key string) (*Node, bool) {	6✔
173	for _, n := range ns {	11✔
174	if n.Key == key {	6✔
175	return n, true	1✔
176	}	1✔
177	if n, ok := n.Children.Get(key); ok {	4✔
NEW 178	return n, true	×
UNCOV 179	}	×
180	}
181	return nil, false	5✔
182	}
183
184	// GetAll recursively searches all nodes with the given key.
185	func (ns Nodes) GetAll(key string) Nodes {	×
186	var nodes Nodes	×
187	for _, n := range ns {	×
188	if n.Key == key {	×
189	nodes = append(nodes, n)	×
190	}	×
191	nodes = append(nodes, n.Children.GetAll(key)...)	×
192	}
193	return nodes	×
194	}
195
196	// Best returns a node with the longest value or nil if the list is empty.
197	func (ns Nodes) Best() *Node {	70✔
198	if len(ns) == 0 {	70✔
199	return nil	×
200	}	×
201
202	best := ns[0]	70✔
203	for _, n := range ns[1:] {	91✔
204	if n.Len() > best.Len() {	22✔
205	best = n	1✔
206	}	1✔
207	}
208	return best	70✔
209	}
210
211	// Compare compares two best nodes.
212	// 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.
213	func (ns Nodes) Compare(other Nodes) int {	32✔
214	return ns.Best().Compare(other.Best())	32✔
215	}	32✔
216
217	func (ns Nodes) Append(n ...Node) {	440✔
218	ns = append(ns, n...)	440✔
219	}	440✔
220
221	// NodesCap is a initial capacity of a new nodes list.
222	var NodesCap = 100
223
224	var nsPool = &sync.Pool{
225	New: func() any {	111✔
226	ns := make(Nodes, 0, NodesCap)	111✔
227	return &ns	111✔
228	},	111✔
229	}
230
231	// NewNodes returns a new nodes list from the pool.
232	func NewNodes() Nodes {	335✔
233	ns := nsPool.Get().(*Nodes)	335✔
234	return *ns	335✔
235	}	335✔
236
237	// Clear clears the nodes list.
238	func (ns *Nodes) Clear() {	581✔
239	if ns == nil {	581✔
NEW 240	return	×
NEW 241	}	×
242
243	clear(*ns)	581✔
244	ns = (ns)[:0]	581✔
245	}
246
247	// Free returns the nodes list to the pool.
248	func (ns *Nodes) Free() {	228✔
249	ns.Clear()	228✔
250		228✔
251	if ns == nil \|\| cap(ns) == 0 \|\| cap(ns) > 2*NodesCap {	228✔
252	return	×
253	}	×
254
255	nsPool.Put(ns)	228✔
256	}

ghettovoice / abnf / 18682945889

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