Re: Proposal: Constant Tables

[Lars Doelle <lars.doelle@...>]

> From: Xavier Wang <weasley.wx@gmail.com>

> maybe you can write you own hash function in lua:
> 
> function hash(tbl) ... end

I actually managed to hack something. The trick is in
'basekey', which produces a usable hash key of whatever
you through at it.

The remainder is a usual external hash table which doesn't
come out too costly, in the end. I've not yet tried the module
under load, but it comes out surprisingly well even written in
LUA itself.

Hope it helps people using composed keys.

-lars


-- ------------------------------------------------------
-- [ToData.lua]
-- Copyright (c) 2011 Lars Dölle <lars.doelle@on-line.de>
-- ------------------------------------------------------

-- 'basekey' is used to simulate hashing

local basekeys = {}
setmetatable( basekeys, { __mode = "k" }) -- ephemeron

local function pair_key(k,v)
  if not basekeys[k] then basekeys[k] = math.random() end
  if not basekeys[v] then basekeys[v] = math.random() end
  return (907+basekeys[k])*(103 + basekeys[v])
end

-- 'const_table' is a hash table knowing all const tables

local const_table = {}
setmetatable( const_table, { __mode = "k" }) -- ephemeron

local function table_key(tbl)
  local hash_key = 401
  for k,v in pairs(tbl) do
    hash_key = hash_key + pair_key(k,v)
  end
  return hash_key
end

local function table_subtable(a,b)
  for k,v in pairs(a) do
    if b[k] ~= v then
      return false
    end
  end
  return true
end

local function table_equal(a,b)
  return table_subtable(a,b)
     and table_subtable(b,a)
end

-- make 'tbl' unique

local function todata(tbl)

  if type(tbl) ~= "table" then return tbl end
  if basekeys[tbl] then return tbl end

  -- do real hashing

  local key = table_key(tbl)
  local val = const_table[key]
  if not val then
    val = {}
    const_table[key] = val
  end

  for _,v in ipairs(val) do
    if table_equal(v,tbl) then
      return v
    end
  end

  -- shallow copy

  local con = {}
  for k,v in pairs(tbl) do
    k = todata(k)
    v = todata(v)
    con[k] = v
  end

  table.insert(val,con)
  basekeys[con] = math.random()

  return con

end

local a = todata({first = "John", last = "Doe"})
local b = todata({first = "John", last = "Doe"})
local c = todata({a,b})
local d = todata({b,a})
print(a,b,c,d)

return todata