Split qstr into pools, and put initial pool in ROM.

Qstr's are now split into a linked-list of qstr pools.  This has 2
benefits: the first pool can be in ROM (huge benefit, since we no longer
use RAM for the core qstrs), and subsequent pools use m_new for the next
pool instead of m_renew (thus avoiding a huge single table for all the
qstrs).

Still would be better to use a hash table, but this scheme takes us part
of the way (eventually convert the pools to hash tables).

Also fixed bug with import.

Also improved the way the module code is referenced (not magic number 1
anymore).

1 files changed, 78 insertions, 23 deletions

diff --git a/py/qstr.c b/py/qstr.c
index 0dd8a04b7..0ed7aa9a2 100644
--- a/py/qstr.c
+++ b/py/qstr.c
@@ -2,55 +2,110 @@
 #include <string.h>
 
 #include "misc.h"
+#include "mpqstr.h"
 
-static int qstrs_alloc;
-static int qstrs_len;
-static const char **qstrs;
+// 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
+#include <stdio.h>
+#define DEBUG_printf(args...) printf(args)
+#else // don't print debugging info
+#define DEBUG_printf(args...) (void)0
+#endif
+
+typedef struct _qstr_pool_t {
+    struct _qstr_pool_t *prev;
+    uint total_prev_len;
+    uint alloc;
+    uint len;
+    const char *qstrs[];
+} 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
+    {
+        "nil", // must be first, since 0 qstr is nil
+#define Q(id) #id,
+#include "mpqstrraw.h"
+#undef Q
+    },
+};
+
+static qstr_pool_t *last_pool = (qstr_pool_t*)&const_pool; // we won't modify the const_pool since it has no allocated room left
 
 void qstr_init(void) {
-    qstrs_alloc = 400;
-    qstrs_len = 1;
-    qstrs = m_new(const char*, qstrs_alloc);
-    qstrs[0] = "nil";
+    // nothing to do!
 }
 
 static qstr qstr_add(const char *str) {
-    if (qstrs_len >= qstrs_alloc) {
-        qstrs = m_renew(const char*, qstrs, qstrs_alloc, qstrs_alloc * 2);
-        qstrs_alloc *= 2;
+    DEBUG_printf("QSTR: add %s\n", str);
+
+    // 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);
     }
-    qstrs[qstrs_len++] = str;
-    return qstrs_len - 1;
+
+    // add the new qstr
+    last_pool->qstrs[last_pool->len++] = str;
+
+    // return id for the newly-added qstr
+    return last_pool->total_prev_len + last_pool->len - 1;
 }
 
 qstr qstr_from_str_static(const char *str) {
-    for (int i = 0; i < qstrs_len; i++) {
-        if (strcmp(qstrs[i], str) == 0) {
-            return i;
+    for (qstr_pool_t *pool = last_pool; pool != NULL; pool = pool->prev) {
+        for (const char **qstr = pool->qstrs, **qstr_top = pool->qstrs + pool->len; qstr < qstr_top; qstr++) {
+            if (strcmp(*qstr, str) == 0) {
+                return pool->total_prev_len + (qstr - pool->qstrs);
+            }
         }
     }
     return qstr_add(str);
 }
 
 qstr qstr_from_str_take(char *str, int alloc_len) {
-    for (int i = 0; i < qstrs_len; i++) {
-        if (strcmp(qstrs[i], str) == 0) {
-            m_del(char, str, alloc_len);
-            return i;
+    for (qstr_pool_t *pool = last_pool; pool != NULL; pool = pool->prev) {
+        for (const char **qstr = pool->qstrs, **qstr_top = pool->qstrs + pool->len; qstr < qstr_top; qstr++) {
+            if (strcmp(*qstr, str) == 0) {
+                m_del(char, str, alloc_len);
+                return pool->total_prev_len + (qstr - pool->qstrs);
+            }
         }
     }
     return qstr_add(str);
 }
 
 qstr qstr_from_strn_copy(const char *str, int len) {
-    for (int i = 0; i < qstrs_len; i++) {
-        if (strncmp(qstrs[i], str, len) == 0 && qstrs[i][len] == '\0') {
-            return i;
+    for (qstr_pool_t *pool = last_pool; pool != NULL; pool = pool->prev) {
+        for (const char **qstr = pool->qstrs, **qstr_top = pool->qstrs + pool->len; qstr < qstr_top; qstr++) {
+            if (strncmp(*qstr, str, len) == 0 && (*qstr)[len] == '\0') {
+                return pool->total_prev_len + (qstr - pool->qstrs);
+            }
         }
     }
     return qstr_add(strndup(str, len));
 }
 
+// convert qstr id to pointer to its string
 const char *qstr_str(qstr qstr) {
-    return qstrs[qstr];
+    // search
+    for (qstr_pool_t *pool = last_pool; pool != NULL; pool = pool->prev) {
+        if (qstr >= pool->total_prev_len) {
+            return pool->qstrs[qstr - pool->total_prev_len];
+        }
+    }
+
+    // not found, return nil
+    return const_pool.qstrs[0];
 }