Skip to content

Commit 0ef01d0

Browse files
Paul Sokolovskydpgeorge
Paul Sokolovsky
authored and
dpgeorge
committed
py: Implement core of OrderedDict type.
Given that there's already support for "fixed table" maps, which are essentially ordered maps, the implementation of OrderedDict just extends "fixed table" maps by adding an "is ordered" flag and add/remove operations, and reuses 95% of objdict code, just making methods tolerant to both dict and OrderedDict. Some things are missing so far, like CPython-compatible repr and comparison. OrderedDict is Disabled by default; enabled on unix and stmhal ports.
1 parent 1004535 commit 0ef01d0

File tree

9 files changed

+112
-31
lines changed

9 files changed

+112
-31
lines changed

‎py/map.c

Lines changed: 35 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@
2626

2727
#include <stdint.h>
2828
#include <stdlib.h>
29+
#include <string.h>
2930
#include <assert.h>
3031

3132
#include "py/mpconfig.h"
@@ -36,7 +37,8 @@
3637
// without any keywords from C, etc.
3738
const mp_map_t mp_const_empty_map = {
3839
.all_keys_are_qstrs = 0,
39-
.table_is_fixed_array = 1,
40+
.is_fixed = 1,
41+
.is_ordered = 1,
4042
.used = 0,
4143
.alloc = 0,
4244
.table = NULL,
@@ -70,14 +72,16 @@ void mp_map_init(mp_map_t *map, mp_uint_t n) {
7072
}
7173
map->used = 0;
7274
map->all_keys_are_qstrs = 1;
73-
map->table_is_fixed_array = 0;
75+
map->is_fixed = 0;
76+
map->is_ordered = 0;
7477
}
7578

7679
void mp_map_init_fixed_table(mp_map_t *map, mp_uint_t n, const mp_obj_t *table) {
7780
map->alloc = n;
7881
map->used = n;
7982
map->all_keys_are_qstrs = 1;
80-
map->table_is_fixed_array = 1;
83+
map->is_fixed = 1;
84+
map->is_ordered = 1;
8185
map->table = (mp_map_elem_t*)table;
8286
}
8387

@@ -89,7 +93,7 @@ mp_map_t *mp_map_new(mp_uint_t n) {
8993

9094
// Differentiate from mp_map_clear() - semantics is different
9195
void mp_map_deinit(mp_map_t *map) {
92-
if (!map->table_is_fixed_array) {
96+
if (!map->is_fixed) {
9397
m_del(mp_map_elem_t, map->table, map->alloc);
9498
}
9599
map->used = map->alloc = 0;
@@ -101,13 +105,13 @@ void mp_map_free(mp_map_t *map) {
101105
}
102106

103107
void mp_map_clear(mp_map_t *map) {
104-
if (!map->table_is_fixed_array) {
108+
if (!map->is_fixed) {
105109
m_del(mp_map_elem_t, map->table, map->alloc);
106110
}
107111
map->alloc = 0;
108112
map->used = 0;
109113
map->all_keys_are_qstrs = 1;
110-
map->table_is_fixed_array = 0;
114+
map->is_fixed = 0;
111115
map->table = NULL;
112116
}
113117

@@ -153,20 +157,40 @@ mp_map_elem_t* mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t
153157
}
154158
}
155159

156-
// if the map is a fixed array then we must do a brute force linear search
157-
if (map->table_is_fixed_array) {
158-
if (lookup_kind != MP_MAP_LOOKUP) {
160+
// if the map is an ordered array then we must do a brute force linear search
161+
if (map->is_ordered) {
162+
if (map->is_fixed && lookup_kind != MP_MAP_LOOKUP) {
163+
// can't add/remove from a fixed array
159164
return NULL;
160165
}
161166
for (mp_map_elem_t *elem = &map->table[0], *top = &map->table[map->used]; elem < top; elem++) {
162167
if (elem->key == index || (!compare_only_ptrs && mp_obj_equal(elem->key, index))) {
168+
if (MP_UNLIKELY(lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND)) {
169+
elem->key = MP_OBJ_SENTINEL;
170+
// keep elem->value so that caller can access it if needed
171+
}
163172
return elem;
164173
}
165174
}
166-
return NULL;
175+
if (MP_LIKELY(lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)) {
176+
return NULL;
177+
}
178+
// TODO shrink array down over any previously-freed slots
179+
if (map->used == map->alloc) {
180+
// TODO: Alloc policy
181+
map->alloc += 4;
182+
map->table = m_renew(mp_map_elem_t, map->table, map->used, map->alloc);
183+
mp_seq_clear(map->table, map->used, map->alloc, sizeof(*map->table));
184+
}
185+
mp_map_elem_t *elem = map->table + map->used++;
186+
elem->key = index;
187+
if (!MP_OBJ_IS_QSTR(index)) {
188+
map->all_keys_are_qstrs = 0;
189+
}
190+
return elem;
167191
}
168192

169-
// map is a hash table (not a fixed array), so do a hash lookup
193+
// map is a hash table (not an ordered array), so do a hash lookup
170194

171195
if (map->alloc == 0) {
172196
if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {

‎py/modcollections.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,9 @@
3131
STATIC const mp_map_elem_t mp_module_collections_globals_table[] = {
3232
{ MP_OBJ_NEW_QSTR(MP_QSTR___name__), MP_OBJ_NEW_QSTR(MP_QSTR__collections) },
3333
{ MP_OBJ_NEW_QSTR(MP_QSTR_namedtuple), (mp_obj_t)&mp_namedtuple_obj },
34+
#if MICROPY_PY_COLLECTIONS_ORDEREDDICT
35+
{ MP_OBJ_NEW_QSTR(MP_QSTR_OrderedDict), (mp_obj_t)&mp_type_ordereddict },
36+
#endif
3437
};
3538

3639
STATIC MP_DEFINE_CONST_DICT(mp_module_collections_globals, mp_module_collections_globals_table);

‎py/mpconfig.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -444,6 +444,11 @@ typedef double mp_float_t;
444444
#define MICROPY_PY_COLLECTIONS (1)
445445
#endif
446446

447+
// Whether to provide "collections.OrderedDict" type
448+
#ifndef MICROPY_PY_COLLECTIONS_ORDEREDDICT
449+
#define MICROPY_PY_COLLECTIONS_ORDEREDDICT (0)
450+
#endif
451+
447452
// Whether to provide "math" module
448453
#ifndef MICROPY_PY_MATH
449454
#define MICROPY_PY_MATH (1)

‎py/obj.h

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -109,7 +109,8 @@ typedef struct _mp_obj_base_t mp_obj_base_t;
109109
#define MP_DEFINE_CONST_MAP(map_name, table_name) \
110110
const mp_map_t map_name = { \
111111
.all_keys_are_qstrs = 1, \
112-
.table_is_fixed_array = 1, \
112+
.is_fixed = 1, \
113+
.is_ordered = 1, \
113114
.used = MP_ARRAY_SIZE(table_name), \
114115
.alloc = MP_ARRAY_SIZE(table_name), \
115116
.table = (mp_map_elem_t*)table_name, \
@@ -120,7 +121,8 @@ typedef struct _mp_obj_base_t mp_obj_base_t;
120121
.base = {&mp_type_dict}, \
121122
.map = { \
122123
.all_keys_are_qstrs = 1, \
123-
.table_is_fixed_array = 1, \
124+
.is_fixed = 1, \
125+
.is_ordered = 1, \
124126
.used = MP_ARRAY_SIZE(table_name), \
125127
.alloc = MP_ARRAY_SIZE(table_name), \
126128
.table = (mp_map_elem_t*)table_name, \
@@ -150,8 +152,9 @@ typedef struct _mp_map_elem_t {
150152

151153
typedef struct _mp_map_t {
152154
mp_uint_t all_keys_are_qstrs : 1;
153-
mp_uint_t table_is_fixed_array : 1;
154-
mp_uint_t used : (8 * sizeof(mp_uint_t) - 2);
155+
mp_uint_t is_fixed : 1; // a fixed array that can't be modified; must also be ordered
156+
mp_uint_t is_ordered : 1; // an ordered array
157+
mp_uint_t used : (8 * sizeof(mp_uint_t) - 3);
155158
mp_uint_t alloc;
156159
mp_map_elem_t *table;
157160
} mp_map_t;
@@ -327,6 +330,7 @@ extern const mp_obj_type_t mp_type_map; // map (the python builtin, not the dict
327330
extern const mp_obj_type_t mp_type_enumerate;
328331
extern const mp_obj_type_t mp_type_filter;
329332
extern const mp_obj_type_t mp_type_dict;
333+
extern const mp_obj_type_t mp_type_ordereddict;
330334
extern const mp_obj_type_t mp_type_range;
331335
extern const mp_obj_type_t mp_type_set;
332336
extern const mp_obj_type_t mp_type_frozenset;

‎py/objdict.c

Lines changed: 54 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,9 @@
3232
#include "py/runtime0.h"
3333
#include "py/runtime.h"
3434
#include "py/builtin.h"
35+
#include "py/objtype.h"
36+
37+
#define MP_OBJ_IS_DICT_TYPE(o) (MP_OBJ_IS_OBJ(o) && ((mp_obj_base_t*)o)->type->make_new == dict_make_new)
3538

3639
STATIC mp_obj_t dict_update(mp_uint_t n_args, const mp_obj_t *args, mp_map_t *kwargs);
3740

@@ -58,6 +61,9 @@ STATIC void dict_print(void (*print)(void *env, const char *fmt, ...), void *env
5861
if (!(MICROPY_PY_UJSON && kind == PRINT_JSON)) {
5962
kind = PRINT_REPR;
6063
}
64+
if (MICROPY_PY_COLLECTIONS_ORDEREDDICT && self->base.type != &mp_type_dict) {
65+
print(env, "%s(", qstr_str(self->base.type->name));
66+
}
6167
print(env, "{");
6268
mp_uint_t cur = 0;
6369
mp_map_elem_t *next = NULL;
@@ -71,11 +77,19 @@ STATIC void dict_print(void (*print)(void *env, const char *fmt, ...), void *env
7177
mp_obj_print_helper(print, env, next->value, kind);
7278
}
7379
print(env, "}");
80+
if (MICROPY_PY_COLLECTIONS_ORDEREDDICT && self->base.type != &mp_type_dict) {
81+
print(env, ")");
82+
}
7483
}
7584

7685
STATIC mp_obj_t dict_make_new(mp_obj_t type_in, mp_uint_t n_args, mp_uint_t n_kw, const mp_obj_t *args) {
77-
(void)type_in;
78-
mp_obj_t dict = mp_obj_new_dict(0);
86+
mp_obj_dict_t *dict = mp_obj_new_dict(0);
87+
dict->base.type = type_in;
88+
#if MICROPY_PY_COLLECTIONS_ORDEREDDICT
89+
if (type_in == &mp_type_ordereddict) {
90+
dict->map.is_ordered = 1;
91+
}
92+
#endif
7993
if (n_args > 0 || n_kw > 0) {
8094
mp_obj_t args2[2] = {dict, args[0]}; // args[0] is always valid, even if it's not a positional arg
8195
mp_map_t kwargs;
@@ -102,6 +116,12 @@ STATIC mp_obj_t dict_binary_op(mp_uint_t op, mp_obj_t lhs_in, mp_obj_t rhs_in) {
102116
return MP_BOOL(elem != NULL);
103117
}
104118
case MP_BINARY_OP_EQUAL: {
119+
#if MICROPY_PY_COLLECTIONS_ORDEREDDICT
120+
if (MP_UNLIKELY(MP_OBJ_IS_TYPE(lhs_in, &mp_type_ordereddict) && MP_OBJ_IS_TYPE(rhs_in, &mp_type_ordereddict))) {
121+
//TODO: implement
122+
return MP_OBJ_NULL;
123+
} else
124+
#endif
105125
if (MP_OBJ_IS_TYPE(rhs_in, &mp_type_dict)) {
106126
mp_obj_dict_t *rhs = rhs_in;
107127
if (o->map.used != rhs->map.used) {
@@ -199,7 +219,7 @@ STATIC mp_obj_t dict_getiter(mp_obj_t o_in) {
199219
/* dict methods */
200220

201221
STATIC mp_obj_t dict_clear(mp_obj_t self_in) {
202-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
222+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
203223
mp_obj_dict_t *self = self_in;
204224

205225
mp_map_clear(&self->map);
@@ -209,12 +229,14 @@ STATIC mp_obj_t dict_clear(mp_obj_t self_in) {
209229
STATIC MP_DEFINE_CONST_FUN_OBJ_1(dict_clear_obj, dict_clear);
210230

211231
STATIC mp_obj_t dict_copy(mp_obj_t self_in) {
212-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
232+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
213233
mp_obj_dict_t *self = self_in;
214234
mp_obj_dict_t *other = mp_obj_new_dict(self->map.alloc);
235+
other->base.type = self->base.type;
215236
other->map.used = self->map.used;
216237
other->map.all_keys_are_qstrs = self->map.all_keys_are_qstrs;
217-
other->map.table_is_fixed_array = 0;
238+
other->map.is_fixed = 0;
239+
other->map.is_ordered = self->map.is_ordered;
218240
memcpy(other->map.table, self->map.table, self->map.alloc * sizeof(mp_map_elem_t));
219241
return other;
220242
}
@@ -276,7 +298,7 @@ STATIC mp_obj_t dict_get_helper(mp_map_t *self, mp_obj_t key, mp_obj_t deflt, mp
276298

277299
STATIC mp_obj_t dict_get(mp_uint_t n_args, const mp_obj_t *args) {
278300
assert(2 <= n_args && n_args <= 3);
279-
assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
301+
assert(MP_OBJ_IS_DICT_TYPE(args[0]));
280302

281303
return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
282304
args[1],
@@ -287,7 +309,7 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_get_obj, 2, 3, dict_get);
287309

288310
STATIC mp_obj_t dict_pop(mp_uint_t n_args, const mp_obj_t *args) {
289311
assert(2 <= n_args && n_args <= 3);
290-
assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
312+
assert(MP_OBJ_IS_DICT_TYPE(args[0]));
291313

292314
return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
293315
args[1],
@@ -299,7 +321,7 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_pop_obj, 2, 3, dict_pop);
299321

300322
STATIC mp_obj_t dict_setdefault(mp_uint_t n_args, const mp_obj_t *args) {
301323
assert(2 <= n_args && n_args <= 3);
302-
assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
324+
assert(MP_OBJ_IS_DICT_TYPE(args[0]));
303325

304326
return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
305327
args[1],
@@ -310,7 +332,7 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_setdefault_obj, 2, 3, dict_setde
310332

311333

312334
STATIC mp_obj_t dict_popitem(mp_obj_t self_in) {
313-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
335+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
314336
mp_obj_dict_t *self = self_in;
315337
mp_uint_t cur = 0;
316338
mp_map_elem_t *next = dict_iter_next(self, &cur);
@@ -328,15 +350,15 @@ STATIC mp_obj_t dict_popitem(mp_obj_t self_in) {
328350
STATIC MP_DEFINE_CONST_FUN_OBJ_1(dict_popitem_obj, dict_popitem);
329351

330352
STATIC mp_obj_t dict_update(mp_uint_t n_args, const mp_obj_t *args, mp_map_t *kwargs) {
331-
assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
353+
assert(MP_OBJ_IS_DICT_TYPE(args[0]));
332354
mp_obj_dict_t *self = args[0];
333355

334356
mp_arg_check_num(n_args, kwargs->used, 1, 2, true);
335357

336358
if (n_args == 2) {
337359
// given a positional argument
338360

339-
if (MP_OBJ_IS_TYPE(args[1], &mp_type_dict)) {
361+
if (MP_OBJ_IS_DICT_TYPE(args[1])) {
340362
// update from other dictionary (make sure other is not self)
341363
if (args[1] != self) {
342364
mp_uint_t cur = 0;
@@ -494,7 +516,7 @@ STATIC mp_obj_t mp_obj_new_dict_view(mp_obj_dict_t *dict, mp_dict_view_kind_t ki
494516
}
495517

496518
STATIC mp_obj_t dict_view(mp_obj_t self_in, mp_dict_view_kind_t kind) {
497-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
519+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
498520
mp_obj_dict_t *self = self_in;
499521
return mp_obj_new_dict_view(self, kind);
500522
}
@@ -548,6 +570,23 @@ const mp_obj_type_t mp_type_dict = {
548570
.locals_dict = (mp_obj_t)&dict_locals_dict,
549571
};
550572

573+
#if MICROPY_PY_COLLECTIONS_ORDEREDDICT
574+
STATIC const mp_obj_tuple_t ordereddict_base_tuple = {{&mp_type_tuple}, 1, {(mp_obj_t)&mp_type_dict}};
575+
576+
const mp_obj_type_t mp_type_ordereddict = {
577+
{ &mp_type_type },
578+
.name = MP_QSTR_OrderedDict,
579+
.print = dict_print,
580+
.make_new = dict_make_new,
581+
.unary_op = dict_unary_op,
582+
.binary_op = dict_binary_op,
583+
.subscr = dict_subscr,
584+
.getiter = dict_getiter,
585+
.bases_tuple = (mp_obj_t)&ordereddict_base_tuple,
586+
.locals_dict = (mp_obj_t)&dict_locals_dict,
587+
};
588+
#endif
589+
551590
void mp_obj_dict_init(mp_obj_dict_t *dict, mp_uint_t n_args) {
552591
dict->base.type = &mp_type_dict;
553592
mp_map_init(&dict->map, n_args);
@@ -564,21 +603,21 @@ mp_uint_t mp_obj_dict_len(mp_obj_t self_in) {
564603
}
565604

566605
mp_obj_t mp_obj_dict_store(mp_obj_t self_in, mp_obj_t key, mp_obj_t value) {
567-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
606+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
568607
mp_obj_dict_t *self = self_in;
569608
mp_map_lookup(&self->map, key, MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)->value = value;
570609
return self_in;
571610
}
572611

573612
mp_obj_t mp_obj_dict_delete(mp_obj_t self_in, mp_obj_t key) {
574-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
613+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
575614
mp_obj_dict_t *self = self_in;
576615
dict_get_helper(&self->map, key, MP_OBJ_NULL, MP_MAP_LOOKUP_REMOVE_IF_FOUND);
577616
return self_in;
578617
}
579618

580619
mp_map_t *mp_obj_dict_get_map(mp_obj_t self_in) {
581-
assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
620+
assert(MP_OBJ_IS_DICT_TYPE(self_in));
582621
mp_obj_dict_t *self = self_in;
583622
return &self->map;
584623
}

‎py/objmodule.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -62,7 +62,7 @@ STATIC void module_load_attr(mp_obj_t self_in, qstr attr, mp_obj_t *dest) {
6262
STATIC bool module_store_attr(mp_obj_t self_in, qstr attr, mp_obj_t value) {
6363
mp_obj_module_t *self = self_in;
6464
mp_obj_dict_t *dict = self->globals;
65-
if (dict->map.table_is_fixed_array) {
65+
if (dict->map.is_fixed) {
6666
#if MICROPY_CAN_OVERRIDE_BUILTINS
6767
if (dict == &mp_module_builtins_globals) {
6868
if (MP_STATE_VM(mp_module_builtins_override_dict) == NULL) {

‎py/qstrdefs.h

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -148,6 +148,10 @@ Q(object)
148148

149149
Q(NoneType)
150150

151+
#if MICROPY_PY_COLLECTIONS_ORDEREDDICT
152+
Q(OrderedDict)
153+
#endif
154+
151155
Q(abs)
152156
Q(all)
153157
Q(any)

‎stmhal/mpconfigport.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -63,6 +63,7 @@
6363
#define MICROPY_PY_ARRAY_SLICE_ASSIGN (1)
6464
#define MICROPY_PY_SYS_EXIT (1)
6565
#define MICROPY_PY_SYS_STDFILES (1)
66+
#define MICROPY_PY_COLLECTIONS_ORDEREDDICT (1)
6667
#define MICROPY_PY_MATH_SPECIAL_FUNCTIONS (1)
6768
#define MICROPY_PY_CMATH (1)
6869
#define MICROPY_PY_IO (1)

‎unix/mpconfigport.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,7 @@
6868
#define MICROPY_PY_SYS_PLATFORM "linux"
6969
#define MICROPY_PY_SYS_MAXSIZE (1)
7070
#define MICROPY_PY_SYS_STDFILES (1)
71+
#define MICROPY_PY_COLLECTIONS_ORDEREDDICT (1)
7172
#define MICROPY_PY_MATH_SPECIAL_FUNCTIONS (1)
7273
#define MICROPY_PY_CMATH (1)
7374
#define MICROPY_PY_IO_FILEIO (1)

0 commit comments

Comments
 (0)