Skip to content

Commit c035ade

Browse files
dhalbertdhalbert
authored
Merge pull request adafruit#9065 from SAK917/expand-objdeque-implementation
Expand objdeque implementation
2 parents ef685b1 + 4010f90 commit c035ade

8 files changed

Lines changed: 367 additions & 46 deletions

File tree

‎docs/library/collections.rst‎

Lines changed: 33 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -14,33 +14,58 @@ hold/accumulate various objects.
1414
Classes
1515
-------
1616

17-
.. class:: deque(iterable, maxlen[, flags])
17+
.. class:: deque(iterable, maxlen[, flag])
1818

19-
Deques (double-ended queues) are a list-like container that support O(1)
20-
appends and pops from either side of the deque. New deques are created
21-
using the following arguments:
19+
Deques (pronounced "deck" and short for "double-ended queue") are fixed length
20+
list-like containers that support O(1) appends and pops from either side of the
21+
deque. New deques are created using the following arguments:
2222

23-
- *iterable* must be the empty tuple, and the new deque is created empty.
23+
- *iterable* must be specified as an empty or non-empty iterable.
24+
If the iterable is empty, the new deque is created empty. If the
25+
iterable is not empty, the new deque is created with the items
26+
from the iterable.
2427

2528
- *maxlen* must be specified and the deque will be bounded to this
2629
maximum length. Once the deque is full, any new items added will
2730
discard items from the opposite end.
2831

29-
- The optional *flags* can be 1 to check for overflow when adding items.
32+
- *flag* is optional and can be set to 1 to check for overflow when
33+
adding items. If the deque is full and overflow checking is enabled,
34+
an IndexError will be raised when adding items.
3035

31-
As well as supporting ``bool`` and ``len``, deque objects have the following
32-
methods:
36+
Deque objects have the following methods:
3337

3438
.. method:: deque.append(x)
3539

3640
Add *x* to the right side of the deque.
3741
Raises IndexError if overflow checking is enabled and there is no more room left.
3842

43+
.. method:: deque.appendleft(x)
44+
45+
Add *x* to the left side of the deque.
46+
Raises IndexError if overflow checking is enabled and there is no more room left.
47+
48+
.. method:: deque.pop()
49+
50+
Remove and return an item from the right side of the deque.
51+
Raises IndexError if no items are present.
52+
3953
.. method:: deque.popleft()
4054

4155
Remove and return an item from the left side of the deque.
4256
Raises IndexError if no items are present.
4357

58+
.. method:: deque.extend(iterable)
59+
60+
Extend the right side of the deque by appending items from the *iterable* argument.
61+
Raises IndexError if overflow checking is enabled and there is no more room left
62+
for all of the items in *iterable*.
63+
64+
In addition to the above, deques support iteration, ``bool``, ``len(d)``, ``reversed(d)``,
65+
membership testing with the ``in`` operator, and subscript references like ``d[0]``.
66+
Note: Indexed access is O(1) at both ends but slows to O(n) in the middle of the deque,
67+
so for fast random access use a ``list`` instead.
68+
4469
.. function:: namedtuple(name, fields)
4570

4671
This is factory function to create a new namedtuple type with a specific

‎py/circuitpy_mpconfig.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -259,6 +259,8 @@ typedef long mp_off_t;
259259
#endif
260260
#ifndef MICROPY_PY_COLLECTIONS_DEQUE
261261
#define MICROPY_PY_COLLECTIONS_DEQUE (CIRCUITPY_FULL_BUILD)
262+
#define MICROPY_PY_COLLECTIONS_DEQUE_ITER (CIRCUITPY_FULL_BUILD)
263+
#define MICROPY_PY_COLLECTIONS_DEQUE_SUBSCR (CIRCUITPY_FULL_BUILD)
262264
#endif
263265
#define MICROPY_PY_RE_MATCH_GROUPS (CIRCUITPY_RE)
264266
#define MICROPY_PY_RE_MATCH_SPAN_START_END (CIRCUITPY_RE)

‎py/mpconfig.h‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1324,6 +1324,16 @@ typedef double mp_float_t;
13241324
#define MICROPY_PY_COLLECTIONS_DEQUE (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES)
13251325
#endif
13261326

1327+
// Whether "collections.deque" supports iteration
1328+
#ifndef MICROPY_PY_COLLECTIONS_DEQUE_ITER
1329+
#define MICROPY_PY_COLLECTIONS_DEQUE_ITER (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES)
1330+
#endif
1331+
1332+
// Whether "collections.deque" supports subscription
1333+
#ifndef MICROPY_PY_COLLECTIONS_DEQUE_SUBSCR
1334+
#define MICROPY_PY_COLLECTIONS_DEQUE_SUBSCR (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES)
1335+
#endif
1336+
13271337
// Whether to provide "collections.OrderedDict" type
13281338
#ifndef MICROPY_PY_COLLECTIONS_ORDEREDDICT
13291339
#define MICROPY_PY_COLLECTIONS_ORDEREDDICT (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES)

‎py/objdeque.c‎

Lines changed: 175 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -25,13 +25,11 @@
2525
*/
2626

2727
#include <unistd.h> // for ssize_t
28-
#include <string.h>
29-
30-
#include "py/mpconfig.h"
31-
#if MICROPY_PY_COLLECTIONS_DEQUE
3228

3329
#include "py/runtime.h"
3430

31+
#if MICROPY_PY_COLLECTIONS_DEQUE
32+
3533
typedef struct _mp_obj_deque_t {
3634
mp_obj_base_t base;
3735
size_t alloc;
@@ -42,14 +40,14 @@ typedef struct _mp_obj_deque_t {
4240
#define FLAG_CHECK_OVERFLOW 1
4341
} mp_obj_deque_t;
4442

45-
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) {
46-
mp_arg_check_num(n_args, n_kw, 2, 3, false);
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
4748

48-
/* Initialization from existing sequence is not supported, so an empty
49-
tuple must be passed as such. */
50-
if (args[0] != mp_const_empty_tuple) {
51-
mp_raise_ValueError(NULL);
52-
}
49+
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+
mp_arg_check_num(n_args, n_kw, 2, 3, false);
5351

5452
// Protect against -1 leading to zero-length allocation and bad array access
5553
mp_int_t maxlen = mp_obj_get_int(args[1]);
@@ -66,21 +64,27 @@ STATIC mp_obj_t deque_make_new(const mp_obj_type_t *type, size_t n_args, size_t
6664
o->flags = mp_obj_get_int(args[2]);
6765
}
6866

67+
mp_obj_deque_extend(MP_OBJ_FROM_PTR(o), args[0]);
68+
6969
return MP_OBJ_FROM_PTR(o);
7070
}
7171

72-
STATIC mp_obj_t deque_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
72+
static size_t deque_len(mp_obj_deque_t *self) {
73+
ssize_t len = self->i_put - self->i_get;
74+
if (len < 0) {
75+
len += self->alloc;
76+
}
77+
return len;
78+
}
79+
80+
static mp_obj_t deque_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
7381
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
7482
switch (op) {
7583
case MP_UNARY_OP_BOOL:
7684
return mp_obj_new_bool(self->i_get != self->i_put);
77-
case MP_UNARY_OP_LEN: {
78-
ssize_t len = self->i_put - self->i_get;
79-
if (len < 0) {
80-
len += self->alloc;
81-
}
82-
return MP_OBJ_NEW_SMALL_INT(len);
83-
}
85+
case MP_UNARY_OP_LEN:
86+
return MP_OBJ_NEW_SMALL_INT(deque_len(self));
87+
8488
#if MICROPY_PY_SYS_GETSIZEOF
8589
case MP_UNARY_OP_SIZEOF: {
8690
size_t sz = sizeof(*self) + sizeof(mp_obj_t) * self->alloc;
@@ -92,7 +96,7 @@ STATIC mp_obj_t deque_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
9296
}
9397
}
9498

95-
STATIC mp_obj_t mp_obj_deque_append(mp_obj_t self_in, mp_obj_t arg) {
99+
static mp_obj_t mp_obj_deque_append(mp_obj_t self_in, mp_obj_t arg) {
96100
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
97101

98102
size_t new_i_put = self->i_put + 1;
@@ -115,9 +119,48 @@ STATIC mp_obj_t mp_obj_deque_append(mp_obj_t self_in, mp_obj_t arg) {
115119

116120
return mp_const_none;
117121
}
118-
STATIC MP_DEFINE_CONST_FUN_OBJ_2(deque_append_obj, mp_obj_deque_append);
122+
static MP_DEFINE_CONST_FUN_OBJ_2(deque_append_obj, mp_obj_deque_append);
123+
124+
static mp_obj_t mp_obj_deque_appendleft(mp_obj_t self_in, mp_obj_t arg) {
125+
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
126+
127+
size_t new_i_get = self->i_get - 1;
128+
if (self->i_get == 0) {
129+
new_i_get = self->alloc - 1;
130+
}
131+
132+
if (self->flags & FLAG_CHECK_OVERFLOW && new_i_get == self->i_put) {
133+
mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("full"));
134+
}
135+
136+
self->i_get = new_i_get;
137+
self->items[self->i_get] = arg;
138+
139+
// overwriting first element in deque
140+
if (self->i_put == new_i_get) {
141+
if (self->i_put == 0) {
142+
self->i_put = self->alloc - 1;
143+
} else {
144+
self->i_put--;
145+
}
146+
}
147+
148+
return mp_const_none;
149+
}
150+
static MP_DEFINE_CONST_FUN_OBJ_2(deque_appendleft_obj, mp_obj_deque_appendleft);
119151

120-
STATIC mp_obj_t deque_popleft(mp_obj_t self_in) {
152+
static mp_obj_t mp_obj_deque_extend(mp_obj_t self_in, mp_obj_t arg_in) {
153+
mp_obj_iter_buf_t iter_buf;
154+
mp_obj_t iter = mp_getiter(arg_in, &iter_buf);
155+
mp_obj_t item;
156+
while ((item = mp_iternext(iter)) != MP_OBJ_STOP_ITERATION) {
157+
mp_obj_deque_append(self_in, item);
158+
}
159+
return mp_const_none;
160+
}
161+
static MP_DEFINE_CONST_FUN_OBJ_2(deque_extend_obj, mp_obj_deque_extend);
162+
163+
static mp_obj_t deque_popleft(mp_obj_t self_in) {
121164
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
122165

123166
if (self->i_get == self->i_put) {
@@ -133,35 +176,139 @@ STATIC mp_obj_t deque_popleft(mp_obj_t self_in) {
133176

134177
return ret;
135178
}
136-
STATIC MP_DEFINE_CONST_FUN_OBJ_1(deque_popleft_obj, deque_popleft);
179+
static MP_DEFINE_CONST_FUN_OBJ_1(deque_popleft_obj, deque_popleft);
180+
181+
static mp_obj_t deque_pop(mp_obj_t self_in) {
182+
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
183+
184+
if (self->i_get == self->i_put) {
185+
mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("empty"));
186+
}
187+
188+
if (self->i_put == 0) {
189+
self->i_put = self->alloc - 1;
190+
} else {
191+
self->i_put--;
192+
}
193+
194+
mp_obj_t ret = self->items[self->i_put];
195+
self->items[self->i_put] = MP_OBJ_NULL;
196+
197+
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+
static mp_obj_t deque_subscr(mp_obj_t self_in, mp_obj_t index, mp_obj_t value) {
203+
if (value == MP_OBJ_NULL) {
204+
// delete not supported, fall back to mp_obj_subscr() error message
205+
return MP_OBJ_NULL;
206+
}
207+
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
208+
209+
size_t offset = mp_get_index(self->base.type, deque_len(self), index, false);
210+
size_t index_val = self->i_get + offset;
211+
if (index_val > self->alloc) {
212+
index_val -= self->alloc;
213+
}
214+
215+
if (value == MP_OBJ_SENTINEL) {
216+
// load
217+
return self->items[index_val];
218+
} else {
219+
// store into deque
220+
self->items[index_val] = value;
221+
return mp_const_none;
222+
}
223+
}
224+
#endif
137225

138226
#if 0
139-
STATIC mp_obj_t deque_clear(mp_obj_t self_in) {
227+
static mp_obj_t deque_clear(mp_obj_t self_in) {
140228
mp_obj_deque_t *self = MP_OBJ_TO_PTR(self_in);
141229
self->i_get = self->i_put = 0;
142230
mp_seq_clear(self->items, 0, self->alloc, sizeof(*self->items));
143231
return mp_const_none;
144232
}
145-
STATIC MP_DEFINE_CONST_FUN_OBJ_1(deque_clear_obj, deque_clear);
233+
static MP_DEFINE_CONST_FUN_OBJ_1(deque_clear_obj, deque_clear);
146234
#endif
147235

148-
STATIC const mp_rom_map_elem_t deque_locals_dict_table[] = {
236+
static const mp_rom_map_elem_t deque_locals_dict_table[] = {
149237
{ 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) },
150240
#if 0
151241
{ MP_ROM_QSTR(MP_QSTR_clear), MP_ROM_PTR(&deque_clear_obj) },
152242
#endif
243+
{ MP_ROM_QSTR(MP_QSTR_pop), MP_ROM_PTR(&deque_pop_obj) },
153244
{ MP_ROM_QSTR(MP_QSTR_popleft), MP_ROM_PTR(&deque_popleft_obj) },
154245
};
155246

156-
STATIC MP_DEFINE_CONST_DICT(deque_locals_dict, deque_locals_dict_table);
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
157262

158263
MP_DEFINE_CONST_OBJ_TYPE(
159264
mp_type_deque,
160265
MP_QSTR_deque,
161-
MP_TYPE_FLAG_NONE,
266+
MP_TYPE_FLAG_ITER_IS_GETITER,
162267
make_new, deque_make_new,
163268
unary_op, deque_unary_op,
269+
DEQUE_TYPE_SUBSCR
270+
DEQUE_TYPE_ITER
164271
locals_dict, &deque_locals_dict
165272
);
166273

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+
static mp_obj_t deque_it_iternext(mp_obj_t self_in) {
287+
mp_obj_deque_it_t *self = MP_OBJ_TO_PTR(self_in);
288+
mp_obj_deque_t *deque = MP_OBJ_TO_PTR(self->deque);
289+
if (self->cur != deque->i_put) {
290+
mp_obj_t o_out = deque->items[self->cur];
291+
if (++self->cur == deque->alloc) {
292+
self->cur = 0;
293+
}
294+
return o_out;
295+
} else {
296+
return MP_OBJ_STOP_ITERATION;
297+
}
298+
}
299+
300+
static mp_obj_t mp_obj_new_deque_it(mp_obj_t deque, mp_obj_iter_buf_t *iter_buf) {
301+
mp_obj_deque_t *deque_ = MP_OBJ_TO_PTR(deque);
302+
size_t i_get = deque_->i_get;
303+
assert(sizeof(mp_obj_deque_it_t) <= sizeof(mp_obj_iter_buf_t));
304+
mp_obj_deque_it_t *o = (mp_obj_deque_it_t *)iter_buf;
305+
o->base.type = &mp_type_polymorph_iter;
306+
o->iternext = deque_it_iternext;
307+
o->deque = deque;
308+
o->cur = i_get;
309+
return MP_OBJ_FROM_PTR(o);
310+
}
311+
312+
#endif
313+
167314
#endif // MICROPY_PY_COLLECTIONS_DEQUE

0 commit comments

Comments
 (0)