18681619119

Committed 21 Oct 2025 10:56AM UTC coverage: 70.676% (+1.2%) from 69.501%

Build # 18681619119

Build Type

Pull #52

github

Committed by

ghettovoice

Commit Message

Update README

Pull Request Pull Request #52: Optimize

Run Details

361 of 420 new or added lines in 7 files covered. (85.95%)

27 existing lines in 4 files now uncovered.

1516 of 2145 relevant lines covered (70.68%)

52.11 hits per line

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

63.12

/node.go

package abnf

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

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

var (
        NodesCap      = 100
        NodeCacheSize = 512
)

// 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.New[uint64, *Node](NodeCacheSize)

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...)
}

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

ghettovoice / abnf / 18681619119

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