podman

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

24
type nodeChunk [_DEFAULT_NODE_CAP]Node
25

26
type linkedNodes struct {
27
    head   nodeChunk
28
    tail   []*nodeChunk
29
    size   int
30
}
31

32
func (self *linkedNodes) Cap() int {
33
    if self == nil {
34
        return 0
35
    }
36
    return (len(self.tail)+1)*_DEFAULT_NODE_CAP 
37
}
38

39
func (self *linkedNodes) Len() int {
40
    if self == nil {
41
        return 0
42
    }
43
    return self.size 
44
}
45

46
func (self *linkedNodes) At(i int) (*Node) {
47
    if self == nil {
48
        return nil
49
    }
50
    if i >= 0 && i<self.size && i < _DEFAULT_NODE_CAP {
51
        return &self.head[i]
52
    } else if i >= _DEFAULT_NODE_CAP && i<self.size  {
53
        a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
54
        if a < len(self.tail) {
55
            return &self.tail[a][b]
56
        }
57
    }
58
    return nil
59
}
60

61
func (self *linkedNodes) Add(v Node) {
62
    if self.size < _DEFAULT_NODE_CAP {
63
        self.head[self.size] = v
64
        self.size++
65
        return
66
    }
67

68
    a, b, c := self.size/_DEFAULT_NODE_CAP-1 , self.size%_DEFAULT_NODE_CAP, cap(self.tail)
69
    if a - c >= 0 {
70
        c += 1 + c>>_APPEND_GROW_SHIFT
71
        tmp := make([]*nodeChunk, a + 1, c)
72
        copy(tmp, self.tail)
73
        self.tail = tmp
74
    } else if a >= len(self.tail) {
75
        self.tail = self.tail[:a+1]
76
    }
77
    
78
    var n = &self.tail[a]
79
    if *n == nil {
80
        *n = new(nodeChunk)
81
    }
82
    (*n)[b] = v
83
    self.size++
84
}
85

86
func (self *linkedNodes) ToSlice(con []Node) {
87
    if len(con) < self.size {
88
        return
89
    }
90
    i := (self.size-1)
91
    a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
92
    if a < 0 {
93
        copy(con, self.head[:b+1])
94
        return
95
    } else {
96
        copy(con, self.head[:])
97
        con = con[_DEFAULT_NODE_CAP:]
98
    }
99

100
    for i:=0; i<a; i++ {
101
        copy(con, self.tail[i][:])
102
        con = con[_DEFAULT_NODE_CAP:]
103
    }
104
    copy(con, self.tail[a][:b+1])
105
}
106

107
func (self *linkedNodes) FromSlice(con []Node) {
108
    self.size = len(con)
109
    i := self.size-1
110
    a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
111
    if a < 0 {
112
        copy(self.head[:b+1], con)
113
        return
114
    } else {
115
        copy(self.head[:], con)
116
        con = con[_DEFAULT_NODE_CAP:]
117
    }
118

119
    if cap(self.tail) <= a {
120
        c := (a+1) + (a+1)>>_APPEND_GROW_SHIFT
121
        self.tail = make([]*nodeChunk, a+1, c)
122
    }
123
    self.tail = self.tail[:a+1]
124

125
    for i:=0; i<a; i++ {
126
        self.tail[i] = new(nodeChunk)
127
        copy(self.tail[i][:], con)
128
        con = con[_DEFAULT_NODE_CAP:]
129
    }
130

131
    self.tail[a] = new(nodeChunk)
132
    copy(self.tail[a][:b+1], con)
133
}
134

135
type pairChunk [_DEFAULT_NODE_CAP]Pair
136

137
type linkedPairs struct {
138
    head pairChunk
139
    tail []*pairChunk
140
    size int
141
}
142

143
func (self *linkedPairs) Cap() int {
144
    if self == nil {
145
        return 0
146
    }
147
    return (len(self.tail)+1)*_DEFAULT_NODE_CAP 
148
}
149

150
func (self *linkedPairs) Len() int {
151
    if self == nil {
152
        return 0
153
    }
154
    return self.size 
155
}
156

157
func (self *linkedPairs) At(i int) *Pair {
158
    if self == nil {
159
        return nil
160
    }
161
    if i >= 0 && i < _DEFAULT_NODE_CAP && i<self.size {
162
        return &self.head[i]
163
    } else if i >= _DEFAULT_NODE_CAP && i<self.size {
164
        a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
165
        if a < len(self.tail) {
166
            return &self.tail[a][b]
167
        }
168
    }
169
    return nil
170
}
171

172
func (self *linkedPairs) Add(v Pair) {
173
    if self.size < _DEFAULT_NODE_CAP {
174
        self.head[self.size] = v
175
        self.size++
176
        return
177
    }
178

179
    a, b, c := self.size/_DEFAULT_NODE_CAP-1 , self.size%_DEFAULT_NODE_CAP, cap(self.tail)
180
    if a - c >= 0 {
181
        c += 1 + c>>_APPEND_GROW_SHIFT
182
        tmp := make([]*pairChunk, a + 1, c)
183
        copy(tmp, self.tail)
184
        self.tail = tmp
185
    } else if a >= len(self.tail) {
186
        self.tail = self.tail[:a+1]
187
    }
188

189
    var n = &self.tail[a]
190
    if *n == nil {
191
        *n = new(pairChunk)
192
    }
193
    (*n)[b] = v
194
    self.size++
195
}
196

197
// linear search
198
func (self *linkedPairs) Get(key string) (*Pair, int) {
199
    for i:=0; i<self.size; i++ {
200
        if n := self.At(i); n.Key == key {
201
            return n, i
202
        }
203
    }
204
    return nil, -1
205
}
206

207
func (self *linkedPairs) ToSlice(con []Pair) {
208
    if len(con) < self.size {
209
        return
210
    }
211
    i := self.size-1
212
    a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
213

214
    if a < 0 {
215
        copy(con, self.head[:b+1])
216
        return
217
    } else {
218
        copy(con, self.head[:])
219
        con = con[_DEFAULT_NODE_CAP:]
220
    }
221

222
    for i:=0; i<a; i++ {
223
        copy(con, self.tail[i][:])
224
        con = con[_DEFAULT_NODE_CAP:]
225
    }
226
    copy(con, self.tail[a][:b+1])
227
}
228

229
func (self *linkedPairs) ToMap(con map[string]Node) {
230
    for i:=0; i<self.size; i++ {
231
        n := self.At(i)
232
        con[n.Key] = n.Value
233
    }
234
}
235

236
func (self *linkedPairs) FromSlice(con []Pair) {
237
    self.size = len(con)
238
    i := self.size-1
239
    a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
240
    if a < 0 {
241
        copy(self.head[:b+1], con)
242
        return
243
    } else {
244
        copy(self.head[:], con)
245
        con = con[_DEFAULT_NODE_CAP:]
246
    }
247

248
    if cap(self.tail) <= a {
249
        c := (a+1) + (a+1)>>_APPEND_GROW_SHIFT
250
        self.tail = make([]*pairChunk, a+1, c)
251
    }
252
    self.tail = self.tail[:a+1]
253

254
    for i:=0; i<a; i++ {
255
        self.tail[i] = new(pairChunk)
256
        copy(self.tail[i][:], con)
257
        con = con[_DEFAULT_NODE_CAP:]
258
    }
259

260
    self.tail[a] = new(pairChunk)
261
    copy(self.tail[a][:b+1], con)
262
}
263

264
func (self *linkedPairs) Less(i, j int) bool {
265
    return lessFrom(self.At(i).Key, self.At(j).Key, 0)
266
}
267

268
func (self *linkedPairs) Swap(i, j int) {
269
    a, b := self.At(i), self.At(j)
270
    *a, *b = *b, *a
271
}
272

273
func (self *linkedPairs) Sort() {
274
    sort.Sort(self)
275
}
276

277
// Compare two strings from the pos d.
278
func lessFrom(a, b string, d int) bool {
279
    l := len(a)
280
    if l > len(b) {
281
        l = len(b)
282
    }
283
    for i := d; i < l; i++ {
284
        if a[i] == b[i] {
285
            continue
286
        }
287
        return a[i] < b[i]
288
    }
289
    return len(a) < len(b)
290
}
291

292
type parseObjectStack struct {
293
    parser Parser
294
    v      linkedPairs
295
}
296

297
type parseArrayStack struct {
298
    parser Parser
299
    v      linkedNodes
300
}
301

302
func newLazyArray(p *Parser) Node {
303
    s := new(parseArrayStack)
304
    s.parser = *p
305
    return Node{
306
        t: _V_ARRAY_LAZY,
307
        p: unsafe.Pointer(s),
308
    }
309
}
310

311
func newLazyObject(p *Parser) Node {
312
    s := new(parseObjectStack)
313
    s.parser = *p
314
    return Node{
315
        t: _V_OBJECT_LAZY,
316
        p: unsafe.Pointer(s),
317
    }
318
}
319

320
func (self *Node) getParserAndArrayStack() (*Parser, *parseArrayStack) {
321
    stack := (*parseArrayStack)(self.p)
322
    return &stack.parser, stack
323
}
324

325
func (self *Node) getParserAndObjectStack() (*Parser, *parseObjectStack) {
326
    stack := (*parseObjectStack)(self.p)
327
    return &stack.parser, stack
328
}
329

330