summaryrefslogtreecommitdiff
path: root/src/ltable.js
diff options
context:
space:
mode:
authordaurnimator <quae@daurnimator.com>2017-05-02 16:37:50 +1000
committerdaurnimator <quae@daurnimator.com>2017-05-03 12:20:43 +1000
commitcb0295e52870f22c5dd1a1726342b8d4b147b1c5 (patch)
tree3655d4d6f4873ed246c00c0eb6680a06124f3046 /src/ltable.js
parent50820e54d065bffbb504e6b20b6c27802e102c25 (diff)
downloadfengari-cb0295e52870f22c5dd1a1726342b8d4b147b1c5.tar.gz
fengari-cb0295e52870f22c5dd1a1726342b8d4b147b1c5.tar.bz2
fengari-cb0295e52870f22c5dd1a1726342b8d4b147b1c5.zip
Refactor table implementation
Diffstat (limited to 'src/ltable.js')
-rw-r--r--src/ltable.js191
1 files changed, 137 insertions, 54 deletions
diff --git a/src/ltable.js b/src/ltable.js
index 432a91d..0d711b4 100644
--- a/src/ltable.js
+++ b/src/ltable.js
@@ -1,84 +1,167 @@
/*jshint esversion: 6 */
"use strict";
+const assert = require('assert');
+
const defs = require('./defs.js');
+const ldebug = require('./ldebug.js');
const lobject = require('./lobject.js');
const CT = defs.constant_types;
-
-const ordered_intindexes = function(table) {
- return [...table.value.keys()]
- .filter(e => typeof e === 'number' && e % 1 === 0 && e > 0) // Only integer indexes
- .sort(function (a, b) {
- return a > b ? 1 : -1;
- });
+/* converts strings (arrays) to a consistent map key */
+const hashstr = function(str) {
+ return str.map(e => `${e}|`).join('');
};
-const ordered_indexes = function(table) {
- return [...table.value.keys()]
- .sort(function(a, b) {
- if (typeof a !== "number" || a <= 0) return 1;
- if (typeof b !== "number" || b <= 0) return -1;
- return a > b ? 1 : -1;
- });
+const table_hash = function(key) {
+ switch(key.type) {
+ case CT.LUA_TBOOLEAN:
+ case CT.LUA_TLIGHTUSERDATA: /* XXX: if user pushes conflicting lightuserdata then the table will do odd things */
+ case CT.LUA_TNUMFLT:
+ case CT.LUA_TNUMINT:
+ case CT.LUA_TTABLE:
+ case CT.LUA_TLCL:
+ case CT.LUA_TLCF:
+ case CT.LUA_TCCL:
+ case CT.LUA_TUSERDATA:
+ case CT.LUA_TTHREAD:
+ return key.value;
+ case CT.LUA_TSHRSTR:
+ case CT.LUA_TLNGSTR:
+ return hashstr(key.value);
+ default:
+ throw new Error("unknown key type: " + key.type);
+ }
};
const luaH_new = function(L) {
- let t = new Map();
+ let t = {
+ strong: new Map(),
+ metatable: null
+ };
return t;
};
-/*
-** Try to find a boundary in table 't'. A 'boundary' is an integer index
-** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
-*/
-const luaH_getn = function(table) {
- let indexes = ordered_intindexes(table);
- let len = indexes.length;
+const getgeneric = function(t, hash) {
+ let v = t.strong.get(hash);
+ return v ? v.value : lobject.luaO_nilobject;
+};
- // If first index != 1, length is 0
- if (indexes[0] !== 1) return 0;
+const luaH_getint = function(t, key) {
+ assert(typeof key == "number");
+ return getgeneric(t, key);
+};
- for (let i = 0; i < len; i++) {
- let key = indexes[i];
+const luaH_getstr = function(t, key) {
+ assert(Array.isArray(key));
+ return getgeneric(t, hashstr(key));
+};
- if (!lobject.table_index(table, key).ttisnil() // t[key] is non-nil
- && (indexes[i + 1] - key > 1 || lobject.table_index(table, indexes[i + 1]).ttisnil())) { // gap with next key or next value is nil
- return indexes[i];
- }
- }
+const luaH_get = function(t, key) {
+ assert(key instanceof lobject.TValue);
+ if (key.ttisnil())
+ return lobject.luaO_nilobject;
+ return getgeneric(t, table_hash(key));
+};
- return 0;
+const setgeneric = function(t, hash, key) {
+ let v = t.strong.get(hash);
+ if (v)
+ return v.value;
+
+ let tv = new lobject.TValue(CT.LUA_TNIL, null);
+ t.strong.set(hash, {
+ key: key,
+ value: tv
+ });
+ return tv;
};
-const luaH_next = function(L, table, keyI) {
- let keyO = L.stack[keyI];
- let key = lobject.table_keyValue(keyO);
- let indexes = ordered_indexes(table);
+const luaH_setint = function(t, key, value) {
+ assert(typeof key == "number" && value instanceof lobject.TValue && key|0 === key);
+ let hash = key; /* table_hash known result */
+ let v = t.strong.get(hash);
+ if (v) {
+ let tv = v.value;
+ tv.setfrom(value);
+ } else {
+ t.strong.set(hash, {
+ key: new lobject.TValue(CT.LUA_TNUMINT, key),
+ value: new lobject.TValue(value.type, value.value)
+ });
+ }
+};
- if (indexes.length === 0) return 0;
+const luaH_set = function(t, key) {
+ assert(key instanceof lobject.TValue);
+ let hash = table_hash(key);
+ return setgeneric(t, hash, new lobject.TValue(key.type, key.value));
+};
- let i = indexes.indexOf(key);
+const luaH_delete = function(t, key) {
+ assert(key instanceof lobject.TValue);
+ let hash = table_hash(key);
+ t.strong.delete(hash);
+};
- if ((i >= 0 || key === null) && i < indexes.length - 1) {
- if (key === null) i = -1;
- let nidx = indexes[i+1];
- let tnidx = typeof nidx;
+/*
+** Try to find a boundary in table 't'. A 'boundary' is an integer index
+** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
+*/
+const luaH_getn = function(t) {
+ let i = 0;
+ let j = t.strong.size + 1; /* use known size of Map to bound search */
+ /* now do a binary search between them */
+ while (j - i > 1) {
+ let m = Math.floor((i+j)/2);
+ if (luaH_getint(t, m).ttisnil()) j = m;
+ else i = m;
+ }
+ return i;
+};
- if (tnidx === 'number' && nidx % 1 === 0)
- L.stack[keyI] = new lobject.TValue(CT.LUA_TNUMINT, indexes[i + 1]);
- else if (tnidx === 'string')
- L.stack[keyI] = new lobject.TValue(CT.LUA_TLNGSTR, indexes[i + 1].split('|').map(e => Number.parseInt(e)).slice(0, -1));
- else
- L.stack[keyI] = indexes[i + 1];
+/*
+** 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];
- L.stack[keyI + 1] = table.value.get(indexes[i + 1]);
- return 1;
+ let iterresult;
+ if (keyO.type === CT.LUA_TNIL) {
+ iterresult = table.strong.keys().next();
+ } else {
+ let hash = table_hash(keyO);
+
+ if (!table.strong.has(hash))
+ /* item not in table */
+ return ldebug.luaG_runerror(L, "invalid key to 'next'");
+
+ let indexes = table.strong.keys();
+ while (1) {
+ let e = indexes.next();
+ if (e.done)
+ throw "unreachable";
+ else if (e.value == hash)
+ break;
+ }
+ iterresult = indexes.next();
}
+ if (iterresult.done)
+ return false;
- return 0;
+ let entry = table.strong.get(iterresult.value);
+ 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;
};
-module.exports.luaH_new = luaH_new;
-module.exports.luaH_next = luaH_next;
-module.exports.luaH_getn = luaH_getn;
+module.exports.luaH_delete = luaH_delete;
+module.exports.luaH_get = luaH_get;
+module.exports.luaH_getint = luaH_getint;
+module.exports.luaH_getn = luaH_getn;
+module.exports.luaH_getstr = luaH_getstr;
+module.exports.luaH_set = luaH_set;
+module.exports.luaH_setint = luaH_setint;
+module.exports.luaH_new = luaH_new;
+module.exports.luaH_next = luaH_next;