How to search Lua table values

Question

I have a project that calls for a relational database like structure in an environment where an actual database isn't possible. The language is restricted to Lua, which is far from being my strongest language. I've got a table of tables with a structure like this:

table={
  m:r={
    x=1
    y=1
    displayName="Red"
  }
  m:y={
    x=1
    y=2
    displayName="Yellow"
  }
}

Building, storing and retrieving the table is straightforward enough. Where I'm running into issues is searching it. For the sake of clarity, if I could use SQL I'd do this:

SELECT * FROM table WHERE displayName="Red"

Is there a Lua function that will let me search this way?

Answer 1

There are no built-in functions for searching tables. There are many ways to go about it which vary in complexity and efficiency.

local t = {
  r={displayname="Red", name="Ruby", age=15, x=4, y=10},
  y={displayname="Blue", name="Trey", age=22, x=3, y=2},
  t={displayname="Red", name="Jack", age=20, x=2, y=3},
  h={displayname="Red", name="Tim", age=25, x=2, y=33},
  v={displayname="Blue", name="Bonny", age=10, x=2, y=0}
}

In Programming in Lua they recommend building a reverse table for efficient look ups.

 revDisplayName = {}
 for k,v in pairs(t) do
      if revDisplayName[v.displayname] then
          table.insert(revDisplayName[v.displayname], k)
      else
         revDisplayName[v] = {k}
      end
 end 

Then you can match display names easily

for _, rowname in pairs(revDisplayName["Red"]) do
   print(t[rowname].x, t[rowname].y)
end

There is code for creating SQL-like queries in Lua, on Lua tables, in Beginning Lua Programming if you want to build complex queries.

If you just want to search through a few records for matches, you can abstract the searching using an iterator in Lua

function allmatching(tbl, kvs)
  return function(t, key)
    repeat
      key, row = next(t, key)
      if key == nil then
        return
      end
      for k, v in pairs(kvs) do
        if row[k] ~= v then
          row = nil
          break
        end
      end
    until row ~= nil
    return key, row
  end, tbl, nil
end

which you can use like so:

for k, row in allmatching(t, {displayname="Red", x=2}) do
  print(k, row.name, row.x, row.y)
end

which prints

h   Tim     2   33
t   Jack    2   3

Answer 2

The straightforward way is to iterate through all elements and find one that matches your criteria:

local t={
  r={
    x=1,
    y=1,
    displayName="Red",
  },
  y={
    x=1,
    y=2,
    displayName="Yellow",
  },
}
for key, value in pairs(t) do
  if value.displayName == 'Red' then
    print(key)
  end
end

This should print 'r'.

This may be quite slow on large tables. To speed up this process, you may keep track of the references in a hash that will provide much faster access. Something like this may work:

local cache = {}

local function findValue(key)
  if cache[key] == nil then
    local value
    -- do a linear search iterating through table elements searching for 'key'
    -- store the result if found
    cache[key] = value
  end
  return cache[key]
end

If the elements in the table change their values, you'll need to invalidate the cache when the values are updated or removed.