From 602780a58c3286d6843e8ff89bd7a3093891a7ad Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sun, 4 Oct 2026 17:39:18 +0100 Subject: Search an event's keyed lists by a key set and lists by fingers, add by key in one descent, and loop without recursion (020) - An event's list keyed by a number keeps its keys beside its tree: bits while they are small whole numbers, else an open-addressing table; has() reads only that, and inserts, removes, key changes, their undoing and clears keep it. - Each thread keeps fingers on the last four leaves it read (list id and version must match): reads by position and searches by key that land in them do not descend. - pure_list_add finds a key's place and inserts there in one descent; a stored keyed list's appends take it too, journaled as inserts. - Child searches count over the whole guide; item fields know at load whether they are text; loops run on a stack of loop records, not by recursion; module-list.c builds at -O3. - test-module: the key set and fingers answer as a model at every step (bits to table, removes inside runs, undone changes, clears, shares), and a stored keyed list's adds replay from its journal. --- core/module-list.h | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'core/module-list.h') diff --git a/core/module-list.h b/core/module-list.h index 69e0d7d..4778280 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -101,6 +101,12 @@ void pure_retired_free(PureRetired *); /* Insert a copy of cells (text bytes are copied) before position at. A NULL * log means the change is not undone. */ PureResult pure_list_insert(PureList *, size_t at, const PureCell *cells, PureUndo *); +/* An item into a list kept in order of a number field, where its key goes, + * found and placed in one descent (docs/design/020): at says where, exists + * whether an item had the key (then nothing changes). Its change is logged + * and journaled as pure_list_insert's. PURE_INVALID when the list is not + * such a one (search it and insert then). */ +PureResult pure_list_add(PureList *, const PureCell *cells, PureUndo *, size_t *at, bool *exists); PureResult pure_list_remove(PureList *, size_t at, PureUndo *); PureResult pure_list_set(PureList *, size_t at, unsigned field, PureCell value, PureUndo *); PureCell pure_list_get(const PureList *, size_t at, unsigned field); @@ -117,6 +123,17 @@ size_t pure_list_seek(const PureList *, unsigned field, PureCell key, bool *foun * field, seek by it reads each level's keys from one node (field -1, or a * text field: none). ALLOCATION leaves the list searched as if it had none. */ PureResult pure_list_keyed(PureList *, int field); +/* A list keyed by a number keeps its keys as a set too, beside its tree + * (docs/design/020): pure_list_contains answers whether a key is there + * without a search. Its changes and their undoing keep the set; a share of + * it has none. For the lists an event searches most (its own). False when + * it is not keyed by a number, is a copy, or memory runs out (it is + * searched as before). */ +bool pure_list_hashed(PureList *); +/* Whether key is there, by the set: false when the list keeps none (search it then). */ +bool pure_list_contains(const PureList *, double key, bool *found); +/* The bytes it keeps beside its items for that. */ +size_t pure_list_extra(const PureList *); /* The list's items ordered by field, as a keyed list keeps them: *out is NULL * when they already are, or a new list in that order with moved[position * before] = position after for every item. CONFLICT when two items have the -- cgit v1.2.3