map.c 5.75 KB
Newer Older
1
2
3
4
5
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>

#include "misc.h"
6
#include "mpconfig.h"
7
#include "obj.h"
8
9
#include "runtime0.h"
#include "map.h"
10
11

// approximatelly doubling primes; made with Mathematica command: Table[Prime[Floor[(1.7)^n]], {n, 3, 24}]
John R. Lenton's avatar
John R. Lenton committed
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};
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;
}

26
27
28
29
/******************************************************************************/
/* map                                                                        */

void mp_map_init(mp_map_t *map, mp_map_kind_t kind, int n) {
30
31
32
    map->kind = kind;
    map->used = 0;
    map->alloc = get_doubling_prime_greater_or_equal_to(n + 1);
33
    map->table = m_new0(mp_map_elem_t, map->alloc);
34
35
}

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);
39
40
41
    return map;
}

John R. Lenton's avatar
John R. Lenton committed
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; i<map->alloc; 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);
}

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);
69
    machine_uint_t hash;
70
71
    if (is_map_mp_obj) {
        hash = mp_obj_hash(index);
72
73
74
    } else {
        hash = (machine_uint_t)index;
    }
John R. Lenton's avatar
John R. Lenton committed
75
76
77
78
79
80
81
    if (map->alloc == 0) {
        if (add_if_not_found) {
            mp_map_rehash(map);
        } else {
            return NULL;
        }
    }
82
83
    uint pos = hash % map->alloc;
    for (;;) {
84
        mp_map_elem_t *elem = &map->table[pos];
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's avatar
John R. Lenton committed
90
                    mp_map_rehash(map);
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;
            }
101
        } else if (elem->key == index || (is_map_mp_obj && mp_obj_equal(elem->key, index))) {
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;
        }
    }
}

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);
119
120
}

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);
128
129
}

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's avatar
John R. Lenton committed
132
    assert(set->alloc); /* FIXME: if alloc is ever 0 when doing a lookup, this'll fail: */
133
    int pos = hash % set->alloc;
134
    for (;;) {
135
136
        mp_obj_t elem = set->table[pos];
        if (elem == MP_OBJ_NULL) {
137
138
            // not in table
            if (add_if_not_found) {
139
                if (set->used + 1 >= set->alloc) {
140
                    // not enough room in table, rehash it
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);
146
147
                    for (int i = 0; i < old_alloc; i++) {
                        if (old_table[i] != NULL) {
148
                            mp_set_lookup(set, old_table[i], true);
149
150
                        }
                    }
151
                    m_del(mp_obj_t, old_table, old_alloc);
152
                    // restart the search for the new element
153
                    pos = hash % set->alloc;
154
                } else {
155
156
                    set->used += 1;
                    set->table[pos] = index;
157
158
159
                    return index;
                }
            } else {
160
                return MP_OBJ_NULL;
161
            }
162
        } else if (mp_obj_equal(elem, index)) {
163
164
165
166
            // found it
            return elem;
        } else {
            // not yet found, keep searching in this table
167
            pos = (pos + 1) % set->alloc;
168
169
170
        }
    }
}