summaryrefslogtreecommitdiff
path: root/src/ltable.js
diff options
context:
space:
mode:
authordaurnimator <quae@daurnimator.com>2017-05-11 23:13:27 +1000
committerdaurnimator <quae@daurnimator.com>2017-05-12 00:12:38 +1000
commit0a4061e70a1d3b0767352dbce98c961d251e3879 (patch)
tree1d6028b6ff3e931411106759c41380f0d352e58d /src/ltable.js
parent0e871348d81de72af3db293fdd28634794b28f56 (diff)
downloadfengari-0a4061e70a1d3b0767352dbce98c961d251e3879.tar.gz
fengari-0a4061e70a1d3b0767352dbce98c961d251e3879.tar.bz2
fengari-0a4061e70a1d3b0767352dbce98c961d251e3879.zip
src/ltable.js: Make next() O(1)
Diffstat (limited to 'src/ltable.js')
-rw-r--r--src/ltable.js108
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;