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 files changed, 54 insertions, 15 deletions

diff --git a/py/objdict.c b/py/objdict.c
index e97f30e7a..09a5b3212 100644
--- a/py/objdict.c
+++ b/py/objdict.c
@@ -32,6 +32,9 @@
 #include "py/runtime0.h"
 #include "py/runtime.h"
 #include "py/builtin.h"
+#include "py/objtype.h"
+
+#define MP_OBJ_IS_DICT_TYPE(o) (MP_OBJ_IS_OBJ(o) && ((mp_obj_base_t*)o)->type->make_new == dict_make_new)
 
 STATIC mp_obj_t dict_update(mp_uint_t n_args, const mp_obj_t *args, mp_map_t *kwargs);
 
@@ -58,6 +61,9 @@ STATIC void dict_print(void (*print)(void *env, const char *fmt, ...), void *env
     if (!(MICROPY_PY_UJSON && kind == PRINT_JSON)) {
         kind = PRINT_REPR;
     }
+    if (MICROPY_PY_COLLECTIONS_ORDEREDDICT && self->base.type != &mp_type_dict) {
+        print(env, "%s(", qstr_str(self->base.type->name));
+    }
     print(env, "{");
     mp_uint_t cur = 0;
     mp_map_elem_t *next = NULL;
@@ -71,11 +77,19 @@ STATIC void dict_print(void (*print)(void *env, const char *fmt, ...), void *env
         mp_obj_print_helper(print, env, next->value, kind);
     }
     print(env, "}");
+    if (MICROPY_PY_COLLECTIONS_ORDEREDDICT && self->base.type != &mp_type_dict) {
+        print(env, ")");
+    }
 }
 
 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) {
-    (void)type_in;
-    mp_obj_t dict = mp_obj_new_dict(0);
+    mp_obj_dict_t *dict = mp_obj_new_dict(0);
+    dict->base.type = type_in;
+    #if MICROPY_PY_COLLECTIONS_ORDEREDDICT
+    if (type_in == &mp_type_ordereddict) {
+        dict->map.is_ordered = 1;
+    }
+    #endif
     if (n_args > 0 || n_kw > 0) {
         mp_obj_t args2[2] = {dict, args[0]}; // args[0] is always valid, even if it's not a positional arg
         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) {
             return MP_BOOL(elem != NULL);
         }
         case MP_BINARY_OP_EQUAL: {
+            #if MICROPY_PY_COLLECTIONS_ORDEREDDICT
+            if (MP_UNLIKELY(MP_OBJ_IS_TYPE(lhs_in, &mp_type_ordereddict) && MP_OBJ_IS_TYPE(rhs_in, &mp_type_ordereddict))) {
+                //TODO: implement
+                return MP_OBJ_NULL;
+            } else
+            #endif
             if (MP_OBJ_IS_TYPE(rhs_in, &mp_type_dict)) {
                 mp_obj_dict_t *rhs = rhs_in;
                 if (o->map.used != rhs->map.used) {
@@ -199,7 +219,7 @@ STATIC mp_obj_t dict_getiter(mp_obj_t o_in) {
 /* dict methods                                                               */
 
 STATIC mp_obj_t dict_clear(mp_obj_t self_in) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
 
     mp_map_clear(&self->map);
@@ -209,12 +229,14 @@ STATIC mp_obj_t dict_clear(mp_obj_t self_in) {
 STATIC MP_DEFINE_CONST_FUN_OBJ_1(dict_clear_obj, dict_clear);
 
 STATIC mp_obj_t dict_copy(mp_obj_t self_in) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
     mp_obj_dict_t *other = mp_obj_new_dict(self->map.alloc);
+    other->base.type = self->base.type;
     other->map.used = self->map.used;
     other->map.all_keys_are_qstrs = self->map.all_keys_are_qstrs;
-    other->map.table_is_fixed_array = 0;
+    other->map.is_fixed = 0;
+    other->map.is_ordered = self->map.is_ordered;
     memcpy(other->map.table, self->map.table, self->map.alloc * sizeof(mp_map_elem_t));
     return other;
 }
@@ -276,7 +298,7 @@ STATIC mp_obj_t dict_get_helper(mp_map_t *self, mp_obj_t key, mp_obj_t deflt, mp
 
 STATIC mp_obj_t dict_get(mp_uint_t n_args, const mp_obj_t *args) {
     assert(2 <= n_args && n_args <= 3);
-    assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(args[0]));
 
     return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
                            args[1],
@@ -287,7 +309,7 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_get_obj, 2, 3, dict_get);
 
 STATIC mp_obj_t dict_pop(mp_uint_t n_args, const mp_obj_t *args) {
     assert(2 <= n_args && n_args <= 3);
-    assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(args[0]));
 
     return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
                            args[1],
@@ -299,7 +321,7 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_pop_obj, 2, 3, dict_pop);
 
 STATIC mp_obj_t dict_setdefault(mp_uint_t n_args, const mp_obj_t *args) {
     assert(2 <= n_args && n_args <= 3);
-    assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(args[0]));
 
     return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
                            args[1],
@@ -310,7 +332,7 @@ STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_setdefault_obj, 2, 3, dict_setde
 
 
 STATIC mp_obj_t dict_popitem(mp_obj_t self_in) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
     mp_uint_t cur = 0;
     mp_map_elem_t *next = dict_iter_next(self, &cur);
@@ -328,7 +350,7 @@ STATIC mp_obj_t dict_popitem(mp_obj_t self_in) {
 STATIC MP_DEFINE_CONST_FUN_OBJ_1(dict_popitem_obj, dict_popitem);
 
 STATIC mp_obj_t dict_update(mp_uint_t n_args, const mp_obj_t *args, mp_map_t *kwargs) {
-    assert(MP_OBJ_IS_TYPE(args[0], &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(args[0]));
     mp_obj_dict_t *self = args[0];
 
     mp_arg_check_num(n_args, kwargs->used, 1, 2, true);
@@ -336,7 +358,7 @@ STATIC mp_obj_t dict_update(mp_uint_t n_args, const mp_obj_t *args, mp_map_t *kw
     if (n_args == 2) {
         // given a positional argument
 
-        if (MP_OBJ_IS_TYPE(args[1], &mp_type_dict)) {
+        if (MP_OBJ_IS_DICT_TYPE(args[1])) {
             // update from other dictionary (make sure other is not self)
             if (args[1] != self) {
                 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
 }
 
 STATIC mp_obj_t dict_view(mp_obj_t self_in, mp_dict_view_kind_t kind) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
     return mp_obj_new_dict_view(self, kind);
 }
@@ -548,6 +570,23 @@ const mp_obj_type_t mp_type_dict = {
     .locals_dict = (mp_obj_t)&dict_locals_dict,
 };
 
+#if MICROPY_PY_COLLECTIONS_ORDEREDDICT
+STATIC const mp_obj_tuple_t ordereddict_base_tuple = {{&mp_type_tuple}, 1, {(mp_obj_t)&mp_type_dict}};
+
+const mp_obj_type_t mp_type_ordereddict = {
+    { &mp_type_type },
+    .name = MP_QSTR_OrderedDict,
+    .print = dict_print,
+    .make_new = dict_make_new,
+    .unary_op = dict_unary_op,
+    .binary_op = dict_binary_op,
+    .subscr = dict_subscr,
+    .getiter = dict_getiter,
+    .bases_tuple = (mp_obj_t)&ordereddict_base_tuple,
+    .locals_dict = (mp_obj_t)&dict_locals_dict,
+};
+#endif
+
 void mp_obj_dict_init(mp_obj_dict_t *dict, mp_uint_t n_args) {
     dict->base.type = &mp_type_dict;
     mp_map_init(&dict->map, n_args);
@@ -564,21 +603,21 @@ mp_uint_t mp_obj_dict_len(mp_obj_t self_in) {
 }
 
 mp_obj_t mp_obj_dict_store(mp_obj_t self_in, mp_obj_t key, mp_obj_t value) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
     mp_map_lookup(&self->map, key, MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)->value = value;
     return self_in;
 }
 
 mp_obj_t mp_obj_dict_delete(mp_obj_t self_in, mp_obj_t key) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
     dict_get_helper(&self->map, key, MP_OBJ_NULL, MP_MAP_LOOKUP_REMOVE_IF_FOUND);
     return self_in;
 }
 
 mp_map_t *mp_obj_dict_get_map(mp_obj_t self_in) {
-    assert(MP_OBJ_IS_TYPE(self_in, &mp_type_dict));
+    assert(MP_OBJ_IS_DICT_TYPE(self_in));
     mp_obj_dict_t *self = self_in;
     return &self->map;
 }