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.

5 files changed, 738 insertions, 96 deletions

diff --git a/core/module-list.c b/core/module-list.c
index 3e643ce..99d19ab 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -74,6 +74,13 @@ struct PureList {
     unsigned needed[2];   /* inner nodes and leaves it made lately: halved each time the retired come back */
     unsigned refs;        /* a shared copy's references */
     bool copy;            /* a shared copy: it owns none of its nodes or texts */
+    /* Its keys as a set, beside the tree (pure_list_hashed; NULL: none):
+     * while every key is a whole number below BITMAP_KEYS, a bit per number
+     * (member_capacity words); else a key's bits (-0 as +0) by open
+     * addressing (member_capacity slots), VACANT where none is. */
+    uint64_t *members;
+    size_t member_capacity, member_count;
+    bool bitmap;
 };
 
 /* The log of an event's changes: a removed item's cells wait in the log's
@@ -100,31 +107,176 @@ typedef struct {
 
 static uint64_t lists_made;
 
-/* The leaf a thread read last, and where it starts: a list read position by
- * position (a view's rows, a fold) finds each next item there. It holds for
- * the list (its id) as it was (its version) and no other. */
-static _Thread_local struct { uint64_t id, version; const Node *leaf; size_t start; } finger;
+/* The leaves a thread read last, and where they start, a few lists' (one
+ * each): a list read position by position (a view's rows, a fold, a walk)
+ * finds each next item there, and an item found by key is read there, while
+ * the thread reads other lists between (a search reads three). Each holds
+ * for its list (its id) as it was (its version) and no other. */
+enum { FINGERS = 4 };
+typedef struct { uint64_t id, version; const Node *leaf; size_t start; } Finger;
+static _Thread_local Finger fingers[FINGERS];
+static _Thread_local unsigned finger_turn;
+
+/* The leaf a finger keeps that holds position at of the list as it is, or NULL. */
+static const Node *fingered(const PureList *list, size_t at, size_t *within) {
+    for (unsigned i = 0; i < FINGERS; ++i) {
+        const Finger *f = &fingers[i];
+        if (f->leaf && f->id == list->id && f->version == list->version && at >= f->start && at < f->start + f->leaf->count) {
+            *within = at - f->start;
+            if (i) { Finger hit = *f; fingers[i] = fingers[0]; fingers[0] = hit; } /* first looked at next */
+            return fingers[0].leaf;
+        }
+    }
+    return NULL;
+}
+
+/* A leaf of the list as it is, from start: kept in the list's finger, or the one used longest ago. */
+static void finger_keep(const PureList *list, const Node *leaf, size_t start) {
+    unsigned at = FINGERS;
+    for (unsigned i = 0; i < FINGERS && at == FINGERS; ++i) if (fingers[i].id == list->id) at = i;
+    if (at == FINGERS) at = finger_turn++ % FINGERS;
+    fingers[at] = (Finger){list->id, list->version, leaf, start};
+}
+
+/* ---- A keyed list's keys as a set
+ * Node numbers, ranks and counts are small whole numbers: as bits they fit
+ * the caches (100,000 keys in 12.5 KB), where a table of them does not. */
+
+enum { BITMAP_KEYS = 1 << 22, BITMAP_KEPT = 1 << 13 /* words a cleared bitmap keeps (64 KiB) */ };
+static const uint64_t VACANT = UINT64_C(0x7FF8000000000001); /* a NaN: never a key */
+
+static uint64_t key_bits(double key) {
+    if (key == 0) key = 0; /* -0 and +0 are one key */
+    uint64_t bits;
+    memcpy(&bits, &key, sizeof(bits));
+    return bits;
+}
+
+static bool small_key(double key) { return key >= 0 && key < BITMAP_KEYS && (double)(uint32_t)key == key; }
+
+static size_t member_slot(uint64_t bits, size_t mask) {
+    bits ^= bits >> 33;
+    bits *= UINT64_C(0xff51afd7ed558ccd);
+    bits ^= bits >> 33;
+    return (size_t)bits & mask;
+}
+
+/* The set given up (memory ran out growing it): the list is searched without it. */
+static void members_drop(PureList *list) {
+    free(list->members);
+    list->members = NULL;
+    list->member_capacity = list->member_count = 0;
+}
+
+/* A new set, empty, as bits. */
+static bool members_start(PureList *list) {
+    list->members = calloc(1, sizeof(*list->members));
+    list->member_capacity = list->members ? 1 : 0;
+    list->member_count = 0;
+    list->bitmap = true;
+    return list->members != NULL;
+}
+
+static void member_put(PureList *list, uint64_t bits) {
+    size_t mask = list->member_capacity - 1, at = member_slot(bits, mask);
+    while (list->members[at] != VACANT && list->members[at] != bits) at = (at + 1) & mask;
+    if (list->members[at] == VACANT) list->members[at] = bits, ++list->member_count;
+}
+
+/* A table of capacity slots holding the keys the set holds. False when memory runs out. */
+static bool members_table(PureList *list, size_t capacity) {
+    uint64_t *old = list->members, *table = malloc(capacity * sizeof(*table));
+    if (!table) return false;
+    size_t was = list->member_capacity;
+    bool bits = list->bitmap;
+    for (size_t i = 0; i < capacity; ++i) table[i] = VACANT;
+    list->members = table, list->member_capacity = capacity, list->member_count = 0, list->bitmap = false;
+    for (size_t i = 0; i < was; ++i) {
+        if (!bits) { if (old[i] != VACANT) member_put(list, old[i]); continue; }
+        for (uint64_t word = old[i]; word; word &= word - 1)
+            member_put(list, key_bits((double)(i * 64 + (size_t)__builtin_ctzll(word))));
+    }
+    free(old);
+    return true;
+}
+
+static void member_add(PureList *list, double key) {
+    if (!list->members) return;
+    if (list->bitmap && small_key(key)) {
+        size_t bit = (size_t)key, word = bit / 64;
+        if (word >= list->member_capacity) { /* the bits grown to hold it */
+            size_t capacity = list->member_capacity;
+            while (capacity <= word) capacity *= 2;
+            uint64_t *grown = realloc(list->members, capacity * sizeof(*grown));
+            if (!grown) { members_drop(list); return; }
+            memset(grown + list->member_capacity, 0, (capacity - list->member_capacity) * sizeof(*grown));
+            list->members = grown, list->member_capacity = capacity;
+        }
+        uint64_t mask = UINT64_C(1) << (bit % 64);
+        list->member_count += !(list->members[word] & mask);
+        list->members[word] |= mask;
+        return;
+    }
+    size_t need = 2 * (list->member_count + 1), capacity = list->bitmap ? 64 : list->member_capacity;
+    while (capacity < need) capacity *= 2;
+    if ((list->bitmap || capacity != list->member_capacity) && !members_table(list, capacity)) { members_drop(list); return; }
+    member_put(list, key_bits(key));
+}
+
+/* A key out of the set; in a table the keys after it in its run moved back (no gap left behind them). */
+static void member_remove(PureList *list, double key) {
+    if (!list->members) return;
+    if (list->bitmap) {
+        if (!small_key(key) || (size_t)key / 64 >= list->member_capacity) return;
+        uint64_t *word = &list->members[(size_t)key / 64], mask = UINT64_C(1) << ((size_t)key % 64);
+        list->member_count -= (*word & mask) != 0;
+        *word &= ~mask;
+        return;
+    }
+    uint64_t bits = key_bits(key);
+    size_t mask = list->member_capacity - 1, at = member_slot(bits, mask);
+    while (list->members[at] != bits) {
+        if (list->members[at] == VACANT) return;
+        at = (at + 1) & mask;
+    }
+    for (size_t next = (at + 1) & mask; list->members[next] != VACANT; next = (next + 1) & mask) {
+        size_t home = member_slot(list->members[next], mask);
+        /* next may fill the gap at when its home is not cyclically within (at, next] */
+        bool stays = at <= next ? (home > at && home <= next) : (home > at || home <= next);
+        if (!stays) list->members[at] = list->members[next], at = next;
+    }
+    list->members[at] = VACANT;
+    --list->member_count;
+}
 
 static Node *child(const Node *node, unsigned i) { return node->child[i]; }
 static Guide *guide(const Node *node) { return (Guide *)((char *)node + sizeof(Node) + FANOUT * sizeof(Node *)); }
 
-/* How many of n (at least one) ascending values are at or below key (upper)
- * or below it (lower). */
-static unsigned upper(const double *values, unsigned n, double key) {
-    const double *base = values;
-    for (; n > 1; n -= n / 2) base = base[n / 2] <= key ? base + n / 2 : base;
-    return (unsigned)(base - values) + (*base <= key);
-}
+/* How many of n (at least one) ascending values are below key. */
 static unsigned lower(const double *values, unsigned n, double key) {
     const double *base = values;
     for (; n > 1; n -= n / 2) base = base[n / 2] < key ? base + n / 2 : base;
     return (unsigned)(base - values) + (*base < key);
 }
-/* The child of an inner node holding its item at (counted from the node's first). */
+/* The child of an inner node holding its item at (counted from the node's
+ * first): its children after the first whose items begin at or before at,
+ * counted rather than halved (no load waits for another; past the last
+ * child the counts are above any position). The end is in the last child. */
 static unsigned child_at(const Node *node, size_t at) {
-    const uint32_t *before = guide(node)->before + 1, *base = before;
-    for (unsigned n = FANOUT - 1; n > 1; n -= n / 2) base = base[n / 2] <= at ? base + n / 2 : base;
-    return (unsigned)(base - before) + (*base <= at);
+    if (at >= node->items) return node->count - 1;
+    const uint32_t *before = guide(node)->before;
+    uint32_t n = 0, position = (uint32_t)at; /* every child, the first's 0 at or below any: a whole number of vectors */
+    for (unsigned i = 0; i < FANOUT; ++i) n += before[i] <= position;
+    return n - 1;
+}
+/* An inner node's last child whose lead is at or below key (the first when
+ * none is): its leads after the first at or below key, counted (past the
+ * last child they are above any key). */
+static unsigned child_by_key(const Node *node, double key) {
+    const double *keys = guide(node)->keys;
+    uint64_t n = 0; /* every child's (a whole number of vectors), less the first's */
+    for (unsigned i = 0; i < FANOUT; ++i) n += keys[i] <= key;
+    return (unsigned)n - (keys[0] <= key);
 }
 static double *numbers(const Layout *l, const Node *leaf, unsigned f) { return (double *)((char *)leaf + l->column[f]); }
 static int64_t *integers(const Layout *l, const Node *leaf, unsigned f) { return (int64_t *)((char *)leaf + l->column[f]); }
@@ -345,11 +497,8 @@ typedef struct { Node *node; unsigned index; } Step; /* a node on the way, and t
 /* The leaf holding position at (the end is in the last leaf), and at's
  * place in it. */
 static const Node *leaf_of(const PureList *list, size_t at, size_t *within) {
-    if (finger.leaf && finger.id == list->id && finger.version == list->version && at >= finger.start &&
-        at < finger.start + finger.leaf->count) {
-        *within = at - finger.start;
-        return finger.leaf;
-    }
+    const Node *kept = fingered(list, at, within);
+    if (kept) return kept;
     const Node *node = list->root;
     size_t start = 0;
     while (!node->leaf) {
@@ -357,7 +506,7 @@ static const Node *leaf_of(const PureList *list, size_t at, size_t *within) {
         start += guide(node)->before[i];
         node = child(node, i);
     }
-    finger.id = list->id, finger.version = list->version, finger.leaf = node, finger.start = start;
+    finger_keep(list, node, start);
     *within = at - start;
     return node;
 }
@@ -441,11 +590,8 @@ typedef struct {
     Node *extra[DEPTH + 1];
 } Place;
 
-static bool prepare(PureList *list, size_t at, Place *p) {
-    if (!list->root && !(list->root = new_node(list, true))) return false;
-    p->extras = p->used = 0;
-    p->appending = at == list->count;
-    if (!(p->depth = descend(list, at, p->path, &p->within))) return false;
+/* The nodes a split may take, made now so that placing cannot fail. */
+static bool prepare_extras(PureList *list, Place *p) {
     if (p->path[p->depth - 1].node->count < FANOUT) return true;
     for (; p->extras <= p->depth; ++p->extras)
         if (!(p->extra[p->extras] = new_node(list, !p->extras))) {
@@ -455,6 +601,44 @@ static bool prepare(PureList *list, size_t at, Place *p) {
     return true;
 }
 
+static bool prepare(PureList *list, size_t at, Place *p) {
+    if (!list->root && !(list->root = new_node(list, true))) return false;
+    p->extras = p->used = 0;
+    p->appending = at == list->count;
+    if (!(p->depth = descend(list, at, p->path, &p->within))) return false;
+    return prepare_extras(list, p);
+}
+
+/* The path to where key goes in a list kept in order of a number field (its
+ * key), the nodes on it the list's own; where in the list that is, and
+ * whether an item has the key there. False when memory runs out. */
+static bool descend_key(PureList *list, double key, Place *p, size_t *at, bool *found) {
+    const Layout *l = &list->layout;
+    Node **place = &list->root;
+    size_t start = 0;
+    for (unsigned depth = 0; depth < DEPTH; ++depth) {
+        Node *node = own(list, place);
+        if (!node) return false;
+        if (node->leaf) {
+            const double *keys = numbers(l, node, (unsigned)l->key);
+            unsigned low = node->count ? lower(keys, node->count, key) : 0;
+            *found = low < node->count && keys[low] == key;
+            p->path[depth] = (Step){node, 0};
+            p->depth = depth + 1;
+            p->within = low;
+            *at = start + low;
+            for (unsigned d = depth; d-- > 0;) p->path[d].node->first = child(p->path[d].node, 0)->first;
+            return true;
+        }
+        const Guide *g = guide(node);
+        unsigned taken = child_by_key(node, key);
+        start += g->before[taken];
+        p->path[depth] = (Step){node, taken};
+        place = &node->child[taken];
+    }
+    return false;
+}
+
 static void release_extras(PureList *list, Place *p) {
     while (p->extras > p->used) drop_node(list, p->extra[--p->extras]);
 }
@@ -468,6 +652,7 @@ static void release_extras(PureList *list, Place *p) {
 static void place(PureList *list, Place *p, const PureCell *cells) {
     const Layout *l = &list->layout;
     unsigned index = p->within;
+    if (list->members) member_add(list, cells[l->key].num);
     Node *pointer = NULL; /* above the leaf: the node that goes in */
     for (unsigned d = p->depth; d-- > 0;) {
         Node *node = p->path[d].node;
@@ -520,6 +705,7 @@ static void place(PureList *list, Place *p, const PureCell *cells) {
 static void take_out(PureList *list, Step *path, unsigned depth, unsigned within) {
     const Layout *l = &list->layout;
     Node *leaf = path[depth - 1].node;
+    if (list->members) member_remove(list, numbers(l, leaf, (unsigned)l->key)[within]);
     move_items(l, leaf, within, leaf, within + 1, leaf->count - within - 1);
     --leaf->count;
     unsigned d = depth - 1;
@@ -624,6 +810,7 @@ void pure_list_free(PureList *list) {
         if (__atomic_sub_fetch(&list->refs, 1, __ATOMIC_ACQ_REL)) return;
     } else {
         free(list->journal);
+        free(list->members);
         let_go_tree(list, list->root);
         for (unsigned kind = 0; kind < 2; ++kind) {
             while (list->spares[kind]) free(list->spare[kind][--list->spares[kind]]);
@@ -639,8 +826,41 @@ void pure_list_clear(PureList *list) {
     list->root = NULL;
     list->count = list->bytes = 0;
     ++list->version;
+    if (!list->members) return;
+    if (list->bitmap && list->member_capacity <= BITMAP_KEPT) { /* small bits are kept for the next event */
+        memset(list->members, 0, list->member_capacity * sizeof(*list->members));
+        list->member_count = 0;
+        return;
+    }
+    members_drop(list); /* else bits again, from few */
+    (void)members_start(list);
 }
 
+bool pure_list_hashed(PureList *list) {
+    const Layout *l = &list->layout;
+    if (list->members) return true;
+    if (l->key < 0 || list->copy || !members_start(list)) return false;
+    for (size_t at = 0; at < list->count && list->members; ++at) /* the keys it has now, once */
+        member_add(list, pure_list_get(list, at, (unsigned)l->key).num);
+    return list->members != NULL;
+}
+
+bool pure_list_contains(const PureList *list, double key, bool *found) {
+    if (!list->members) return false;
+    if (list->bitmap) {
+        *found = small_key(key) && (size_t)key / 64 < list->member_capacity &&
+                 list->members[(size_t)key / 64] >> ((size_t)key % 64) & 1;
+        return true;
+    }
+    uint64_t bits = key_bits(key);
+    size_t mask = list->member_capacity - 1, at = member_slot(bits, mask);
+    while (list->members[at] != VACANT && list->members[at] != bits) at = (at + 1) & mask;
+    *found = list->members[at] == bits;
+    return true;
+}
+
+size_t pure_list_extra(const PureList *list) { return list->member_capacity * sizeof(*list->members); }
+
 size_t pure_list_count(const PureList *list) { return list->count; }
 
 PureList *pure_list_share(PureList *list, PureRetired *retired, uint64_t epoch) {
@@ -1005,6 +1225,49 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu
     return PURE_OK;
 }
 
+PureResult pure_list_add(PureList *list, const PureCell *cells, PureUndo *undo, size_t *at, bool *exists) {
+    const Layout *l = &list->layout;
+    *exists = false;
+    if (l->key < 0) return PURE_INVALID; /* searched and inserted apart, then */
+    if (list->members) { /* the set says at once when the key is there */
+        bool found;
+        if (pure_list_contains(list, cells[l->key].num, &found) && found) {
+            *at = pure_list_seek(list, (unsigned)l->key, cells[l->key], exists);
+            return PURE_OK;
+        }
+    }
+    if (list->count == PURE_LIST_ITEMS) return PURE_LIMIT;
+    if (!list->root && !(list->root = new_node(list, true))) return PURE_ALLOCATION;
+    Place p = {.extras = 0, .used = 0};
+    if (!descend_key(list, cells[l->key].num, &p, at, exists)) return PURE_ALLOCATION;
+    if (*exists) return PURE_OK;
+    p.appending = *at == list->count;
+    PureCell item[16];
+    unsigned owned = 0;
+    for (; owned < l->fields; ++owned)
+        if (!own_cell(list, owned, cells[owned], &item[owned])) break;
+    size_t size = RECORD_HEAD;
+    for (unsigned f = 0; list->journaled && f < l->fields; ++f) size += compact_bound(l, f, cells[f]);
+    unsigned char *record = list->journaled ? journal_room(list, size) : NULL;
+    if (owned < l->fields || (list->journaled && !record) || !prepare_extras(list, &p)) {
+        for (unsigned f = 0; f < owned; ++f) free_text(item[f].text);
+        return PURE_ALLOCATION;
+    }
+    if (undo && !log_change(undo, (Entry){.change = INSERTED, .list = list, .at = *at})) {
+        release_extras(list, &p);
+        for (unsigned f = 0; f < l->fields; ++f) free_text(item[f].text);
+        return PURE_ALLOCATION;
+    }
+    if (record) {
+        unsigned char *end = record_head(record, RECORD_INSERT, *at);
+        for (unsigned f = 0; f < l->fields; ++f) end = put_compact(l, f, item[f], end);
+        list->journal_size += (size_t)(end - record);
+    }
+    list->bytes += cells_bytes(l, item);
+    place(list, &p, item);
+    return PURE_OK;
+}
+
 /* Room for one more item's cells in the log. */
 static PureCell *log_cells(PureUndo *undo, unsigned fields) {
     if (undo->cell_count + fields > undo->cell_capacity) {
@@ -1051,10 +1314,11 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val
     unsigned within, depth = 0;
     bool keyed = (int)field == l->key;
     Node *leaf;
-    if (!keyed && finger.leaf && finger.id == list->id && finger.version == list->version && at >= finger.start &&
-        at < finger.start + finger.leaf->count && !shared_node(list, finger.leaf)) {
-        leaf = (Node *)finger.leaf;
-        within = (unsigned)(at - finger.start);
+    size_t found_within;
+    const Node *kept = keyed ? NULL : fingered(list, at, &found_within);
+    if (kept && !shared_node(list, kept)) {
+        leaf = (Node *)kept;
+        within = (unsigned)found_within;
     } else {
         if (!(depth = descend(list, at, path, &within))) return PURE_ALLOCATION;
         leaf = path[depth - 1].node;
@@ -1079,9 +1343,12 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val
     else if (l->kinds[field] == PURE_CELL_INTEGER) integers(l, leaf, field)[within] = copy.i64;
     else numbers(l, leaf, field)[within] = copy.num;
     if (!undo) let_go_text(list, old.text);
-    if (keyed) sum_path(list, path, depth);
+    if (keyed) {
+        sum_path(list, path, depth);
+        if (list->members) member_remove(list, old.num), member_add(list, copy.num);
+    }
     ++list->version;
-    finger.id = list->id, finger.version = list->version, finger.leaf = leaf, finger.start = at - within;
+    finger_keep(list, leaf, at - within);
     return PURE_OK;
 }
 
@@ -1165,11 +1432,22 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *
     *found = false;
     if (!node || !list->count) return 0;
     if ((int)field == l->key) {
+        /* A leaf a finger keeps whose keys reach round key holds its place
+         * (a slice's high bound is near its low one, found just before). */
+        for (unsigned i = 0; i < FINGERS; ++i) {
+            const Finger *f = &fingers[i];
+            if (!f->leaf || f->id != list->id || f->version != list->version || !f->leaf->count) continue;
+            const double *keys = numbers(l, f->leaf, field);
+            if (!(keys[0] <= key.num && key.num <= keys[f->leaf->count - 1])) continue;
+            unsigned low = lower(keys, f->leaf->count, key.num);
+            *found = low < f->leaf->count && keys[low] == key.num;
+            return f->start + low;
+        }
         /* Each level: the last child whose lead is at or below key (the
          * first when none is); then the leaf's items below key. */
         while (!node->leaf) {
             const Guide *g = guide(node);
-            unsigned taken = upper(g->keys + 1, FANOUT - 1, key.num);
+            unsigned taken = child_by_key(node, key.num);
             start += g->before[taken];
             node = child(node, taken);
         }
@@ -1178,6 +1456,7 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *
             for (unsigned i = 0; i < node->count; i += 8) __builtin_prefetch(keys + i);
         unsigned low = lower(keys, node->count, key.num);
         *found = low < node->count && keys[low] == key.num;
+        finger_keep(list, node, start); /* the item found is read there next */
         return start + low;
     }
     while (!node->leaf) {
@@ -1305,8 +1584,11 @@ void pure_undo_rollback(PureUndo *undo, size_t mark) {
             *text = (PureSpan){e->old.text, e->old.size};
         } else if (l->kinds[e->field] == PURE_CELL_INTEGER)
             integers(l, leaf, e->field)[within] = e->old.i64;
-        else
+        else {
+            double now = numbers(l, leaf, e->field)[within];
             numbers(l, leaf, e->field)[within] = e->old.num;
+            if (list->members && (int)e->field == l->key) member_remove(list, now), member_add(list, e->old.num);
+        }
         sum_path(list, path, depth);
         ++list->version;
     }
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
diff --git a/core/module.c b/core/module.c
index ffcc9cb..5b43fea 100644
--- a/core/module.c
+++ b/core/module.c
@@ -354,6 +354,11 @@ static unsigned char state_type(const PureModule *m, uint32_t state) {
     return m->state_type[state] == PURE_STATE_BOOL ? T_BOOL : m->state_type[state] == PURE_STATE_I64 ? T_I64 : T_NUM;
 }
 
+/* Whether a list's record field is a text. */
+static bool text_field(const PureModule *m, uint32_t list, uint32_t field) {
+    return m->record_field_type[m->record[m->state_ref[list]].first + field] == PURE_RECORD_TEXT;
+}
+
 /* What a local holds (its argument's bits 8-15): a number, an index, a bool or an i64. */
 static unsigned char local_type(uint32_t arg) {
     static const unsigned char types[] = {T_NUM, T_INDEX, T_BOOL, T_I64};
@@ -1336,6 +1341,13 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule
         plan_folds(out, out->handler[i].code, input);
         range_code(out, out->handler[i].code, input);
     }
+    /* What a cell is, read once here: an item's field, or a keyed list's key, a text (plan) or not. */
+    for (uint32_t pc = 0; pc < out->code_count; ++pc) {
+        PureOp *op = &out->code[pc];
+        if (op->op == PURE_OP_ITEM_GET || op->op == PURE_OP_ITEM_SET) op->plan = text_field(out, list_of(op->arg), item_field(op->arg));
+        else if (op->op == PURE_OP_LIST_FIND || op->op == PURE_OP_LIST_HAS)
+            op->plan = text_field(out, op->arg, out->state_key[op->arg] - 1u);
+    }
     return PURE_OK;
 refused:
     if (error_size) snprintf(error, error_size, "%s (%u)", why, bad);
@@ -1477,6 +1489,18 @@ static bool related(uint32_t relation, int order) {
 /* A walk (EACH): the list, the item it runs for, where it ends (items the
  * walk removes move it), and whether that item left. */
 typedef struct { uint32_t list; size_t at, end; bool removed; } Walk;
+/* A loop that runs in its block's run (LOOP, EACH): its block, the arena as
+ * it began, a walk's walk and the event's walk and row around it, a
+ * count's values (low + k of count) and slot. */
+typedef struct {
+    uint32_t start, end;
+    size_t mark;
+    bool walking, integer;
+    Walk walk, *around;
+    size_t row;
+    uint64_t count, k;
+    PureValue low, *slot;
+} Loop;
 typedef struct {
     PureApp *app;
     const PureInputShape *shape; /* message, or NULL */
@@ -1490,7 +1514,6 @@ typedef struct {
     PureValue *locals; /* the event's locals (a handler's, and what runs in it), or NULL */
     bool arguments; /* FIELD reads the arguments given for a view, not the message */
     bool modified, exists;
-    bool broke; /* a BREAK ended the loop whose block this runs */
     uint32_t (*spans)[2]; /* a message's variable fields: start and size in the payload */
 } Event;
 
@@ -1517,7 +1540,7 @@ static inline bool charge(PureApp *app, uint64_t instructions) {
 typedef struct { size_t stored, kept; } Held;
 
 static inline Held list_held(const PureApp *app, const PureList *list) {
-    return (Held){pure_list_size(list), pure_list_changes(list).size + pure_undo_size(&app->undo)};
+    return (Held){pure_list_size(list), pure_list_changes(list).size + pure_undo_size(&app->undo) + pure_list_extra(list)};
 }
 
 static inline Held text_held(const PureApp *app, uint32_t text) { return (Held){pure_draft_size(app->texts[text]), 0}; }
@@ -1643,9 +1666,7 @@ static void move_indices(const PureModule *m, PureValue *values, uint32_t list,
     }
 }
 
-static bool text_field(const PureModule *m, uint32_t list, uint32_t field) {
-    return m->record_field_type[m->record[m->state_ref[list]].first + field] == PURE_RECORD_TEXT;
-}
+
 
 /* Append bytes to the arena as a value of it. */
 static PureResult keep_bytes(PureArena *arena, const void *bytes, size_t length, PureBytes *out) {
@@ -1904,7 +1925,8 @@ static bool run_lanes(const PureModule *m, const PureValue *values, PureBlock bl
             if (uniform(top)) {
                 double value;
                 if (!recalled(memo, pc - block.start, &value)) {
-                    size_t at = pure_list_seek(keyed, key, (PureCell){.num = top->value}, &found);
+                    size_t at = find || !pure_list_contains(keyed, top->value, &found) ?
+                                pure_list_seek(keyed, key, (PureCell){.num = top->value}, &found) : 0;
                     if (find && !found) return false;
                     remember(memo, pc - block.start, value = find ? (double)at : found);
                 }
@@ -1913,7 +1935,8 @@ static bool run_lanes(const PureModule *m, const PureValue *values, PureBlock bl
             }
             const double *keys = lanes_of(top, scratch[0], items);
             for (unsigned i = 0; i < n; ++i) {
-                size_t at = pure_list_seek(keyed, key, (PureCell){.num = keys[i]}, &found);
+                size_t at = find || !pure_list_contains(keyed, keys[i], &found) ?
+                            pure_list_seek(keyed, key, (PureCell){.num = keys[i]}, &found) : 0;
                 if (find && !found) return false;
                 out[i] = find ? (double)at : found;
             }
@@ -2415,7 +2438,40 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
     PureResult status;
     PureFault kind;
     const PureOp *op = NULL;
-    for (uint32_t pc = block.start, end = block.start + block.length; pc < end;) {
+    /* The loops open here (LOOP, EACH), innermost last, and where the innermost's block ends. */
+    Loop loops[PURE_MODULE_NESTING];
+    unsigned depth = 0;
+    uint32_t loop_end = UINT32_MAX;
+    for (uint32_t pc = block.start, end = block.start + block.length;;) {
+        if (pc == loop_end) { /* a loop's block ran once: again, or the loop ends (its end may be the block's) */
+            Loop *loop = &loops[depth - 1];
+            arena->used = loop->mark;
+            if (loop->walking) {
+                Walk *walk = &loop->walk;
+                if (!walk->removed) ++walk->at;
+                walk->removed = false;
+                if (walk->at < walk->end && walk->at < pure_list_count(app->lists[walk->list])) {
+                    ev->row = walk->at;
+                    pc = loop->start;
+                    continue;
+                }
+                ev->walk = loop->around, ev->row = loop->row;
+            } else if (++loop->k < loop->count) {
+                if (!charge(app, (uint64_t)(loop->end - loop->start) + 1)) {
+                    kind = PURE_FAULT_WORK;
+                    op = &m->code[loop->start - 1];
+                    goto failed;
+                }
+                if (loop->integer) loop->slot->i64 = (int64_t)((uint64_t)loop->low.i64 + loop->k);
+                else loop->slot->num = loop->low.num + (double)loop->k;
+                pc = loop->start;
+                continue;
+            }
+            --depth;
+            loop_end = depth ? loops[depth - 1].end : UINT32_MAX;
+            continue;
+        }
+        if (pc >= end) break;
         op = &m->code[pc++];
         uint32_t arg = op->arg;
         Slot *top = sp ? &stack[sp - 1] : stack;
@@ -2622,14 +2678,17 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
                     return status;
                 cells[f] = (PureCell){.i64 = stack[base + f].i64, .text = (unsigned char *)span.data, .size = span.size};
             }
-            if (m->state_key[arg]) { /* a keyed list places the item by its key */
+            Held before = list_held(app, list);
+            status = PURE_INVALID;
+            if (m->state_key[arg]) { /* a keyed list places the item by its key: found and placed at once when kept by a number */
                 bool found;
-                unsigned key = m->state_key[arg] - 1u;
-                at = pure_list_seek(list, key, cells[key], &found);
+                if ((status = pure_list_add(list, cells, undo_for(app, arg), &at, &found)) == PURE_INVALID) {
+                    unsigned key = m->state_key[arg] - 1u;
+                    at = pure_list_seek(list, key, cells[key], &found);
+                }
                 if (found) { arena->used = mark; kind = PURE_FAULT_EXISTS; goto failed; }
             }
-            Held before = list_held(app, list);
-            status = pure_list_insert(list, at, cells, undo_for(app, arg));
+            if (status == PURE_INVALID) status = pure_list_insert(list, at, cells, undo_for(app, arg));
             arena->used = mark;
             if (status != PURE_OK) goto refused;
             move_indices(m, values, arg, pure_list_count(list), at, true);
@@ -2656,7 +2715,7 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
             if (at >= pure_list_count(app->lists[list])) { kind = PURE_FAULT_NOT_FOUND; goto failed; }
             PureCell cell = pure_list_get(app->lists[list], at, field);
             /* A text is copied: the item may change or go before the value is used. */
-            if (!text_field(m, list, field)) top->i64 = cell.i64; /* the bits: a number's, a bool's or an i64's */
+            if (!op->plan) top->i64 = cell.i64; /* the bits: a number's, a bool's or an i64's (plan: a text, set at load) */
             else if ((status = keep_bytes(arena, cell.text, cell.size, &top->bytes)) != PURE_OK) return status;
             continue;
         }
@@ -2666,7 +2725,7 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
             size_t at = (size_t)stack[--sp].num, mark = arena->used;
             Held before = list_held(app, app->lists[list]);
             PureSpan span = {0};
-            status = text_field(m, list, field) ? contiguous(app, arena, value.bytes, &span) : PURE_OK;
+            status = op->plan ? contiguous(app, arena, value.bytes, &span) : PURE_OK; /* plan: a text */
             if (status == PURE_OK)
                 status = pure_list_set(app->lists[list], at, field,
                                        (PureCell){.i64 = value.i64, .text = (unsigned char *)span.data, .size = span.size},
@@ -2722,44 +2781,37 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
         }
         case PURE_OP_EACH: {
             /* The block that follows runs for each item the list has, as the
-             * handler's code with ROW the item; the list only shrinks meanwhile. */
-            PureBlock inner = {pc, arg >> 16};
-            Walk walk = {arg >> 8 & 0xFF, 0, SIZE_MAX, false};
-            pc += inner.length;
-            Event per = *ev;
-            per.walk = &walk;
+             * handler's code with ROW the item; the list only shrinks meanwhile.
+             * It runs here, a loop opened (its end takes pc back), not by recursion. */
+            uint32_t length = arg >> 16;
+            Loop *loop = &loops[depth];
+            loop->walking = true;
+            loop->walk = (Walk){arg >> 8 & 0xFF, 0, SIZE_MAX, false};
             if (arg & PURE_EACH_SLICED) { /* the items with keys from low up to before high */
                 Slot high = stack[--sp], low = stack[--sp];
-                slice_of(app->lists[walk.list], m->state_key[walk.list] - 1u, low, high, &walk.at, &walk.end);
+                slice_of(app->lists[loop->walk.list], m->state_key[loop->walk.list] - 1u, low, high, &loop->walk.at,
+                         &loop->walk.end);
             }
-            size_t items = pure_list_count(app->lists[walk.list]); /* as written: what it starts with, the list only shrinking */
-            if (!charge(app, (uint64_t)inner.length * ((walk.end < items ? walk.end : items) - walk.at))) {
+            size_t items = pure_list_count(app->lists[loop->walk.list]); /* as written: what it starts with, the list only shrinking */
+            if (!charge(app, (uint64_t)length * ((loop->walk.end < items ? loop->walk.end : items) - loop->walk.at))) {
                 kind = PURE_FAULT_WORK;
                 goto failed;
             }
             if (!(arg & PURE_EACH_SLICED) && op->range) /* a where that bounds the key: only the items in bounds */
-                range_bounds(m, values, &m->range[op->range - 1], app->lists[walk.list], m->state_key[walk.list] - 1u, &per,
-                             &walk.at, &walk.end);
-            per.broke = false;
-            while (walk.at < walk.end && walk.at < pure_list_count(app->lists[walk.list])) {
-                size_t mark = arena->used;
-                per.row = walk.at;
-                walk.removed = false;
-                status = run(m, values, inner, &per, NULL);
-                arena->used = mark;
-                if (status != PURE_OK) return status;
-                if (per.broke) break;
-                if (!walk.removed) ++walk.at;
-            }
-            ev->modified = per.modified;
-            ev->exists = per.exists;
+                range_bounds(m, values, &m->range[op->range - 1], app->lists[loop->walk.list], m->state_key[loop->walk.list] - 1u,
+                             ev, &loop->walk.at, &loop->walk.end);
+            if (!(loop->walk.at < loop->walk.end && loop->walk.at < items)) { pc += length; continue; } /* none */
+            loop->start = pc, loop->end = pc + length, loop->mark = arena->used;
+            loop->around = ev->walk, loop->row = ev->row;
+            ev->walk = &loop->walk;
+            ev->row = loop->walk.at;
+            loop_end = loops[depth++].end;
             continue;
         }
         case PURE_OP_LOOP: {
             /* The block that follows runs once for each value from low up to before high, the slot holding it; its
-             * work counts as it runs (the LOOP too, so an empty block counts). */
-            PureBlock inner = {pc, arg >> 16};
-            pc += inner.length;
+             * work counts as it runs (the LOOP too, so an empty block counts). It runs here, as a walk does. */
+            uint32_t length = arg >> 16;
             Slot high = stack[--sp], low = stack[--sp];
             bool integer = arg & PURE_LOOP_INTEGER;
             uint64_t count = 0;
@@ -2767,23 +2819,28 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
             else if (!(fabs(low.num) <= 0x1p53 && fabs(high.num) <= 0x1p53 && low.num == floor(low.num) &&
                        high.num == floor(high.num))) { kind = PURE_FAULT_LIMIT; goto failed; }
             else count = high.num > low.num ? (uint64_t)(high.num - low.num) : 0;
-            Event per = *ev;
-            per.broke = false;
-            PureValue *slot = &ev->locals[arg & 0xFF];
-            for (uint64_t k = 0; k < count && !per.broke; ++k) {
-                if (!charge(app, (uint64_t)inner.length + 1)) { kind = PURE_FAULT_WORK; goto failed; }
-                if (integer) slot->i64 = (int64_t)((uint64_t)low.i64 + k);
-                else slot->num = low.num + (double)k;
-                size_t mark = arena->used;
-                status = run(m, values, inner, &per, NULL);
-                arena->used = mark;
-                if (status != PURE_OK) return status;
-            }
-            ev->modified = per.modified;
-            ev->exists = per.exists;
+            if (!count) { pc += length; continue; }
+            if (!charge(app, (uint64_t)length + 1)) { kind = PURE_FAULT_WORK; goto failed; }
+            Loop *loop = &loops[depth];
+            loop->walking = false;
+            loop->integer = integer;
+            loop->count = count, loop->k = 0;
+            loop->low = (PureValue){.i64 = low.i64};
+            loop->slot = &ev->locals[arg & 0xFF];
+            if (integer) loop->slot->i64 = low.i64;
+            else loop->slot->num = low.num;
+            loop->start = pc, loop->end = pc + length, loop->mark = arena->used;
+            loop_end = loops[depth++].end;
+            continue;
+        }
+        case PURE_OP_BREAK: { /* the innermost loop ends: the code after its block runs next */
+            Loop *loop = &loops[--depth];
+            arena->used = loop->mark;
+            if (loop->walking) ev->walk = loop->around, ev->row = loop->row;
+            pc = loop->end;
+            loop_end = depth ? loops[depth - 1].end : UINT32_MAX;
             continue;
         }
-        case PURE_OP_BREAK: ev->broke = true; return PURE_OK; /* the loop that runs this block ends */
         case PURE_OP_TEXT_COMPARE: {
             /* Texts order by their bytes: a shorter text before a longer one it begins. */
             PureBytes right = stack[--sp].bytes, left = stack[sp - 1].bytes;
@@ -2804,12 +2861,17 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
             unsigned key = m->state_key[arg] - 1u;
             size_t mark = arena->used;
             PureCell cell = {.i64 = top->i64};
-            if (text_field(m, arg, key)) {
+            if (op->plan) { /* a text key (set at load) */
                 PureSpan span;
                 if ((status = contiguous(app, arena, top->bytes, &span)) != PURE_OK) return status;
                 cell = (PureCell){.text = (unsigned char *)span.data, .size = span.size};
             }
             bool found;
+            /* An event's list keeps its keys as a set: HAS asks it alone (020). */
+            if (op->op == PURE_OP_LIST_HAS && pure_list_contains(app->lists[arg], cell.num, &found)) {
+                top->num = found;
+                continue;
+            }
             size_t at = pure_list_seek(app->lists[arg], key, cell, &found);
             arena->used = mark;
             if (op->op == PURE_OP_LIST_HAS) { top->num = found; continue; }
@@ -3604,6 +3666,7 @@ static bool own_lists(PureApp *app, uint32_t lists) {
         if (!app->own[i]) {
             if (!(app->own[i] = new_list(m, m->state_ref[i]))) return false;
             (void)pure_list_keyed(app->own[i], m->state_key[i] ? (int)m->state_key[i] - 1 : -1);
+            if (m->state_key[i]) (void)pure_list_hashed(app->own[i]);
         }
         app->lists[i] = app->own[i];
     }
@@ -4267,9 +4330,11 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module)
         /* A stored list's changes are recorded from now on; a transient one's never. */
         if (lists_stored && module->state_type[i] == PURE_STATE_LIST && !(module->state_flags[i] & PURE_LIST_ROWS >> 8))
             pure_list_journal(lists[i], !pure_state_transient(module, i));
-        /* Without memory for its keys a keyed list is still searched, only slower. */
+        /* Without memory for its keys a keyed list is still searched, only slower; an event's keeps them as a set too (020). */
         if (module->state_type[i] == PURE_STATE_LIST)
             (void)pure_list_keyed(lists[i], module->state_key[i] ? (int)module->state_key[i] - 1 : -1);
+        if (module->state_type[i] == PURE_STATE_LIST && module->state_key[i] && module->state_flags[i] & PURE_LIST_ROWS >> 8)
+            (void)pure_list_hashed(lists[i]);
     }
     if (old) remap_outputs(app, old, module, true, NULL, NULL);
     if (recast) { /* in the place of the outbox, its sends now the new module's */
diff --git a/core/module.h b/core/module.h
index c5b7ba0..80d4460 100644
--- a/core/module.h
+++ b/core/module.h
@@ -198,7 +198,8 @@ const char *pure_fault_name(PureFault);
 
 /* plan, shape and range are the runtime's, set at load: a fold whose block
  * has a form for every instruction that works on a leaf of its list at once
- * runs so (plan), one in a column may be answered for every row from one
+ * runs so (plan; for an item's field, or a keyed list's key, read or set:
+ * whether it is a text), one in a column may be answered for every row from one
  * pass over its list (shape: its PureShape + 1), and a fold or a walk whose
  * test bounds a keyed list's key reads only the items in bounds (range: its
  * PureRange + 1). */
diff --git a/core/test-module.c b/core/test-module.c
index 9bf34ff..35a154f 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -1031,7 +1031,7 @@ static bool collect_bytes(void *context, PureSpan span) {
         b->bytes = realloc(b->bytes, b->capacity);
         CHECK(b->bytes);
     }
-    memcpy(b->bytes + b->size, span.data, span.size);
+    if (span.size) memcpy(b->bytes + b->size, span.data, span.size); /* none: a save of changes all undone */
     b->size += span.size;
     return true;
 }
@@ -1099,6 +1099,281 @@ static void retired_come_back(void) {
     pure_retired_free(&retired[1]);
 }
 
+/* ---- A keyed list's keys as a set, and fingers (docs/design/020): a list
+ * keeping its keys as a set beside its tree answers as a model array does at
+ * every step of a random run of adds, removes and key changes (some undone),
+ * searches by key, reads by position and clears. Its keys go from bits to a
+ * table (a key not a small whole number), leave a table's runs from their
+ * middle, and grow bits past what a clear keeps; shares (a snapshot's copies,
+ * the same list as it was) and other lists read between, so a finger kept
+ * for one is never taken for another. */
+
+static size_t model_lower(const Model *m, double key) {
+    size_t low = 0, high = m->count;
+    while (low < high) {
+        size_t middle = (low + high) / 2;
+        if (m->items[middle].key < key) low = middle + 1;
+        else high = middle;
+    }
+    return low;
+}
+
+/* A key the set keeps as a bit. */
+static bool small_whole(double key) { return key >= 0 && key < 4194304 && floor(key) == key; }
+
+static bool model_has(const Model *m, double key) {
+    size_t at = model_lower(m, key);
+    return at < m->count && m->items[at].key == key;
+}
+
+/* Position at read as the model has it, by get, and the search for its key. */
+static bool reads_as(const PureList *list, const Model *m, size_t at) {
+    PureCell key = pure_list_get(list, at, 0), text = pure_list_get(list, at, 1);
+    bool found;
+    return same_item(m, at, key.num, (PureSpan){text.text, text.size}) &&
+           pure_list_seek(list, 0, (PureCell){.num = m->items[at].key}, &found) == at && found;
+}
+
+static void key_sets(void) {
+    static const uint8_t fields[2] = {PURE_CELL_NUMBER, PURE_CELL_TEXT};
+    enum { ROUNDS = 120000, OTHERS = 4 };
+    uint32_t seed = 0x6b657973u;
+    PureList *list = pure_list_new(2, fields), *others[OTHERS], *copy = NULL;
+    PureRetired retired = {0};
+    PureUndo undo = {0};
+    Model model = {0}, shared = {0};
+    CHECK(list && pure_list_keyed(list, 0) == PURE_OK);
+    /* Items there before it keeps a set: the set starts with them. */
+    for (unsigned i = 0; i < 300; ++i) {
+        double key = (double)(i * 7);
+        PureCell cells[2] = {{.num = key}, {.text = (unsigned char *)"a", .size = 1}};
+        CHECK(pure_list_insert(list, i, cells, NULL) == PURE_OK);
+        model_insert(&model, i, (ModelItem){key, "a", 1});
+    }
+    CHECK(pure_list_hashed(list) && pure_list_hashed(list) && pure_list_extra(list) > 0);
+    bool found;
+    CHECK(pure_list_contains(list, 7, &found) && found && pure_list_contains(list, 8, &found) && !found);
+    CHECK(pure_list_contains(list, -0.0, &found) && found); /* -0 is the key 0 */
+    for (unsigned o = 0; o < OTHERS; ++o) { /* other lists, read between: key i at i */
+        CHECK((others[o] = pure_list_new(2, fields)) && pure_list_keyed(others[o], 0) == PURE_OK);
+        for (unsigned i = 0; i < 2000; ++i)
+            CHECK(pure_list_insert(others[o], i, (PureCell[]){{.num = i + o}, {.size = 0}}, NULL) == PURE_OK);
+    }
+    {
+        PureList *texts = pure_list_new(2, (const uint8_t[]){PURE_CELL_TEXT, PURE_CELL_NUMBER});
+        CHECK(texts && pure_list_keyed(texts, 0) == PURE_OK && !pure_list_hashed(texts) && !pure_list_contains(texts, 1, &found));
+        pure_list_free(texts);
+    }
+    size_t adds = 0, removes = 0, changes = 0, undone = 0, clears = 0, tables = 0, shares = 0;
+    bool table = false;
+    for (unsigned round = 0; round < ROUNDS; ++round) {
+        /* The keys: small whole ones (bits); some past what a clear keeps;
+         * then quarters too (a table), dense, so runs are long and removes
+         * from their middle many; then whole ones past the bits. */
+        unsigned phase = round / (ROUNDS / 4), r = next_random(&seed);
+        double key = phase == 0   ? (double)(r % 30000)
+                     : phase == 1 ? (r % 997 ? (double)(r % 30000) : (double)(r % 4000000))
+                     : phase == 2 ? (double)(r % 24000) / 4
+                                  : (r % 5 ? (double)(r % 30000) : 4194304.0 + (double)(r % 100000));
+        if (phase == 2 && r % 7 == 0) key = -key; /* negative keys too */
+        CHECK(pure_list_contains(list, key, &found) && found == model_has(&model, key));
+        unsigned op = next_random(&seed) % 16;
+        bool undoing = next_random(&seed) % 9 == 0;
+        if (op < 7) { /* add */
+            char text[12];
+            size_t size = (size_t)snprintf(text, sizeof(text), "%u", round % 100000);
+            PureCell cells[2] = {{.num = key}, {.text = (unsigned char *)text, .size = size}};
+            size_t at, low = model_lower(&model, key);
+            bool exists;
+            CHECK(pure_list_add(list, cells, undoing ? &undo : NULL, &at, &exists) == PURE_OK);
+            CHECK(at == low && exists == found);
+            if (!exists && undoing) {
+                pure_undo_rollback(&undo, 0);
+                ++undone;
+                CHECK(pure_list_contains(list, key, &found) && !found && pure_list_count(list) == model.count);
+            } else if (!exists) {
+                ModelItem item = {key, {0}, size};
+                memcpy(item.text, text, size);
+                model_insert(&model, at, item);
+                ++adds;
+                if (!table && !small_whole(key)) {
+                    table = true, ++tables; /* a table: at most half full */
+                    CHECK(pure_list_extra(list) >= 2 * model.count * sizeof(uint64_t));
+                }
+            }
+            pure_undo_commit(&undo);
+        } else if (op < 10 && model.count) { /* remove */
+            size_t at = next_random(&seed) % model.count;
+            double gone = model.items[at].key;
+            CHECK(pure_list_remove(list, at, undoing ? &undo : NULL) == PURE_OK);
+            CHECK(pure_list_contains(list, gone, &found) && !found);
+            if (undoing) {
+                pure_undo_rollback(&undo, 0);
+                ++undone;
+                CHECK(pure_list_contains(list, gone, &found) && found && reads_as(list, &model, at));
+            } else {
+                memmove(model.items + at, model.items + at + 1, (model.count - at - 1) * sizeof(*model.items));
+                --model.count;
+                ++removes;
+            }
+            pure_undo_commit(&undo);
+        } else if (op < 12 && model.count) { /* a key changed to one between its neighbours */
+            size_t at = next_random(&seed) % model.count;
+            double was = model.items[at].key, low = at ? model.items[at - 1].key : was - 4,
+                   high = at + 1 < model.count ? model.items[at + 1].key : was + 4;
+            double to = phase == 2 ? low + (high - low) * (double)(1 + next_random(&seed) % 3) / 4
+                                   : floor(low) + 1 + (double)(next_random(&seed) % 3);
+            if (to > low && to < high && (phase == 2 || to >= 0)) {
+                CHECK(pure_list_set(list, at, 0, (PureCell){.num = to}, undoing ? &undo : NULL) == PURE_OK);
+                CHECK(pure_list_contains(list, to, &found) && found);
+                CHECK(to == was || (pure_list_contains(list, was, &found) && !found));
+                if (undoing) {
+                    pure_undo_rollback(&undo, 0);
+                    ++undone;
+                    CHECK(pure_list_contains(list, was, &found) && found);
+                    CHECK(to == was || (pure_list_contains(list, to, &found) && !found));
+                } else {
+                    model.items[at].key = to;
+                    ++changes;
+                    if (!table && !small_whole(to)) table = true, ++tables;
+                }
+                CHECK(reads_as(list, &model, at));
+                pure_undo_commit(&undo);
+            }
+        } else if (op < 14) { /* a search, and the items around what it found */
+            size_t at = pure_list_seek(list, 0, (PureCell){.num = key}, &found);
+            CHECK(at == model_lower(&model, key) && found == model_has(&model, key));
+            for (size_t i = at ? at - 1 : 0; i < at + 2 && i < model.count; ++i) CHECK(reads_as(list, &model, i));
+        } else if (model.count) { /* items read in order from one */
+            size_t at = next_random(&seed) % model.count;
+            for (size_t i = at; i < at + 40 && i < model.count; ++i) {
+                PureCell k = pure_list_get(list, i, 0), t = pure_list_get(list, i, 1);
+                CHECK(same_item(&model, i, k.num, (PureSpan){t.text, t.size}));
+            }
+        }
+        /* Another list read between (fingers for five lists, four kept). */
+        unsigned o = next_random(&seed) % OTHERS, i = next_random(&seed) % 2000;
+        CHECK(pure_list_get(others[o], i, 0).num == i + o);
+        CHECK(pure_list_seek(others[o], 0, (PureCell){.num = i + o + 0.5}, &found) == i + 1 && !found);
+        /* A share: the list as it was, read beside it while it changes. */
+        if (copy) {
+            CHECK(pure_list_count(copy) == shared.count && !pure_list_contains(copy, key, &found));
+            if (shared.count) CHECK(reads_as(copy, &shared, next_random(&seed) % shared.count));
+            size_t at = pure_list_seek(copy, 0, (PureCell){.num = key}, &found);
+            CHECK(at == model_lower(&shared, key) && found == model_has(&shared, key));
+        }
+        if (round % 6000 == 3000) {
+            if (copy) {
+                CHECK(same_items(copy, &shared));
+                pure_list_free(copy);
+            }
+            CHECK((copy = pure_list_share(list, &retired, round + 1)) && !pure_list_hashed(copy));
+            model_copy(&shared, &model);
+            ++shares;
+        }
+        if (round % 9973 == 9972) { /* cleared: an event's list begins each event empty */
+            CHECK(same_items(list, &model));
+            for (size_t k = 0; k < model.count; ++k) CHECK(pure_list_contains(list, model.items[k].key, &found) && found);
+            pure_list_clear(list);
+            model.count = 0, table = false, ++clears;
+            CHECK(pure_list_count(list) == 0 && pure_list_contains(list, key, &found) && !found);
+        }
+    }
+    CHECK(same_items(list, &model));
+    for (size_t k = 0; k < model.count; ++k) CHECK(pure_list_contains(list, model.items[k].key, &found) && found);
+    CHECK(adds > 10000 && removes > 5000 && changes > 1000 && undone > 1000 && tables >= 2 && clears >= 10);
+    if (copy) pure_list_free(copy);
+    pure_list_free(list);
+    for (unsigned o = 0; o < OTHERS; ++o) pure_list_free(others[o]);
+    pure_retired_free(&retired);
+    pure_undo_free(&undo);
+    free(model.items);
+    free(shared.items);
+    printf("{\"key_sets\":{\"adds\":%zu,\"removes\":%zu,\"changes\":%zu,\"undone\":%zu,\"tables\":%zu,\"clears\":%zu,\"shares\":%zu}}\n",
+           adds, removes, changes, undone, tables, clears, shares);
+}
+
+/* A stored keyed list adds by key too (an append to it, as an event's):
+ * what it journals after the items stored whole makes the list again, with
+ * adds of keys it has (no record), adds undone (their records forgotten),
+ * removes and key changes among them. */
+static void keyed_journal(void) {
+    static const uint8_t fields[2] = {PURE_CELL_NUMBER, PURE_CELL_TEXT};
+    uint32_t seed = 0x6a6f7572u;
+    PureList *list = pure_list_new(2, fields);
+    CHECK(list && pure_list_keyed(list, 0) == PURE_OK);
+    pure_list_journal(list, true);
+    Grown stored = {0};
+    size_t stored_items = 0, adds = 0, had = 0, undone = 0, restarts = 0;
+    PureUndo undo = {0};
+    Model model = {0}, before = {0};
+    for (unsigned event = 0; event < 3000; ++event) {
+        size_t mark = undo.count, journal = pure_list_changes(list).size;
+        model_copy(&before, &model);
+        for (unsigned change = 1 + (unsigned)(next_random(&seed) % 12); change--;) {
+            unsigned roll = (unsigned)(next_random(&seed) % 100);
+            if (roll < 60 || !model.count) {
+                ModelItem item = {(double)(next_random(&seed) % 20000) / 2 - 2000, "", next_random(&seed) % 11};
+                for (size_t k = 0; k < item.size; ++k) item.text[k] = (char)('a' + next_random(&seed) % 26);
+                PureCell cells[2] = {{.num = item.key}, {.text = (unsigned char *)item.text, .size = item.size}};
+                size_t at;
+                bool exists;
+                CHECK(pure_list_add(list, cells, &undo, &at, &exists) == PURE_OK);
+                CHECK(at == model_lower(&model, item.key) && exists == model_has(&model, item.key));
+                if (exists) ++had;
+                else model_insert(&model, at, item), ++adds;
+            } else if (roll < 85) {
+                size_t at = next_random(&seed) % model.count;
+                CHECK(pure_list_remove(list, at, &undo) == PURE_OK);
+                memmove(model.items + at, model.items + at + 1, (model.count - at - 1) * sizeof(*model.items));
+                --model.count;
+            } else { /* a key changed to one between its neighbours */
+                size_t at = next_random(&seed) % model.count;
+                double low = at ? model.items[at - 1].key : model.items[at].key - 1,
+                       high = at + 1 < model.count ? model.items[at + 1].key : model.items[at].key + 1;
+                double to = low + (high - low) / 2;
+                if (to > low && to < high) {
+                    CHECK(pure_list_set(list, at, 0, (PureCell){.num = to}, &undo) == PURE_OK);
+                    model.items[at].key = to;
+                }
+            }
+        }
+        if (next_random(&seed) % 5 == 0) { /* undone: the list and its journal as before */
+            pure_undo_rollback(&undo, mark);
+            pure_list_forget(list, journal);
+            model_copy(&model, &before);
+            ++undone;
+        } else
+            pure_undo_commit(&undo);
+        if (event % 3 == 0) { /* a save: its records after the stored ones, or now and then the items whole */
+            if (event % 120 == 0) {
+                stored.size = 0;
+                Grown whole = {malloc(pure_list_size(list) + 1), 0, 0};
+                CHECK(whole.bytes);
+                pure_list_encode(list, whole.bytes);
+                collect_bytes(&stored, (PureSpan){whole.bytes, pure_list_size(list)});
+                free(whole.bytes);
+                stored_items = pure_list_size(list);
+            } else
+                collect_bytes(&stored, pure_list_changes(list));
+            pure_list_forget(list, 0);
+            if (event % 17 == 0) { /* what a restart finds is the list as it is */
+                PureList *restarted = stored_list(&stored, stored_items);
+                CHECK(restarted && same_items(restarted, &model));
+                pure_list_free(restarted);
+                ++restarts;
+            }
+        }
+    }
+    CHECK(same_items(list, &model) && adds > 5000 && had > 500 && undone > 400 && restarts > 40);
+    pure_list_free(list);
+    pure_undo_free(&undo);
+    free(stored.bytes);
+    free(model.items);
+    free(before.items);
+    printf("{\"keyed_journal\":{\"adds\":%zu,\"had\":%zu,\"undone\":%zu,\"restarts\":%zu}}\n", adds, had, undone, restarts);
+}
+
 static void list_trees(void) {
     static const uint8_t text_fields[2] = {0, 1};
     uint32_t seed = 0x5eed1234u;
@@ -5573,6 +5848,8 @@ int main(void) {
     lists();
     retired_come_back();
     list_trees();
+    key_sets();
+    keyed_journal();
     folds();
     filters();
     lane_folds();
@@ -5601,6 +5878,6 @@ int main(void) {
     stored_states();
     deferred();
     printf("{\"sizeof_module\":%zu,\"sizeof_app\":%zu}\n", sizeof(PureModule), sizeof(PureApp));
-    puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-bools-replace-by-name-rejections-mutations-messages-documents-typed-verification-text-cursors-utf8-views-rollback-replace-lists-indices-undo-migration-joins-tables-columns-pick-slide-stored-equivalence-crashes-frames-messages-migration-deferred-bursts-pointing-marks-folds-filters-keyed-lists-text-order-message-fields-timers-now-snapshots-links\"}");
+    puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-bools-replace-by-name-rejections-mutations-messages-documents-typed-verification-text-cursors-utf8-views-rollback-replace-lists-indices-undo-migration-joins-tables-columns-pick-slide-stored-equivalence-crashes-frames-messages-migration-deferred-bursts-pointing-marks-folds-filters-keyed-lists-key-sets-text-order-message-fields-timers-now-snapshots-links\"}");
     return 0;
 }