Branch data Line data Source code
1 : : /*
2 : : * This file is part of the MicroPython project, http://micropython.org/
3 : : *
4 : : * The MIT License (MIT)
5 : : *
6 : : * Copyright (c) 2013, 2014 Damien P. George
7 : : *
8 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
9 : : * of this software and associated documentation files (the "Software"), to deal
10 : : * in the Software without restriction, including without limitation the rights
11 : : * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : : * copies of the Software, and to permit persons to whom the Software is
13 : : * furnished to do so, subject to the following conditions:
14 : : *
15 : : * The above copyright notice and this permission notice shall be included in
16 : : * all copies or substantial portions of the Software.
17 : : *
18 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 : : * THE SOFTWARE.
25 : : */
26 : :
27 : : #include <string.h>
28 : : #include <assert.h>
29 : :
30 : : #include "py/objlist.h"
31 : : #include "py/runtime.h"
32 : : #include "py/stackctrl.h"
33 : :
34 : : static mp_obj_t mp_obj_new_list_iterator(mp_obj_t list, size_t cur, mp_obj_iter_buf_t *iter_buf);
35 : : static mp_obj_list_t *list_new(size_t n);
36 : : static mp_obj_t list_extend(mp_obj_t self_in, mp_obj_t arg_in);
37 : : static mp_obj_t list_pop(size_t n_args, const mp_obj_t *args);
38 : :
39 : : // TODO: Move to mpconfig.h
40 : : #define LIST_MIN_ALLOC 4
41 : :
42 : : /******************************************************************************/
43 : : /* list */
44 : :
45 : 23274 : static void list_print(const mp_print_t *print, mp_obj_t o_in, mp_print_kind_t kind) {
46 : 23274 : mp_obj_list_t *o = MP_OBJ_TO_PTR(o_in);
47 : 23274 : const char *item_separator = ", ";
48 [ + + ]: 23274 : if (!(MICROPY_PY_JSON && kind == PRINT_JSON)) {
49 : : kind = PRINT_REPR;
50 : : } else {
51 : : #if MICROPY_PY_JSON_SEPARATORS
52 : 98 : item_separator = MP_PRINT_GET_EXT(print)->item_separator;
53 : : #endif
54 : : }
55 : 23274 : mp_print_str(print, "[");
56 [ + + ]: 68189 : for (size_t i = 0; i < o->len; i++) {
57 [ + + ]: 46886 : if (i > 0) {
58 : 26746 : mp_print_str(print, item_separator);
59 : : }
60 : 46886 : mp_obj_print_helper(print, o->items[i], kind);
61 : : }
62 : 21303 : mp_print_str(print, "]");
63 : 21303 : }
64 : :
65 : 19648 : static mp_obj_t list_extend_from_iter(mp_obj_t list, mp_obj_t iterable) {
66 : 19648 : mp_obj_t iter = mp_getiter(iterable, NULL);
67 : 19648 : mp_obj_t item;
68 [ + + ]: 261328 : while ((item = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
69 : 241684 : mp_obj_list_append(list, item);
70 : : }
71 : 19634 : return list;
72 : : }
73 : :
74 : 19640 : mp_obj_t mp_obj_list_make_new(const mp_obj_type_t *type_in, size_t n_args, size_t n_kw, const mp_obj_t *args) {
75 : 19640 : (void)type_in;
76 : 19640 : mp_arg_check_num(n_args, n_kw, 0, 1, false);
77 : :
78 [ + + ]: 19640 : switch (n_args) {
79 : 16 : case 0:
80 : : // return a new, empty list
81 : 16 : return mp_obj_new_list(0, NULL);
82 : :
83 : 19624 : case 1:
84 : : default: {
85 : : // make list from iterable
86 : : // TODO: optimize list/tuple
87 : 19624 : mp_obj_t list = mp_obj_new_list(0, NULL);
88 : 19624 : return list_extend_from_iter(list, args[0]);
89 : : }
90 : : }
91 : : }
92 : :
93 : 141005 : static mp_obj_t list_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
94 : 141005 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
95 [ + + + + ]: 141005 : switch (op) {
96 : 129443 : case MP_UNARY_OP_BOOL:
97 [ + + ]: 129443 : return mp_obj_new_bool(self->len != 0);
98 : 11522 : case MP_UNARY_OP_LEN:
99 : 11522 : return MP_OBJ_NEW_SMALL_INT(self->len);
100 : : #if MICROPY_PY_SYS_GETSIZEOF
101 : 4 : case MP_UNARY_OP_SIZEOF: {
102 : 4 : size_t sz = sizeof(*self) + sizeof(mp_obj_t) * self->alloc;
103 : 4 : return MP_OBJ_NEW_SMALL_INT(sz);
104 : : }
105 : : #endif
106 : : default:
107 : : return MP_OBJ_NULL; // op not supported
108 : : }
109 : : }
110 : :
111 : 1127 : static mp_obj_t list_binary_op(mp_binary_op_t op, mp_obj_t lhs, mp_obj_t rhs) {
112 : 1127 : mp_obj_list_t *o = MP_OBJ_TO_PTR(lhs);
113 [ + + + + : 1127 : switch (op) {
+ ]
114 : : case MP_BINARY_OP_ADD: {
115 [ + + + - ]: 50 : if (!mp_obj_is_type(rhs, &mp_type_list)) {
116 : : return MP_OBJ_NULL; // op not supported
117 : : }
118 : 46 : mp_obj_list_t *p = MP_OBJ_TO_PTR(rhs);
119 : 46 : mp_obj_list_t *s = list_new(o->len + p->len);
120 : 46 : mp_seq_cat(s->items, o->items, o->len, p->items, p->len, mp_obj_t);
121 : 46 : return MP_OBJ_FROM_PTR(s);
122 : : }
123 : 186 : case MP_BINARY_OP_INPLACE_ADD: {
124 : 186 : list_extend(lhs, rhs);
125 : 186 : return lhs;
126 : : }
127 : 402 : case MP_BINARY_OP_MULTIPLY: {
128 : 402 : mp_int_t n;
129 [ + + ]: 402 : if (!mp_obj_get_int_maybe(rhs, &n)) {
130 : : return MP_OBJ_NULL; // op not supported
131 : : }
132 [ + + ]: 398 : if (n < 0) {
133 : 16 : n = 0;
134 : : }
135 : 398 : mp_obj_list_t *s = list_new(o->len * n);
136 : 392 : mp_seq_multiply(o->items, sizeof(*o->items), o->len, n, s->items);
137 : 392 : return MP_OBJ_FROM_PTR(s);
138 : : }
139 : : case MP_BINARY_OP_EQUAL:
140 : : case MP_BINARY_OP_LESS:
141 : : case MP_BINARY_OP_LESS_EQUAL:
142 : : case MP_BINARY_OP_MORE:
143 : : case MP_BINARY_OP_MORE_EQUAL: {
144 [ + - + + ]: 225 : if (!mp_obj_is_type(rhs, &mp_type_list)) {
145 [ + - ]: 4 : if (op == MP_BINARY_OP_EQUAL) {
146 : : return mp_const_false;
147 : : }
148 : 4 : return MP_OBJ_NULL; // op not supported
149 : : }
150 : :
151 : 221 : mp_obj_list_t *another = MP_OBJ_TO_PTR(rhs);
152 : 221 : bool res = mp_seq_cmp_objs(op, o->items, o->len, another->items, another->len);
153 [ + + ]: 221 : return mp_obj_new_bool(res);
154 : : }
155 : :
156 : : default:
157 : : return MP_OBJ_NULL; // op not supported
158 : : }
159 : : }
160 : :
161 : 415698 : static mp_obj_t list_subscr(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
162 [ + + ]: 415698 : if (value == MP_OBJ_NULL) {
163 : : // delete
164 : : #if MICROPY_PY_BUILTINS_SLICE
165 [ - + - + : 24 : if (mp_obj_is_type(index, &mp_type_slice)) {
- + - + +
+ + - ]
166 : 14 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
167 : 14 : mp_bound_slice_t slice;
168 [ + + ]: 14 : if (!mp_seq_get_fast_slice_indexes(self->len, index, &slice)) {
169 : 2 : mp_raise_NotImplementedError(NULL);
170 : : }
171 : :
172 : 12 : mp_int_t len_adj = slice.start - slice.stop;
173 [ - + ]: 12 : assert(len_adj <= 0);
174 : 12 : mp_seq_replace_slice_no_grow(self->items, self->len, slice.start, slice.stop, self->items /*NULL*/, 0, sizeof(*self->items));
175 : : // Clear "freed" elements at the end of list
176 : 12 : mp_seq_clear(self->items, self->len + len_adj, self->len, sizeof(*self->items));
177 : 12 : self->len += len_adj;
178 : 12 : return mp_const_none;
179 : : }
180 : : #endif
181 : 10 : mp_obj_t args[2] = {self_in, index};
182 : 10 : list_pop(2, args);
183 : 10 : return mp_const_none;
184 [ + + ]: 415674 : } else if (value == MP_OBJ_SENTINEL) {
185 : : // load
186 : 280691 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
187 : : #if MICROPY_PY_BUILTINS_SLICE
188 [ - + - + : 280691 : if (mp_obj_is_type(index, &mp_type_slice)) {
- + - + +
+ + + ]
189 : 1164 : mp_bound_slice_t slice;
190 [ + + ]: 1164 : if (!mp_seq_get_fast_slice_indexes(self->len, index, &slice)) {
191 : 132 : return mp_seq_extract_slice(self->len, self->items, &slice);
192 : : }
193 : 1028 : mp_obj_list_t *res = list_new(slice.stop - slice.start);
194 : 1024 : mp_seq_copy(res->items, self->items + slice.start, res->len, mp_obj_t);
195 : 1024 : return MP_OBJ_FROM_PTR(res);
196 : : }
197 : : #endif
198 : 279527 : size_t index_val = mp_get_index(self->base.type, self->len, index, false);
199 : 281666 : return self->items[index_val];
200 : : } else {
201 : : #if MICROPY_PY_BUILTINS_SLICE
202 [ - + - + : 134983 : if (mp_obj_is_type(index, &mp_type_slice)) {
- + - + +
+ + - ]
203 : 74 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
204 : 74 : size_t value_len;
205 : 74 : mp_obj_t *value_items;
206 : 74 : mp_obj_get_array(value, &value_len, &value_items);
207 : 70 : mp_bound_slice_t slice_out;
208 [ + + ]: 70 : if (!mp_seq_get_fast_slice_indexes(self->len, index, &slice_out)) {
209 : 2 : mp_raise_NotImplementedError(NULL);
210 : : }
211 : 68 : mp_int_t len_adj = value_len - (slice_out.stop - slice_out.start);
212 [ + + ]: 68 : if (len_adj > 0) {
213 [ + + ]: 40 : if (self->len + len_adj > self->alloc) {
214 : : // TODO: Might optimize memory copies here by checking if block can
215 : : // be grown inplace or not
216 : 28 : self->items = m_renew(mp_obj_t, self->items, self->alloc, self->len + len_adj);
217 : 24 : self->alloc = self->len + len_adj;
218 : : }
219 : 36 : mp_seq_replace_slice_grow_inplace(self->items, self->len,
220 : 36 : slice_out.start, slice_out.stop, value_items, value_len, len_adj, sizeof(*self->items));
221 : : } else {
222 : 28 : mp_seq_replace_slice_no_grow(self->items, self->len,
223 : 28 : slice_out.start, slice_out.stop, value_items, value_len, sizeof(*self->items));
224 : : // Clear "freed" elements at the end of list
225 : 28 : mp_seq_clear(self->items, self->len + len_adj, self->len, sizeof(*self->items));
226 : : // TODO: apply allocation policy re: alloc_size
227 : : }
228 : 64 : self->len += len_adj;
229 : 64 : return mp_const_none;
230 : : }
231 : : #endif
232 : 134909 : mp_obj_list_store(self_in, index, value);
233 : 134909 : return mp_const_none;
234 : : }
235 : : }
236 : :
237 : 7550 : static mp_obj_t list_getiter(mp_obj_t o_in, mp_obj_iter_buf_t *iter_buf) {
238 : 7550 : return mp_obj_new_list_iterator(o_in, 0, iter_buf);
239 : : }
240 : :
241 : 294892 : mp_obj_t mp_obj_list_append(mp_obj_t self_in, mp_obj_t arg) {
242 : 294892 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
243 : 294892 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
244 [ + + ]: 294892 : if (self->len >= self->alloc) {
245 : 7041 : self->items = m_renew(mp_obj_t, self->items, self->alloc, self->alloc * 2);
246 : 7037 : self->alloc *= 2;
247 : 7037 : mp_seq_clear(self->items, self->len + 1, self->alloc, sizeof(*self->items));
248 : : }
249 : 294888 : self->items[self->len++] = arg;
250 : 294888 : return mp_const_none; // return None, as per CPython
251 : : }
252 : :
253 : 222 : static mp_obj_t list_extend(mp_obj_t self_in, mp_obj_t arg_in) {
254 : 222 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
255 [ + + + + ]: 222 : if (mp_obj_is_type(arg_in, &mp_type_list)) {
256 : 198 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
257 : 198 : mp_obj_list_t *arg = MP_OBJ_TO_PTR(arg_in);
258 : :
259 [ + + ]: 198 : if (self->len + arg->len > self->alloc) {
260 : : // TODO: use alloc policy for "4"
261 : 44 : self->items = m_renew(mp_obj_t, self->items, self->alloc, self->len + arg->len + 4);
262 : 40 : self->alloc = self->len + arg->len + 4;
263 : 40 : mp_seq_clear(self->items, self->len + arg->len, self->alloc, sizeof(*self->items));
264 : : }
265 : :
266 : 194 : memcpy(self->items + self->len, arg->items, sizeof(mp_obj_t) * arg->len);
267 : 194 : self->len += arg->len;
268 : : } else {
269 : 24 : list_extend_from_iter(self_in, arg_in);
270 : : }
271 : 214 : return mp_const_none; // return None, as per CPython
272 : : }
273 : :
274 : 224 : static mp_obj_t list_pop(size_t n_args, const mp_obj_t *args) {
275 : 224 : mp_check_self(mp_obj_is_type(args[0], &mp_type_list));
276 : 224 : mp_obj_list_t *self = MP_OBJ_TO_PTR(args[0]);
277 [ + + ]: 224 : if (self->len == 0) {
278 : 8 : mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("pop from empty list"));
279 : : }
280 [ + + ]: 216 : size_t index = mp_get_index(self->base.type, self->len, n_args == 1 ? MP_OBJ_NEW_SMALL_INT(-1) : args[1], false);
281 : 216 : mp_obj_t ret = self->items[index];
282 : 216 : self->len -= 1;
283 : 216 : memmove(self->items + index, self->items + index + 1, (self->len - index) * sizeof(mp_obj_t));
284 : : // Clear stale pointer from slot which just got freed to prevent GC issues
285 : 216 : self->items[self->len] = MP_OBJ_NULL;
286 [ + + + + ]: 216 : if (self->alloc > LIST_MIN_ALLOC && self->alloc > 2 * self->len) {
287 : 16 : self->items = m_renew(mp_obj_t, self->items, self->alloc, self->alloc / 2);
288 : 16 : self->alloc /= 2;
289 : : }
290 : 216 : return ret;
291 : : }
292 : :
293 : 32666 : static void mp_quicksort(mp_obj_t *head, mp_obj_t *tail, mp_obj_t key_fn, mp_obj_t binop_less_result) {
294 : 32666 : MP_STACK_CHECK();
295 [ + + ]: 55895 : while (head < tail) {
296 : 23229 : mp_obj_t *h = head - 1;
297 : 23229 : mp_obj_t *t = tail;
298 [ + + ]: 23229 : mp_obj_t v = key_fn == MP_OBJ_NULL ? tail[0] : mp_call_function_1(key_fn, tail[0]); // get pivot using key_fn
299 : 6190305 : for (;;) {
300 : 6187214 : do {++h;
301 [ + + + + : 6187214 : } while (h < t && mp_binary_op(MP_BINARY_OP_LESS, key_fn == MP_OBJ_NULL ? h[0] : mp_call_function_1(key_fn, h[0]), v) == binop_less_result);
+ + ]
302 : 2066055 : do {--t;
303 [ + + + + : 2066055 : } while (h < t && mp_binary_op(MP_BINARY_OP_LESS, v, key_fn == MP_OBJ_NULL ? t[0] : mp_call_function_1(key_fn, t[0])) == binop_less_result);
+ + ]
304 [ + + ]: 26320 : if (h >= t) {
305 : : break;
306 : : }
307 : 3091 : mp_obj_t x = h[0];
308 : 3091 : h[0] = t[0];
309 : 3091 : t[0] = x;
310 : : }
311 : 23229 : mp_obj_t x = h[0];
312 : 23229 : h[0] = tail[0];
313 : 23229 : tail[0] = x;
314 : : // do the smaller recursive call first, to keep stack within O(log(N))
315 [ + + ]: 23229 : if (t - head < tail - h - 1) {
316 : 3560 : mp_quicksort(head, t, key_fn, binop_less_result);
317 : 3560 : head = h + 1;
318 : : } else {
319 : 19669 : mp_quicksort(h + 1, tail, key_fn, binop_less_result);
320 : 19669 : tail = t;
321 : : }
322 : : }
323 : 32666 : }
324 : :
325 : : // TODO Python defines sort to be stable but ours is not
326 : 18787 : mp_obj_t mp_obj_list_sort(size_t n_args, const mp_obj_t *pos_args, mp_map_t *kw_args) {
327 : 18787 : static const mp_arg_t allowed_args[] = {
328 : : { MP_QSTR_key, MP_ARG_KW_ONLY | MP_ARG_OBJ, {.u_rom_obj = MP_ROM_NONE} },
329 : : { MP_QSTR_reverse, MP_ARG_KW_ONLY | MP_ARG_BOOL, {.u_bool = false} },
330 : : };
331 : :
332 : : // parse args
333 : 18787 : struct {
334 : : mp_arg_val_t key, reverse;
335 : : } args;
336 : 18787 : mp_arg_parse_all(n_args - 1, pos_args + 1, kw_args,
337 : : MP_ARRAY_SIZE(allowed_args), allowed_args, (mp_arg_val_t *)&args);
338 : :
339 : 18779 : mp_check_self(mp_obj_is_type(pos_args[0], &mp_type_list));
340 : 18779 : mp_obj_list_t *self = MP_OBJ_TO_PTR(pos_args[0]);
341 : :
342 [ + + ]: 18779 : if (self->len > 1) {
343 : 9437 : mp_quicksort(self->items, self->items + self->len - 1,
344 [ + + ]: 9437 : args.key.u_obj == mp_const_none ? MP_OBJ_NULL : args.key.u_obj,
345 [ + + ]: 9437 : args.reverse.u_bool ? mp_const_false : mp_const_true);
346 : : }
347 : :
348 : 18779 : return mp_const_none;
349 : : }
350 : :
351 : 10 : static mp_obj_t list_clear(mp_obj_t self_in) {
352 : 10 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
353 : 10 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
354 : 10 : self->len = 0;
355 : 10 : self->items = m_renew(mp_obj_t, self->items, self->alloc, LIST_MIN_ALLOC);
356 : 10 : self->alloc = LIST_MIN_ALLOC;
357 : 10 : mp_seq_clear(self->items, 0, self->alloc, sizeof(*self->items));
358 : 10 : return mp_const_none;
359 : : }
360 : :
361 : 4 : static mp_obj_t list_copy(mp_obj_t self_in) {
362 : 4 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
363 : 4 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
364 : 4 : return mp_obj_new_list(self->len, self->items);
365 : : }
366 : :
367 : 36 : static mp_obj_t list_count(mp_obj_t self_in, mp_obj_t value) {
368 : 36 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
369 : 36 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
370 : 36 : return mp_seq_count_obj(self->items, self->len, value);
371 : : }
372 : :
373 : 64 : static mp_obj_t list_index(size_t n_args, const mp_obj_t *args) {
374 : 64 : mp_check_self(mp_obj_is_type(args[0], &mp_type_list));
375 : 64 : mp_obj_list_t *self = MP_OBJ_TO_PTR(args[0]);
376 : 64 : return mp_seq_index_obj(self->items, self->len, n_args, args);
377 : : }
378 : :
379 : 18 : static mp_obj_t list_insert(mp_obj_t self_in, mp_obj_t idx, mp_obj_t obj) {
380 : 18 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
381 : 18 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
382 : : // insert has its own strange index logic
383 : 18 : mp_int_t index = MP_OBJ_SMALL_INT_VALUE(idx);
384 [ + + ]: 18 : if (index < 0) {
385 : 8 : index += self->len;
386 : : }
387 [ + + ]: 8 : if (index < 0) {
388 : 4 : index = 0;
389 : : }
390 [ + + ]: 18 : if ((size_t)index > self->len) {
391 : 4 : index = self->len;
392 : : }
393 : :
394 : 18 : mp_obj_list_append(self_in, mp_const_none);
395 : :
396 [ + + ]: 60 : for (mp_int_t i = self->len - 1; i > index; i--) {
397 : 42 : self->items[i] = self->items[i - 1];
398 : : }
399 : 18 : self->items[index] = obj;
400 : :
401 : 18 : return mp_const_none;
402 : : }
403 : :
404 : 8 : mp_obj_t mp_obj_list_remove(mp_obj_t self_in, mp_obj_t value) {
405 : 8 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
406 : 8 : mp_obj_t args[] = {self_in, value};
407 : 8 : args[1] = list_index(2, args);
408 : 4 : list_pop(2, args);
409 : :
410 : 4 : return mp_const_none;
411 : : }
412 : :
413 : 400 : static mp_obj_t list_reverse(mp_obj_t self_in) {
414 : 400 : mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
415 : 400 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
416 : :
417 : 400 : mp_int_t len = self->len;
418 [ + + ]: 10400 : for (mp_int_t i = 0; i < len / 2; i++) {
419 : 10000 : mp_obj_t a = self->items[i];
420 : 10000 : self->items[i] = self->items[len - i - 1];
421 : 10000 : self->items[len - i - 1] = a;
422 : : }
423 : :
424 : 400 : return mp_const_none;
425 : : }
426 : :
427 : : static MP_DEFINE_CONST_FUN_OBJ_2(list_append_obj, mp_obj_list_append);
428 : : static MP_DEFINE_CONST_FUN_OBJ_2(list_extend_obj, list_extend);
429 : : static MP_DEFINE_CONST_FUN_OBJ_1(list_clear_obj, list_clear);
430 : : static MP_DEFINE_CONST_FUN_OBJ_1(list_copy_obj, list_copy);
431 : : static MP_DEFINE_CONST_FUN_OBJ_2(list_count_obj, list_count);
432 : : static MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(list_index_obj, 2, 4, list_index);
433 : : static MP_DEFINE_CONST_FUN_OBJ_3(list_insert_obj, list_insert);
434 : : static MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(list_pop_obj, 1, 2, list_pop);
435 : : static MP_DEFINE_CONST_FUN_OBJ_2(list_remove_obj, mp_obj_list_remove);
436 : : static MP_DEFINE_CONST_FUN_OBJ_1(list_reverse_obj, list_reverse);
437 : : static MP_DEFINE_CONST_FUN_OBJ_KW(list_sort_obj, 1, mp_obj_list_sort);
438 : :
439 : : static const mp_rom_map_elem_t list_locals_dict_table[] = {
440 : : { MP_ROM_QSTR(MP_QSTR_append), MP_ROM_PTR(&list_append_obj) },
441 : : { MP_ROM_QSTR(MP_QSTR_clear), MP_ROM_PTR(&list_clear_obj) },
442 : : { MP_ROM_QSTR(MP_QSTR_copy), MP_ROM_PTR(&list_copy_obj) },
443 : : { MP_ROM_QSTR(MP_QSTR_count), MP_ROM_PTR(&list_count_obj) },
444 : : { MP_ROM_QSTR(MP_QSTR_extend), MP_ROM_PTR(&list_extend_obj) },
445 : : { MP_ROM_QSTR(MP_QSTR_index), MP_ROM_PTR(&list_index_obj) },
446 : : { MP_ROM_QSTR(MP_QSTR_insert), MP_ROM_PTR(&list_insert_obj) },
447 : : { MP_ROM_QSTR(MP_QSTR_pop), MP_ROM_PTR(&list_pop_obj) },
448 : : { MP_ROM_QSTR(MP_QSTR_remove), MP_ROM_PTR(&list_remove_obj) },
449 : : { MP_ROM_QSTR(MP_QSTR_reverse), MP_ROM_PTR(&list_reverse_obj) },
450 : : { MP_ROM_QSTR(MP_QSTR_sort), MP_ROM_PTR(&list_sort_obj) },
451 : : };
452 : :
453 : : static MP_DEFINE_CONST_DICT(list_locals_dict, list_locals_dict_table);
454 : :
455 : : MP_DEFINE_CONST_OBJ_TYPE(
456 : : mp_type_list,
457 : : MP_QSTR_list,
458 : : MP_TYPE_FLAG_ITER_IS_GETITER,
459 : : make_new, mp_obj_list_make_new,
460 : : print, list_print,
461 : : unary_op, list_unary_op,
462 : : binary_op, list_binary_op,
463 : : subscr, list_subscr,
464 : : iter, list_getiter,
465 : : locals_dict, &list_locals_dict
466 : : );
467 : :
468 : :
469 : 678392 : void mp_obj_list_init(mp_obj_list_t *o, size_t n) {
470 : 678392 : o->base.type = &mp_type_list;
471 : 678392 : o->alloc = n < LIST_MIN_ALLOC ? LIST_MIN_ALLOC : n;
472 : 678392 : o->len = n;
473 : 678392 : o->items = m_new(mp_obj_t, o->alloc);
474 : 678400 : mp_seq_clear(o->items, n, o->alloc, sizeof(*o->items));
475 : 678400 : }
476 : :
477 : 671379 : static mp_obj_list_t *list_new(size_t n) {
478 : 671379 : mp_obj_list_t *o = m_new_obj(mp_obj_list_t);
479 : 671401 : mp_obj_list_init(o, n);
480 : 671293 : return o;
481 : : }
482 : :
483 : 669861 : mp_obj_t mp_obj_new_list(size_t n, mp_obj_t *items) {
484 : 669861 : mp_obj_list_t *o = list_new(n);
485 [ + + ]: 669830 : if (items != NULL) {
486 [ + + ]: 3180795 : for (size_t i = 0; i < n; i++) {
487 : 2534776 : o->items[i] = items[i];
488 : : }
489 : : }
490 : 669830 : return MP_OBJ_FROM_PTR(o);
491 : : }
492 : :
493 : 10244 : void mp_obj_list_get(mp_obj_t self_in, size_t *len, mp_obj_t **items) {
494 : 10244 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
495 : 10244 : *len = self->len;
496 : 10244 : *items = self->items;
497 : 10244 : }
498 : :
499 : 36 : void mp_obj_list_set_len(mp_obj_t self_in, size_t len) {
500 : : // trust that the caller knows what it's doing
501 : : // TODO realloc if len got much smaller than alloc
502 : 36 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
503 : 36 : self->len = len;
504 : 36 : }
505 : :
506 : 136869 : void mp_obj_list_store(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
507 : 136869 : mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
508 : 136869 : size_t i = mp_get_index(self->base.type, self->len, index, false);
509 : 136869 : self->items[i] = value;
510 : 136869 : }
511 : :
512 : : /******************************************************************************/
513 : : /* list iterator */
514 : :
515 : : typedef struct _mp_obj_list_it_t {
516 : : mp_obj_base_t base;
517 : : mp_fun_1_t iternext;
518 : : mp_obj_t list;
519 : : size_t cur;
520 : : } mp_obj_list_it_t;
521 : :
522 : 49611 : static mp_obj_t list_it_iternext(mp_obj_t self_in) {
523 : 49611 : mp_obj_list_it_t *self = MP_OBJ_TO_PTR(self_in);
524 : 49611 : mp_obj_list_t *list = MP_OBJ_TO_PTR(self->list);
525 [ + + ]: 49611 : if (self->cur < list->len) {
526 : 42418 : mp_obj_t o_out = list->items[self->cur];
527 : 42418 : self->cur += 1;
528 : 42418 : return o_out;
529 : : } else {
530 : : return MP_OBJ_STOP_ITERATION;
531 : : }
532 : : }
533 : :
534 : 7550 : mp_obj_t mp_obj_new_list_iterator(mp_obj_t list, size_t cur, mp_obj_iter_buf_t *iter_buf) {
535 : 7550 : assert(sizeof(mp_obj_list_it_t) <= sizeof(mp_obj_iter_buf_t));
536 : 7550 : mp_obj_list_it_t *o = (mp_obj_list_it_t *)iter_buf;
537 : 7550 : o->base.type = &mp_type_polymorph_iter;
538 : 7550 : o->iternext = list_it_iternext;
539 : 7550 : o->list = list;
540 : 7550 : o->cur = cur;
541 : 7550 : return MP_OBJ_FROM_PTR(o);
542 : : }
|
