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
|
#
#
# 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 allocateds for us.
proc supportsCopyMem(t: typedesc): bool {.magic: "TypeTrait".}
## Default seq implementation used by Nim's core.
type
NimSeqPayloadBase = object
cap: int
NimSeqPayload[T] = object
cap: int
data: UncheckedArray[T]
NimSeqV2*[T] = object # \
# if you change this implementation, also change seqs_v2_reimpl.nim!
len: int
p: ptr NimSeqPayload[T]
const nimSeqVersion {.core.} = 2
# XXX make code memory safe for overflows in '*'
proc newSeqPayload(cap, elemSize, elemAlign: 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:
var p = cast[ptr NimSeqPayloadBase](alignedAlloc0(align(sizeof(NimSeqPayloadBase), elemAlign) + cap * elemSize, elemAlign))
p.cap = cap
result = p
else:
result = nil
template `+!`(p: pointer, s: int): pointer =
cast[pointer](cast[int](p) +% s)
template `-!`(p: pointer, s: int): pointer =
cast[pointer](cast[int](p) -% s)
proc prepareSeqAdd(len: int; p: pointer; addlen, elemSize, elemAlign: int): pointer {.
noSideEffect, raises: [], compilerRtl.} =
{.noSideEffect.}:
let headerSize = align(sizeof(NimSeqPayloadBase), elemAlign)
if addlen <= 0:
result = p
elif p == nil:
result = newSeqPayload(len+addlen, elemSize, elemAlign)
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 NimSeqPayloadBase](p)
let oldCap = p.cap and not strlitFlag
let newCap = max(resize(oldCap), len+addlen)
if (p.cap and strlitFlag) == strlitFlag:
var q = cast[ptr NimSeqPayloadBase](alignedAlloc0(headerSize + elemSize * newCap, elemAlign))
copyMem(q +! headerSize, p +! headerSize, len * elemSize)
q.cap = newCap
result = q
else:
let oldSize = headerSize + elemSize * oldCap
let newSize = headerSize + elemSize * newCap
var q = cast[ptr NimSeqPayloadBase](alignedRealloc0(p, oldSize, newSize, elemAlign))
q.cap = newCap
result = q
proc shrink*[T](x: var seq[T]; newLen: Natural) =
when nimvm:
setLen(x, newLen)
else:
#sysAssert newLen <= x.len, "invalid newLen parameter for 'shrink'"
when not supportsCopyMem(T):
for i in countdown(x.len - 1, newLen):
reset 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
#sysAssert newLen >= x.len, "invalid newLen parameter for 'grow'"
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), alignof(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, nodestroy.} =
## 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), alignof(T)))
xu.len = oldLen+1
# .nodestroy means `xu.p.data[oldLen] = value` is compiled into a
# copyMem(). This is fine as know by construction that
# in `xu.p.data[oldLen]` there is nothing to destroy.
# We also save the `wasMoved + destroy` pair for the sink parameter.
xu.p.data[oldLen] = value
proc setLen[T](s: var seq[T], newlen: Natural) =
{.noSideEffect.}:
if newlen < s.len:
shrink(s, newlen)
else:
let oldLen = s.len
if newlen <= oldLen: return
var xu = cast[ptr NimSeqV2[T]](addr s)
if xu.p == nil or xu.p.cap < newlen:
xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, newlen - oldLen, sizeof(T), alignof(T)))
xu.len = newlen
|