buffer.go raw
1 /**
2 * Copyright 2023 ByteDance Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package ast
18
19 import (
20 "sort"
21 "unsafe"
22
23 "github.com/bytedance/sonic/internal/caching"
24 )
25
26 type nodeChunk [_DEFAULT_NODE_CAP]Node
27
28 type linkedNodes struct {
29 head nodeChunk
30 tail []*nodeChunk
31 size int
32 }
33
34 func (self *linkedNodes) Cap() int {
35 if self == nil {
36 return 0
37 }
38 return (len(self.tail)+1)*_DEFAULT_NODE_CAP
39 }
40
41 func (self *linkedNodes) Len() int {
42 if self == nil {
43 return 0
44 }
45 return self.size
46 }
47
48 func (self *linkedNodes) At(i int) (*Node) {
49 if self == nil {
50 return nil
51 }
52 if i >= 0 && i<self.size && i < _DEFAULT_NODE_CAP {
53 return &self.head[i]
54 } else if i >= _DEFAULT_NODE_CAP && i<self.size {
55 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
56 if a < len(self.tail) {
57 return &self.tail[a][b]
58 }
59 }
60 return nil
61 }
62
63 func (self *linkedNodes) MoveOne(source int, target int) {
64 if source == target {
65 return
66 }
67 if source < 0 || source >= self.size || target < 0 || target >= self.size {
68 return
69 }
70 // reserve source
71 n := *self.At(source)
72 if source < target {
73 // move every element (source,target] one step back
74 for i:=source; i<target; i++ {
75 *self.At(i) = *self.At(i+1)
76 }
77 } else {
78 // move every element [target,source) one step forward
79 for i:=source; i>target; i-- {
80 *self.At(i) = *self.At(i-1)
81 }
82 }
83 // set target
84 *self.At(target) = n
85 }
86
87 func (self *linkedNodes) Pop() {
88 if self == nil || self.size == 0 {
89 return
90 }
91 self.Set(self.size-1, Node{})
92 self.size--
93 }
94
95 func (self *linkedNodes) Push(v Node) {
96 self.Set(self.size, v)
97 }
98
99
100 func (self *linkedNodes) Set(i int, v Node) {
101 if i < _DEFAULT_NODE_CAP {
102 self.head[i] = v
103 if self.size <= i {
104 self.size = i+1
105 }
106 return
107 }
108 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
109 if a < 0 {
110 self.head[b] = v
111 } else {
112 self.growTailLength(a+1)
113 var n = &self.tail[a]
114 if *n == nil {
115 *n = new(nodeChunk)
116 }
117 (*n)[b] = v
118 }
119 if self.size <= i {
120 self.size = i+1
121 }
122 }
123
124 func (self *linkedNodes) growTailLength(l int) {
125 if l <= len(self.tail) {
126 return
127 }
128 c := cap(self.tail)
129 for c < l {
130 c += 1 + c>>_APPEND_GROW_SHIFT
131 }
132 if c == cap(self.tail) {
133 self.tail = self.tail[:l]
134 return
135 }
136 tmp := make([]*nodeChunk, l, c)
137 copy(tmp, self.tail)
138 self.tail = tmp
139 }
140
141 func (self *linkedNodes) ToSlice(con []Node) {
142 if len(con) < self.size {
143 return
144 }
145 i := (self.size-1)
146 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
147 if a < 0 {
148 copy(con, self.head[:b+1])
149 return
150 } else {
151 copy(con, self.head[:])
152 con = con[_DEFAULT_NODE_CAP:]
153 }
154
155 for i:=0; i<a; i++ {
156 copy(con, self.tail[i][:])
157 con = con[_DEFAULT_NODE_CAP:]
158 }
159 copy(con, self.tail[a][:b+1])
160 }
161
162 func (self *linkedNodes) FromSlice(con []Node) {
163 self.size = len(con)
164 i := self.size-1
165 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
166 if a < 0 {
167 copy(self.head[:b+1], con)
168 return
169 } else {
170 copy(self.head[:], con)
171 con = con[_DEFAULT_NODE_CAP:]
172 }
173
174 if cap(self.tail) <= a {
175 c := (a+1) + (a+1)>>_APPEND_GROW_SHIFT
176 self.tail = make([]*nodeChunk, a+1, c)
177 }
178 self.tail = self.tail[:a+1]
179
180 for i:=0; i<a; i++ {
181 self.tail[i] = new(nodeChunk)
182 copy(self.tail[i][:], con)
183 con = con[_DEFAULT_NODE_CAP:]
184 }
185
186 self.tail[a] = new(nodeChunk)
187 copy(self.tail[a][:b+1], con)
188 }
189
190 type pairChunk [_DEFAULT_NODE_CAP]Pair
191
192 type linkedPairs struct {
193 index map[uint64]int
194 head pairChunk
195 tail []*pairChunk
196 size int
197 }
198
199 func (self *linkedPairs) BuildIndex() {
200 if self.index == nil {
201 self.index = make(map[uint64]int, self.size)
202 }
203 for i:=0; i<self.size; i++ {
204 p := self.At(i)
205 self.index[p.hash] = i
206 }
207 }
208
209 func (self *linkedPairs) Cap() int {
210 if self == nil {
211 return 0
212 }
213 return (len(self.tail)+1)*_DEFAULT_NODE_CAP
214 }
215
216 func (self *linkedPairs) Len() int {
217 if self == nil {
218 return 0
219 }
220 return self.size
221 }
222
223 func (self *linkedPairs) At(i int) *Pair {
224 if self == nil {
225 return nil
226 }
227 if i >= 0 && i < _DEFAULT_NODE_CAP && i<self.size {
228 return &self.head[i]
229 } else if i >= _DEFAULT_NODE_CAP && i<self.size {
230 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
231 if a < len(self.tail) {
232 return &self.tail[a][b]
233 }
234 }
235 return nil
236 }
237
238 func (self *linkedPairs) Push(v Pair) {
239 self.Set(self.size, v)
240 }
241
242 func (self *linkedPairs) Pop() {
243 if self == nil || self.size == 0 {
244 return
245 }
246 self.Unset(self.size-1)
247 self.size--
248 }
249
250 func (self *linkedPairs) Unset(i int) {
251 if self.index != nil {
252 p := self.At(i)
253 delete(self.index, p.hash)
254 }
255 self.set(i, Pair{})
256 }
257
258 func (self *linkedPairs) Set(i int, v Pair) {
259 if self.index != nil {
260 h := v.hash
261 self.index[h] = i
262 }
263 self.set(i, v)
264 }
265
266 func (self *linkedPairs) set(i int, v Pair) {
267 if i < _DEFAULT_NODE_CAP {
268 self.head[i] = v
269 if self.size <= i {
270 self.size = i+1
271 }
272 return
273 }
274 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
275 if a < 0 {
276 self.head[b] = v
277 } else {
278 self.growTailLength(a+1)
279 var n = &self.tail[a]
280 if *n == nil {
281 *n = new(pairChunk)
282 }
283 (*n)[b] = v
284 }
285 if self.size <= i {
286 self.size = i+1
287 }
288 }
289
290 func (self *linkedPairs) growTailLength(l int) {
291 if l <= len(self.tail) {
292 return
293 }
294 c := cap(self.tail)
295 for c < l {
296 c += 1 + c>>_APPEND_GROW_SHIFT
297 }
298 if c == cap(self.tail) {
299 self.tail = self.tail[:l]
300 return
301 }
302 tmp := make([]*pairChunk, l, c)
303 copy(tmp, self.tail)
304 self.tail = tmp
305 }
306
307 // linear search
308 func (self *linkedPairs) Get(key string) (*Pair, int) {
309 if self.index != nil {
310 // fast-path
311 i, ok := self.index[caching.StrHash(key)]
312 if ok {
313 n := self.At(i)
314 if n.Key == key {
315 return n, i
316 }
317 // hash conflicts
318 goto linear_search
319 } else {
320 return nil, -1
321 }
322 }
323 linear_search:
324 for i:=0; i<self.size; i++ {
325 if n := self.At(i); n.Key == key {
326 return n, i
327 }
328 }
329 return nil, -1
330 }
331
332 func (self *linkedPairs) ToSlice(con []Pair) {
333 if len(con) < self.size {
334 return
335 }
336 i := self.size-1
337 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
338
339 if a < 0 {
340 copy(con, self.head[:b+1])
341 return
342 } else {
343 copy(con, self.head[:])
344 con = con[_DEFAULT_NODE_CAP:]
345 }
346
347 for i:=0; i<a; i++ {
348 copy(con, self.tail[i][:])
349 con = con[_DEFAULT_NODE_CAP:]
350 }
351 copy(con, self.tail[a][:b+1])
352 }
353
354 func (self *linkedPairs) ToMap(con map[string]Node) {
355 for i:=0; i<self.size; i++ {
356 n := self.At(i)
357 con[n.Key] = n.Value
358 }
359 }
360
361 func (self *linkedPairs) copyPairs(to []Pair, from []Pair, l int) {
362 copy(to, from)
363 if self.index != nil {
364 for i:=0; i<l; i++ {
365 // NOTICE: in case of user not pass hash, just cal it
366 h := caching.StrHash(from[i].Key)
367 from[i].hash = h
368 self.index[h] = i
369 }
370 }
371 }
372
373 func (self *linkedPairs) FromSlice(con []Pair) {
374 self.size = len(con)
375 i := self.size-1
376 a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
377 if a < 0 {
378 self.copyPairs(self.head[:b+1], con, b+1)
379 return
380 } else {
381 self.copyPairs(self.head[:], con, len(self.head))
382 con = con[_DEFAULT_NODE_CAP:]
383 }
384
385 if cap(self.tail) <= a {
386 c := (a+1) + (a+1)>>_APPEND_GROW_SHIFT
387 self.tail = make([]*pairChunk, a+1, c)
388 }
389 self.tail = self.tail[:a+1]
390
391 for i:=0; i<a; i++ {
392 self.tail[i] = new(pairChunk)
393 self.copyPairs(self.tail[i][:], con, len(self.tail[i]))
394 con = con[_DEFAULT_NODE_CAP:]
395 }
396
397 self.tail[a] = new(pairChunk)
398 self.copyPairs(self.tail[a][:b+1], con, b+1)
399 }
400
401 func (self *linkedPairs) Less(i, j int) bool {
402 return lessFrom(self.At(i).Key, self.At(j).Key, 0)
403 }
404
405 func (self *linkedPairs) Swap(i, j int) {
406 a, b := self.At(i), self.At(j)
407 if self.index != nil {
408 self.index[a.hash] = j
409 self.index[b.hash] = i
410 }
411 *a, *b = *b, *a
412 }
413
414 func (self *linkedPairs) Sort() {
415 sort.Stable(self)
416 }
417
418 // Compare two strings from the pos d.
419 func lessFrom(a, b string, d int) bool {
420 l := len(a)
421 if l > len(b) {
422 l = len(b)
423 }
424 for i := d; i < l; i++ {
425 if a[i] == b[i] {
426 continue
427 }
428 return a[i] < b[i]
429 }
430 return len(a) < len(b)
431 }
432
433 type parseObjectStack struct {
434 parser Parser
435 v linkedPairs
436 }
437
438 type parseArrayStack struct {
439 parser Parser
440 v linkedNodes
441 }
442
443 func newLazyArray(p *Parser) Node {
444 s := new(parseArrayStack)
445 s.parser = *p
446 return Node{
447 t: _V_ARRAY_LAZY,
448 p: unsafe.Pointer(s),
449 }
450 }
451
452 func newLazyObject(p *Parser) Node {
453 s := new(parseObjectStack)
454 s.parser = *p
455 return Node{
456 t: _V_OBJECT_LAZY,
457 p: unsafe.Pointer(s),
458 }
459 }
460
461 func (self *Node) getParserAndArrayStack() (*Parser, *parseArrayStack) {
462 stack := (*parseArrayStack)(self.p)
463 return &stack.parser, stack
464 }
465
466 func (self *Node) getParserAndObjectStack() (*Parser, *parseObjectStack) {
467 stack := (*parseObjectStack)(self.p)
468 return &stack.parser, stack
469 }
470
471