setModule
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 aboutlength + 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
Class set
| set:has (s) | Returns whether a string is in the set. |
set
| labeled (t) | Builds a labeled set from a table of members, each with a label bitmask. |
| new (strings) | Builds a plain set from an array of strings. |
Class set.labeled
| set.labeled:match (s) | Returns the union of the labels of s and its suffixes, or 0. |
Class set in detail
- 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 in detail
- 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, 232).
Returns
-
set.labeled
the built labeled set.
Raises
Error on a non-string member, a label outside[1, 232), 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
- 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 table with entries and no sequence (set.labeled takes a map), a non-string member, if the keys exceed 4 GiB, or on allocation failure.Usage
local s = set.new({ "alpha", "bravo" })
Class set.labeled in detail
- 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.