Text file src/pkg/runtime/slice.c
1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 #include "runtime.h"
6 #include "arch_GOARCH.h"
7 #include "type.h"
8 #include "typekind.h"
9 #include "malloc.h"
10 #include "race.h"
11
12 static bool debug = 0;
13
14 static void makeslice1(SliceType*, intgo, intgo, Slice*);
15 static void growslice1(SliceType*, Slice, intgo, Slice *);
16 void runtime·copy(Slice to, Slice fm, uintptr width, intgo ret);
17
18 // see also unsafe·NewArray
19 // makeslice(typ *Type, len, cap int64) (ary []any);
20 void
21 runtime·makeslice(SliceType *t, int64 len, int64 cap, Slice ret)
22 {
23 // NOTE: The len > MaxMem/elemsize check here is not strictly necessary,
24 // but it produces a 'len out of range' error instead of a 'cap out of range' error
25 // when someone does make([]T, bignumber). 'cap out of range' is true too,
26 // but since the cap is only being supplied implicitly, saying len is clearer.
27 // See issue 4085.
28 if(len < 0 || (intgo)len != len || t->elem->size > 0 && len > MaxMem / t->elem->size)
29 runtime·panicstring("makeslice: len out of range");
30
31 if(cap < len || (intgo)cap != cap || t->elem->size > 0 && cap > MaxMem / t->elem->size)
32 runtime·panicstring("makeslice: cap out of range");
33
34 makeslice1(t, len, cap, &ret);
35
36 if(debug) {
37 runtime·printf("makeslice(%S, %D, %D); ret=",
38 *t->string, len, cap);
39 runtime·printslice(ret);
40 }
41 }
42
43 // Dummy word to use as base pointer for make([]T, 0).
44 // Since you cannot take the address of such a slice,
45 // you can't tell that they all have the same base pointer.
46 uintptr runtime·zerobase;
47
48 static void
49 makeslice1(SliceType *t, intgo len, intgo cap, Slice *ret)
50 {
51 uintptr size;
52
53 size = cap*t->elem->size;
54
55 ret->len = len;
56 ret->cap = cap;
57
58 if(size == 0)
59 ret->array = (byte*)&runtime·zerobase;
60 else if((t->elem->kind&KindNoPointers))
61 ret->array = runtime·mallocgc(size, FlagNoPointers, 1, 1);
62 else {
63 ret->array = runtime·mallocgc(size, 0, 1, 1);
64
65 if(UseSpanType) {
66 if(false) {
67 runtime·printf("new slice [%D]%S: %p\n", (int64)cap, *t->elem->string, ret->array);
68 }
69 runtime·settype(ret->array, (uintptr)t->elem | TypeInfo_Array);
70 }
71 }
72 }
73
74 // appendslice(type *Type, x, y, []T) []T
75 #pragma textflag 7
76 void
77 runtime·appendslice(SliceType *t, Slice x, Slice y, Slice ret)
78 {
79 intgo m;
80 uintptr w;
81 void *pc;
82 uint8 *p, *q;
83
84 m = x.len+y.len;
85 w = t->elem->size;
86
87 if(m < x.len)
88 runtime·throw("append: slice overflow");
89
90 if(m > x.cap)
91 growslice1(t, x, m, &ret);
92 else
93 ret = x;
94
95 if(raceenabled) {
96 // Don't mark read/writes on the newly allocated slice.
97 pc = runtime·getcallerpc(&t);
98 // read x[:len]
99 if(m > x.cap)
100 runtime·racereadrangepc(x.array, x.len*w, w, pc, runtime·appendslice);
101 // read y
102 runtime·racereadrangepc(y.array, y.len*w, w, pc, runtime·appendslice);
103 // write x[len(x):len(x)+len(y)]
104 if(m <= x.cap)
105 runtime·racewriterangepc(ret.array+ret.len*w, y.len*w, w, pc, runtime·appendslice);
106 }
107
108 // A very common case is appending bytes. Small appends can avoid the overhead of memmove.
109 // We can generalize a bit here, and just pick small-sized appends.
110 p = ret.array+ret.len*w;
111 q = y.array;
112 w *= y.len;
113 if(w <= appendCrossover) {
114 if(p <= q || w <= p-q) // No overlap.
115 while(w-- > 0)
116 *p++ = *q++;
117 else {
118 p += w;
119 q += w;
120 while(w-- > 0)
121 *--p = *--q;
122 }
123 } else {
124 runtime·memmove(p, q, w);
125 }
126 ret.len += y.len;
127 FLUSH(&ret);
128 }
129
130
131 // appendstr([]byte, string) []byte
132 #pragma textflag 7
133 void
134 runtime·appendstr(SliceType *t, Slice x, String y, Slice ret)
135 {
136 intgo m;
137 void *pc;
138 uintptr w;
139 uint8 *p, *q;
140
141 m = x.len+y.len;
142
143 if(m < x.len)
144 runtime·throw("append: string overflow");
145
146 if(m > x.cap)
147 growslice1(t, x, m, &ret);
148 else
149 ret = x;
150
151 if(raceenabled) {
152 // Don't mark read/writes on the newly allocated slice.
153 pc = runtime·getcallerpc(&t);
154 // read x[:len]
155 if(m > x.cap)
156 runtime·racereadrangepc(x.array, x.len, 1, pc, runtime·appendstr);
157 // write x[len(x):len(x)+len(y)]
158 if(m <= x.cap)
159 runtime·racewriterangepc(ret.array+ret.len, y.len, 1, pc, runtime·appendstr);
160 }
161
162 // Small appends can avoid the overhead of memmove.
163 w = y.len;
164 p = ret.array+ret.len;
165 q = y.str;
166 if(w <= appendCrossover) {
167 while(w-- > 0)
168 *p++ = *q++;
169 } else {
170 runtime·memmove(p, q, w);
171 }
172 ret.len += y.len;
173 FLUSH(&ret);
174 }
175
176
177 // growslice(type *Type, x, []T, n int64) []T
178 void
179 runtime·growslice(SliceType *t, Slice old, int64 n, Slice ret)
180 {
181 int64 cap;
182 void *pc;
183
184 if(n < 1)
185 runtime·panicstring("growslice: invalid n");
186
187 cap = old.cap + n;
188
189 if((intgo)cap != cap || cap < old.cap || (t->elem->size > 0 && cap > MaxMem/t->elem->size))
190 runtime·panicstring("growslice: cap out of range");
191
192 if(raceenabled) {
193 pc = runtime·getcallerpc(&t);
194 runtime·racereadrangepc(old.array, old.len*t->elem->size, t->elem->size, pc, runtime·growslice);
195 }
196
197 growslice1(t, old, cap, &ret);
198
199 FLUSH(&ret);
200
201 if(debug) {
202 runtime·printf("growslice(%S,", *t->string);
203 runtime·printslice(old);
204 runtime·printf(", new cap=%D) =", cap);
205 runtime·printslice(ret);
206 }
207 }
208
209 static void
210 growslice1(SliceType *t, Slice x, intgo newcap, Slice *ret)
211 {
212 intgo m;
213
214 m = x.cap;
215
216 // Using newcap directly for m+m < newcap handles
217 // both the case where m == 0 and also the case where
218 // m+m/4 wraps around, in which case the loop
219 // below might never terminate.
220 if(m+m < newcap)
221 m = newcap;
222 else {
223 do {
224 if(x.len < 1024)
225 m += m;
226 else
227 m += m/4;
228 } while(m < newcap);
229 }
230 makeslice1(t, x.len, m, ret);
231 runtime·memmove(ret->array, x.array, ret->len * t->elem->size);
232 }
233
234 // copy(to any, fr any, wid uintptr) int
235 #pragma textflag 7
236 void
237 runtime·copy(Slice to, Slice fm, uintptr width, intgo ret)
238 {
239 void *pc;
240
241 if(fm.len == 0 || to.len == 0 || width == 0) {
242 ret = 0;
243 goto out;
244 }
245
246 ret = fm.len;
247 if(to.len < ret)
248 ret = to.len;
249
250 if(raceenabled) {
251 pc = runtime·getcallerpc(&to);
252 runtime·racewriterangepc(to.array, ret*width, width, pc, runtime·copy);
253 runtime·racereadrangepc(fm.array, ret*width, width, pc, runtime·copy);
254 }
255
256 if(ret == 1 && width == 1) { // common case worth about 2x to do here
257 *to.array = *fm.array; // known to be a byte pointer
258 } else {
259 runtime·memmove(to.array, fm.array, ret*width);
260 }
261
262 out:
263 FLUSH(&ret);
264
265 if(debug) {
266 runtime·prints("main·copy: to=");
267 runtime·printslice(to);
268 runtime·prints("; fm=");
269 runtime·printslice(fm);
270 runtime·prints("; width=");
271 runtime·printint(width);
272 runtime·prints("; ret=");
273 runtime·printint(ret);
274 runtime·prints("\n");
275 }
276 }
277
278 #pragma textflag 7
279 void
280 runtime·slicestringcopy(Slice to, String fm, intgo ret)
281 {
282 void *pc;
283
284 if(fm.len == 0 || to.len == 0) {
285 ret = 0;
286 goto out;
287 }
288
289 ret = fm.len;
290 if(to.len < ret)
291 ret = to.len;
292
293 if(raceenabled) {
294 pc = runtime·getcallerpc(&to);
295 runtime·racewriterangepc(to.array, ret, 1, pc, runtime·slicestringcopy);
296 }
297
298 runtime·memmove(to.array, fm.str, ret);
299
300 out:
301 FLUSH(&ret);
302 }
303
304 void
305 runtime·printslice(Slice a)
306 {
307 runtime·prints("[");
308 runtime·printint(a.len);
309 runtime·prints("/");
310 runtime·printint(a.cap);
311 runtime·prints("]");
312 runtime·printpointer(a.array);
313 }
View as plain text