← Back to branch summary

~ubuntu-branches/ubuntu/vivid/golang/vivid

« back to all changes in this revision

Viewing changes to src/pkg/runtime/slice.c

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-20 14:06:23 UTC
  • mfrom: (14.1.23 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130820140623-b414jfxi3m0qkmrq
Tags: 2:1.1.2-2ubuntu1
https://launchpad.net/bugs/1211749
https://launchpad.net/bugs/1202027
* Merge from Debian unstable (LP: #1211749, #1202027). Remaining changes:
  - 016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.
  - d/control,control.cross: Update Breaks/Replaces for Ubuntu
    versions to ensure smooth upgrades, regenerate control file.

Show diffs side-by-side

added added

removed removed

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