src/ltable.js: Make next() O(1)

1 files 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;