LCOV - code coverage report
Current view: top level - py - objlist.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.19.1-724-gfb7d21153.info Lines: 280 280 100.0 %
Date: 2022-12-01 09:37:31 Functions: 27 27 100.0 %
Branches: 129 147 87.8 %

           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                 :      23200 : STATIC void list_print(const mp_print_t *print, mp_obj_t o_in, mp_print_kind_t kind) {
      46                 :      23200 :     mp_obj_list_t *o = MP_OBJ_TO_PTR(o_in);
      47                 :      23200 :     const char *item_separator = ", ";
      48         [ +  + ]:      23200 :     if (!(MICROPY_PY_UJSON && kind == PRINT_JSON)) {
      49                 :            :         kind = PRINT_REPR;
      50                 :            :     } else {
      51                 :            :         #if MICROPY_PY_UJSON_SEPARATORS
      52                 :         98 :         item_separator = MP_PRINT_GET_EXT(print)->item_separator;
      53                 :            :         #endif
      54                 :            :     }
      55                 :      23200 :     mp_print_str(print, "[");
      56         [ +  + ]:      67937 :     for (size_t i = 0; i < o->len; i++) {
      57         [ +  + ]:      46708 :         if (i > 0) {
      58                 :      26634 :             mp_print_str(print, item_separator);
      59                 :            :         }
      60                 :      46708 :         mp_obj_print_helper(print, o->items[i], kind);
      61                 :            :     }
      62                 :      21229 :     mp_print_str(print, "]");
      63                 :      21229 : }
      64                 :            : 
      65                 :      19634 : STATIC mp_obj_t list_extend_from_iter(mp_obj_t list, mp_obj_t iterable) {
      66                 :      19634 :     mp_obj_t iter = mp_getiter(iterable, NULL);
      67                 :      19634 :     mp_obj_t item;
      68         [ +  + ]:     260788 :     while ((item = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
      69                 :     241158 :         mp_obj_list_append(list, item);
      70                 :            :     }
      71                 :      19620 :     return list;
      72                 :            : }
      73                 :            : 
      74                 :      19626 : 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                 :      19626 :     (void)type_in;
      76                 :      19626 :     mp_arg_check_num(n_args, n_kw, 0, 1, false);
      77                 :            : 
      78         [ +  + ]:      19626 :     switch (n_args) {
      79                 :         16 :         case 0:
      80                 :            :             // return a new, empty list
      81                 :         16 :             return mp_obj_new_list(0, NULL);
      82                 :            : 
      83                 :      19610 :         case 1:
      84                 :            :         default: {
      85                 :            :             // make list from iterable
      86                 :            :             // TODO: optimize list/tuple
      87                 :      19610 :             mp_obj_t list = mp_obj_new_list(0, NULL);
      88                 :      19610 :             return list_extend_from_iter(list, args[0]);
      89                 :            :         }
      90                 :            :     }
      91                 :            : }
      92                 :            : 
      93                 :     134125 : STATIC mp_obj_t list_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
      94                 :     134125 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
      95   [ +  +  +  + ]:     134125 :     switch (op) {
      96                 :     129430 :         case MP_UNARY_OP_BOOL:
      97         [ +  + ]:     129430 :             return mp_obj_new_bool(self->len != 0);
      98                 :       4655 :         case MP_UNARY_OP_LEN:
      99                 :       4655 :             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                 :       1116 : STATIC mp_obj_t list_binary_op(mp_binary_op_t op, mp_obj_t lhs, mp_obj_t rhs) {
     112                 :       1116 :     mp_obj_list_t *o = MP_OBJ_TO_PTR(lhs);
     113   [ +  +  +  +  :       1116 :     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                 :        394 :         case MP_BINARY_OP_MULTIPLY: {
     128                 :        394 :             mp_int_t n;
     129         [ +  + ]:        394 :             if (!mp_obj_get_int_maybe(rhs, &n)) {
     130                 :            :                 return MP_OBJ_NULL; // op not supported
     131                 :            :             }
     132         [ +  + ]:        390 :             if (n < 0) {
     133                 :         16 :                 n = 0;
     134                 :            :             }
     135                 :        390 :             mp_obj_list_t *s = list_new(o->len * n);
     136                 :        384 :             mp_seq_multiply(o->items, sizeof(*o->items), o->len, n, s->items);
     137                 :        384 :             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   [ +  -  +  + ]:        228 :             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                 :        224 :             mp_obj_list_t *another = MP_OBJ_TO_PTR(rhs);
     152                 :        224 :             bool res = mp_seq_cmp_objs(op, o->items, o->len, another->items, another->len);
     153         [ +  + ]:        224 :             return mp_obj_new_bool(res);
     154                 :            :         }
     155                 :            : 
     156                 :            :         default:
     157                 :            :             return MP_OBJ_NULL; // op not supported
     158                 :            :     }
     159                 :            : }
     160                 :            : 
     161                 :     417319 : STATIC mp_obj_t list_subscr(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
     162         [ +  + ]:     417319 :     if (value == MP_OBJ_NULL) {
     163                 :            :         // delete
     164                 :            :         #if MICROPY_PY_BUILTINS_SLICE
     165   [ -  +  -  +  :         22 :         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                 :          8 :         mp_obj_t args[2] = {self_in, index};
     182                 :          8 :         list_pop(2, args);
     183                 :          8 :         return mp_const_none;
     184         [ +  + ]:     417297 :     } else if (value == MP_OBJ_SENTINEL) {
     185                 :            :         // load
     186                 :     282359 :         mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
     187                 :            :         #if MICROPY_PY_BUILTINS_SLICE
     188   [ -  +  -  +  :     282359 :         if (mp_obj_is_type(index, &mp_type_slice)) {
          -  +  -  +  +  
                +  +  + ]
     189                 :       1156 :             mp_bound_slice_t slice;
     190         [ +  + ]:       1156 :             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                 :       1020 :             mp_obj_list_t *res = list_new(slice.stop - slice.start);
     194                 :       1016 :             mp_seq_copy(res->items, self->items + slice.start, res->len, mp_obj_t);
     195                 :       1016 :             return MP_OBJ_FROM_PTR(res);
     196                 :            :         }
     197                 :            :         #endif
     198                 :     281203 :         size_t index_val = mp_get_index(self->base.type, self->len, index, false);
     199                 :     280445 :         return self->items[index_val];
     200                 :            :     } else {
     201                 :            :         #if MICROPY_PY_BUILTINS_SLICE
     202   [ -  +  -  +  :     134938 :         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                 :     134864 :         mp_obj_list_store(self_in, index, value);
     233                 :     134864 :         return mp_const_none;
     234                 :            :     }
     235                 :            : }
     236                 :            : 
     237                 :       7558 : STATIC mp_obj_t list_getiter(mp_obj_t o_in, mp_obj_iter_buf_t *iter_buf) {
     238                 :       7558 :     return mp_obj_new_list_iterator(o_in, 0, iter_buf);
     239                 :            : }
     240                 :            : 
     241                 :     282731 : mp_obj_t mp_obj_list_append(mp_obj_t self_in, mp_obj_t arg) {
     242                 :     282731 :     mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
     243                 :     282731 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
     244         [ +  + ]:     282731 :     if (self->len >= self->alloc) {
     245                 :       6971 :         self->items = m_renew(mp_obj_t, self->items, self->alloc, self->alloc * 2);
     246                 :       6967 :         self->alloc *= 2;
     247                 :       6967 :         mp_seq_clear(self->items, self->len + 1, self->alloc, sizeof(*self->items));
     248                 :            :     }
     249                 :     282727 :     self->items[self->len++] = arg;
     250                 :     282727 :     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                 :        190 : STATIC mp_obj_t list_pop(size_t n_args, const mp_obj_t *args) {
     275                 :        190 :     mp_check_self(mp_obj_is_type(args[0], &mp_type_list));
     276                 :        190 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(args[0]);
     277         [ +  + ]:        190 :     if (self->len == 0) {
     278                 :          8 :         mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("pop from empty list"));
     279                 :            :     }
     280         [ +  + ]:        182 :     size_t index = mp_get_index(self->base.type, self->len, n_args == 1 ? MP_OBJ_NEW_SMALL_INT(-1) : args[1], false);
     281                 :        182 :     mp_obj_t ret = self->items[index];
     282                 :        182 :     self->len -= 1;
     283                 :        182 :     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                 :        182 :     self->items[self->len] = MP_OBJ_NULL;
     286   [ +  +  +  + ]:        182 :     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                 :        182 :     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                 :    6190413 :         for (;;) {
     300                 :    6187352 :             do {++h;
     301   [ +  +  +  +  :    6187352 :             } 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                 :    2065869 :             do {--t;
     303   [ +  +  +  +  :    2065869 :             } 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         [ +  + ]:      26290 :             if (h >= t) {
     305                 :            :                 break;
     306                 :            :             }
     307                 :       3061 :             mp_obj_t x = h[0];
     308                 :       3061 :             h[0] = t[0];
     309                 :       3061 :             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                 :       3555 :             mp_quicksort(head, t, key_fn, binop_less_result);
     317                 :       3555 :             head = h + 1;
     318                 :            :         } else {
     319                 :      19674 :             mp_quicksort(h + 1, tail, key_fn, binop_less_result);
     320                 :      19674 :             tail = t;
     321                 :            :         }
     322                 :            :     }
     323                 :      32666 : }
     324                 :            : 
     325                 :            : // TODO Python defines sort to be stable but ours is not
     326                 :      18781 : mp_obj_t mp_obj_list_sort(size_t n_args, const mp_obj_t *pos_args, mp_map_t *kw_args) {
     327                 :      18781 :     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                 :      18781 :     struct {
     334                 :            :         mp_arg_val_t key, reverse;
     335                 :            :     } args;
     336                 :      18781 :     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                 :      18773 :     mp_check_self(mp_obj_is_type(pos_args[0], &mp_type_list));
     340                 :      18773 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(pos_args[0]);
     341                 :            : 
     342         [ +  + ]:      18773 :     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                 :      18773 :     return mp_const_none;
     349                 :            : }
     350                 :            : 
     351                 :          8 : STATIC mp_obj_t list_clear(mp_obj_t self_in) {
     352                 :          8 :     mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
     353                 :          8 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
     354                 :          8 :     self->len = 0;
     355                 :          8 :     self->items = m_renew(mp_obj_t, self->items, self->alloc, LIST_MIN_ALLOC);
     356                 :          8 :     self->alloc = LIST_MIN_ALLOC;
     357                 :          8 :     mp_seq_clear(self->items, 0, self->alloc, sizeof(*self->items));
     358                 :          8 :     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                 :         16 : STATIC mp_obj_t list_insert(mp_obj_t self_in, mp_obj_t idx, mp_obj_t obj) {
     380                 :         16 :     mp_check_self(mp_obj_is_type(self_in, &mp_type_list));
     381                 :         16 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
     382                 :            :     // insert has its own strange index logic
     383                 :         16 :     mp_int_t index = MP_OBJ_SMALL_INT_VALUE(idx);
     384         [ +  + ]:         16 :     if (index < 0) {
     385                 :          8 :         index += self->len;
     386                 :            :     }
     387         [ +  + ]:          8 :     if (index < 0) {
     388                 :          4 :         index = 0;
     389                 :            :     }
     390         [ +  + ]:         16 :     if ((size_t)index > self->len) {
     391                 :          4 :         index = self->len;
     392                 :            :     }
     393                 :            : 
     394                 :         16 :     mp_obj_list_append(self_in, mp_const_none);
     395                 :            : 
     396         [ +  + ]:         52 :     for (mp_int_t i = self->len - 1; i > index; i--) {
     397                 :         36 :         self->items[i] = self->items[i - 1];
     398                 :            :     }
     399                 :         16 :     self->items[index] = obj;
     400                 :            : 
     401                 :         16 :     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                 :     677964 : void mp_obj_list_init(mp_obj_list_t *o, size_t n) {
     470                 :     677964 :     o->base.type = &mp_type_list;
     471                 :     677964 :     o->alloc = n < LIST_MIN_ALLOC ? LIST_MIN_ALLOC : n;
     472                 :     677964 :     o->len = n;
     473                 :     677964 :     o->items = m_new(mp_obj_t, o->alloc);
     474                 :     677776 :     mp_seq_clear(o->items, n, o->alloc, sizeof(*o->items));
     475                 :     677776 : }
     476                 :            : 
     477                 :     667915 : STATIC mp_obj_list_t *list_new(size_t n) {
     478                 :     667915 :     mp_obj_list_t *o = m_new_obj(mp_obj_list_t);
     479                 :     667993 :     mp_obj_list_init(o, n);
     480                 :     667782 :     return o;
     481                 :            : }
     482                 :            : 
     483                 :     666446 : mp_obj_t mp_obj_new_list(size_t n, mp_obj_t *items) {
     484                 :     666446 :     mp_obj_list_t *o = list_new(n);
     485         [ +  + ]:     666248 :     if (items != NULL) {
     486         [ +  + ]:    3178785 :         for (size_t i = 0; i < n; i++) {
     487                 :    2532984 :             o->items[i] = items[i];
     488                 :            :         }
     489                 :            :     }
     490                 :     666248 :     return MP_OBJ_FROM_PTR(o);
     491                 :            : }
     492                 :            : 
     493                 :      10688 : void mp_obj_list_get(mp_obj_t self_in, size_t *len, mp_obj_t **items) {
     494                 :      10688 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
     495                 :      10688 :     *len = self->len;
     496                 :      10688 :     *items = self->items;
     497                 :      10688 : }
     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                 :     134864 : void mp_obj_list_store(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
     507                 :     134864 :     mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
     508                 :     134864 :     size_t i = mp_get_index(self->base.type, self->len, index, false);
     509                 :     134864 :     self->items[i] = value;
     510                 :     134864 : }
     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                 :      48661 : STATIC mp_obj_t list_it_iternext(mp_obj_t self_in) {
     523                 :      48661 :     mp_obj_list_it_t *self = MP_OBJ_TO_PTR(self_in);
     524                 :      48661 :     mp_obj_list_t *list = MP_OBJ_TO_PTR(self->list);
     525         [ +  + ]:      48661 :     if (self->cur < list->len) {
     526                 :      41452 :         mp_obj_t o_out = list->items[self->cur];
     527                 :      41452 :         self->cur += 1;
     528                 :      41452 :         return o_out;
     529                 :            :     } else {
     530                 :            :         return MP_OBJ_STOP_ITERATION;
     531                 :            :     }
     532                 :            : }
     533                 :            : 
     534                 :       7558 : mp_obj_t mp_obj_new_list_iterator(mp_obj_t list, size_t cur, mp_obj_iter_buf_t *iter_buf) {
     535                 :       7558 :     assert(sizeof(mp_obj_list_it_t) <= sizeof(mp_obj_iter_buf_t));
     536                 :       7558 :     mp_obj_list_it_t *o = (mp_obj_list_it_t *)iter_buf;
     537                 :       7558 :     o->base.type = &mp_type_polymorph_iter;
     538                 :       7558 :     o->iternext = list_it_iternext;
     539                 :       7558 :     o->list = list;
     540                 :       7558 :     o->cur = cur;
     541                 :       7558 :     return MP_OBJ_FROM_PTR(o);
     542                 :            : }

Generated by: LCOV version 1.15-5-g462f71d