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
|
