From 68fe72a336c7e732164e2eacfdc8c86a25939957 Mon Sep 17 00:00:00 2001
From: daurnimator <quae@daurnimator.com>
Date: Thu, 11 May 2017 23:07:52 +1000
Subject: src/ltable.js: Iterate past dead keys

---
 src/ltable.js | 26 +++++++++++++++-----------
 1 file changed, 15 insertions(+), 11 deletions(-)

diff --git a/src/ltable.js b/src/ltable.js
index 0619efe..5eae939 100644
--- a/src/ltable.js
+++ b/src/ltable.js
@@ -150,9 +150,10 @@ const luaH_getn = function(t) {
 const luaH_next = function(L, table, keyI) {
     let keyO = L.stack[keyI];
 
-    let iterresult;
+    let iterator;
+    /* Iterate until we find the current key */
     if (keyO.type === CT.LUA_TNIL) {
-        iterresult = table.strong.keys().next();
+        iterator = table.strong.keys();
     } else {
         let hash = table_hash(keyO);
 
@@ -160,18 +161,21 @@ const luaH_next = function(L, table, keyI) {
             /* item not in table */
             return ldebug.luaG_runerror(L, defs.to_luastring("invalid key to 'next'"))
 
-        let indexes = table.strong.keys();
-        while (1) {
-            let e = indexes.next();
+        iterator = table.strong.keys();
+        do {
+            let e = iterator.next();
             if (e.done)
                 throw "unreachable";
-            else if (e.value == hash)
-                break;
-        }
-        iterresult = indexes.next();
+        } while(e.value !== hash);
     }
-    if (iterresult.done)
-        return false;
+    /* Now iterator is positioned at current key.
+     * Iterate until either out of keys, or until finding a non-dead key */
+    let iterresult
+    do {
+        iterresult = indexes.next();
+        if (iterresult.done)
+            return false;
+    } while(iterresult.value.ttisdeadkey());
 
     let entry = table.strong.get(iterresult.value);
     L.stack[keyI] = new lobject.TValue(entry.key.type, entry.key.value);
-- 
cgit v1.2.3-54-g00ecf


From 0e871348d81de72af3db293fdd28634794b28f56 Mon Sep 17 00:00:00 2001
From: daurnimator <quae@daurnimator.com>
Date: Thu, 11 May 2017 23:08:57 +1000
Subject: src/ltable.js: Reset dead_hashes after clearing out

---
 src/ltable.js | 1 +
 1 file changed, 1 insertion(+)

diff --git a/src/ltable.js b/src/ltable.js
index 5eae939..32193c8 100644
--- a/src/ltable.js
+++ b/src/ltable.js
@@ -43,6 +43,7 @@ const clean_dead_keys = function(t) {
     for (let i=0; i<t.dead_hashes.length; i++) {
         t.strong.delete(t.dead_hashes[i]);
     }
+    t.dead_hashes.length = 0;
 };
 
 const luaH_new = function(L) {
-- 
cgit v1.2.3-54-g00ecf


From 0a4061e70a1d3b0767352dbce98c961d251e3879 Mon Sep 17 00:00:00 2001
From: daurnimator <quae@daurnimator.com>
Date: Thu, 11 May 2017 23:13:27 +1000
Subject: src/ltable.js: Make next() O(1)

---
 src/ltable.js | 108 ++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 60 insertions(+), 48 deletions(-)

diff --git a/src/ltable.js b/src/ltable.js
index 32193c8..4a43936 100644
--- a/src/ltable.js
+++ b/src/ltable.js
@@ -35,13 +35,53 @@ class Table {
         this.id = L.l_G.id_counter++;
         this.strong = new Map();
         this.dead_hashes = [];
+        this.f = void 0; /* first entry */
+        this.l = void 0; /* last entry */
         this.metatable = null;
     }
 }
 
+const add = function(t, hash, key, value) {
+    clean_dead_keys(t);
+    let prev;
+    let entry = {
+        key: key,
+        value: value,
+        p: prev = t.l,
+        n: void 0
+    };
+    if (!t.f) t.f = entry;
+    if (prev) prev.n = entry;
+    t.strong.set(hash, entry);
+    t.l = entry;
+};
+
+const remove = function(t, hash) {
+    let entry = t.strong.get(hash);
+    if (entry) {
+        let next = entry.n;
+        let prev = entry.p;
+        if(prev) prev.n = next;
+        if(next) next.p = prev;
+        if(t.f === entry) t.f = next;
+        if(t.l === entry) t.l = prev;
+        t.strong.delete(hash);
+    }
+};
+
+/* Can't remove from table immediately due to next() */
+const mark_dead = function(t, hash) {
+    let e = t.strong.get(hash);
+    if (e) {
+        e.key.setdeadvalue();
+        e.value = new lobject.TValue(CT.LUA_TNIL, null);
+        t.dead_hashes.push(hash);
+    }
+}
+
 const clean_dead_keys = function(t) {
     for (let i=0; i<t.dead_hashes.length; i++) {
-        t.strong.delete(t.dead_hashes[i]);
+        remove(t, t.dead_hashes[i]);
     }
     t.dead_hashes.length = 0;
 };
@@ -77,12 +117,8 @@ const setgeneric = function(t, hash, key) {
     if (v)
         return v.value;
 
-    clean_dead_keys(t);
     let tv = new lobject.TValue(CT.LUA_TNIL, null);
-    t.strong.set(hash, {
-        key: key,
-        value: tv
-    });
+    add(t, hash, key, tv);
     return tv;
 };
 
@@ -90,7 +126,7 @@ const luaH_setint = function(t, key, value) {
     assert(typeof key == "number" && (key|0) === key && value instanceof lobject.TValue);
     let hash = key; /* table_hash known result */
     if (value.ttisnil()) {
-        delete_hash(t, hash);
+        mark_dead(t, hash);
         return;
     }
     let v = t.strong.get(hash);
@@ -98,11 +134,9 @@ const luaH_setint = function(t, key, value) {
         let tv = v.value;
         tv.setfrom(value);
     } else {
-        clean_dead_keys(t);
-        t.strong.set(hash, {
-            key: new lobject.TValue(CT.LUA_TNUMINT, key),
-            value: new lobject.TValue(value.type, value.value)
-        });
+        let k = new lobject.TValue(CT.LUA_TNUMINT, key);
+        let v = new lobject.TValue(value.type, value.value);
+        add(t, hash, k, v);
     }
 };
 
@@ -112,20 +146,10 @@ const luaH_set = function(t, key) {
     return setgeneric(t, hash, new lobject.TValue(key.type, key.value));
 };
 
-/* Can't remove from table immediately due to next() */
-const delete_hash = function(t, hash) {
-    let e = t.strong.get(hash);
-    if (e) {
-        e.key.setdeadvalue();
-        e.value = new lobject.TValue(CT.LUA_TNIL, null);
-        t.dead_hashes.push(hash);
-    }
-};
-
 const luaH_delete = function(t, key) {
     assert(key instanceof lobject.TValue);
     let hash = table_hash(key);
-    return delete_hash(t, hash);
+    return mark_dead(t, hash);
 };
 
 /*
@@ -144,41 +168,29 @@ const luaH_getn = function(t) {
     return i;
 };
 
-/*
-** Javascript tables don't have any next-like primitive.
-** For each call of `next` this does a full iteration up to the item
-*/
 const luaH_next = function(L, table, keyI) {
     let keyO = L.stack[keyI];
 
-    let iterator;
-    /* Iterate until we find the current key */
+    let entry;
     if (keyO.type === CT.LUA_TNIL) {
-        iterator = table.strong.keys();
+        entry = table.f;
     } else {
+        /* First find current key */
         let hash = table_hash(keyO);
-
-        if (!table.strong.has(hash))
+        entry = table.strong.get(hash);
+        if (!entry)
             /* item not in table */
             return ldebug.luaG_runerror(L, defs.to_luastring("invalid key to 'next'"))
-
-        iterator = table.strong.keys();
-        do {
-            let e = iterator.next();
-            if (e.done)
-                throw "unreachable";
-        } while(e.value !== hash);
+        entry = entry.n;
     }
-    /* Now iterator is positioned at current key.
-     * Iterate until either out of keys, or until finding a non-dead key */
-    let iterresult
-    do {
-        iterresult = indexes.next();
-        if (iterresult.done)
+    /* Iterate until either out of keys, or until finding a non-dead key */
+    while (1) {
+        if (!entry)
             return false;
-    } while(iterresult.value.ttisdeadkey());
-
-    let entry = table.strong.get(iterresult.value);
+        if (!entry.key.ttisdeadkey())
+            break;
+        entry = entry.n;
+    }
     L.stack[keyI] = new lobject.TValue(entry.key.type, entry.key.value);
     L.stack[keyI+1] = new lobject.TValue(entry.value.type, entry.value.value);
     return true;
-- 
cgit v1.2.3-54-g00ecf


From 8d6bc19dd30a1583ff9fec1092a2c9c7668e3e24 Mon Sep 17 00:00:00 2001
From: daurnimator <quae@daurnimator.com>
Date: Fri, 12 May 2017 00:34:46 +1000
Subject: src/ltable.js: Move dead keys to their own Map

---
 src/ltable.js | 67 ++++++++++++++++++++++++++++-------------------------------
 1 file changed, 32 insertions(+), 35 deletions(-)

diff --git a/src/ltable.js b/src/ltable.js
index 4a43936..aa3473d 100644
--- a/src/ltable.js
+++ b/src/ltable.js
@@ -34,7 +34,7 @@ class Table {
     constructor(L) {
         this.id = L.l_G.id_counter++;
         this.strong = new Map();
-        this.dead_hashes = [];
+        this.dead = new Map();
         this.f = void 0; /* first entry */
         this.l = void 0; /* last entry */
         this.metatable = null;
@@ -42,7 +42,7 @@ class Table {
 }
 
 const add = function(t, hash, key, value) {
-    clean_dead_keys(t);
+    t.dead.clear();
     let prev;
     let entry = {
         key: key,
@@ -56,36 +56,25 @@ const add = function(t, hash, key, value) {
     t.l = entry;
 };
 
-const remove = function(t, hash) {
-    let entry = t.strong.get(hash);
-    if (entry) {
-        let next = entry.n;
-        let prev = entry.p;
-        if(prev) prev.n = next;
-        if(next) next.p = prev;
-        if(t.f === entry) t.f = next;
-        if(t.l === entry) t.l = prev;
-        t.strong.delete(hash);
-    }
-};
 
-/* Can't remove from table immediately due to next() */
+/* Move out of 'strong' part and into 'dead' part. */
 const mark_dead = function(t, hash) {
     let e = t.strong.get(hash);
     if (e) {
         e.key.setdeadvalue();
         e.value = new lobject.TValue(CT.LUA_TNIL, null);
-        t.dead_hashes.push(hash);
+        let next = e.n;
+        let prev = e.p;
+        e.p = void 0; /* no need to know previous item any more */
+        if(prev) prev.n = next;
+        if(next) next.p = prev;
+        if(t.f === e) t.f = next;
+        if(t.l === e) t.l = prev;
+        t.strong.delete(hash);
+        t.dead.set(hash, e);
     }
 }
 
-const clean_dead_keys = function(t) {
-    for (let i=0; i<t.dead_hashes.length; i++) {
-        remove(t, t.dead_hashes[i]);
-    }
-    t.dead_hashes.length = 0;
-};
-
 const luaH_new = function(L) {
     return new Table(L);
 };
@@ -174,22 +163,30 @@ const luaH_next = function(L, table, keyI) {
     let entry;
     if (keyO.type === CT.LUA_TNIL) {
         entry = table.f;
+        if (!entry)
+            return false;
     } else {
         /* First find current key */
         let hash = table_hash(keyO);
+        /* Look in main part of table */
         entry = table.strong.get(hash);
-        if (!entry)
-            /* item not in table */
-            return ldebug.luaG_runerror(L, defs.to_luastring("invalid key to 'next'"))
-        entry = entry.n;
-    }
-    /* Iterate until either out of keys, or until finding a non-dead key */
-    while (1) {
-        if (!entry)
-            return false;
-        if (!entry.key.ttisdeadkey())
-            break;
-        entry = entry.n;
+        if (entry) {
+            entry = entry.n;
+            if (!entry)
+                return false;
+        } else if (!entry) {
+            /* Try dead keys */
+            entry = table.dead.get(hash);
+            if (!entry)
+                /* item not in table */
+                return ldebug.luaG_runerror(L, defs.to_luastring("invalid key to 'next'"))
+            /* Iterate until either out of keys, or until finding a non-dead key */
+            do {
+                entry = entry.n;
+                if (!entry)
+                    return false;
+            } while (entry.key.ttisdeadkey())
+        }
     }
     L.stack[keyI] = new lobject.TValue(entry.key.type, entry.key.value);
     L.stack[keyI+1] = new lobject.TValue(entry.value.type, entry.value.value);
-- 
cgit v1.2.3-54-g00ecf