py/map: Store key/value in earliest possible slot in hash table.

dpgeorge · dpgeorge · commit 593faf14c470 · 2015-11-19T01:27:28.000Z
This change makes the code behave how it was supposed to work when first
written.  The avail_slot variable is set to the first free slot when
looking for a key (which would come from deleting an entry).  So it's
more efficient (for subsequent lookups) to insert a new key into such a
slot, rather than the very last slot that was searched.
diff --git a/py/map.c b/py/map.c
@@ -214,12 +214,12 @@ mp_map_elem_t *mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t
                 if (avail_slot == NULL) {
                     avail_slot = slot;
                 }
-                slot->key = index;
-                slot->value = MP_OBJ_NULL;
+                avail_slot->key = index;
+                avail_slot->value = MP_OBJ_NULL;
                 if (!MP_OBJ_IS_QSTR(index)) {
                     map->all_keys_are_qstrs = 0;
                 }
-                return slot;
+                return avail_slot;
             } else {
                 return NULL;
             }

Original file line number	Diff line number	Diff line change
`@@ -214,12 +214,12 @@ mp_map_elem_t mp_map_lookup(mp_map_t map, mp_obj_t index, mp_map_lookup_kind_t`
`214`	`214`	`if (avail_slot == NULL) {`
`215`	`215`	`avail_slot = slot;`
`216`	`216`	`}`
`217`		`- slot->key = index;`
`218`		`- slot->value = MP_OBJ_NULL;`
	`217`	`+ avail_slot->key = index;`
	`218`	`+ avail_slot->value = MP_OBJ_NULL;`
`219`	`219`	`if (!MP_OBJ_IS_QSTR(index)) {`
`220`	`220`	`map->all_keys_are_qstrs = 0;`
`221`	`221`	`}`
`222`		`- return slot;`
	`222`	`+ return avail_slot;`
`223`	`223`	`} else {`
`224`	`224`	`return NULL;`
`225`	`225`	`}`