blob: ef31a682ee8e43e53a3f7a9e58a2f3ffe583bb82 [file] [log] [blame]
Damien George04b91472014-05-03 23:27:38 +01001/*
2 * This file is part of the Micro Python project, http://micropython.org/
3 *
4 * The MIT License (MIT)
5 *
6 * Copyright (c) 2013, 2014 Damien P. George
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a copy
9 * of this software and associated documentation files (the "Software"), to deal
10 * in the Software without restriction, including without limitation the rights
11 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 * copies of the Software, and to permit persons to whom the Software is
13 * furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be included in
16 * all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 * THE SOFTWARE.
25 */
26
Damien429d7192013-10-04 19:53:11 +010027#include <assert.h>
28#include <string.h>
Damien Georgeea0461d2015-02-10 11:02:28 +000029#include <stdio.h>
Damien429d7192013-10-04 19:53:11 +010030
Damien Georgeb4b10fd2015-01-01 23:30:53 +000031#include "py/mpstate.h"
Damien George51dfcb42015-01-01 20:27:54 +000032#include "py/qstr.h"
33#include "py/gc.h"
Damien429d7192013-10-04 19:53:11 +010034
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000035// NOTE: we are using linear arrays to store and search for qstr's (unique strings, interned strings)
36// ultimately we will replace this with a static hash table of some kind
37// also probably need to include the length in the string data, to allow null bytes in the string
38
39#if 0 // print debugging info
Paul Sokolovsky44739e22014-02-16 18:11:42 +020040#define DEBUG_printf DEBUG_printf
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000041#else // don't print debugging info
Damien George1dc76af2014-02-26 16:57:08 +000042#define DEBUG_printf(...) (void)0
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000043#endif
44
Damien George55baff42014-01-21 21:40:13 +000045// A qstr is an index into the qstr pool.
Damien Georgec3bd9412015-07-20 11:03:13 +000046// The data for a qstr contains (hash, length, data):
47// - hash (configurable number of bytes)
48// - length (configurable number of bytes)
49// - data ("length" number of bytes)
50// - \0 terminated (so they can be printed using printf)
Damien George55baff42014-01-21 21:40:13 +000051
Damien Georgec3bd9412015-07-20 11:03:13 +000052#if MICROPY_QSTR_BYTES_IN_HASH == 1
53 #define Q_HASH_MASK (0xff)
54 #define Q_GET_HASH(q) ((mp_uint_t)(q)[0])
55 #define Q_SET_HASH(q, hash) do { (q)[0] = (hash); } while (0)
56#elif MICROPY_QSTR_BYTES_IN_HASH == 2
57 #define Q_HASH_MASK (0xffff)
58 #define Q_GET_HASH(q) ((mp_uint_t)(q)[0] | ((mp_uint_t)(q)[1] << 8))
59 #define Q_SET_HASH(q, hash) do { (q)[0] = (hash); (q)[1] = (hash) >> 8; } while (0)
60#else
61 #error unimplemented qstr hash decoding
62#endif
63#define Q_GET_ALLOC(q) (MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + Q_GET_LENGTH(q) + 1)
64#define Q_GET_DATA(q) ((q) + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN)
Damien George95836f82015-01-11 22:27:30 +000065#if MICROPY_QSTR_BYTES_IN_LEN == 1
Damien Georgec3bd9412015-07-20 11:03:13 +000066 #define Q_GET_LENGTH(q) ((q)[MICROPY_QSTR_BYTES_IN_HASH])
67 #define Q_SET_LENGTH(q, len) do { (q)[MICROPY_QSTR_BYTES_IN_HASH] = (len); } while (0)
Damien George95836f82015-01-11 22:27:30 +000068#elif MICROPY_QSTR_BYTES_IN_LEN == 2
Damien Georgec3bd9412015-07-20 11:03:13 +000069 #define Q_GET_LENGTH(q) ((q)[MICROPY_QSTR_BYTES_IN_HASH] | ((q)[MICROPY_QSTR_BYTES_IN_HASH + 1] << 8))
70 #define Q_SET_LENGTH(q, len) do { (q)[MICROPY_QSTR_BYTES_IN_HASH] = (len); (q)[MICROPY_QSTR_BYTES_IN_HASH + 1] = (len) >> 8; } while (0)
Damien George95836f82015-01-11 22:27:30 +000071#else
72 #error unimplemented qstr length decoding
73#endif
Damien George55baff42014-01-21 21:40:13 +000074
Damien George6e628c42014-03-25 15:27:15 +000075// this must match the equivalent function in makeqstrdata.py
Damien Georgec3f64d92015-11-27 12:23:18 +000076mp_uint_t qstr_compute_hash(const byte *data, size_t len) {
Damien George6e628c42014-03-25 15:27:15 +000077 // djb2 algorithm; see http://www.cse.yorku.ca/~oz/hash.html
Damien George40f3c022014-07-03 13:25:24 +010078 mp_uint_t hash = 5381;
Damien George55baff42014-01-21 21:40:13 +000079 for (const byte *top = data + len; data < top; data++) {
Damien George6e628c42014-03-25 15:27:15 +000080 hash = ((hash << 5) + hash) ^ (*data); // hash * 33 ^ data
Damien George55baff42014-01-21 21:40:13 +000081 }
Damien Georgec3bd9412015-07-20 11:03:13 +000082 hash &= Q_HASH_MASK;
Paul Sokolovsky59e269c2014-04-14 01:43:01 +030083 // Make sure that valid hash is never zero, zero means "hash not computed"
84 if (hash == 0) {
85 hash++;
86 }
87 return hash;
Damien George55baff42014-01-21 21:40:13 +000088}
89
Damien George0a2e9652016-01-31 22:24:16 +000090const qstr_pool_t mp_qstr_const_pool = {
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000091 NULL, // no previous pool
92 0, // no previous pool
93 10, // set so that the first dynamically allocated pool is twice this size; must be <= the len (just below)
Damien George0a2e9652016-01-31 22:24:16 +000094 MP_QSTRnumber_of, // corresponds to number of strings in array just below
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000095 {
Damien George6942f802015-01-11 17:52:45 +000096#define QDEF(id, str) str,
Damien Georged553be52014-04-17 18:03:27 +010097#include "genhdr/qstrdefs.generated.h"
Damien George6942f802015-01-11 17:52:45 +000098#undef QDEF
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000099 },
100};
101
Damien George0a2e9652016-01-31 22:24:16 +0000102#ifdef MICROPY_QSTR_EXTRA_POOL
103extern const qstr_pool_t MICROPY_QSTR_EXTRA_POOL;
104#define CONST_POOL MICROPY_QSTR_EXTRA_POOL
105#else
106#define CONST_POOL mp_qstr_const_pool
107#endif
108
Damien8b3a7c22013-10-23 20:20:17 +0100109void qstr_init(void) {
Damien George0a2e9652016-01-31 22:24:16 +0000110 MP_STATE_VM(last_pool) = (qstr_pool_t*)&CONST_POOL; // we won't modify the const_pool since it has no allocated room left
Damien Georgeade9a052015-06-13 21:53:22 +0100111 MP_STATE_VM(qstr_last_chunk) = NULL;
Damien429d7192013-10-04 19:53:11 +0100112}
113
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200114STATIC const byte *find_qstr(qstr q) {
Damien George55baff42014-01-21 21:40:13 +0000115 // search pool for this qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000116 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
Damien George55baff42014-01-21 21:40:13 +0000117 if (q >= pool->total_prev_len) {
118 return pool->qstrs[q - pool->total_prev_len];
119 }
120 }
121
122 // not found
123 return 0;
124}
125
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200126STATIC qstr qstr_add(const byte *q_ptr) {
Damien George55baff42014-01-21 21:40:13 +0000127 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));
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000128
129 // make sure we have room in the pool for a new qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000130 if (MP_STATE_VM(last_pool)->len >= MP_STATE_VM(last_pool)->alloc) {
131 qstr_pool_t *pool = m_new_obj_var(qstr_pool_t, const char*, MP_STATE_VM(last_pool)->alloc * 2);
132 pool->prev = MP_STATE_VM(last_pool);
133 pool->total_prev_len = MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len;
134 pool->alloc = MP_STATE_VM(last_pool)->alloc * 2;
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000135 pool->len = 0;
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000136 MP_STATE_VM(last_pool) = pool;
137 DEBUG_printf("QSTR: allocate new pool of size %d\n", MP_STATE_VM(last_pool)->alloc);
Damien429d7192013-10-04 19:53:11 +0100138 }
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000139
140 // add the new qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000141 MP_STATE_VM(last_pool)->qstrs[MP_STATE_VM(last_pool)->len++] = q_ptr;
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000142
143 // return id for the newly-added qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000144 return MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len - 1;
Damien429d7192013-10-04 19:53:11 +0100145}
146
Damien Georgec3f64d92015-11-27 12:23:18 +0000147qstr qstr_find_strn(const char *str, size_t str_len) {
Damien George55baff42014-01-21 21:40:13 +0000148 // work out hash of str
Damien George40f3c022014-07-03 13:25:24 +0100149 mp_uint_t str_hash = qstr_compute_hash((const byte*)str, str_len);
Damien George55baff42014-01-21 21:40:13 +0000150
151 // search pools for the data
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000152 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
Damien George55baff42014-01-21 21:40:13 +0000153 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
Damien George1e708fe2014-01-23 18:27:51 +0000154 if (Q_GET_HASH(*q) == str_hash && Q_GET_LENGTH(*q) == str_len && memcmp(Q_GET_DATA(*q), str, str_len) == 0) {
Damien George55baff42014-01-21 21:40:13 +0000155 return pool->total_prev_len + (q - pool->qstrs);
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000156 }
Damien429d7192013-10-04 19:53:11 +0100157 }
158 }
Damien George55baff42014-01-21 21:40:13 +0000159
160 // not found; return null qstr
161 return 0;
Damien429d7192013-10-04 19:53:11 +0100162}
163
Damien George55baff42014-01-21 21:40:13 +0000164qstr qstr_from_str(const char *str) {
165 return qstr_from_strn(str, strlen(str));
Damien429d7192013-10-04 19:53:11 +0100166}
167
Damien Georgec3f64d92015-11-27 12:23:18 +0000168qstr qstr_from_strn(const char *str, size_t len) {
Damien George4c81ba82015-01-13 16:21:23 +0000169 assert(len < (1 << (8 * MICROPY_QSTR_BYTES_IN_LEN)));
Damien George2617eeb2014-05-25 22:27:57 +0100170 qstr q = qstr_find_strn(str, len);
Damien George55baff42014-01-21 21:40:13 +0000171 if (q == 0) {
Damien Georgeade9a052015-06-13 21:53:22 +0100172 // qstr does not exist in interned pool so need to add it
173
174 // compute number of bytes needed to intern this string
Damien George25784852015-12-17 12:41:40 +0000175 size_t n_bytes = MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len + 1;
Damien Georgeade9a052015-06-13 21:53:22 +0100176
177 if (MP_STATE_VM(qstr_last_chunk) != NULL && MP_STATE_VM(qstr_last_used) + n_bytes > MP_STATE_VM(qstr_last_alloc)) {
178 // not enough room at end of previously interned string so try to grow
179 byte *new_p = m_renew_maybe(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_alloc) + n_bytes, false);
180 if (new_p == NULL) {
181 // could not grow existing memory; shrink it to fit previous
182 (void)m_renew(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_used));
183 MP_STATE_VM(qstr_last_chunk) = NULL;
184 } else {
185 // could grow existing memory
186 MP_STATE_VM(qstr_last_alloc) += n_bytes;
187 }
188 }
189
190 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
191 // no existing memory for the interned string so allocate a new chunk
Damien Georgec3f64d92015-11-27 12:23:18 +0000192 size_t al = n_bytes;
Damien Georgeade9a052015-06-13 21:53:22 +0100193 if (al < MICROPY_ALLOC_QSTR_CHUNK_INIT) {
194 al = MICROPY_ALLOC_QSTR_CHUNK_INIT;
195 }
196 MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, al);
197 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
198 // failed to allocate a large chunk so try with exact size
199 MP_STATE_VM(qstr_last_chunk) = m_new(byte, n_bytes);
200 al = n_bytes;
201 }
202 MP_STATE_VM(qstr_last_alloc) = al;
203 MP_STATE_VM(qstr_last_used) = 0;
204 }
205
206 // allocate memory from the chunk for this new interned string's data
207 byte *q_ptr = MP_STATE_VM(qstr_last_chunk) + MP_STATE_VM(qstr_last_used);
208 MP_STATE_VM(qstr_last_used) += n_bytes;
209
210 // store the interned strings' data
Damien George40f3c022014-07-03 13:25:24 +0100211 mp_uint_t hash = qstr_compute_hash((const byte*)str, len);
Damien Georgec3bd9412015-07-20 11:03:13 +0000212 Q_SET_HASH(q_ptr, hash);
Damien George95836f82015-01-11 22:27:30 +0000213 Q_SET_LENGTH(q_ptr, len);
Damien Georgec3bd9412015-07-20 11:03:13 +0000214 memcpy(q_ptr + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN, str, len);
215 q_ptr[MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len] = '\0';
Damien George55baff42014-01-21 21:40:13 +0000216 q = qstr_add(q_ptr);
Damien429d7192013-10-04 19:53:11 +0100217 }
Damien George55baff42014-01-21 21:40:13 +0000218 return q;
Damien429d7192013-10-04 19:53:11 +0100219}
220
Damien Georgec3f64d92015-11-27 12:23:18 +0000221byte *qstr_build_start(size_t len, byte **q_ptr) {
Damien George95836f82015-01-11 22:27:30 +0000222 assert(len < (1 << (8 * MICROPY_QSTR_BYTES_IN_LEN)));
Damien Georgec3bd9412015-07-20 11:03:13 +0000223 *q_ptr = m_new(byte, MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len + 1);
Damien George95836f82015-01-11 22:27:30 +0000224 Q_SET_LENGTH(*q_ptr, len);
Damien George55baff42014-01-21 21:40:13 +0000225 return Q_GET_DATA(*q_ptr);
226}
227
228qstr qstr_build_end(byte *q_ptr) {
Damien George2617eeb2014-05-25 22:27:57 +0100229 qstr q = qstr_find_strn((const char*)Q_GET_DATA(q_ptr), Q_GET_LENGTH(q_ptr));
Damien George55baff42014-01-21 21:40:13 +0000230 if (q == 0) {
Damien George25784852015-12-17 12:41:40 +0000231 size_t len = Q_GET_LENGTH(q_ptr);
Damien George40f3c022014-07-03 13:25:24 +0100232 mp_uint_t hash = qstr_compute_hash(Q_GET_DATA(q_ptr), len);
Damien Georgec3bd9412015-07-20 11:03:13 +0000233 Q_SET_HASH(q_ptr, hash);
234 q_ptr[MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len] = '\0';
Damien George55baff42014-01-21 21:40:13 +0000235 q = qstr_add(q_ptr);
236 } else {
237 m_del(byte, q_ptr, Q_GET_ALLOC(q_ptr));
238 }
239 return q;
240}
241
Damien George40f3c022014-07-03 13:25:24 +0100242mp_uint_t qstr_hash(qstr q) {
Damien George55baff42014-01-21 21:40:13 +0000243 return Q_GET_HASH(find_qstr(q));
244}
245
Damien Georgec3f64d92015-11-27 12:23:18 +0000246size_t qstr_len(qstr q) {
Damien George55baff42014-01-21 21:40:13 +0000247 const byte *qd = find_qstr(q);
248 return Q_GET_LENGTH(qd);
249}
250
251// XXX to remove!
252const char *qstr_str(qstr q) {
253 const byte *qd = find_qstr(q);
254 return (const char*)Q_GET_DATA(qd);
255}
256
Damien Georgec3f64d92015-11-27 12:23:18 +0000257const byte *qstr_data(qstr q, size_t *len) {
Damien George55baff42014-01-21 21:40:13 +0000258 const byte *qd = find_qstr(q);
259 *len = Q_GET_LENGTH(qd);
260 return Q_GET_DATA(qd);
Damien429d7192013-10-04 19:53:11 +0100261}
Damien George4d5b28c2014-01-29 18:56:46 +0000262
Damien George25784852015-12-17 12:41:40 +0000263void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, size_t *n_total_bytes) {
Damien George4d5b28c2014-01-29 18:56:46 +0000264 *n_pool = 0;
265 *n_qstr = 0;
266 *n_str_data_bytes = 0;
267 *n_total_bytes = 0;
Damien George0a2e9652016-01-31 22:24:16 +0000268 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
Damien George4d5b28c2014-01-29 18:56:46 +0000269 *n_pool += 1;
270 *n_qstr += pool->len;
271 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
272 *n_str_data_bytes += Q_GET_ALLOC(*q);
273 }
Damien George0b13f3e2014-10-24 23:12:25 +0100274 #if MICROPY_ENABLE_GC
275 *n_total_bytes += gc_nbytes(pool); // this counts actual bytes used in heap
276 #else
Damien George4d5b28c2014-01-29 18:56:46 +0000277 *n_total_bytes += sizeof(qstr_pool_t) + sizeof(qstr) * pool->alloc;
Damien George0b13f3e2014-10-24 23:12:25 +0100278 #endif
Damien George4d5b28c2014-01-29 18:56:46 +0000279 }
280 *n_total_bytes += *n_str_data_bytes;
281}
Damien Georgeea0461d2015-02-10 11:02:28 +0000282
283#if MICROPY_PY_MICROPYTHON_MEM_INFO
284void qstr_dump_data(void) {
Damien George0a2e9652016-01-31 22:24:16 +0000285 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
Damien Georgeea0461d2015-02-10 11:02:28 +0000286 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
Damien Georgee72cda92015-04-11 12:15:47 +0100287 mp_printf(&mp_plat_print, "Q(%s)\n", Q_GET_DATA(*q));
Damien Georgeea0461d2015-02-10 11:02:28 +0000288 }
289 }
290}
291#endif