From cb0295e52870f22c5dd1a1726342b8d4b147b1c5 Mon Sep 17 00:00:00 2001 From: daurnimator Date: Tue, 2 May 2017 16:37:50 +1000 Subject: Refactor table implementation --- src/ltable.js | 191 +++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 137 insertions(+), 54 deletions(-) (limited to 'src/ltable.js') 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; -- cgit v1.2.3-54-g00ecf