Debian Codegraph @

hugolib/doctree/simpletree.go

raw
1 // Copyright 2024 The Hugo Authors. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 package doctree
15
16 import (
17 "iter"
18 "sync"
19
20 radix "github.com/gohugoio/go-radix"
21 )
22
23 // Tree is a non thread safe radix tree that holds T.
24 type Tree[T any] interface {
25 TreeCommon[T]
26 WalkPrefix(s string, f func(s string, v T) (bool, error)) error
27 WalkPath(s string, f func(s string, v T) (bool, error)) error
28 All() iter.Seq2[string, T]
29 }
30
31 // TreeThreadSafe is a thread safe radix tree that holds T.
32 type TreeThreadSafe[T any] interface {
33 TreeCommon[T]
34 WalkPrefix(lockType LockType, s string, f func(s string, v T) (bool, error)) error
35 WalkPath(lockType LockType, s string, f func(s string, v T) (bool, error)) error
36 All(lockType LockType) iter.Seq2[string, T]
37 }
38
39 type TreeCommon[T any] interface {
40 Get(s string) T
41 LongestPrefix(s string) (string, T)
42 Insert(s string, v T) T
43 }
44
45 func NewSimpleTree[T any]() *SimpleTree[T] {
46 return &SimpleTree[T]{tree: radix.New[T]()}
47 }
48
49 // SimpleTree is a radix tree that holds T.
50 // This tree is not thread safe.
51 type SimpleTree[T any] struct {
52 tree *radix.Tree[T]
53 zero T
54 }
55
56 func (tree *SimpleTree[T]) Get(s string) T {
57 v, _ := tree.tree.Get(s)
58 return v
59 }
60
61 func (tree *SimpleTree[T]) LongestPrefix(s string) (string, T) {
62 s, v, _ := tree.tree.LongestPrefix(s)
63 return s, v
64 }
65
66 func (tree *SimpleTree[T]) Insert(s string, v T) T {
67 tree.tree.Insert(s, v)
68 return v
69 }
70
71 func (tree *SimpleTree[T]) Walk(f func(s string, v T) (bool, error)) error {
72 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
73 var b bool
74 b, err := f(s, v)
75 if b || err != nil {
76 return radix.WalkStop, tree.zero, err
77 }
78 return radix.WalkContinue, tree.zero, nil
79 }
80 return tree.tree.Walk(walkFn)
81 }
82
83 func (tree *SimpleTree[T]) WalkPrefix(s string, f func(s string, v T) (bool, error)) error {
84 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
85 b, err := f(s, v)
86 if b || err != nil {
87 return radix.WalkStop, tree.zero, err
88 }
89 return radix.WalkContinue, tree.zero, nil
90 }
91 return tree.tree.WalkPrefix(s, walkFn)
92 }
93
94 func (tree *SimpleTree[T]) WalkPath(s string, f func(s string, v T) (bool, error)) error {
95 var err error
96 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
97 var b bool
98 b, err = f(s, v)
99 if b || err != nil {
100 return radix.WalkStop, tree.zero, err
101 }
102 return radix.WalkContinue, tree.zero, nil
103 }
104 tree.tree.WalkPath(s, walkFn)
105 return err
106 }
107
108 func (tree *SimpleTree[T]) All() iter.Seq2[string, T] {
109 return func(yield func(s string, v T) bool) {
110 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
111 if !yield(s, v) {
112 return radix.WalkStop, tree.zero, nil
113 }
114 return radix.WalkContinue, tree.zero, nil
115 }
116 tree.tree.Walk(walkFn)
117 }
118 }
119
120 func (tree *SimpleTree[T]) Len() int {
121 return tree.tree.Len()
122 }
123
124 // NewSimpleThreadSafeTree creates a new SimpleTree.
125 func NewSimpleThreadSafeTree[T any]() *SimpleThreadSafeTree[T] {
126 return &SimpleThreadSafeTree[T]{tree: radix.New[T](), mu: new(sync.RWMutex)}
127 }
128
129 // SimpleThreadSafeTree is a thread safe radix tree that holds T.
130 type SimpleThreadSafeTree[T any] struct {
131 mu *sync.RWMutex
132 tree *radix.Tree[T]
133 zero T
134 }
135
136 func (tree *SimpleThreadSafeTree[T]) Get(s string) T {
137 tree.mu.RLock()
138 defer tree.mu.RUnlock()
139 v, _ := tree.tree.Get(s)
140 return v
141 }
142
143 func (tree *SimpleThreadSafeTree[T]) LongestPrefix(s string) (string, T) {
144 tree.mu.RLock()
145 defer tree.mu.RUnlock()
146
147 s, v, _ := tree.tree.LongestPrefix(s)
148 return s, v
149 }
150
151 func (tree *SimpleThreadSafeTree[T]) Insert(s string, v T) T {
152 tree.mu.Lock()
153 defer tree.mu.Unlock()
154
155 tree.tree.Insert(s, v)
156 return v
157 }
158
159 func (tree *SimpleThreadSafeTree[T]) Lock(lockType LockType) {
160 switch lockType {
161 case LockTypeRead:
162 tree.mu.RLock()
163 case LockTypeWrite:
164 tree.mu.Lock()
165 }
166 }
167
168 func (tree *SimpleThreadSafeTree[T]) Unlock(lockType LockType) {
169 switch lockType {
170 case LockTypeRead:
171 tree.mu.RUnlock()
172 case LockTypeWrite:
173 tree.mu.Unlock()
174 }
175 }
176
177 func (tree *SimpleThreadSafeTree[T]) WalkPrefix(lockType LockType, s string, f func(s string, v T) (bool, error)) error {
178 tree.Lock(lockType)
179 defer tree.Unlock(lockType)
180 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
181 var b bool
182 b, err := f(s, v)
183 if b || err != nil {
184 return radix.WalkStop, tree.zero, err
185 }
186 return radix.WalkContinue, tree.zero, nil
187 }
188 return tree.tree.WalkPrefix(s, walkFn)
189 }
190
191 func (tree *SimpleThreadSafeTree[T]) WalkPath(lockType LockType, s string, f func(s string, v T) (bool, error)) error {
192 tree.Lock(lockType)
193 defer tree.Unlock(lockType)
194 var err error
195 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
196 var b bool
197 b, err = f(s, v)
198 if b || err != nil {
199 return radix.WalkStop, tree.zero, err
200 }
201 return radix.WalkContinue, tree.zero, nil
202 }
203 tree.tree.WalkPath(s, walkFn)
204
205 return err
206 }
207
208 func (tree *SimpleThreadSafeTree[T]) All(lockType LockType) iter.Seq2[string, T] {
209 return func(yield func(s string, v T) bool) {
210 tree.Lock(lockType)
211 defer tree.Unlock(lockType)
212 var walkFn radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
213 if !yield(s, v) {
214 return radix.WalkStop, tree.zero, nil
215 }
216 return radix.WalkContinue, tree.zero, nil
217 }
218 tree.tree.Walk(walkFn)
219 }
220 }