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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
#
#
# 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[T] = object
cap: int
allocator: 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])
#[
Keep in mind that C optimizers are bad at detecting the connection
between ``s.p != nil`` and ``s.len != 0`` and that these are intermingled
with user-level code that accesses ``s.len`` only, never ``s.p`` directly.
This means the check for whether ``s.p`` needs to be freed should
be ``s.len == 0`` even though that feels slightly more awkward.
]#
when not defined(nimV2):
proc `=destroy`[T](s: var seq[T]) =
var x = cast[ptr NimSeqV2[T]](addr s)
var p = x.p
if p != nil:
mixin `=destroy`
when not supportsCopyMem(T):
for i in 0..<x.len: `=destroy`(p.data[i])
if p.allocator != nil:
p.allocator.dealloc(p.allocator, p, payloadSize(p.cap))
x.p = nil
x.len = 0
proc `=`[T](x: var seq[T]; y: seq[T]) =
mixin `=destroy`
var a = cast[ptr NimSeqV2[T]](addr x)
var b = cast[ptr NimSeqV2[T]](unsafeAddr y)
if a.p == b.p: return
`=destroy`(x)
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]) =
mixin `=destroy`
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`(x)
a.len = b.len
a.p = b.p
type
PayloadBase = object
cap: int
allocator: Allocator
proc newSeqPayload(cap, elemSize: int): pointer {.compilerRtl, raises: [].} =
# 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 allocator = getLocalAllocator()
var p = cast[ptr PayloadBase](allocator.alloc(allocator, cap * elemSize + sizeof(int) + sizeof(Allocator)))
p.allocator = allocator
p.cap = cap
result = p
else:
result = nil
proc prepareSeqAdd(len: int; p: pointer; addlen, elemSize: int): pointer {.
compilerRtl, noSideEffect, raises: [].} =
{.noSideEffect.}:
template `+!`(p: pointer, s: int): pointer =
cast[pointer](cast[int](p) +% s)
const headerSize = sizeof(int) + sizeof(Allocator)
if addlen <= 0:
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 cap = max(resize(p.cap), len+addlen)
if p.allocator == nil:
let allocator = getLocalAllocator()
var q = cast[ptr PayloadBase](allocator.alloc(allocator,
headerSize + elemSize * cap))
copyMem(q +! headerSize, p +! headerSize, len * elemSize)
q.allocator = allocator
q.cap = cap
result = q
else:
let allocator = p.allocator
var q = cast[ptr PayloadBase](allocator.realloc(allocator, p,
headerSize + elemSize * p.cap,
headerSize + elemSize * cap))
q.allocator = allocator
q.cap = cap
result = q
proc shrink*[T](x: var seq[T]; newLen: Natural) =
mixin `=destroy`
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])
# XXX This is wrong for const seqs that were moved into 'x'!
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 add*[T](x: var seq[T]; value: sink T) {.magic: "AppendSeqElem", noSideEffect.} =
## Generic proc for adding a data item `y` to a container `x`.
##
## For containers that have an order, `add` means *append*. New generic
## containers should also call their adding proc `add` for consistency.
## Generic code becomes much easier to write if the Nim naming scheme is
## respected.
let oldLen = x.len
var xu = cast[ptr NimSeqV2[T]](addr x)
if xu.p == nil or xu.p.cap < oldLen+1:
xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, 1, sizeof(T)))
xu.len = oldLen+1
xu.p.data[oldLen] = value
proc setLen[T](s: var seq[T], newlen: Natural) =
{.noSideEffect.}:
if newlen < s.len:
shrink(s, newLen)
else:
grow(s, newLen, default(T))
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]
|