Module set
A set is a compact, immutable set of strings, queried by binary search.
It stores many short strings as a sorted blob of key bytes plus a uint32 offset
array, with no per-key allocation, so it costs about length + 4 bytes per key,
instead of the hash node and slab rounding a Lua or rcu table pays per key.
Built once, it is then read-only: lookups take no lock and allocate nothing, safe
from softirq.
set.new builds a plain set, tested for exact membership with set:has: a single
binary search, O(log n).
set.labeled builds a labeled set: each member carries a 32-bit label bitmask, and
set:match walks a key by . returning the bitwise OR of the labels of every member
that is a suffix of it (0 when nothing matches); one binary search per .-separated
level, O(d log n) for a d-level key.
See also:
Functions
| __len () | Returns the number of members. |
Class set
| set:has (s) | Returns whether a string is in the set. |
| set:new (strings) | Builds a plain set from an array of strings. |
Class set.labeled
| set.labeled:labeled (t) | Builds a labeled set from a table of members, each with a label bitmask. |
| set.labeled:match (s) | Returns the union of the labels of s and its suffixes, or 0. |
Functions
Class set
- set:has (s)
-
Returns whether a string is in the set.
Parameters:
- s string the string to test.
Returns:
-
boolean
whether
sis in the set. - set:new (strings)
-
Builds a plain set from an array of strings.
The array is sorted in place. The members must be unique; duplicates are kept, which keeps lookups correct but wastes space, so de-duplicate first if it matters. It allocates, so call it where it can sleep (a process-context runtime, or any runtime's load).
Parameters:
- strings {string,...} the member strings, in any order.
Returns:
-
set
the built set.
Raises:
Error on a non-string member, if the keys exceed 4 GiB, or on allocation failure.Usage:
local s = set.new({ "alpha", "bravo" })
Class set.labeled
- set.labeled:labeled (t)
-
Builds a labeled set from a table of members, each with a label bitmask.
It allocates, so call it where it can sleep (a process-context runtime, or any runtime's load).
Parameters:
- t
{[string]=integer}
the member/labels pairs; labels are in
[1, 2^32).
Returns:
-
set.labeled
the built labeled set.
Raises:
Error on a non-string member, a label outside[1, 2^32), if the members exceed 4 GiB, or on allocation failure.Usage:
local s = set.labeled({ ["a.b.c"] = 1, ["b.c"] = 2, ["c"] = 4 }) local labels = s:match("a.b.c") --> 7, the union 1 | 2 | 4
- t
{[string]=integer}
the member/labels pairs; labels are in
- set.labeled:match (s)
-
Returns the union of the labels of
sand its suffixes, or 0.Walks
sby.("a.b.c"tries"a.b.c","b.c","c"), ORing the labels of every level that is a member. This roots the hierarchy on the right.Parameters:
- s string the string to look up.
Returns:
-
integer
the union of the matching levels' labels, or 0.