Colin Hogben / micropython

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   micropython-repl

py/map.c@2:c89e95946844, 2016-04-16 (annotated)

Committer:
Colin Hogben
Date:
Sat Apr 16 22:43:41 2016 +0100
Revision:
2:c89e95946844
Parent:
0:5868e8752d44 
py: update to upstream master

Who changed what in which revision?

UserRevisionLine numberNew contents of line
pythontech 0:5868e8752d44 1 /*
pythontech 0:5868e8752d44 2 * This file is part of the Micro Python project, http://micropython.org/
pythontech 0:5868e8752d44 3 *
pythontech 0:5868e8752d44 4 * The MIT License (MIT)
pythontech 0:5868e8752d44 5 *
pythontech 0:5868e8752d44 6 * Copyright (c) 2013, 2014 Damien P. George
pythontech 0:5868e8752d44 7 *
pythontech 0:5868e8752d44 8 * Permission is hereby granted, free of charge, to any person obtaining a copy
pythontech 0:5868e8752d44 9 * of this software and associated documentation files (the "Software"), to deal
pythontech 0:5868e8752d44 10 * in the Software without restriction, including without limitation the rights
pythontech 0:5868e8752d44 11 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
pythontech 0:5868e8752d44 12 * copies of the Software, and to permit persons to whom the Software is
pythontech 0:5868e8752d44 13 * furnished to do so, subject to the following conditions:
pythontech 0:5868e8752d44 14 *
pythontech 0:5868e8752d44 15 * The above copyright notice and this permission notice shall be included in
pythontech 0:5868e8752d44 16 * all copies or substantial portions of the Software.
pythontech 0:5868e8752d44 17 *
pythontech 0:5868e8752d44 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
pythontech 0:5868e8752d44 19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
pythontech 0:5868e8752d44 20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
pythontech 0:5868e8752d44 21 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
pythontech 0:5868e8752d44 22 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
pythontech 0:5868e8752d44 23 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
pythontech 0:5868e8752d44 24 * THE SOFTWARE.
pythontech 0:5868e8752d44 25 */
pythontech 0:5868e8752d44 26
pythontech 0:5868e8752d44 27 #include <stdint.h>
pythontech 0:5868e8752d44 28 #include <stdlib.h>
pythontech 0:5868e8752d44 29 #include <string.h>
pythontech 0:5868e8752d44 30 #include <assert.h>
pythontech 0:5868e8752d44 31
pythontech 0:5868e8752d44 32 #include "py/mpconfig.h"
pythontech 0:5868e8752d44 33 #include "py/misc.h"
pythontech 0:5868e8752d44 34 #include "py/runtime0.h"
pythontech 0:5868e8752d44 35 #include "py/runtime.h"
pythontech 0:5868e8752d44 36
pythontech 0:5868e8752d44 37 // Fixed empty map. Useful when need to call kw-receiving functions
pythontech 0:5868e8752d44 38 // without any keywords from C, etc.
pythontech 0:5868e8752d44 39 const mp_map_t mp_const_empty_map = {
pythontech 0:5868e8752d44 40 .all_keys_are_qstrs = 0,
pythontech 0:5868e8752d44 41 .is_fixed = 1,
pythontech 0:5868e8752d44 42 .is_ordered = 1,
pythontech 0:5868e8752d44 43 .used = 0,
pythontech 0:5868e8752d44 44 .alloc = 0,
pythontech 0:5868e8752d44 45 .table = NULL,
pythontech 0:5868e8752d44 46 };
pythontech 0:5868e8752d44 47
Colin Hogben 2:c89e95946844 48 // This table of sizes is used to control the growth of hash tables.
Colin Hogben 2:c89e95946844 49 // The first set of sizes are chosen so the allocation fits exactly in a
Colin Hogben 2:c89e95946844 50 // 4-word GC block, and it's not so important for these small values to be
Colin Hogben 2:c89e95946844 51 // prime. The latter sizes are prime and increase at an increasing rate.
Colin Hogben 2:c89e95946844 52 STATIC uint16_t hash_allocation_sizes[] = {
Colin Hogben 2:c89e95946844 53 0, 2, 4, 6, 8, 10, 12, // +2
Colin Hogben 2:c89e95946844 54 17, 23, 29, 37, 47, 59, 73, // *1.25
Colin Hogben 2:c89e95946844 55 97, 127, 167, 223, 293, 389, 521, 691, 919, 1223, 1627, 2161, // *1.33
Colin Hogben 2:c89e95946844 56 3229, 4831, 7243, 10861, 16273, 24407, 36607, 54907, // *1.5
Colin Hogben 2:c89e95946844 57 };
pythontech 0:5868e8752d44 58
Colin Hogben 2:c89e95946844 59 STATIC mp_uint_t get_hash_alloc_greater_or_equal_to(mp_uint_t x) {
Colin Hogben 2:c89e95946844 60 for (size_t i = 0; i < MP_ARRAY_SIZE(hash_allocation_sizes); i++) {
Colin Hogben 2:c89e95946844 61 if (hash_allocation_sizes[i] >= x) {
Colin Hogben 2:c89e95946844 62 return hash_allocation_sizes[i];
pythontech 0:5868e8752d44 63 }
pythontech 0:5868e8752d44 64 }
pythontech 0:5868e8752d44 65 // ran out of primes in the table!
pythontech 0:5868e8752d44 66 // return something sensible, at least make it odd
Colin Hogben 2:c89e95946844 67 return (x + x / 2) | 1;
pythontech 0:5868e8752d44 68 }
pythontech 0:5868e8752d44 69
pythontech 0:5868e8752d44 70 /******************************************************************************/
pythontech 0:5868e8752d44 71 /* map */
pythontech 0:5868e8752d44 72
pythontech 0:5868e8752d44 73 void mp_map_init(mp_map_t *map, mp_uint_t n) {
pythontech 0:5868e8752d44 74 if (n == 0) {
pythontech 0:5868e8752d44 75 map->alloc = 0;
pythontech 0:5868e8752d44 76 map->table = NULL;
pythontech 0:5868e8752d44 77 } else {
pythontech 0:5868e8752d44 78 map->alloc = n;
pythontech 0:5868e8752d44 79 map->table = m_new0(mp_map_elem_t, map->alloc);
pythontech 0:5868e8752d44 80 }
pythontech 0:5868e8752d44 81 map->used = 0;
pythontech 0:5868e8752d44 82 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 83 map->is_fixed = 0;
pythontech 0:5868e8752d44 84 map->is_ordered = 0;
pythontech 0:5868e8752d44 85 }
pythontech 0:5868e8752d44 86
pythontech 0:5868e8752d44 87 void mp_map_init_fixed_table(mp_map_t *map, mp_uint_t n, const mp_obj_t *table) {
pythontech 0:5868e8752d44 88 map->alloc = n;
pythontech 0:5868e8752d44 89 map->used = n;
pythontech 0:5868e8752d44 90 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 91 map->is_fixed = 1;
pythontech 0:5868e8752d44 92 map->is_ordered = 1;
pythontech 0:5868e8752d44 93 map->table = (mp_map_elem_t*)table;
pythontech 0:5868e8752d44 94 }
pythontech 0:5868e8752d44 95
pythontech 0:5868e8752d44 96 mp_map_t *mp_map_new(mp_uint_t n) {
pythontech 0:5868e8752d44 97 mp_map_t *map = m_new(mp_map_t, 1);
pythontech 0:5868e8752d44 98 mp_map_init(map, n);
pythontech 0:5868e8752d44 99 return map;
pythontech 0:5868e8752d44 100 }
pythontech 0:5868e8752d44 101
pythontech 0:5868e8752d44 102 // Differentiate from mp_map_clear() - semantics is different
pythontech 0:5868e8752d44 103 void mp_map_deinit(mp_map_t *map) {
pythontech 0:5868e8752d44 104 if (!map->is_fixed) {
pythontech 0:5868e8752d44 105 m_del(mp_map_elem_t, map->table, map->alloc);
pythontech 0:5868e8752d44 106 }
pythontech 0:5868e8752d44 107 map->used = map->alloc = 0;
pythontech 0:5868e8752d44 108 }
pythontech 0:5868e8752d44 109
pythontech 0:5868e8752d44 110 void mp_map_free(mp_map_t *map) {
pythontech 0:5868e8752d44 111 mp_map_deinit(map);
pythontech 0:5868e8752d44 112 m_del_obj(mp_map_t, map);
pythontech 0:5868e8752d44 113 }
pythontech 0:5868e8752d44 114
pythontech 0:5868e8752d44 115 void mp_map_clear(mp_map_t *map) {
pythontech 0:5868e8752d44 116 if (!map->is_fixed) {
pythontech 0:5868e8752d44 117 m_del(mp_map_elem_t, map->table, map->alloc);
pythontech 0:5868e8752d44 118 }
pythontech 0:5868e8752d44 119 map->alloc = 0;
pythontech 0:5868e8752d44 120 map->used = 0;
pythontech 0:5868e8752d44 121 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 122 map->is_fixed = 0;
pythontech 0:5868e8752d44 123 map->table = NULL;
pythontech 0:5868e8752d44 124 }
pythontech 0:5868e8752d44 125
pythontech 0:5868e8752d44 126 STATIC void mp_map_rehash(mp_map_t *map) {
pythontech 0:5868e8752d44 127 mp_uint_t old_alloc = map->alloc;
Colin Hogben 2:c89e95946844 128 mp_uint_t new_alloc = get_hash_alloc_greater_or_equal_to(map->alloc + 1);
pythontech 0:5868e8752d44 129 mp_map_elem_t *old_table = map->table;
pythontech 0:5868e8752d44 130 mp_map_elem_t *new_table = m_new0(mp_map_elem_t, new_alloc);
pythontech 0:5868e8752d44 131 // If we reach this point, table resizing succeeded, now we can edit the old map.
pythontech 0:5868e8752d44 132 map->alloc = new_alloc;
pythontech 0:5868e8752d44 133 map->used = 0;
pythontech 0:5868e8752d44 134 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 135 map->table = new_table;
pythontech 0:5868e8752d44 136 for (mp_uint_t i = 0; i < old_alloc; i++) {
pythontech 0:5868e8752d44 137 if (old_table[i].key != MP_OBJ_NULL && old_table[i].key != MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 138 mp_map_lookup(map, old_table[i].key, MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)->value = old_table[i].value;
pythontech 0:5868e8752d44 139 }
pythontech 0:5868e8752d44 140 }
pythontech 0:5868e8752d44 141 m_del(mp_map_elem_t, old_table, old_alloc);
pythontech 0:5868e8752d44 142 }
pythontech 0:5868e8752d44 143
pythontech 0:5868e8752d44 144 // MP_MAP_LOOKUP behaviour:
pythontech 0:5868e8752d44 145 // - returns NULL if not found, else the slot it was found in with key,value non-null
pythontech 0:5868e8752d44 146 // MP_MAP_LOOKUP_ADD_IF_NOT_FOUND behaviour:
pythontech 0:5868e8752d44 147 // - returns slot, with key non-null and value=MP_OBJ_NULL if it was added
pythontech 0:5868e8752d44 148 // MP_MAP_LOOKUP_REMOVE_IF_FOUND behaviour:
pythontech 0:5868e8752d44 149 // - returns NULL if not found, else the slot if was found in with key null and value non-null
pythontech 0:5868e8752d44 150 mp_map_elem_t *mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t lookup_kind) {
pythontech 0:5868e8752d44 151
pythontech 0:5868e8752d44 152 if (map->is_fixed && lookup_kind != MP_MAP_LOOKUP) {
pythontech 0:5868e8752d44 153 // can't add/remove from a fixed array
pythontech 0:5868e8752d44 154 return NULL;
pythontech 0:5868e8752d44 155 }
pythontech 0:5868e8752d44 156
pythontech 0:5868e8752d44 157 // Work out if we can compare just pointers
pythontech 0:5868e8752d44 158 bool compare_only_ptrs = map->all_keys_are_qstrs;
pythontech 0:5868e8752d44 159 if (compare_only_ptrs) {
pythontech 0:5868e8752d44 160 if (MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 161 // Index is a qstr, so can just do ptr comparison.
pythontech 0:5868e8752d44 162 } else if (MP_OBJ_IS_TYPE(index, &mp_type_str)) {
pythontech 0:5868e8752d44 163 // Index is a non-interned string.
pythontech 0:5868e8752d44 164 // We can either intern the string, or force a full equality comparison.
pythontech 0:5868e8752d44 165 // We chose the latter, since interning costs time and potentially RAM,
pythontech 0:5868e8752d44 166 // and it won't necessarily benefit subsequent calls because these calls
pythontech 0:5868e8752d44 167 // most likely won't pass the newly-interned string.
pythontech 0:5868e8752d44 168 compare_only_ptrs = false;
pythontech 0:5868e8752d44 169 } else if (lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 170 // If we are not adding, then we can return straight away a failed
pythontech 0:5868e8752d44 171 // lookup because we know that the index will never be found.
pythontech 0:5868e8752d44 172 return NULL;
pythontech 0:5868e8752d44 173 }
pythontech 0:5868e8752d44 174 }
pythontech 0:5868e8752d44 175
pythontech 0:5868e8752d44 176 // if the map is an ordered array then we must do a brute force linear search
pythontech 0:5868e8752d44 177 if (map->is_ordered) {
pythontech 0:5868e8752d44 178 for (mp_map_elem_t *elem = &map->table[0], *top = &map->table[map->used]; elem < top; elem++) {
pythontech 0:5868e8752d44 179 if (elem->key == index || (!compare_only_ptrs && mp_obj_equal(elem->key, index))) {
pythontech 0:5868e8752d44 180 if (MP_UNLIKELY(lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND)) {
pythontech 0:5868e8752d44 181 elem->key = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 182 // keep elem->value so that caller can access it if needed
pythontech 0:5868e8752d44 183 }
pythontech 0:5868e8752d44 184 return elem;
pythontech 0:5868e8752d44 185 }
pythontech 0:5868e8752d44 186 }
pythontech 0:5868e8752d44 187 if (MP_LIKELY(lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)) {
pythontech 0:5868e8752d44 188 return NULL;
pythontech 0:5868e8752d44 189 }
pythontech 0:5868e8752d44 190 // TODO shrink array down over any previously-freed slots
pythontech 0:5868e8752d44 191 if (map->used == map->alloc) {
pythontech 0:5868e8752d44 192 // TODO: Alloc policy
pythontech 0:5868e8752d44 193 map->alloc += 4;
pythontech 0:5868e8752d44 194 map->table = m_renew(mp_map_elem_t, map->table, map->used, map->alloc);
pythontech 0:5868e8752d44 195 mp_seq_clear(map->table, map->used, map->alloc, sizeof(*map->table));
pythontech 0:5868e8752d44 196 }
pythontech 0:5868e8752d44 197 mp_map_elem_t *elem = map->table + map->used++;
pythontech 0:5868e8752d44 198 elem->key = index;
pythontech 0:5868e8752d44 199 if (!MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 200 map->all_keys_are_qstrs = 0;
pythontech 0:5868e8752d44 201 }
pythontech 0:5868e8752d44 202 return elem;
pythontech 0:5868e8752d44 203 }
pythontech 0:5868e8752d44 204
pythontech 0:5868e8752d44 205 // map is a hash table (not an ordered array), so do a hash lookup
pythontech 0:5868e8752d44 206
pythontech 0:5868e8752d44 207 if (map->alloc == 0) {
pythontech 0:5868e8752d44 208 if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 209 mp_map_rehash(map);
pythontech 0:5868e8752d44 210 } else {
pythontech 0:5868e8752d44 211 return NULL;
pythontech 0:5868e8752d44 212 }
pythontech 0:5868e8752d44 213 }
pythontech 0:5868e8752d44 214
pythontech 0:5868e8752d44 215 // get hash of index, with fast path for common case of qstr
pythontech 0:5868e8752d44 216 mp_uint_t hash;
pythontech 0:5868e8752d44 217 if (MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 218 hash = qstr_hash(MP_OBJ_QSTR_VALUE(index));
pythontech 0:5868e8752d44 219 } else {
pythontech 0:5868e8752d44 220 hash = MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, index));
pythontech 0:5868e8752d44 221 }
pythontech 0:5868e8752d44 222
pythontech 0:5868e8752d44 223 mp_uint_t pos = hash % map->alloc;
pythontech 0:5868e8752d44 224 mp_uint_t start_pos = pos;
pythontech 0:5868e8752d44 225 mp_map_elem_t *avail_slot = NULL;
pythontech 0:5868e8752d44 226 for (;;) {
pythontech 0:5868e8752d44 227 mp_map_elem_t *slot = &map->table[pos];
pythontech 0:5868e8752d44 228 if (slot->key == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 229 // found NULL slot, so index is not in table
pythontech 0:5868e8752d44 230 if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 231 map->used += 1;
pythontech 0:5868e8752d44 232 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 233 avail_slot = slot;
pythontech 0:5868e8752d44 234 }
pythontech 0:5868e8752d44 235 avail_slot->key = index;
pythontech 0:5868e8752d44 236 avail_slot->value = MP_OBJ_NULL;
pythontech 0:5868e8752d44 237 if (!MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 238 map->all_keys_are_qstrs = 0;
pythontech 0:5868e8752d44 239 }
pythontech 0:5868e8752d44 240 return avail_slot;
pythontech 0:5868e8752d44 241 } else {
pythontech 0:5868e8752d44 242 return NULL;
pythontech 0:5868e8752d44 243 }
pythontech 0:5868e8752d44 244 } else if (slot->key == MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 245 // found deleted slot, remember for later
pythontech 0:5868e8752d44 246 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 247 avail_slot = slot;
pythontech 0:5868e8752d44 248 }
pythontech 0:5868e8752d44 249 } else if (slot->key == index || (!compare_only_ptrs && mp_obj_equal(slot->key, index))) {
pythontech 0:5868e8752d44 250 // found index
pythontech 0:5868e8752d44 251 // Note: CPython does not replace the index; try x={True:'true'};x[1]='one';x
pythontech 0:5868e8752d44 252 if (lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
pythontech 0:5868e8752d44 253 // delete element in this slot
pythontech 0:5868e8752d44 254 map->used--;
pythontech 0:5868e8752d44 255 if (map->table[(pos + 1) % map->alloc].key == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 256 // optimisation if next slot is empty
pythontech 0:5868e8752d44 257 slot->key = MP_OBJ_NULL;
pythontech 0:5868e8752d44 258 } else {
pythontech 0:5868e8752d44 259 slot->key = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 260 }
pythontech 0:5868e8752d44 261 // keep slot->value so that caller can access it if needed
pythontech 0:5868e8752d44 262 }
pythontech 0:5868e8752d44 263 return slot;
pythontech 0:5868e8752d44 264 }
pythontech 0:5868e8752d44 265
pythontech 0:5868e8752d44 266 // not yet found, keep searching in this table
pythontech 0:5868e8752d44 267 pos = (pos + 1) % map->alloc;
pythontech 0:5868e8752d44 268
pythontech 0:5868e8752d44 269 if (pos == start_pos) {
pythontech 0:5868e8752d44 270 // search got back to starting position, so index is not in table
pythontech 0:5868e8752d44 271 if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 272 if (avail_slot != NULL) {
pythontech 0:5868e8752d44 273 // there was an available slot, so use that
pythontech 0:5868e8752d44 274 map->used++;
pythontech 0:5868e8752d44 275 avail_slot->key = index;
pythontech 0:5868e8752d44 276 avail_slot->value = MP_OBJ_NULL;
pythontech 0:5868e8752d44 277 if (!MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 278 map->all_keys_are_qstrs = 0;
pythontech 0:5868e8752d44 279 }
pythontech 0:5868e8752d44 280 return avail_slot;
pythontech 0:5868e8752d44 281 } else {
pythontech 0:5868e8752d44 282 // not enough room in table, rehash it
pythontech 0:5868e8752d44 283 mp_map_rehash(map);
pythontech 0:5868e8752d44 284 // restart the search for the new element
pythontech 0:5868e8752d44 285 start_pos = pos = hash % map->alloc;
pythontech 0:5868e8752d44 286 }
pythontech 0:5868e8752d44 287 } else {
pythontech 0:5868e8752d44 288 return NULL;
pythontech 0:5868e8752d44 289 }
pythontech 0:5868e8752d44 290 }
pythontech 0:5868e8752d44 291 }
pythontech 0:5868e8752d44 292 }
pythontech 0:5868e8752d44 293
pythontech 0:5868e8752d44 294 /******************************************************************************/
pythontech 0:5868e8752d44 295 /* set */
pythontech 0:5868e8752d44 296
pythontech 0:5868e8752d44 297 #if MICROPY_PY_BUILTINS_SET
pythontech 0:5868e8752d44 298
pythontech 0:5868e8752d44 299 void mp_set_init(mp_set_t *set, mp_uint_t n) {
pythontech 0:5868e8752d44 300 set->alloc = n;
pythontech 0:5868e8752d44 301 set->used = 0;
pythontech 0:5868e8752d44 302 set->table = m_new0(mp_obj_t, set->alloc);
pythontech 0:5868e8752d44 303 }
pythontech 0:5868e8752d44 304
pythontech 0:5868e8752d44 305 STATIC void mp_set_rehash(mp_set_t *set) {
pythontech 0:5868e8752d44 306 mp_uint_t old_alloc = set->alloc;
pythontech 0:5868e8752d44 307 mp_obj_t *old_table = set->table;
Colin Hogben 2:c89e95946844 308 set->alloc = get_hash_alloc_greater_or_equal_to(set->alloc + 1);
pythontech 0:5868e8752d44 309 set->used = 0;
pythontech 0:5868e8752d44 310 set->table = m_new0(mp_obj_t, set->alloc);
pythontech 0:5868e8752d44 311 for (mp_uint_t i = 0; i < old_alloc; i++) {
pythontech 0:5868e8752d44 312 if (old_table[i] != MP_OBJ_NULL && old_table[i] != MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 313 mp_set_lookup(set, old_table[i], MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
pythontech 0:5868e8752d44 314 }
pythontech 0:5868e8752d44 315 }
pythontech 0:5868e8752d44 316 m_del(mp_obj_t, old_table, old_alloc);
pythontech 0:5868e8752d44 317 }
pythontech 0:5868e8752d44 318
pythontech 0:5868e8752d44 319 mp_obj_t mp_set_lookup(mp_set_t *set, mp_obj_t index, mp_map_lookup_kind_t lookup_kind) {
pythontech 0:5868e8752d44 320 // Note: lookup_kind can be MP_MAP_LOOKUP_ADD_IF_NOT_FOUND_OR_REMOVE_IF_FOUND which
pythontech 0:5868e8752d44 321 // is handled by using bitwise operations.
pythontech 0:5868e8752d44 322
pythontech 0:5868e8752d44 323 if (set->alloc == 0) {
pythontech 0:5868e8752d44 324 if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 325 mp_set_rehash(set);
pythontech 0:5868e8752d44 326 } else {
pythontech 0:5868e8752d44 327 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 328 }
pythontech 0:5868e8752d44 329 }
pythontech 0:5868e8752d44 330 mp_uint_t hash = MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, index));
pythontech 0:5868e8752d44 331 mp_uint_t pos = hash % set->alloc;
pythontech 0:5868e8752d44 332 mp_uint_t start_pos = pos;
pythontech 0:5868e8752d44 333 mp_obj_t *avail_slot = NULL;
pythontech 0:5868e8752d44 334 for (;;) {
pythontech 0:5868e8752d44 335 mp_obj_t elem = set->table[pos];
pythontech 0:5868e8752d44 336 if (elem == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 337 // found NULL slot, so index is not in table
pythontech 0:5868e8752d44 338 if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 339 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 340 avail_slot = &set->table[pos];
pythontech 0:5868e8752d44 341 }
pythontech 0:5868e8752d44 342 set->used++;
pythontech 0:5868e8752d44 343 *avail_slot = index;
pythontech 0:5868e8752d44 344 return index;
pythontech 0:5868e8752d44 345 } else {
pythontech 0:5868e8752d44 346 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 347 }
pythontech 0:5868e8752d44 348 } else if (elem == MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 349 // found deleted slot, remember for later
pythontech 0:5868e8752d44 350 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 351 avail_slot = &set->table[pos];
pythontech 0:5868e8752d44 352 }
pythontech 0:5868e8752d44 353 } else if (mp_obj_equal(elem, index)) {
pythontech 0:5868e8752d44 354 // found index
pythontech 0:5868e8752d44 355 if (lookup_kind & MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
pythontech 0:5868e8752d44 356 // delete element
pythontech 0:5868e8752d44 357 set->used--;
pythontech 0:5868e8752d44 358 if (set->table[(pos + 1) % set->alloc] == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 359 // optimisation if next slot is empty
pythontech 0:5868e8752d44 360 set->table[pos] = MP_OBJ_NULL;
pythontech 0:5868e8752d44 361 } else {
pythontech 0:5868e8752d44 362 set->table[pos] = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 363 }
pythontech 0:5868e8752d44 364 }
pythontech 0:5868e8752d44 365 return elem;
pythontech 0:5868e8752d44 366 }
pythontech 0:5868e8752d44 367
pythontech 0:5868e8752d44 368 // not yet found, keep searching in this table
pythontech 0:5868e8752d44 369 pos = (pos + 1) % set->alloc;
pythontech 0:5868e8752d44 370
pythontech 0:5868e8752d44 371 if (pos == start_pos) {
pythontech 0:5868e8752d44 372 // search got back to starting position, so index is not in table
pythontech 0:5868e8752d44 373 if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 374 if (avail_slot != NULL) {
pythontech 0:5868e8752d44 375 // there was an available slot, so use that
pythontech 0:5868e8752d44 376 set->used++;
pythontech 0:5868e8752d44 377 *avail_slot = index;
pythontech 0:5868e8752d44 378 return index;
pythontech 0:5868e8752d44 379 } else {
pythontech 0:5868e8752d44 380 // not enough room in table, rehash it
pythontech 0:5868e8752d44 381 mp_set_rehash(set);
pythontech 0:5868e8752d44 382 // restart the search for the new element
pythontech 0:5868e8752d44 383 start_pos = pos = hash % set->alloc;
pythontech 0:5868e8752d44 384 }
pythontech 0:5868e8752d44 385 } else {
pythontech 0:5868e8752d44 386 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 387 }
pythontech 0:5868e8752d44 388 }
pythontech 0:5868e8752d44 389 }
pythontech 0:5868e8752d44 390 }
pythontech 0:5868e8752d44 391
pythontech 0:5868e8752d44 392 mp_obj_t mp_set_remove_first(mp_set_t *set) {
pythontech 0:5868e8752d44 393 for (mp_uint_t pos = 0; pos < set->alloc; pos++) {
pythontech 0:5868e8752d44 394 if (MP_SET_SLOT_IS_FILLED(set, pos)) {
pythontech 0:5868e8752d44 395 mp_obj_t elem = set->table[pos];
pythontech 0:5868e8752d44 396 // delete element
pythontech 0:5868e8752d44 397 set->used--;
pythontech 0:5868e8752d44 398 if (set->table[(pos + 1) % set->alloc] == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 399 // optimisation if next slot is empty
pythontech 0:5868e8752d44 400 set->table[pos] = MP_OBJ_NULL;
pythontech 0:5868e8752d44 401 } else {
pythontech 0:5868e8752d44 402 set->table[pos] = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 403 }
pythontech 0:5868e8752d44 404 return elem;
pythontech 0:5868e8752d44 405 }
pythontech 0:5868e8752d44 406 }
pythontech 0:5868e8752d44 407 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 408 }
pythontech 0:5868e8752d44 409
pythontech 0:5868e8752d44 410 void mp_set_clear(mp_set_t *set) {
pythontech 0:5868e8752d44 411 m_del(mp_obj_t, set->table, set->alloc);
pythontech 0:5868e8752d44 412 set->alloc = 0;
pythontech 0:5868e8752d44 413 set->used = 0;
pythontech 0:5868e8752d44 414 set->table = NULL;
pythontech 0:5868e8752d44 415 }
pythontech 0:5868e8752d44 416
pythontech 0:5868e8752d44 417 #endif // MICROPY_PY_BUILTINS_SET
pythontech 0:5868e8752d44 418
pythontech 0:5868e8752d44 419 #if defined(DEBUG_PRINT) && DEBUG_PRINT
pythontech 0:5868e8752d44 420 void mp_map_dump(mp_map_t *map) {
pythontech 0:5868e8752d44 421 for (mp_uint_t i = 0; i < map->alloc; i++) {
pythontech 0:5868e8752d44 422 if (map->table[i].key != NULL) {
pythontech 0:5868e8752d44 423 mp_obj_print(map->table[i].key, PRINT_REPR);
pythontech 0:5868e8752d44 424 } else {
pythontech 0:5868e8752d44 425 printf("(nil)");
pythontech 0:5868e8752d44 426 }
pythontech 0:5868e8752d44 427 printf(": %p\n", map->table[i].value);
pythontech 0:5868e8752d44 428 }
pythontech 0:5868e8752d44 429 printf("---\n");
pythontech 0:5868e8752d44 430 }
pythontech 0:5868e8752d44 431 #endif