prosody
638f627e707f
spec/util_iterators_spec.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Annotate

spec/util_iterators_spec.lua @ 13134:638f627e707f

util.datamanager: Add O(1) list indexing with on-disk index Index file contains offsets and lengths of each item() which allows seeking directly to each item and reading it without parsing the entire file. Also allows tricks like binary search, assuming items have some defined order. We take advantage of the 1-based indexing in tables to store a magic header in the 0 position, so that table index 1 ends up at file index 1.
author Kim Alvefur <zash@zash.se>
date Tue, 11 May 2021 02:09:56 +0200
parent 12744:e894677359e5
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
8802
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
1 local iter = require "util.iterators";
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
2
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
3 describe("util.iterators", function ()
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
4 describe("join", function ()
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
5 it("should produce a joined iterator", function ()
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
6 local expect = { "a", "b", "c", 1, 2, 3 };
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
7 local output = {};
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
8 for x in iter.join(iter.values({"a", "b", "c"})):append(iter.values({1, 2, 3})) do
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
9 table.insert(output, x);
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
10 end
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
11 assert.same(output, expect);
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
12 end);
12744
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
13 it("should work with only a single iterator", function ()
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
14 local expect = { "a", "b", "c" };
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
15 local output = {};
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
16 for x in iter.join(iter.values({"a", "b", "c"})) do
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
17 table.insert(output, x);
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
18 end
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
19 assert.same(output, expect);
e894677359e5 util.iterators: join: Work even with only a single iterator in the chain
Matthew Wild <mwild1@gmail.com>
parents: 9328
diff changeset
20 end);
8802
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
21 end);
9327
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
22
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
23 describe("sorted_pairs", function ()
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
24 it("should produce sorted pairs", function ()
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
25 local orig = { b = 1, c = 2, a = "foo", d = false };
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
26 local n, last_key = 0, nil;
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
27 for k, v in iter.sorted_pairs(orig) do
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
28 n = n + 1;
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
29 if last_key then
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
30 assert(k > last_key, "Expected "..k.." > "..last_key)
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
31 end
9328
a9592107021b util.iterators tests: Check value matches expected [luacheck]
Matthew Wild <mwild1@gmail.com>
parents: 9327
diff changeset
32 assert.equal(orig[k], v);
9327
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
33 last_key = k;
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
34 end
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
35 assert.equal("d", last_key);
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
36 assert.equal(4, n);
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
37 end);
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
38
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
39 it("should allow a custom sort function", function ()
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
40 local orig = { b = 1, c = 2, a = "foo", d = false };
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
41 local n, last_key = 0, nil;
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
42 for k, v in iter.sorted_pairs(orig, function (a, b) return a > b end) do
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
43 n = n + 1;
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
44 if last_key then
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
45 assert(k < last_key, "Expected "..k.." > "..last_key)
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
46 end
9328
a9592107021b util.iterators tests: Check value matches expected [luacheck]
Matthew Wild <mwild1@gmail.com>
parents: 9327
diff changeset
47 assert.equal(orig[k], v);
9327
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
48 last_key = k;
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
49 end
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
50 assert.equal("a", last_key);
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
51 assert.equal(4, n);
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
52 end);
f6f1dec164b5 util.iterators: Add sorted_pairs() method
Matthew Wild <mwild1@gmail.com>
parents: 8805
diff changeset
53 end);
8802
befffddf1b25 Fix wrong tests committed with 7b621a4a2e8d
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
54 end);