map.c 5.75 KB
 Damien committed Dec 17, 2013 1 2 3 4 5 ``````#include #include #include #include "misc.h" `````` Damien committed Dec 21, 2013 6 ``````#include "mpconfig.h" `````` Damien committed Dec 17, 2013 7 ``````#include "obj.h" `````` Damien committed Dec 21, 2013 8 9 ``````#include "runtime0.h" #include "map.h" `````` Damien committed Dec 17, 2013 10 11 `````` // approximatelly doubling primes; made with Mathematica command: Table[Prime[Floor[(1.7)^n]], {n, 3, 24}] `````` John R. Lenton committed Jan 07, 2014 12 13 ``````// prefixed with zero for the empty case. 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}; `````` Damien committed Dec 17, 2013 14 15 16 17 18 19 20 21 22 23 24 25 `````` int get_doubling_prime_greater_or_equal_to(int x) { for (int i = 0; i < sizeof(doubling_primes) / sizeof(int); i++) { if (doubling_primes[i] >= x) { return doubling_primes[i]; } } // ran out of primes in the table! // return something sensible, at least make it odd return x | 1; } `````` Damien committed Dec 21, 2013 26 27 28 29 ``````/******************************************************************************/ /* map */ void mp_map_init(mp_map_t *map, mp_map_kind_t kind, int n) { `````` Damien committed Dec 17, 2013 30 31 32 `````` map->kind = kind; map->used = 0; map->alloc = get_doubling_prime_greater_or_equal_to(n + 1); `````` Damien committed Dec 21, 2013 33 `````` map->table = m_new0(mp_map_elem_t, map->alloc); `````` Damien committed Dec 17, 2013 34 35 ``````} `````` Damien committed Dec 21, 2013 36 37 38 ``````mp_map_t *mp_map_new(mp_map_kind_t kind, int n) { mp_map_t *map = m_new(mp_map_t, 1); mp_map_init(map, kind, n); `````` Damien committed Dec 17, 2013 39 40 41 `````` return map; } `````` John R. Lenton committed Jan 07, 2014 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 ``````void mp_map_clear(mp_map_t *map) { map->used = 0; machine_uint_t a = map->alloc; map->alloc = 0; map->table = m_renew(mp_map_elem_t, map->table, a, map->alloc); mp_map_elem_t nul = {NULL, NULL}; for (uint i=0; ialloc; i++) { map->table[i] = nul; } } static void mp_map_rehash (mp_map_t *map) { int old_alloc = map->alloc; mp_map_elem_t *old_table = map->table; map->alloc = get_doubling_prime_greater_or_equal_to(map->alloc + 1); map->used = 0; map->table = m_new0(mp_map_elem_t, map->alloc); for (int i = 0; i < old_alloc; i++) { if (old_table[i].key != NULL) { mp_map_lookup_helper(map, old_table[i].key, true)->value = old_table[i].value; } } m_del(mp_map_elem_t, old_table, old_alloc); } `````` Damien committed Dec 21, 2013 67 68 ``````mp_map_elem_t* mp_map_lookup_helper(mp_map_t *map, mp_obj_t index, bool add_if_not_found) { bool is_map_mp_obj = (map->kind == MP_MAP_OBJ); `````` Damien committed Dec 17, 2013 69 `````` machine_uint_t hash; `````` Damien committed Dec 21, 2013 70 71 `````` if (is_map_mp_obj) { hash = mp_obj_hash(index); `````` Damien committed Dec 17, 2013 72 73 74 `````` } else { hash = (machine_uint_t)index; } `````` John R. Lenton committed Jan 07, 2014 75 76 77 78 79 80 81 `````` if (map->alloc == 0) { if (add_if_not_found) { mp_map_rehash(map); } else { return NULL; } } `````` Damien committed Dec 17, 2013 82 83 `````` uint pos = hash % map->alloc; for (;;) { `````` Damien committed Dec 21, 2013 84 `````` mp_map_elem_t *elem = &map->table[pos]; `````` Damien committed Dec 17, 2013 85 86 87 88 89 `````` if (elem->key == NULL) { // not in table if (add_if_not_found) { if (map->used + 1 >= map->alloc) { // not enough room in table, rehash it `````` John R. Lenton committed Jan 07, 2014 90 `````` mp_map_rehash(map); `````` Damien committed Dec 17, 2013 91 92 93 94 95 96 97 98 99 100 `````` // restart the search for the new element pos = hash % map->alloc; } else { map->used += 1; elem->key = index; return elem; } } else { return NULL; } `````` Damien committed Dec 21, 2013 101 `````` } else if (elem->key == index || (is_map_mp_obj && mp_obj_equal(elem->key, index))) { `````` Damien committed Dec 17, 2013 102 103 104 105 106 107 108 109 110 111 112 113 114 115 `````` // found it /* it seems CPython does not replace the index; try x={True:'true'};x[1]='one';x if (add_if_not_found) { elem->key = index; } */ return elem; } else { // not yet found, keep searching in this table pos = (pos + 1) % map->alloc; } } } `````` Damien committed Dec 21, 2013 116 117 118 ``````mp_map_elem_t* mp_qstr_map_lookup(mp_map_t *map, qstr index, bool add_if_not_found) { mp_obj_t o = (mp_obj_t)(machine_uint_t)index; return mp_map_lookup_helper(map, o, add_if_not_found); `````` Damien committed Dec 17, 2013 119 120 ``````} `````` Damien committed Dec 21, 2013 121 122 123 124 125 126 127 ``````/******************************************************************************/ /* set */ void mp_set_init(mp_set_t *set, int n) { set->alloc = get_doubling_prime_greater_or_equal_to(n + 1); set->used = 0; set->table = m_new0(mp_obj_t, set->alloc); `````` Damien committed Dec 17, 2013 128 129 ``````} `````` Damien committed Dec 21, 2013 130 131 ``````mp_obj_t mp_set_lookup(mp_set_t *set, mp_obj_t index, bool add_if_not_found) { int hash = mp_obj_hash(index); `````` John R. Lenton committed Jan 07, 2014 132 `````` assert(set->alloc); /* FIXME: if alloc is ever 0 when doing a lookup, this'll fail: */ `````` Damien committed Dec 21, 2013 133 `````` int pos = hash % set->alloc; `````` Damien committed Dec 17, 2013 134 `````` for (;;) { `````` Damien committed Dec 21, 2013 135 136 `````` mp_obj_t elem = set->table[pos]; if (elem == MP_OBJ_NULL) { `````` Damien committed Dec 17, 2013 137 138 `````` // not in table if (add_if_not_found) { `````` Damien committed Dec 21, 2013 139 `````` if (set->used + 1 >= set->alloc) { `````` Damien committed Dec 17, 2013 140 `````` // not enough room in table, rehash it `````` Damien committed Dec 21, 2013 141 142 143 144 145 `````` int old_alloc = set->alloc; mp_obj_t *old_table = set->table; set->alloc = get_doubling_prime_greater_or_equal_to(set->alloc + 1); set->used = 0; set->table = m_new(mp_obj_t, set->alloc); `````` Damien committed Dec 17, 2013 146 147 `````` for (int i = 0; i < old_alloc; i++) { if (old_table[i] != NULL) { `````` Damien committed Dec 21, 2013 148 `````` mp_set_lookup(set, old_table[i], true); `````` Damien committed Dec 17, 2013 149 150 `````` } } `````` Damien committed Dec 29, 2013 151 `````` m_del(mp_obj_t, old_table, old_alloc); `````` Damien committed Dec 17, 2013 152 `````` // restart the search for the new element `````` Damien committed Dec 21, 2013 153 `````` pos = hash % set->alloc; `````` Damien committed Dec 17, 2013 154 `````` } else { `````` Damien committed Dec 21, 2013 155 156 `````` set->used += 1; set->table[pos] = index; `````` Damien committed Dec 17, 2013 157 158 159 `````` return index; } } else { `````` Damien committed Dec 21, 2013 160 `````` return MP_OBJ_NULL; `````` Damien committed Dec 17, 2013 161 `````` } `````` Damien committed Dec 21, 2013 162 `````` } else if (mp_obj_equal(elem, index)) { `````` Damien committed Dec 17, 2013 163 164 165 166 `````` // found it return elem; } else { // not yet found, keep searching in this table `````` Damien committed Dec 21, 2013 167 `````` pos = (pos + 1) % set->alloc; `````` Damien committed Dec 17, 2013 168 169 170 `````` } } }``````