Skip to content

Commit 6d6bc9e

Browse files
dpgeorgedpgeorge
committed
Merge pull request adafruit#108 from chipaca/dict_feats
Dictionary features that don't involve views or classmethods. First part of issue adafruit#99.
2 parents dfc0bac + baa6654 commit 6d6bc9e

12 files changed

Lines changed: 329 additions & 36 deletions

File tree

‎py/map.c‎

Lines changed: 48 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,8 @@
99
#include "map.h"
1010

1111
// approximatelly doubling primes; made with Mathematica command: Table[Prime[Floor[(1.7)^n]], {n, 3, 24}]
12-
static int doubling_primes[] = {7, 19, 43, 89, 179, 347, 647, 1229, 2297, 4243, 7829, 14347, 26017, 47149, 84947, 152443, 273253, 488399, 869927, 1547173, 2745121, 4861607};
12+
// prefixed with zero for the empty case.
13+
static int doubling_primes[] = {0, 7, 19, 43, 89, 179, 347, 647, 1229, 2297, 4243, 7829, 14347, 26017, 47149, 84947, 152443, 273253, 488399, 869927, 1547173, 2745121, 4861607};
1314

1415
int get_doubling_prime_greater_or_equal_to(int x) {
1516
for (int i = 0; i < sizeof(doubling_primes) / sizeof(int); i++) {
@@ -38,14 +39,46 @@ mp_map_t *mp_map_new(mp_map_kind_t kind, int n) {
3839
return map;
3940
}
4041

41-
mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_not_found) {
42+
void mp_map_clear(mp_map_t *map) {
43+
map->used = 0;
44+
machine_uint_t a = map->alloc;
45+
map->alloc = 0;
46+
map->table = m_renew(mp_map_elem_t, map->table, a, map->alloc);
47+
mp_map_elem_t nul = {NULL, NULL};
48+
for (uint i=0; i<map->alloc; i++) {
49+
map->table[i] = nul;
50+
}
51+
}
52+
53+
static void mp_map_rehash (mp_map_t *map) {
54+
int old_alloc = map->alloc;
55+
mp_map_elem_t *old_table = map->table;
56+
map->alloc = get_doubling_prime_greater_or_equal_to(map->alloc + 1);
57+
map->used = 0;
58+
map->table = m_new0(mp_map_elem_t, map->alloc);
59+
for (int i = 0; i < old_alloc; i++) {
60+
if (old_table[i].key != NULL) {
61+
mp_map_lookup_helper(map, old_table[i].key, true, false)->value = old_table[i].value;
62+
}
63+
}
64+
m_del(mp_map_elem_t, old_table, old_alloc);
65+
}
66+
67+
mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_not_found, bool remove_if_found) {
4268
bool is_map_mp_obj = (map->kind == MP_MAP_OBJ);
4369
machine_uint_t hash;
4470
if (is_map_mp_obj) {
4571
hash = mp_obj_hash(index);
4672
} else {
4773
hash = (machine_uint_t)index;
4874
}
75+
if (map->alloc == 0) {
76+
if (add_if_not_found) {
77+
mp_map_rehash(map);
78+
} else {
79+
return NULL;
80+
}
81+
}
4982
uint pos = hash % map->alloc;
5083
for (;;) {
5184
mp_map_elem_t *elem = &map->table[pos];
@@ -54,17 +87,7 @@ mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_n
5487
if (add_if_not_found) {
5588
if (map->used + 1 >= map->alloc) {
5689
// not enough room in table, rehash it
57-
int old_alloc = map->alloc;
58-
mp_map_elem_t *old_table = map->table;
59-
map->alloc = get_doubling_prime_greater_or_equal_to(map->alloc + 1);
60-
map->used = 0;
61-
map->table = m_new0(mp_map_elem_t, map->alloc);
62-
for (int i = 0; i < old_alloc; i++) {
63-
if (old_table[i].key != NULL) {
64-
mp_map_lookup_helper(map, old_table[i].key, true)->value = old_table[i].value;
65-
}
66-
}
67-
m_del(mp_map_elem_t, old_table, old_alloc);
90+
mp_map_rehash(map);
6891
// restart the search for the new element
6992
pos = hash % map->alloc;
7093
} else {
@@ -82,6 +105,16 @@ mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_n
82105
elem->key = index;
83106
}
84107
*/
108+
if (remove_if_found) {
109+
map->used--;
110+
/* this leaks this memory (but see dict_get_helper) */
111+
mp_map_elem_t *retval = m_new(mp_map_elem_t, 1);
112+
retval->key = elem->key;
113+
retval->value = elem->value;
114+
elem->key = NULL;
115+
elem->value = NULL;
116+
return retval;
117+
}
85118
return elem;
86119
} else {
87120
// not yet found, keep searching in this table
@@ -92,7 +125,7 @@ mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_n
92125

93126
mp_map_elem_t* mp_qstr_map_lookup(mp_map_t *map, qstr index, bool add_if_not_found) {
94127
mp_obj_t o = (mp_obj_t)(machine_uint_t)index;
95-
return mp_map_lookup_helper(map, o, add_if_not_found);
128+
return mp_map_lookup_helper(map, o, add_if_not_found, false);
96129
}
97130

98131
/******************************************************************************/
@@ -106,6 +139,7 @@ void mp_set_init(mp_set_t *set, int n) {
106139

107140
mp_obj_t mp_set_lookup(mp_set_t *set, mp_obj_t index, bool add_if_not_found) {
108141
int hash = mp_obj_hash(index);
142+
assert(set->alloc); /* FIXME: if alloc is ever 0 when doing a lookup, this'll fail: */
109143
int pos = hash % set->alloc;
110144
for (;;) {
111145
mp_obj_t elem = set->table[pos];

‎py/map.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,8 +26,9 @@ typedef struct _mp_set_t {
2626
int get_doubling_prime_greater_or_equal_to(int x);
2727
void mp_map_init(mp_map_t *map, mp_map_kind_t kind, int n);
2828
mp_map_t *mp_map_new(mp_map_kind_t kind, int n);
29-
mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_not_found);
29+
mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_not_found, bool remove_if_found);
3030
mp_map_elem_t* mp_qstr_map_lookup(mp_map_t *map, qstr index, bool add_if_not_found);
31+
void mp_map_clear(mp_map_t *map);
3132

3233
void mp_set_init(mp_set_t *set, int n);
3334
mp_obj_t mp_set_lookup(mp_set_t *set, mp_obj_t index, bool add_if_not_found);

‎py/objdict.c‎

Lines changed: 214 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -17,20 +17,23 @@ typedef struct _mp_obj_dict_t {
1717
mp_map_t map;
1818
} mp_obj_dict_t;
1919

20+
static mp_obj_t mp_obj_new_dict_iterator(mp_obj_dict_t *dict, int cur);
21+
static mp_map_elem_t *dict_it_iternext_elem(mp_obj_t self_in);
22+
2023
static void dict_print(void (*print)(void *env, const char *fmt, ...), void *env, mp_obj_t self_in) {
2124
mp_obj_dict_t *self = self_in;
2225
bool first = true;
2326
print(env, "{");
24-
for (int i = 0; i < self->map.alloc; i++) {
25-
if (self->map.table[i].key != NULL) {
26-
if (!first) {
27-
print(env, ", ");
28-
}
29-
first = false;
30-
mp_obj_print_helper(print, env, self->map.table[i].key);
31-
print(env, ": ");
32-
mp_obj_print_helper(print, env, self->map.table[i].value);
27+
mp_obj_t *dict_iter = mp_obj_new_dict_iterator(self, 0);
28+
mp_map_elem_t *next = NULL;
29+
while ((next = dict_it_iternext_elem(dict_iter)) != NULL) {
30+
if (!first) {
31+
print(env, ", ");
3332
}
33+
first = false;
34+
mp_obj_print_helper(print, env, next->key);
35+
print(env, ": ");
36+
mp_obj_print_helper(print, env, next->value);
3437
}
3538
print(env, "}");
3639
}
@@ -47,7 +50,7 @@ static mp_obj_t dict_binary_op(int op, mp_obj_t lhs_in, mp_obj_t rhs_in) {
4750
case RT_BINARY_OP_SUBSCR:
4851
{
4952
// dict load
50-
mp_map_elem_t *elem = mp_map_lookup_helper(&o->map, rhs_in, false);
53+
mp_map_elem_t *elem = mp_map_lookup_helper(&o->map, rhs_in, false, false);
5154
if (elem == NULL) {
5255
nlr_jump(mp_obj_new_exception_msg(MP_QSTR_KeyError, "<value>"));
5356
} else {
@@ -60,12 +63,211 @@ static mp_obj_t dict_binary_op(int op, mp_obj_t lhs_in, mp_obj_t rhs_in) {
6063
}
6164
}
6265

66+
67+
/******************************************************************************/
68+
/* dict iterator */
69+
70+
typedef struct _mp_obj_dict_it_t {
71+
mp_obj_base_t base;
72+
mp_obj_dict_t *dict;
73+
machine_uint_t cur;
74+
} mp_obj_dict_it_t;
75+
76+
static mp_map_elem_t *dict_it_iternext_elem(mp_obj_t self_in) {
77+
mp_obj_dict_it_t *self = self_in;
78+
machine_uint_t max = self->dict->map.alloc;
79+
mp_map_elem_t *table = self->dict->map.table;
80+
81+
for (int i = self->cur; i < max; i++) {
82+
if (table[i].key != NULL) {
83+
self->cur = i + 1;
84+
return &(table[i]);
85+
}
86+
}
87+
88+
return NULL;
89+
}
90+
91+
mp_obj_t dict_it_iternext(mp_obj_t self_in) {
92+
mp_map_elem_t *next = dict_it_iternext_elem(self_in);
93+
94+
if (next != NULL) {
95+
return next->key;
96+
} else {
97+
return mp_const_stop_iteration;
98+
}
99+
}
100+
101+
static const mp_obj_type_t dict_it_type = {
102+
{ &mp_const_type },
103+
"dict_iterator",
104+
.iternext = dict_it_iternext,
105+
};
106+
107+
static mp_obj_t mp_obj_new_dict_iterator(mp_obj_dict_t *dict, int cur) {
108+
mp_obj_dict_it_t *o = m_new_obj(mp_obj_dict_it_t);
109+
o->base.type = &dict_it_type;
110+
o->dict = dict;
111+
o->cur = cur;
112+
return o;
113+
}
114+
115+
static mp_obj_t dict_getiter(mp_obj_t o_in) {
116+
return mp_obj_new_dict_iterator(o_in, 0);
117+
}
118+
119+
/******************************************************************************/
120+
/* dict methods */
121+
122+
static mp_obj_t dict_clear(mp_obj_t self_in) {
123+
assert(MP_OBJ_IS_TYPE(self_in, &dict_type));
124+
mp_obj_dict_t *self = self_in;
125+
126+
mp_map_clear(&self->map);
127+
128+
return mp_const_none;
129+
}
130+
static MP_DEFINE_CONST_FUN_OBJ_1(dict_clear_obj, dict_clear);
131+
132+
static mp_obj_t dict_copy(mp_obj_t self_in) {
133+
assert(MP_OBJ_IS_TYPE(self_in, &dict_type));
134+
mp_obj_dict_t *self = self_in;
135+
mp_obj_dict_t *other = mp_obj_new_dict(self->map.alloc);
136+
other->map.used = self->map.used;
137+
memcpy(other->map.table, self->map.table, self->map.alloc * sizeof(mp_map_elem_t));
138+
return other;
139+
}
140+
static MP_DEFINE_CONST_FUN_OBJ_1(dict_copy_obj, dict_copy);
141+
142+
static mp_obj_t dict_get_helper(mp_map_t *self, mp_obj_t key, mp_obj_t deflt, bool pop, bool set) {
143+
mp_map_elem_t *elem = mp_map_lookup_helper(self, key, set, pop);
144+
mp_obj_t value;
145+
if (elem == NULL || elem->value == NULL) {
146+
if (deflt == NULL) {
147+
if (pop) {
148+
nlr_jump(mp_obj_new_exception_msg(MP_QSTR_KeyError, "<value>"));
149+
} else {
150+
value = mp_const_none;
151+
}
152+
} else {
153+
value = deflt;
154+
}
155+
} else {
156+
value = elem->value;
157+
if (pop) {
158+
/* catch the leak (from mp_map_lookup_helper) */
159+
m_free(elem, sizeof(mp_map_elem_t));
160+
}
161+
}
162+
if (set) {
163+
elem->value = value;
164+
}
165+
return value;
166+
}
167+
168+
static mp_obj_t dict_get(int n_args, const mp_obj_t *args) {
169+
assert(2 <= n_args && n_args <= 3);
170+
assert(MP_OBJ_IS_TYPE(args[0], &dict_type));
171+
172+
return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
173+
args[1],
174+
n_args == 3 ? args[2] : NULL,
175+
false, false);
176+
}
177+
static MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_get_obj, 2, 3, dict_get);
178+
179+
static mp_obj_t dict_pop(int n_args, const mp_obj_t *args) {
180+
assert(2 <= n_args && n_args <= 3);
181+
assert(MP_OBJ_IS_TYPE(args[0], &dict_type));
182+
183+
return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
184+
args[1],
185+
n_args == 3 ? args[2] : NULL,
186+
true, false);
187+
}
188+
static MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_pop_obj, 2, 3, dict_pop);
189+
190+
191+
static mp_obj_t dict_setdefault(int n_args, const mp_obj_t *args) {
192+
assert(2 <= n_args && n_args <= 3);
193+
assert(MP_OBJ_IS_TYPE(args[0], &dict_type));
194+
195+
return dict_get_helper(&((mp_obj_dict_t *)args[0])->map,
196+
args[1],
197+
n_args == 3 ? args[2] : NULL,
198+
false, true);
199+
}
200+
static MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(dict_setdefault_obj, 2, 3, dict_setdefault);
201+
202+
203+
static mp_obj_t dict_popitem(mp_obj_t self_in) {
204+
assert(MP_OBJ_IS_TYPE(self_in, &dict_type));
205+
mp_obj_dict_t *self = self_in;
206+
if (self->map.used == 0) {
207+
nlr_jump(mp_obj_new_exception_msg(MP_QSTR_KeyError, "popitem(): dictionary is empty"));
208+
}
209+
mp_obj_dict_it_t *iter = mp_obj_new_dict_iterator(self, 0);
210+
211+
mp_map_elem_t *next = dict_it_iternext_elem(iter);
212+
self->map.used--;
213+
mp_obj_t items[] = {next->key, next->value};
214+
next->key = NULL;
215+
next->value = NULL;
216+
mp_obj_t tuple = mp_obj_new_tuple(2, items);
217+
218+
return tuple;
219+
}
220+
static MP_DEFINE_CONST_FUN_OBJ_1(dict_popitem_obj, dict_popitem);
221+
222+
static mp_obj_t dict_update(mp_obj_t self_in, mp_obj_t iterable) {
223+
assert(MP_OBJ_IS_TYPE(self_in, &dict_type));
224+
mp_obj_dict_t *self = self_in;
225+
/* TODO: check for the "keys" method */
226+
mp_obj_t iter = rt_getiter(iterable);
227+
mp_obj_t next = NULL;
228+
while ((next = rt_iternext(iter)) != mp_const_stop_iteration) {
229+
mp_obj_t inneriter = rt_getiter(next);
230+
mp_obj_t key = rt_iternext(inneriter);
231+
mp_obj_t value = rt_iternext(inneriter);
232+
mp_obj_t stop = rt_iternext(inneriter);
233+
if (key == mp_const_stop_iteration
234+
|| value == mp_const_stop_iteration
235+
|| stop != mp_const_stop_iteration) {
236+
nlr_jump(mp_obj_new_exception_msg(
237+
MP_QSTR_ValueError,
238+
"dictionary update sequence has the wrong length"));
239+
} else {
240+
mp_map_lookup_helper(&self->map, key, true, false)->value = value;
241+
}
242+
}
243+
244+
return mp_const_none;
245+
}
246+
static MP_DEFINE_CONST_FUN_OBJ_2(dict_update_obj, dict_update);
247+
248+
249+
/******************************************************************************/
250+
/* dict constructors & etc */
251+
252+
static const mp_method_t dict_type_methods[] = {
253+
{ "clear", &dict_clear_obj },
254+
{ "copy", &dict_copy_obj },
255+
{ "get", &dict_get_obj },
256+
{ "pop", &dict_pop_obj },
257+
{ "popitem", &dict_popitem_obj },
258+
{ "setdefault", &dict_setdefault_obj },
259+
{ "update", &dict_update_obj },
260+
{ NULL, NULL }, // end-of-list sentinel
261+
};
262+
63263
const mp_obj_type_t dict_type = {
64264
{ &mp_const_type },
65265
"dict",
66266
.print = dict_print,
67267
.make_new = dict_make_new,
68268
.binary_op = dict_binary_op,
269+
.getiter = dict_getiter,
270+
.methods = dict_type_methods,
69271
};
70272

71273
mp_obj_t mp_obj_new_dict(int n_args) {
@@ -76,19 +278,12 @@ mp_obj_t mp_obj_new_dict(int n_args) {
76278
}
77279

78280
uint mp_obj_dict_len(mp_obj_t self_in) {
79-
mp_obj_dict_t *self = self_in;
80-
uint len = 0;
81-
for (int i = 0; i < self->map.alloc; i++) {
82-
if (self->map.table[i].key != NULL) {
83-
len += 1;
84-
}
85-
}
86-
return len;
281+
return ((mp_obj_dict_t *)self_in)->map.used;
87282
}
88283

89284
mp_obj_t mp_obj_dict_store(mp_obj_t self_in, mp_obj_t key, mp_obj_t value) {
90285
assert(MP_OBJ_IS_TYPE(self_in, &dict_type));
91286
mp_obj_dict_t *self = self_in;
92-
mp_map_lookup_helper(&self->map, key, true)->value = value;
287+
mp_map_lookup_helper(&self->map, key, true, false)->value = value;
93288
return self_in;
94289
}

0 commit comments

Comments
 (0)