From 63bfa85e6a63f0718f8e644921201b26bbe8bfd8 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sun, 27 Sep 2026 18:48:32 +0100 Subject: Find a burst's keys in one look A message for a document scanned the burst's pending keys with strcmp to see whether its key was there, and the host scanned the burst's earlier requests the same way before each one: both quadratic in the burst (64 concurrent reads, about 31 compares each, twice). The app now indexes its pending documents by key (open addressing over an FNV-1a hash, 1 KiB), answers pure_app_pending in one look, and the host asks it; whether the current event's document is pending is a flag instead of a scan by pointer. Bursts split where they did, except that on an owner, which applies a round's reads first, an edit of a key read in the same round now splits the burst at the host rather than the app saving on its own. A unit test checks the index at 200 keys. --- core/test-module.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) (limited to 'core/test-module.c') diff --git a/core/test-module.c b/core/test-module.c index ccb3371..307d565 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -1716,6 +1716,38 @@ static void deferred_messages(void) { remove_store(path); } +/* The burst's keys are found in one look (an index over their hashes, most + * slots shared at 200 keys): every pending key and no other, reads as well + * as edits, and a message for one of them saves the burst first. */ +static void pending_keys(void) { + char *path = new_store(); + CHECK(load(editor_spec, &module_a) == PURE_OK); + PureApp app; + unsigned char buffer[64]; + char key[8]; + CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK && pure_app_defer(&app, true)); + for (int i = 0; i < 200; ++i) { + snprintf(key, sizeof(key), "p%d", i); + CHECK(!pure_app_pending(&app, key)); + CHECK(pure_app_message(&app, 1, key, 0, edit_payload(buffer, 0, 0, "q")) == PURE_OK); + } + CHECK(pure_app_save(&app) == PURE_OK && !pure_app_pending(&app, "p0")); + for (int i = 0; i < 200; ++i) { + snprintf(key, sizeof(key), "p%d", i); + CHECK((i % 2 ? pure_app_message(&app, 0, key, -1, (PureSpan){0}) + : pure_app_message(&app, 1, key, 1, edit_payload(buffer, 1, 0, "r"))) == PURE_OK); + } + for (int i = 0; i < 210; ++i) { + snprintf(key, sizeof(key), "p%d", i); + CHECK(pure_app_pending(&app, key) == (i < 200)); + } + CHECK(!pure_app_pending(&app, "p") && !pure_app_pending(&app, "p1000") && app.pending_count == 200); + CHECK(pure_app_message(&app, 0, "p150", -1, (PureSpan){0}) == PURE_OK && app.pending_count == 1); + CHECK(pure_app_pending(&app, "p150") && !pure_app_pending(&app, "p151")); + pure_app_stop(&app); + remove_store(path); +} + static void deferred(void) { static const char *const list_words[] = {"a", "\xea\xb0\x80", "", "\n", "\xf0\x9f\x98\x80"}; static const char *const text_words[] = {"a", "\xea\xb0\x80", "\n", "\xf0\x9f\x98\x80", "xy\nz", ""}; @@ -1723,6 +1755,7 @@ static void deferred(void) { deferred_equivalence(text_spec, text_words, LEN(text_words), 0x1b873593u); deferred_bursts(); deferred_messages(); + pending_keys(); } /* Text inserted at a cursor goes before it; at a mark (a cursor that stays), -- cgit v1.2.3