LCOV - code coverage report
Current view: top level - py - objdeque.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.23.0-410-g82e69df33.info Lines: 109 110 99.1 %
Date: 2024-10-10 13:49:24 Functions: 11 11 100.0 %
Branches: 50 52 96.2 %

           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) 2018 Paul Sokolovsky
       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 <unistd.h> // for ssize_t
      28                 :            : 
      29                 :            : #include "py/runtime.h"
      30                 :            : 
      31                 :            : #if MICROPY_PY_COLLECTIONS_DEQUE
      32                 :            : 
      33                 :            : typedef struct _mp_obj_deque_t {
      34                 :            :     mp_obj_base_t base;
      35                 :            :     size_t alloc;
      36                 :            :     size_t i_get;
      37                 :            :     size_t i_put;
      38                 :            :     mp_obj_t *items;
      39                 :            :     uint32_t flags;
      40                 :            :     #define FLAG_CHECK_OVERFLOW 1
      41                 :            : } mp_obj_deque_t;
      42                 :            : 
      43                 :            : static mp_obj_t mp_obj_deque_append(mp_obj_t self_in, mp_obj_t arg);
      44                 :            : static mp_obj_t mp_obj_deque_extend(mp_obj_t self_in, mp_obj_t arg_in);
      45                 :            : #if MICROPY_PY_COLLECTIONS_DEQUE_ITER
      46                 :            : static mp_obj_t mp_obj_new_deque_it(mp_obj_t deque, mp_obj_iter_buf_t *iter_buf);
      47                 :            : #endif
      48                 :            : 
      49                 :         52 : static mp_obj_t deque_make_new(const mp_obj_type_t *type, size_t n_args, size_t n_kw, const mp_obj_t *args) {
      50                 :         52 :     mp_arg_check_num(n_args, n_kw, 2, 3, false);
      51                 :            : 
      52                 :            :     // Protect against -1 leading to zero-length allocation and bad array access
      53                 :         48 :     mp_int_t maxlen = mp_obj_get_int(args[1]);
      54         [ +  + ]:         48 :     if (maxlen < 0) {
      55                 :          4 :         mp_raise_ValueError(NULL);
      56                 :            :     }
      57                 :            : 
      58                 :         44 :     mp_obj_deque_t *o = mp_obj_malloc(mp_obj_deque_t, type);
      59                 :         44 :     o->alloc = maxlen + 1;
      60                 :         44 :     o->i_get = o->i_put = 0;
      61                 :         44 :     o->items = m_new0(mp_obj_t, o->alloc);
      62                 :            : 
      63         [ +  + ]:         44 :     if (n_args > 2) {
      64                 :          4 :         o->flags = mp_obj_get_int(args[2]);
      65                 :            :     }
      66                 :            : 
      67                 :         44 :     mp_obj_deque_extend(MP_OBJ_FROM_PTR(o), args[0]);
      68                 :            : 
      69                 :         44 :     return MP_OBJ_FROM_PTR(o);
      70                 :            : }
      71                 :            : 
      72                 :         96 : static size_t deque_len(mp_obj_deque_t *self) {
      73                 :         96 :     ssize_t len = self->i_put - self->i_get;
      74         [ +  + ]:         96 :     if (len < 0) {
      75                 :         24 :         len += self->alloc;
      76                 :            :     }
      77                 :         96 :     return len;
      78                 :            : }
      79                 :            : 
      80                 :         84 : static mp_obj_t deque_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
      81                 :         84 :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
      82   [ +  +  +  + ]:         84 :     switch (op) {
      83                 :         16 :         case MP_UNARY_OP_BOOL:
      84         [ +  + ]:         16 :             return mp_obj_new_bool(self->i_get != self->i_put);
      85                 :         60 :         case MP_UNARY_OP_LEN:
      86                 :         60 :             return MP_OBJ_NEW_SMALL_INT(deque_len(self));
      87                 :            : 
      88                 :            :         #if MICROPY_PY_SYS_GETSIZEOF
      89                 :          4 :         case MP_UNARY_OP_SIZEOF: {
      90                 :          4 :             size_t sz = sizeof(*self) + sizeof(mp_obj_t) * self->alloc;
      91                 :          4 :             return MP_OBJ_NEW_SMALL_INT(sz);
      92                 :            :         }
      93                 :            :         #endif
      94                 :            :         default:
      95                 :            :             return MP_OBJ_NULL; // op not supported
      96                 :            :     }
      97                 :            : }
      98                 :            : 
      99                 :        172 : static mp_obj_t mp_obj_deque_append(mp_obj_t self_in, mp_obj_t arg) {
     100                 :        172 :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
     101                 :            : 
     102                 :        172 :     size_t new_i_put = self->i_put + 1;
     103         [ +  + ]:        172 :     if (new_i_put == self->alloc) {
     104                 :         32 :         new_i_put = 0;
     105                 :            :     }
     106                 :            : 
     107   [ +  +  +  + ]:        172 :     if (self->flags & FLAG_CHECK_OVERFLOW && new_i_put == self->i_get) {
     108                 :          4 :         mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("full"));
     109                 :            :     }
     110                 :            : 
     111                 :        168 :     self->items[self->i_put] = arg;
     112                 :        168 :     self->i_put = new_i_put;
     113                 :            : 
     114         [ +  + ]:        168 :     if (self->i_get == new_i_put) {
     115         [ +  + ]:         36 :         if (++self->i_get == self->alloc) {
     116                 :          8 :             self->i_get = 0;
     117                 :            :         }
     118                 :            :     }
     119                 :            : 
     120                 :        168 :     return mp_const_none;
     121                 :            : }
     122                 :            : static MP_DEFINE_CONST_FUN_OBJ_2(deque_append_obj, mp_obj_deque_append);
     123                 :            : 
     124                 :         24 : static mp_obj_t mp_obj_deque_appendleft(mp_obj_t self_in, mp_obj_t arg) {
     125                 :         24 :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
     126                 :            : 
     127                 :         24 :     size_t new_i_get = self->i_get - 1;
     128         [ +  + ]:         24 :     if (self->i_get == 0) {
     129                 :          8 :         new_i_get = self->alloc - 1;
     130                 :            :     }
     131                 :            : 
     132   [ +  +  +  - ]:         24 :     if (self->flags & FLAG_CHECK_OVERFLOW && new_i_get == self->i_put) {
     133                 :          4 :         mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("full"));
     134                 :            :     }
     135                 :            : 
     136                 :         20 :     self->i_get = new_i_get;
     137                 :         20 :     self->items[self->i_get] = arg;
     138                 :            : 
     139                 :            :     // overwriting first element in deque
     140         [ +  + ]:         20 :     if (self->i_put == new_i_get) {
     141         [ +  + ]:         12 :         if (self->i_put == 0) {
     142                 :          4 :             self->i_put = self->alloc - 1;
     143                 :            :         } else {
     144                 :          8 :             self->i_put--;
     145                 :            :         }
     146                 :            :     }
     147                 :            : 
     148                 :         20 :     return mp_const_none;
     149                 :            : }
     150                 :            : static MP_DEFINE_CONST_FUN_OBJ_2(deque_appendleft_obj, mp_obj_deque_appendleft);
     151                 :            : 
     152                 :         48 : static mp_obj_t mp_obj_deque_extend(mp_obj_t self_in, mp_obj_t arg_in) {
     153                 :         48 :     mp_obj_iter_buf_t iter_buf;
     154                 :         48 :     mp_obj_t iter = mp_getiter(arg_in, &iter_buf);
     155                 :         48 :     mp_obj_t item;
     156         [ +  + ]:        104 :     while ((item = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
     157                 :         56 :         mp_obj_deque_append(self_in, item);
     158                 :            :     }
     159                 :         48 :     return mp_const_none;
     160                 :            : }
     161                 :            : static MP_DEFINE_CONST_FUN_OBJ_2(deque_extend_obj, mp_obj_deque_extend);
     162                 :            : 
     163                 :        116 : static mp_obj_t deque_popleft(mp_obj_t self_in) {
     164                 :        116 :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
     165                 :            : 
     166         [ +  + ]:        116 :     if (self->i_get == self->i_put) {
     167                 :         36 :         mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("empty"));
     168                 :            :     }
     169                 :            : 
     170                 :         80 :     mp_obj_t ret = self->items[self->i_get];
     171                 :         80 :     self->items[self->i_get] = MP_OBJ_NULL;
     172                 :            : 
     173         [ +  + ]:         80 :     if (++self->i_get == self->alloc) {
     174                 :         24 :         self->i_get = 0;
     175                 :            :     }
     176                 :            : 
     177                 :         80 :     return ret;
     178                 :            : }
     179                 :            : static MP_DEFINE_CONST_FUN_OBJ_1(deque_popleft_obj, deque_popleft);
     180                 :            : 
     181                 :         16 : static mp_obj_t deque_pop(mp_obj_t self_in) {
     182                 :         16 :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
     183                 :            : 
     184         [ +  + ]:         16 :     if (self->i_get == self->i_put) {
     185                 :          8 :         mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("empty"));
     186                 :            :     }
     187                 :            : 
     188         [ +  + ]:          8 :     if (self->i_put == 0) {
     189                 :          4 :         self->i_put = self->alloc - 1;
     190                 :            :     } else {
     191                 :          4 :         self->i_put--;
     192                 :            :     }
     193                 :            : 
     194                 :          8 :     mp_obj_t ret = self->items[self->i_put];
     195                 :          8 :     self->items[self->i_put] = MP_OBJ_NULL;
     196                 :            : 
     197                 :          8 :     return ret;
     198                 :            : }
     199                 :            : static MP_DEFINE_CONST_FUN_OBJ_1(deque_pop_obj, deque_pop);
     200                 :            : 
     201                 :            : #if MICROPY_PY_COLLECTIONS_DEQUE_SUBSCR
     202                 :         44 : static mp_obj_t deque_subscr(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
     203         [ +  + ]:         44 :     if (value == MP_OBJ_NULL) {
     204                 :            :         // delete not supported, fall back to mp_obj_subscr() error message
     205                 :            :         return MP_OBJ_NULL;
     206                 :            :     }
     207                 :         36 :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
     208                 :            : 
     209                 :         36 :     size_t offset = mp_get_index(self->base.type, deque_len(self), index, false);
     210                 :         20 :     size_t index_val = self->i_get + offset;
     211         [ -  + ]:         20 :     if (index_val > self->alloc) {
     212                 :          0 :         index_val -= self->alloc;
     213                 :            :     }
     214                 :            : 
     215         [ +  + ]:         20 :     if (value == MP_OBJ_SENTINEL) {
     216                 :            :         // load
     217                 :         16 :         return self->items[index_val];
     218                 :            :     } else {
     219                 :            :         // store into deque
     220                 :          4 :         self->items[index_val] = value;
     221                 :          4 :         return mp_const_none;
     222                 :            :     }
     223                 :            : }
     224                 :            : #endif
     225                 :            : 
     226                 :            : #if 0
     227                 :            : static mp_obj_t deque_clear(mp_obj_t self_in) {
     228                 :            :     mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
     229                 :            :     self->i_get = self->i_put = 0;
     230                 :            :     mp_seq_clear(self->items, 0, self->alloc, sizeof(*self->items));
     231                 :            :     return mp_const_none;
     232                 :            : }
     233                 :            : static MP_DEFINE_CONST_FUN_OBJ_1(deque_clear_obj, deque_clear);
     234                 :            : #endif
     235                 :            : 
     236                 :            : static const mp_rom_map_elem_t deque_locals_dict_table[] = {
     237                 :            :     { MP_ROM_QSTR(MP_QSTR_append), MP_ROM_PTR(&deque_append_obj) },
     238                 :            :     { MP_ROM_QSTR(MP_QSTR_appendleft), MP_ROM_PTR(&deque_appendleft_obj) },
     239                 :            :     { MP_ROM_QSTR(MP_QSTR_extend), MP_ROM_PTR(&deque_extend_obj) },
     240                 :            :     #if 0
     241                 :            :     { MP_ROM_QSTR(MP_QSTR_clear), MP_ROM_PTR(&deque_clear_obj) },
     242                 :            :     #endif
     243                 :            :     { MP_ROM_QSTR(MP_QSTR_pop), MP_ROM_PTR(&deque_pop_obj) },
     244                 :            :     { MP_ROM_QSTR(MP_QSTR_popleft), MP_ROM_PTR(&deque_popleft_obj) },
     245                 :            : };
     246                 :            : 
     247                 :            : static MP_DEFINE_CONST_DICT(deque_locals_dict, deque_locals_dict_table);
     248                 :            : 
     249                 :            : #if MICROPY_PY_COLLECTIONS_DEQUE_ITER
     250                 :            : #define DEQUE_TYPE_FLAGS MP_TYPE_FLAG_ITER_IS_GETITER
     251                 :            : #define DEQUE_TYPE_ITER iter, mp_obj_new_deque_it,
     252                 :            : #else
     253                 :            : #define DEQUE_TYPE_FLAGS MP_TYPE_FLAG_NONE
     254                 :            : #define DEQUE_TYPE_ITER
     255                 :            : #endif
     256                 :            : 
     257                 :            : #if MICROPY_PY_COLLECTIONS_DEQUE_SUBSCR
     258                 :            : #define DEQUE_TYPE_SUBSCR subscr, deque_subscr,
     259                 :            : #else
     260                 :            : #define DEQUE_TYPE_SUBSCR
     261                 :            : #endif
     262                 :            : 
     263                 :            : MP_DEFINE_CONST_OBJ_TYPE(
     264                 :            :     mp_type_deque,
     265                 :            :     MP_QSTR_deque,
     266                 :            :     DEQUE_TYPE_FLAGS,
     267                 :            :     make_new, deque_make_new,
     268                 :            :     unary_op, deque_unary_op,
     269                 :            :     DEQUE_TYPE_SUBSCR
     270                 :            :     DEQUE_TYPE_ITER
     271                 :            :     locals_dict, &deque_locals_dict
     272                 :            :     );
     273                 :            : 
     274                 :            : /******************************************************************************/
     275                 :            : /* deque iterator                                                             */
     276                 :            : 
     277                 :            : #if MICROPY_PY_COLLECTIONS_DEQUE_ITER
     278                 :            : 
     279                 :            : typedef struct _mp_obj_deque_it_t {
     280                 :            :     mp_obj_base_t base;
     281                 :            :     mp_fun_1_t iternext;
     282                 :            :     mp_obj_t deque;
     283                 :            :     size_t cur;
     284                 :            : } mp_obj_deque_it_t;
     285                 :            : 
     286                 :         48 : static mp_obj_t deque_it_iternext(mp_obj_t self_in) {
     287                 :         48 :     mp_obj_deque_it_t *self = MP_OBJ_TO_PTR(self_in);
     288                 :         48 :     mp_obj_deque_t *deque = MP_OBJ_TO_PTR(self->deque);
     289         [ +  + ]:         48 :     if (self->cur != deque->i_put) {
     290                 :         36 :         mp_obj_t o_out = deque->items[self->cur];
     291         [ +  + ]:         36 :         if (++self->cur == deque->alloc) {
     292                 :          4 :             self->cur = 0;
     293                 :            :         }
     294                 :         36 :         return o_out;
     295                 :            :     } else {
     296                 :            :         return MP_OBJ_STOP_ITERATION;
     297                 :            :     }
     298                 :            : }
     299                 :            : 
     300                 :         12 : static mp_obj_t mp_obj_new_deque_it(mp_obj_t deque, mp_obj_iter_buf_t *iter_buf) {
     301                 :         12 :     mp_obj_deque_t *deque_ = MP_OBJ_TO_PTR(deque);
     302                 :         12 :     size_t i_get = deque_->i_get;
     303                 :         12 :     assert(sizeof(mp_obj_deque_it_t) <= sizeof(mp_obj_iter_buf_t));
     304                 :         12 :     mp_obj_deque_it_t *o = (mp_obj_deque_it_t *)iter_buf;
     305                 :         12 :     o->base.type = &mp_type_polymorph_iter;
     306                 :         12 :     o->iternext = deque_it_iternext;
     307                 :         12 :     o->deque = deque;
     308                 :         12 :     o->cur = i_get;
     309                 :         12 :     return MP_OBJ_FROM_PTR(o);
     310                 :            : }
     311                 :            : 
     312                 :            : #endif
     313                 :            : 
     314                 :            : #endif // MICROPY_PY_COLLECTIONS_DEQUE

Generated by: LCOV version 1.15-5-g462f71d