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@0:5868e8752d44, 2016-04-16 (annotated)

Committer:
pythontech
Date:
Sat Apr 16 17:11:56 2016 +0000
Revision:
0:5868e8752d44
Child:
2:c89e95946844
Split off library from repl

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
pythontech 0:5868e8752d44 48 // approximatelly doubling primes; made with Mathematica command: Table[Prime[Floor[(1.7)^n]], {n, 3, 24}]
pythontech 0:5868e8752d44 49 // prefixed with zero for the empty case.
pythontech 0:5868e8752d44 50 STATIC uint32_t 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};
pythontech 0:5868e8752d44 51
pythontech 0:5868e8752d44 52 STATIC mp_uint_t get_doubling_prime_greater_or_equal_to(mp_uint_t x) {
pythontech 0:5868e8752d44 53 for (size_t i = 0; i < MP_ARRAY_SIZE(doubling_primes); i++) {
pythontech 0:5868e8752d44 54 if (doubling_primes[i] >= x) {
pythontech 0:5868e8752d44 55 return doubling_primes[i];
pythontech 0:5868e8752d44 56 }
pythontech 0:5868e8752d44 57 }
pythontech 0:5868e8752d44 58 // ran out of primes in the table!
pythontech 0:5868e8752d44 59 // return something sensible, at least make it odd
pythontech 0:5868e8752d44 60 return x | 1;
pythontech 0:5868e8752d44 61 }
pythontech 0:5868e8752d44 62
pythontech 0:5868e8752d44 63 /******************************************************************************/
pythontech 0:5868e8752d44 64 /* map */
pythontech 0:5868e8752d44 65
pythontech 0:5868e8752d44 66 void mp_map_init(mp_map_t *map, mp_uint_t n) {
pythontech 0:5868e8752d44 67 if (n == 0) {
pythontech 0:5868e8752d44 68 map->alloc = 0;
pythontech 0:5868e8752d44 69 map->table = NULL;
pythontech 0:5868e8752d44 70 } else {
pythontech 0:5868e8752d44 71 map->alloc = n;
pythontech 0:5868e8752d44 72 map->table = m_new0(mp_map_elem_t, map->alloc);
pythontech 0:5868e8752d44 73 }
pythontech 0:5868e8752d44 74 map->used = 0;
pythontech 0:5868e8752d44 75 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 76 map->is_fixed = 0;
pythontech 0:5868e8752d44 77 map->is_ordered = 0;
pythontech 0:5868e8752d44 78 }
pythontech 0:5868e8752d44 79
pythontech 0:5868e8752d44 80 void mp_map_init_fixed_table(mp_map_t *map, mp_uint_t n, const mp_obj_t *table) {
pythontech 0:5868e8752d44 81 map->alloc = n;
pythontech 0:5868e8752d44 82 map->used = n;
pythontech 0:5868e8752d44 83 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 84 map->is_fixed = 1;
pythontech 0:5868e8752d44 85 map->is_ordered = 1;
pythontech 0:5868e8752d44 86 map->table = (mp_map_elem_t*)table;
pythontech 0:5868e8752d44 87 }
pythontech 0:5868e8752d44 88
pythontech 0:5868e8752d44 89 mp_map_t *mp_map_new(mp_uint_t n) {
pythontech 0:5868e8752d44 90 mp_map_t *map = m_new(mp_map_t, 1);
pythontech 0:5868e8752d44 91 mp_map_init(map, n);
pythontech 0:5868e8752d44 92 return map;
pythontech 0:5868e8752d44 93 }
pythontech 0:5868e8752d44 94
pythontech 0:5868e8752d44 95 // Differentiate from mp_map_clear() - semantics is different
pythontech 0:5868e8752d44 96 void mp_map_deinit(mp_map_t *map) {
pythontech 0:5868e8752d44 97 if (!map->is_fixed) {
pythontech 0:5868e8752d44 98 m_del(mp_map_elem_t, map->table, map->alloc);
pythontech 0:5868e8752d44 99 }
pythontech 0:5868e8752d44 100 map->used = map->alloc = 0;
pythontech 0:5868e8752d44 101 }
pythontech 0:5868e8752d44 102
pythontech 0:5868e8752d44 103 void mp_map_free(mp_map_t *map) {
pythontech 0:5868e8752d44 104 mp_map_deinit(map);
pythontech 0:5868e8752d44 105 m_del_obj(mp_map_t, map);
pythontech 0:5868e8752d44 106 }
pythontech 0:5868e8752d44 107
pythontech 0:5868e8752d44 108 void mp_map_clear(mp_map_t *map) {
pythontech 0:5868e8752d44 109 if (!map->is_fixed) {
pythontech 0:5868e8752d44 110 m_del(mp_map_elem_t, map->table, map->alloc);
pythontech 0:5868e8752d44 111 }
pythontech 0:5868e8752d44 112 map->alloc = 0;
pythontech 0:5868e8752d44 113 map->used = 0;
pythontech 0:5868e8752d44 114 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 115 map->is_fixed = 0;
pythontech 0:5868e8752d44 116 map->table = NULL;
pythontech 0:5868e8752d44 117 }
pythontech 0:5868e8752d44 118
pythontech 0:5868e8752d44 119 STATIC void mp_map_rehash(mp_map_t *map) {
pythontech 0:5868e8752d44 120 mp_uint_t old_alloc = map->alloc;
pythontech 0:5868e8752d44 121 mp_uint_t new_alloc = get_doubling_prime_greater_or_equal_to(map->alloc + 1);
pythontech 0:5868e8752d44 122 mp_map_elem_t *old_table = map->table;
pythontech 0:5868e8752d44 123 mp_map_elem_t *new_table = m_new0(mp_map_elem_t, new_alloc);
pythontech 0:5868e8752d44 124 // If we reach this point, table resizing succeeded, now we can edit the old map.
pythontech 0:5868e8752d44 125 map->alloc = new_alloc;
pythontech 0:5868e8752d44 126 map->used = 0;
pythontech 0:5868e8752d44 127 map->all_keys_are_qstrs = 1;
pythontech 0:5868e8752d44 128 map->table = new_table;
pythontech 0:5868e8752d44 129 for (mp_uint_t i = 0; i < old_alloc; i++) {
pythontech 0:5868e8752d44 130 if (old_table[i].key != MP_OBJ_NULL && old_table[i].key != MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 131 mp_map_lookup(map, old_table[i].key, MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)->value = old_table[i].value;
pythontech 0:5868e8752d44 132 }
pythontech 0:5868e8752d44 133 }
pythontech 0:5868e8752d44 134 m_del(mp_map_elem_t, old_table, old_alloc);
pythontech 0:5868e8752d44 135 }
pythontech 0:5868e8752d44 136
pythontech 0:5868e8752d44 137 // MP_MAP_LOOKUP behaviour:
pythontech 0:5868e8752d44 138 // - returns NULL if not found, else the slot it was found in with key,value non-null
pythontech 0:5868e8752d44 139 // MP_MAP_LOOKUP_ADD_IF_NOT_FOUND behaviour:
pythontech 0:5868e8752d44 140 // - returns slot, with key non-null and value=MP_OBJ_NULL if it was added
pythontech 0:5868e8752d44 141 // MP_MAP_LOOKUP_REMOVE_IF_FOUND behaviour:
pythontech 0:5868e8752d44 142 // - returns NULL if not found, else the slot if was found in with key null and value non-null
pythontech 0:5868e8752d44 143 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 144
pythontech 0:5868e8752d44 145 if (map->is_fixed && lookup_kind != MP_MAP_LOOKUP) {
pythontech 0:5868e8752d44 146 // can't add/remove from a fixed array
pythontech 0:5868e8752d44 147 return NULL;
pythontech 0:5868e8752d44 148 }
pythontech 0:5868e8752d44 149
pythontech 0:5868e8752d44 150 // Work out if we can compare just pointers
pythontech 0:5868e8752d44 151 bool compare_only_ptrs = map->all_keys_are_qstrs;
pythontech 0:5868e8752d44 152 if (compare_only_ptrs) {
pythontech 0:5868e8752d44 153 if (MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 154 // Index is a qstr, so can just do ptr comparison.
pythontech 0:5868e8752d44 155 } else if (MP_OBJ_IS_TYPE(index, &mp_type_str)) {
pythontech 0:5868e8752d44 156 // Index is a non-interned string.
pythontech 0:5868e8752d44 157 // We can either intern the string, or force a full equality comparison.
pythontech 0:5868e8752d44 158 // We chose the latter, since interning costs time and potentially RAM,
pythontech 0:5868e8752d44 159 // and it won't necessarily benefit subsequent calls because these calls
pythontech 0:5868e8752d44 160 // most likely won't pass the newly-interned string.
pythontech 0:5868e8752d44 161 compare_only_ptrs = false;
pythontech 0:5868e8752d44 162 } else if (lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 163 // If we are not adding, then we can return straight away a failed
pythontech 0:5868e8752d44 164 // lookup because we know that the index will never be found.
pythontech 0:5868e8752d44 165 return NULL;
pythontech 0:5868e8752d44 166 }
pythontech 0:5868e8752d44 167 }
pythontech 0:5868e8752d44 168
pythontech 0:5868e8752d44 169 // if the map is an ordered array then we must do a brute force linear search
pythontech 0:5868e8752d44 170 if (map->is_ordered) {
pythontech 0:5868e8752d44 171 for (mp_map_elem_t *elem = &map->table[0], *top = &map->table[map->used]; elem < top; elem++) {
pythontech 0:5868e8752d44 172 if (elem->key == index || (!compare_only_ptrs && mp_obj_equal(elem->key, index))) {
pythontech 0:5868e8752d44 173 if (MP_UNLIKELY(lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND)) {
pythontech 0:5868e8752d44 174 elem->key = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 175 // keep elem->value so that caller can access it if needed
pythontech 0:5868e8752d44 176 }
pythontech 0:5868e8752d44 177 return elem;
pythontech 0:5868e8752d44 178 }
pythontech 0:5868e8752d44 179 }
pythontech 0:5868e8752d44 180 if (MP_LIKELY(lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)) {
pythontech 0:5868e8752d44 181 return NULL;
pythontech 0:5868e8752d44 182 }
pythontech 0:5868e8752d44 183 // TODO shrink array down over any previously-freed slots
pythontech 0:5868e8752d44 184 if (map->used == map->alloc) {
pythontech 0:5868e8752d44 185 // TODO: Alloc policy
pythontech 0:5868e8752d44 186 map->alloc += 4;
pythontech 0:5868e8752d44 187 map->table = m_renew(mp_map_elem_t, map->table, map->used, map->alloc);
pythontech 0:5868e8752d44 188 mp_seq_clear(map->table, map->used, map->alloc, sizeof(*map->table));
pythontech 0:5868e8752d44 189 }
pythontech 0:5868e8752d44 190 mp_map_elem_t *elem = map->table + map->used++;
pythontech 0:5868e8752d44 191 elem->key = index;
pythontech 0:5868e8752d44 192 if (!MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 193 map->all_keys_are_qstrs = 0;
pythontech 0:5868e8752d44 194 }
pythontech 0:5868e8752d44 195 return elem;
pythontech 0:5868e8752d44 196 }
pythontech 0:5868e8752d44 197
pythontech 0:5868e8752d44 198 // map is a hash table (not an ordered array), so do a hash lookup
pythontech 0:5868e8752d44 199
pythontech 0:5868e8752d44 200 if (map->alloc == 0) {
pythontech 0:5868e8752d44 201 if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 202 mp_map_rehash(map);
pythontech 0:5868e8752d44 203 } else {
pythontech 0:5868e8752d44 204 return NULL;
pythontech 0:5868e8752d44 205 }
pythontech 0:5868e8752d44 206 }
pythontech 0:5868e8752d44 207
pythontech 0:5868e8752d44 208 // get hash of index, with fast path for common case of qstr
pythontech 0:5868e8752d44 209 mp_uint_t hash;
pythontech 0:5868e8752d44 210 if (MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 211 hash = qstr_hash(MP_OBJ_QSTR_VALUE(index));
pythontech 0:5868e8752d44 212 } else {
pythontech 0:5868e8752d44 213 hash = MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, index));
pythontech 0:5868e8752d44 214 }
pythontech 0:5868e8752d44 215
pythontech 0:5868e8752d44 216 mp_uint_t pos = hash % map->alloc;
pythontech 0:5868e8752d44 217 mp_uint_t start_pos = pos;
pythontech 0:5868e8752d44 218 mp_map_elem_t *avail_slot = NULL;
pythontech 0:5868e8752d44 219 for (;;) {
pythontech 0:5868e8752d44 220 mp_map_elem_t *slot = &map->table[pos];
pythontech 0:5868e8752d44 221 if (slot->key == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 222 // found NULL slot, so index is not in table
pythontech 0:5868e8752d44 223 if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 224 map->used += 1;
pythontech 0:5868e8752d44 225 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 226 avail_slot = slot;
pythontech 0:5868e8752d44 227 }
pythontech 0:5868e8752d44 228 avail_slot->key = index;
pythontech 0:5868e8752d44 229 avail_slot->value = MP_OBJ_NULL;
pythontech 0:5868e8752d44 230 if (!MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 231 map->all_keys_are_qstrs = 0;
pythontech 0:5868e8752d44 232 }
pythontech 0:5868e8752d44 233 return avail_slot;
pythontech 0:5868e8752d44 234 } else {
pythontech 0:5868e8752d44 235 return NULL;
pythontech 0:5868e8752d44 236 }
pythontech 0:5868e8752d44 237 } else if (slot->key == MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 238 // found deleted slot, remember for later
pythontech 0:5868e8752d44 239 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 240 avail_slot = slot;
pythontech 0:5868e8752d44 241 }
pythontech 0:5868e8752d44 242 } else if (slot->key == index || (!compare_only_ptrs && mp_obj_equal(slot->key, index))) {
pythontech 0:5868e8752d44 243 // found index
pythontech 0:5868e8752d44 244 // Note: CPython does not replace the index; try x={True:'true'};x[1]='one';x
pythontech 0:5868e8752d44 245 if (lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
pythontech 0:5868e8752d44 246 // delete element in this slot
pythontech 0:5868e8752d44 247 map->used--;
pythontech 0:5868e8752d44 248 if (map->table[(pos + 1) % map->alloc].key == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 249 // optimisation if next slot is empty
pythontech 0:5868e8752d44 250 slot->key = MP_OBJ_NULL;
pythontech 0:5868e8752d44 251 } else {
pythontech 0:5868e8752d44 252 slot->key = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 253 }
pythontech 0:5868e8752d44 254 // keep slot->value so that caller can access it if needed
pythontech 0:5868e8752d44 255 }
pythontech 0:5868e8752d44 256 return slot;
pythontech 0:5868e8752d44 257 }
pythontech 0:5868e8752d44 258
pythontech 0:5868e8752d44 259 // not yet found, keep searching in this table
pythontech 0:5868e8752d44 260 pos = (pos + 1) % map->alloc;
pythontech 0:5868e8752d44 261
pythontech 0:5868e8752d44 262 if (pos == start_pos) {
pythontech 0:5868e8752d44 263 // search got back to starting position, so index is not in table
pythontech 0:5868e8752d44 264 if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 265 if (avail_slot != NULL) {
pythontech 0:5868e8752d44 266 // there was an available slot, so use that
pythontech 0:5868e8752d44 267 map->used++;
pythontech 0:5868e8752d44 268 avail_slot->key = index;
pythontech 0:5868e8752d44 269 avail_slot->value = MP_OBJ_NULL;
pythontech 0:5868e8752d44 270 if (!MP_OBJ_IS_QSTR(index)) {
pythontech 0:5868e8752d44 271 map->all_keys_are_qstrs = 0;
pythontech 0:5868e8752d44 272 }
pythontech 0:5868e8752d44 273 return avail_slot;
pythontech 0:5868e8752d44 274 } else {
pythontech 0:5868e8752d44 275 // not enough room in table, rehash it
pythontech 0:5868e8752d44 276 mp_map_rehash(map);
pythontech 0:5868e8752d44 277 // restart the search for the new element
pythontech 0:5868e8752d44 278 start_pos = pos = hash % map->alloc;
pythontech 0:5868e8752d44 279 }
pythontech 0:5868e8752d44 280 } else {
pythontech 0:5868e8752d44 281 return NULL;
pythontech 0:5868e8752d44 282 }
pythontech 0:5868e8752d44 283 }
pythontech 0:5868e8752d44 284 }
pythontech 0:5868e8752d44 285 }
pythontech 0:5868e8752d44 286
pythontech 0:5868e8752d44 287 /******************************************************************************/
pythontech 0:5868e8752d44 288 /* set */
pythontech 0:5868e8752d44 289
pythontech 0:5868e8752d44 290 #if MICROPY_PY_BUILTINS_SET
pythontech 0:5868e8752d44 291
pythontech 0:5868e8752d44 292 void mp_set_init(mp_set_t *set, mp_uint_t n) {
pythontech 0:5868e8752d44 293 set->alloc = n;
pythontech 0:5868e8752d44 294 set->used = 0;
pythontech 0:5868e8752d44 295 set->table = m_new0(mp_obj_t, set->alloc);
pythontech 0:5868e8752d44 296 }
pythontech 0:5868e8752d44 297
pythontech 0:5868e8752d44 298 STATIC void mp_set_rehash(mp_set_t *set) {
pythontech 0:5868e8752d44 299 mp_uint_t old_alloc = set->alloc;
pythontech 0:5868e8752d44 300 mp_obj_t *old_table = set->table;
pythontech 0:5868e8752d44 301 set->alloc = get_doubling_prime_greater_or_equal_to(set->alloc + 1);
pythontech 0:5868e8752d44 302 set->used = 0;
pythontech 0:5868e8752d44 303 set->table = m_new0(mp_obj_t, set->alloc);
pythontech 0:5868e8752d44 304 for (mp_uint_t i = 0; i < old_alloc; i++) {
pythontech 0:5868e8752d44 305 if (old_table[i] != MP_OBJ_NULL && old_table[i] != MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 306 mp_set_lookup(set, old_table[i], MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
pythontech 0:5868e8752d44 307 }
pythontech 0:5868e8752d44 308 }
pythontech 0:5868e8752d44 309 m_del(mp_obj_t, old_table, old_alloc);
pythontech 0:5868e8752d44 310 }
pythontech 0:5868e8752d44 311
pythontech 0:5868e8752d44 312 mp_obj_t mp_set_lookup(mp_set_t *set, mp_obj_t index, mp_map_lookup_kind_t lookup_kind) {
pythontech 0:5868e8752d44 313 // Note: lookup_kind can be MP_MAP_LOOKUP_ADD_IF_NOT_FOUND_OR_REMOVE_IF_FOUND which
pythontech 0:5868e8752d44 314 // is handled by using bitwise operations.
pythontech 0:5868e8752d44 315
pythontech 0:5868e8752d44 316 if (set->alloc == 0) {
pythontech 0:5868e8752d44 317 if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 318 mp_set_rehash(set);
pythontech 0:5868e8752d44 319 } else {
pythontech 0:5868e8752d44 320 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 321 }
pythontech 0:5868e8752d44 322 }
pythontech 0:5868e8752d44 323 mp_uint_t hash = MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, index));
pythontech 0:5868e8752d44 324 mp_uint_t pos = hash % set->alloc;
pythontech 0:5868e8752d44 325 mp_uint_t start_pos = pos;
pythontech 0:5868e8752d44 326 mp_obj_t *avail_slot = NULL;
pythontech 0:5868e8752d44 327 for (;;) {
pythontech 0:5868e8752d44 328 mp_obj_t elem = set->table[pos];
pythontech 0:5868e8752d44 329 if (elem == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 330 // found NULL slot, so index is not in table
pythontech 0:5868e8752d44 331 if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 332 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 333 avail_slot = &set->table[pos];
pythontech 0:5868e8752d44 334 }
pythontech 0:5868e8752d44 335 set->used++;
pythontech 0:5868e8752d44 336 *avail_slot = index;
pythontech 0:5868e8752d44 337 return index;
pythontech 0:5868e8752d44 338 } else {
pythontech 0:5868e8752d44 339 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 340 }
pythontech 0:5868e8752d44 341 } else if (elem == MP_OBJ_SENTINEL) {
pythontech 0:5868e8752d44 342 // found deleted slot, remember for later
pythontech 0:5868e8752d44 343 if (avail_slot == NULL) {
pythontech 0:5868e8752d44 344 avail_slot = &set->table[pos];
pythontech 0:5868e8752d44 345 }
pythontech 0:5868e8752d44 346 } else if (mp_obj_equal(elem, index)) {
pythontech 0:5868e8752d44 347 // found index
pythontech 0:5868e8752d44 348 if (lookup_kind & MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
pythontech 0:5868e8752d44 349 // delete element
pythontech 0:5868e8752d44 350 set->used--;
pythontech 0:5868e8752d44 351 if (set->table[(pos + 1) % set->alloc] == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 352 // optimisation if next slot is empty
pythontech 0:5868e8752d44 353 set->table[pos] = MP_OBJ_NULL;
pythontech 0:5868e8752d44 354 } else {
pythontech 0:5868e8752d44 355 set->table[pos] = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 356 }
pythontech 0:5868e8752d44 357 }
pythontech 0:5868e8752d44 358 return elem;
pythontech 0:5868e8752d44 359 }
pythontech 0:5868e8752d44 360
pythontech 0:5868e8752d44 361 // not yet found, keep searching in this table
pythontech 0:5868e8752d44 362 pos = (pos + 1) % set->alloc;
pythontech 0:5868e8752d44 363
pythontech 0:5868e8752d44 364 if (pos == start_pos) {
pythontech 0:5868e8752d44 365 // search got back to starting position, so index is not in table
pythontech 0:5868e8752d44 366 if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
pythontech 0:5868e8752d44 367 if (avail_slot != NULL) {
pythontech 0:5868e8752d44 368 // there was an available slot, so use that
pythontech 0:5868e8752d44 369 set->used++;
pythontech 0:5868e8752d44 370 *avail_slot = index;
pythontech 0:5868e8752d44 371 return index;
pythontech 0:5868e8752d44 372 } else {
pythontech 0:5868e8752d44 373 // not enough room in table, rehash it
pythontech 0:5868e8752d44 374 mp_set_rehash(set);
pythontech 0:5868e8752d44 375 // restart the search for the new element
pythontech 0:5868e8752d44 376 start_pos = pos = hash % set->alloc;
pythontech 0:5868e8752d44 377 }
pythontech 0:5868e8752d44 378 } else {
pythontech 0:5868e8752d44 379 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 380 }
pythontech 0:5868e8752d44 381 }
pythontech 0:5868e8752d44 382 }
pythontech 0:5868e8752d44 383 }
pythontech 0:5868e8752d44 384
pythontech 0:5868e8752d44 385 mp_obj_t mp_set_remove_first(mp_set_t *set) {
pythontech 0:5868e8752d44 386 for (mp_uint_t pos = 0; pos < set->alloc; pos++) {
pythontech 0:5868e8752d44 387 if (MP_SET_SLOT_IS_FILLED(set, pos)) {
pythontech 0:5868e8752d44 388 mp_obj_t elem = set->table[pos];
pythontech 0:5868e8752d44 389 // delete element
pythontech 0:5868e8752d44 390 set->used--;
pythontech 0:5868e8752d44 391 if (set->table[(pos + 1) % set->alloc] == MP_OBJ_NULL) {
pythontech 0:5868e8752d44 392 // optimisation if next slot is empty
pythontech 0:5868e8752d44 393 set->table[pos] = MP_OBJ_NULL;
pythontech 0:5868e8752d44 394 } else {
pythontech 0:5868e8752d44 395 set->table[pos] = MP_OBJ_SENTINEL;
pythontech 0:5868e8752d44 396 }
pythontech 0:5868e8752d44 397 return elem;
pythontech 0:5868e8752d44 398 }
pythontech 0:5868e8752d44 399 }
pythontech 0:5868e8752d44 400 return MP_OBJ_NULL;
pythontech 0:5868e8752d44 401 }
pythontech 0:5868e8752d44 402
pythontech 0:5868e8752d44 403 void mp_set_clear(mp_set_t *set) {
pythontech 0:5868e8752d44 404 m_del(mp_obj_t, set->table, set->alloc);
pythontech 0:5868e8752d44 405 set->alloc = 0;
pythontech 0:5868e8752d44 406 set->used = 0;
pythontech 0:5868e8752d44 407 set->table = NULL;
pythontech 0:5868e8752d44 408 }
pythontech 0:5868e8752d44 409
pythontech 0:5868e8752d44 410 #endif // MICROPY_PY_BUILTINS_SET
pythontech 0:5868e8752d44 411
pythontech 0:5868e8752d44 412 #if defined(DEBUG_PRINT) && DEBUG_PRINT
pythontech 0:5868e8752d44 413 void mp_map_dump(mp_map_t *map) {
pythontech 0:5868e8752d44 414 for (mp_uint_t i = 0; i < map->alloc; i++) {
pythontech 0:5868e8752d44 415 if (map->table[i].key != NULL) {
pythontech 0:5868e8752d44 416 mp_obj_print(map->table[i].key, PRINT_REPR);
pythontech 0:5868e8752d44 417 } else {
pythontech 0:5868e8752d44 418 printf("(nil)");
pythontech 0:5868e8752d44 419 }
pythontech 0:5868e8752d44 420 printf(": %p\n", map->table[i].value);
pythontech 0:5868e8752d44 421 }
pythontech 0:5868e8752d44 422 printf("---\n");
pythontech 0:5868e8752d44 423 }
pythontech 0:5868e8752d44 424 #endif