1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
#
#
# Nim's Runtime Library
# (c) Copyright 2017 Nim contributors
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
# import typetraits
# strs already imported allocators for us.
proc supportsCopyMem(t: typedesc): bool {.magic: "TypeTrait".}
## Default seq implementation used by Nim's core.
type
NimSeqPayload {.core.}[T] = object
cap: int
region: Allocator
data: UncheckedArray[T]
NimSeqV2*[T] = object
len: int
p: ptr NimSeqPayload[T]
const nimSeqVersion {.core.} = 2
template payloadSize(cap): int = cap * sizeof(T) + sizeof(int) + sizeof(Allocator)
# XXX make code memory safe for overflows in '*'
when false:
# this is currently not part of Nim's type bound operators and so it's
# built into the tracing proc generation just like before.
proc `=trace`[T](s: NimSeqV2[T]) =
for i in 0 ..< s.len: `=trace`(s.data[i])
proc `=destroy`[T](s: var seq[T]) =
var x = cast[ptr NimSeqV2[T]](addr s)
var p = x.p
if p != nil:
when not supportsCopyMem(T):
for i in 0..<x.len: `=destroy`(p.data[i])
p.region.dealloc(p.region, p, payloadSize(p.cap))
x.p = nil
x.len = 0
proc `=`[T](x: var seq[T]; y: seq[T]) =
var a = cast[ptr NimSeqV2[T]](addr x)
var b = cast[ptr NimSeqV2[T]](unsafeAddr y)
if a.p == b.p: return
`=destroy`(a)
a.len = b.len
if b.p != nil:
a.p = cast[type(a.p)](alloc(payloadSize(a.len)))
when supportsCopyMem(T):
if a.len > 0:
copyMem(unsafeAddr a.p.data[0], unsafeAddr b.p.data[0], a.len * sizeof(T))
else:
for i in 0..<a.len:
a.p.data[i] = b.p.data[i]
proc `=sink`[T](x: var seq[T]; y: seq[T]) =
var a = cast[ptr NimSeqV2[T]](addr x)
var b = cast[ptr NimSeqV2[T]](unsafeAddr y)
if a.p != nil and a.p != b.p:
`=destroy`(a)
a.len = b.len
a.p = b.p
when false:
proc incrSeqV3(s: PGenericSeq, typ: PNimType): PGenericSeq {.compilerProc.}
proc setLengthSeqV2(s: PGenericSeq, typ: PNimType, newLen: int): PGenericSeq {.
compilerRtl.}
proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.}
type
PayloadBase = object
cap: int
region: Allocator
proc newSeqPayload(cap, elemSize: int): pointer {.compilerRtl.} =
# we have to use type erasure here as Nim does not support generic
# compilerProcs. Oh well, this will all be inlined anyway.
if cap > 0:
let region = getLocalAllocator()
var p = cast[ptr PayloadBase](region.alloc(region, cap * elemSize + sizeof(int) + sizeof(Allocator)))
p.region = region
p.cap = cap
result = p
else:
result = nil
proc prepareSeqAdd(len: int; p: pointer; addlen, elemSize: int): pointer {.
compilerRtl, noSideEffect.} =
{.noSideEffect.}:
if len+addlen <= len:
result = p
elif p == nil:
result = newSeqPayload(len+addlen, elemSize)
else:
# Note: this means we cannot support things that have internal pointers as
# they get reallocated here. This needs to be documented clearly.
var p = cast[ptr PayloadBase](p)
let region = if p.region == nil: getLocalAllocator() else: p.region
let cap = max(resize(p.cap), len+addlen)
var q = cast[ptr PayloadBase](region.realloc(region, p,
sizeof(int) + sizeof(Allocator) + elemSize * p.cap,
sizeof(int) + sizeof(Allocator) + elemSize * cap))
q.region = region
q.cap = cap
result = q
proc shrink*[T](x: var seq[T]; newLen: Natural) =
sysAssert newLen <= x.len, "invalid newLen parameter for 'shrink'"
when not supportsCopyMem(T):
for i in countdown(x.len - 1, newLen - 1):
`=destroy`(x[i])
cast[ptr NimSeqV2[T]](addr x).len = newLen
proc grow*[T](x: var seq[T]; newLen: Natural; value: T) =
let oldLen = x.len
if newLen <= oldLen: return
var xu = cast[ptr NimSeqV2[T]](addr x)
if xu.p == nil or xu.p.cap < newLen:
xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, newLen - oldLen, sizeof(T)))
xu.len = newLen
for i in oldLen .. newLen-1:
xu.p.data[i] = value
proc setLen[T](s: var seq[T], newlen: Natural) =
{.noSideEffect.}:
if newlen < s.len:
shrink(s, newLen)
else:
var v: T # get the default value of 'v'
grow(s, newLen, v)
when false:
proc resize[T](s: var NimSeqV2[T]) =
let old = s.cap
if old == 0: s.cap = 8
else: s.cap = (s.cap * 3) shr 1
s.data = cast[type(s.data)](realloc(s.data, old * sizeof(T), s.cap * sizeof(T)))
proc reserveSlot[T](x: var NimSeqV2[T]): ptr T =
if x.len >= x.cap: resize(x)
result = addr(x.data[x.len])
inc x.len
template add*[T](x: var NimSeqV2[T]; y: T) =
reserveSlot(x)[] = y
template `[]`*[T](x: NimSeqV2[T]; i: Natural): T =
assert i < x.len
x.data[i]
template `[]=`*[T](x: NimSeqV2[T]; i: Natural; y: T) =
assert i < x.len
x.data[i] = y
proc `@`*[T](elems: openArray[T]): NimSeqV2[T] =
result.cap = elems.len
result.len = elems.len
result.data = cast[type(result.data)](alloc(result.cap * sizeof(T)))
when supportsCopyMem(T):
copyMem(result.data, unsafeAddr(elems[0]), result.cap * sizeof(T))
else:
for i in 0..<result.len:
result.data[i] = elems[i]
|