From 07791a8b9f9c25e83ef849e1cea431ed25be7553 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 06:54:21 +0100 Subject: Keep an event's lists in arrays, flat or at their keys, and read a field by key as one (021) - pure_list_arrays: an event's list (never shared, journaled or undone) keeps its items in arrays: FLAT in order, or DENSE at their keys when keyed by small whole numbers. A position asked of a DENSE list makes it FLAT; moves past a few times its items, arrays past 64 MiB, or a third change of form make it a tree. Answers are the tree's; the stored bytes stand for its items in the memory budget whatever it keeps them in. - pure_list_add need not say where an item went: a list no index state refers to is not asked. - A LIST_FIND whose index the next ITEM_GET of its list takes at once is joined to it at load (PLAN_JOINED): pure_list_lookup reads the field by key, at the key in a DENSE list. - test-module arrays_equivalence: beside a tree, every step of a random run (adds, inserts, removes, changes, finds, reads, runs, clears) gives the same answers through every form and change of form. - A search (100,000 nodes, 1,000,000 edges, core only): 187 to 126 ms. --- core/module-list.h | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-) (limited to 'core/module-list.h') diff --git a/core/module-list.h b/core/module-list.h index 4778280..0addcf0 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -102,10 +102,11 @@ void pure_retired_free(PureRetired *); * 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). */ + * found and placed in one descent (docs/design/020): at says where (NULL: + * not asked, so a DENSE list need not count it), 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 *); @@ -134,6 +135,18 @@ bool pure_list_hashed(PureList *); 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 *); +/* An event's list (empty, never shared, journaled or undone) may keep its + * items in arrays rather than a tree (docs/design/021): in order (FLAT), or + * at their keys when keyed by small whole numbers (DENSE), as the changes it + * gets allow; a clear makes it FLAT again. Answers are the tree's. False + * when the list cannot (it stays a tree). */ +bool pure_list_arrays(PureList *); +/* What it keeps its items in now: 0 a tree, 1 FLAT arrays, 2 DENSE (for tests and counts). */ +unsigned pure_list_form(const PureList *); +/* Field of the item whose key_field is key, in a list ordered by key_field + * (seek, then get, as one: a DENSE list reads it at its key); false when no + * item has key. */ +bool pure_list_lookup(const PureList *, unsigned key_field, PureCell key, unsigned field, PureCell *cell); /* 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