Merge with 0.10

[prosody.git] / util / multitable.lua

diff --git a/util/multitable.lua b/util/multitable.lua
index e5e875216970b980baa0e2ecc02082b3adb0f4a4..caf25118e3f622ecd66dbea06b5c24de7abba968 100644 (file)
--- a/util/multitable.lua
+++ b/util/multitable.lua
@@ -1,17 +1,14 @@
--- Prosody IM v0.3
--- Copyright (C) 2008-2009 Matthew Wild
--- Copyright (C) 2008-2009 Waqas Hussain
--- 
+-- Prosody IM
+-- Copyright (C) 2008-2010 Matthew Wild
+-- Copyright (C) 2008-2010 Waqas Hussain
+--
 -- This project is MIT/X11 licensed. Please see the
 -- COPYING file in the source package for more information.
 --
 
-
-
 local select = select;
 local t_insert = table.insert;
-local pairs = pairs;
-local next = next;
+local unpack, pairs, next, type = unpack, pairs, next, type;
 
 module "multitable"
 
@@ -56,7 +53,7 @@ local function r(t, n, _end, ...)
                return;
        end
        if k then
-               v = t[k];
+               local v = t[k];
                if v then
                        r(v, n+1, _end, ...);
                        if not next(v) then
@@ -82,6 +79,88 @@ local function remove(self, ...)
 end
 
 
+local function s(t, n, results, _end, ...)
+       if t == nil then return; end
+       local k = select(n, ...);
+       if n == _end then
+               if k == nil then
+                       for _, v in pairs(t) do
+                               t_insert(results, v);
+                       end
+               else
+                       t_insert(results, t[k]);
+               end
+               return;
+       end
+       if k then
+               local v = t[k];
+               if v then
+                       s(v, n+1, results, _end, ...);
+               end
+       else
+               for _,b in pairs(t) do
+                       s(b, n+1, results, _end, ...);
+               end
+       end
+end
+
+-- Search for keys, nil == wildcard
+local function search(self, ...)
+       local _end = select('#', ...);
+       for n = _end,1 do
+               if select(n, ...) then _end = n; break; end
+       end
+       local results = {};
+       s(self.data, 1, results, _end, ...);
+       return results;
+end
+
+-- Append results to an existing list
+local function search_add(self, results, ...)
+       if not results then results = {}; end
+       local _end = select('#', ...);
+       for n = _end,1 do
+               if select(n, ...) then _end = n; break; end
+       end
+       s(self.data, 1, results, _end, ...);
+       return results;
+end
+
+function iter(self, ...)
+       local query = { ... };
+       local maxdepth = select("#", ...);
+       local stack = { self.data };
+       local keys = { };
+       local function it(self)
+               local depth = #stack;
+               local key = next(stack[depth], keys[depth]);
+               if key == nil then -- Go up the stack
+                       stack[depth], keys[depth] = nil, nil;
+                       if depth > 1 then
+                               return it(self);
+                       end
+                       return; -- The end
+               else
+                       keys[depth] = key;
+               end
+               local value = stack[depth][key];
+               if query[depth] == nil or key == query[depth] then
+                       if depth == maxdepth then -- Result
+                               local result = {}; -- Collect keys forming path to result
+                               for i = 1, depth do
+                                       result[i] = keys[i];
+                               end
+                               result[depth+1] = value;
+                               return unpack(result, 1, depth+1);
+                       elseif type(value) == "table" then
+                               t_insert(stack, value); -- Descend
+                       end
+               end
+               return it(self);
+       end;
+       return it, self;
+end
+
 function new()
        return {
                data = {};
@@ -89,6 +168,9 @@ function new()
                add = add;
                set = set;
                remove = remove;
+               search = search;
+               search_add = search_add;
+               iter = iter;
        };
 end