qstr.c 6.38 KB
Newer Older
Damien's avatar
Damien committed
1
2
3
4
#include <assert.h>
#include <string.h>

#include "misc.h"
5
6
#include "mpconfig.h"
#include "qstr.h"
Damien's avatar
Damien committed
7

8
9
10
11
12
// NOTE: we are using linear arrays to store and search for qstr's (unique strings, interned strings)
// ultimately we will replace this with a static hash table of some kind
// also probably need to include the length in the string data, to allow null bytes in the string

#if 0 // print debugging info
13
#define DEBUG_printf DEBUG_printf
14
#else // don't print debugging info
15
#define DEBUG_printf(...) (void)0
16
17
#endif

18
19
20
// A qstr is an index into the qstr pool.
// The data for a qstr contains (hash, length, data).
// For now we use very simple encoding, just to get the framework correct:
21
//  - hash is 2 bytes (see function below)
22
23
24
25
26
27
28
29
30
//  - length is 2 bytes
//  - data follows
//  - \0 terminated (for now, so they can be printed using printf)

#define Q_GET_HASH(q)   ((q)[0] | ((q)[1] << 8))
#define Q_GET_ALLOC(q)  (4 + Q_GET_LENGTH(q) + 1)
#define Q_GET_LENGTH(q) ((q)[2] | ((q)[3] << 8))
#define Q_GET_DATA(q)   ((q) + 4)

31
// this must match the equivalent function in makeqstrdata.py
32
machine_uint_t qstr_compute_hash(const byte *data, uint len) {
33
34
    // djb2 algorithm; see http://www.cse.yorku.ca/~oz/hash.html
    machine_uint_t hash = 5381;
35
    for (const byte *top = data + len; data < top; data++) {
36
        hash = ((hash << 5) + hash) ^ (*data); // hash * 33 ^ data
37
38
39
40
    }
    return hash & 0xffff;
}

41
42
43
44
45
typedef struct _qstr_pool_t {
    struct _qstr_pool_t *prev;
    uint total_prev_len;
    uint alloc;
    uint len;
46
    const byte *qstrs[];
47
48
49
50
51
52
53
54
} qstr_pool_t;

const static qstr_pool_t const_pool = {
    NULL,               // no previous pool
    0,                  // no previous pool
    10,                 // set so that the first dynamically allocated pool is twice this size; must be <= the len (just below)
    MP_QSTR_number_of,  // corresponds to number of strings in array just below
    {
55
56
57
58
        (const byte*) "\0\0\0\0", // invalid/no qstr has empty data
        (const byte*) "\0\0\0\0", // empty qstr
#define Q(id, str) str,
// TODO having 'build/' here is a bit of a hack, should take config variable from Makefile
59
#include "build/py/qstrdefs.generated.h"
60
61
62
63
#undef Q
    },
};

64
STATIC qstr_pool_t *last_pool;
Damien's avatar
Damien committed
65

66
void qstr_init(void) {
67
    last_pool = (qstr_pool_t*)&const_pool; // we won't modify the const_pool since it has no allocated room left
Damien's avatar
Damien committed
68
69
}

70
STATIC const byte *find_qstr(qstr q) {
71
72
73
74
75
76
77
78
79
80
81
    // search pool for this qstr
    for (qstr_pool_t *pool = last_pool; pool != NULL; pool = pool->prev) {
        if (q >= pool->total_prev_len) {
            return pool->qstrs[q - pool->total_prev_len];
        }
    }

    // not found
    return 0;
}

82
STATIC qstr qstr_add(const byte *q_ptr) {
83
    DEBUG_printf("QSTR: add hash=%d len=%d data=%.*s\n", Q_GET_HASH(q_ptr), Q_GET_LENGTH(q_ptr), Q_GET_LENGTH(q_ptr), Q_GET_DATA(q_ptr));
84
85
86
87
88
89
90
91
92
93

    // make sure we have room in the pool for a new qstr
    if (last_pool->len >= last_pool->alloc) {
        qstr_pool_t *pool = m_new_obj_var(qstr_pool_t, const char*, last_pool->alloc * 2);
        pool->prev = last_pool;
        pool->total_prev_len = last_pool->total_prev_len + last_pool->len;
        pool->alloc = last_pool->alloc * 2;
        pool->len = 0;
        last_pool = pool;
        DEBUG_printf("QSTR: allocate new pool of size %d\n", last_pool->alloc);
Damien's avatar
Damien committed
94
    }
95
96

    // add the new qstr
97
    last_pool->qstrs[last_pool->len++] = q_ptr;
98
99
100

    // return id for the newly-added qstr
    return last_pool->total_prev_len + last_pool->len - 1;
Damien's avatar
Damien committed
101
102
}

103
qstr qstr_find_strn(const byte *str, uint str_len) {
104
    // work out hash of str
105
    machine_uint_t str_hash = qstr_compute_hash((const byte*)str, str_len);
106
107

    // search pools for the data
108
    for (qstr_pool_t *pool = last_pool; pool != NULL; pool = pool->prev) {
109
        for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
110
            if (Q_GET_HASH(*q) == str_hash && Q_GET_LENGTH(*q) == str_len && memcmp(Q_GET_DATA(*q), str, str_len) == 0) {
111
                return pool->total_prev_len + (q - pool->qstrs);
112
            }
Damien's avatar
Damien committed
113
114
        }
    }
115
116
117

    // not found; return null qstr
    return 0;
Damien's avatar
Damien committed
118
119
}

120
121
qstr qstr_from_str(const char *str) {
    return qstr_from_strn(str, strlen(str));
Damien's avatar
Damien committed
122
123
}

124
125
126
qstr qstr_from_strn(const char *str, uint len) {
    qstr q = qstr_find_strn((const byte*)str, len);
    if (q == 0) {
127
        machine_uint_t hash = qstr_compute_hash((const byte*)str, len);
128
129
130
131
132
133
134
135
        byte *q_ptr = m_new(byte, 4 + len + 1);
        q_ptr[0] = hash;
        q_ptr[1] = hash >> 8;
        q_ptr[2] = len;
        q_ptr[3] = len >> 8;
        memcpy(q_ptr + 4, str, len);
        q_ptr[4 + len] = '\0';
        q = qstr_add(q_ptr);
Damien's avatar
Damien committed
136
    }
137
    return q;
Damien's avatar
Damien committed
138
139
}

140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
qstr qstr_from_strn_take(char *str, uint alloc_len, uint len) {
    qstr q = qstr_from_strn(str, len);
    m_del(char, str, alloc_len);
    return q;
}

byte *qstr_build_start(uint len, byte **q_ptr) {
    assert(len <= 65535);
    *q_ptr = m_new(byte, 4 + len + 1);
    (*q_ptr)[2] = len;
    (*q_ptr)[3] = len >> 8;
    return Q_GET_DATA(*q_ptr);
}

qstr qstr_build_end(byte *q_ptr) {
    qstr q = qstr_find_strn(Q_GET_DATA(q_ptr), Q_GET_LENGTH(q_ptr));
    if (q == 0) {
        machine_uint_t len = Q_GET_LENGTH(q_ptr);
158
        machine_uint_t hash = qstr_compute_hash(Q_GET_DATA(q_ptr), len);
159
160
161
162
163
164
        q_ptr[0] = hash;
        q_ptr[1] = hash >> 8;
        q_ptr[4 + len] = '\0';
        q = qstr_add(q_ptr);
    } else {
        m_del(byte, q_ptr, Q_GET_ALLOC(q_ptr));
165
    }
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
    return q;
}

machine_uint_t qstr_hash(qstr q) {
    return Q_GET_HASH(find_qstr(q));
}

uint qstr_len(qstr q) {
    const byte *qd = find_qstr(q);
    return Q_GET_LENGTH(qd);
}

// XXX to remove!
const char *qstr_str(qstr q) {
    const byte *qd = find_qstr(q);
    return (const char*)Q_GET_DATA(qd);
}
183

184
185
186
187
const byte *qstr_data(qstr q, uint *len) {
    const byte *qd = find_qstr(q);
    *len = Q_GET_LENGTH(qd);
    return Q_GET_DATA(qd);
Damien's avatar
Damien committed
188
}
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

void qstr_pool_info(uint *n_pool, uint *n_qstr, uint *n_str_data_bytes, uint *n_total_bytes) {
    *n_pool = 0;
    *n_qstr = 0;
    *n_str_data_bytes = 0;
    *n_total_bytes = 0;
    for (qstr_pool_t *pool = last_pool; pool != NULL && pool != &const_pool; pool = pool->prev) {
        *n_pool += 1;
        *n_qstr += pool->len;
        for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
            *n_str_data_bytes += Q_GET_ALLOC(*q);
        }
        *n_total_bytes += sizeof(qstr_pool_t) + sizeof(qstr) * pool->alloc;
    }
    *n_total_bytes += *n_str_data_bytes;
}