1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#ifndef PURE_MODULE_LIST_H
#define PURE_MODULE_LIST_H
#include "result.h"
#include "state.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
/* Executor paths that run once per module or app (loading, verifying,
* starting, replacing, reading stored states) are built for size; events
* stay built for speed. */
#if defined(__GNUC__) || defined(__clang__)
#define PURE_COLD __attribute__((cold))
#else
#define PURE_COLD
#endif
/* Runtime-owned lists of records for the module executor. An item is one
* cell per field: a number, or text bytes the list owns. Every change made
* during an event is logged; a failed event undoes the log in reverse and a
* successful one frees what it replaced. */
typedef struct { double num; unsigned char *text; size_t size; } PureCell;
typedef struct PureList PureList;
/* An event's list changes; a removed item's cells wait in cells. */
typedef struct {
void *entries;
size_t count, capacity;
PureCell *cells;
size_t cell_count, cell_capacity;
} PureUndo;
/* Nodes and texts a list let go while a shared copy may still read them. */
typedef struct { void *entries; size_t count, capacity; } PureRetired;
/* Items one after another, as a leaf of the list keeps them: positions start
* to start + count - 1, each field's cells side by side (a number field's as
* numbers, a text field's as spans). */
typedef struct {
size_t start;
unsigned count;
union { const double *numbers; const PureSpan *texts; } column[16];
/* Where the run is in the list's tree, for the next one. */
const void *path[16];
uint8_t taken[16];
unsigned depth;
} PureRun;
/* A list holds up to PURE_LIST_ITEMS items, a run up to PURE_LIST_RUN. */
enum { PURE_LIST_ITEMS = 1 << 24, PURE_LIST_RUN = 32 };
PureList *pure_list_new(unsigned fields, const uint8_t *text_fields);
void pure_list_free(PureList *);
/* Let every item go (retired where a shared copy may read it). */
void pure_list_clear(PureList *);
size_t pure_list_count(const PureList *);
/* Share the items as they are with a read-only copy (for readers on other
* threads), without copying them: from then on the list copies the nodes it
* changes, and nodes and texts it lets go go to retired instead of being
* freed, since the copy may still read them. The copy is freed with
* pure_list_free, on any thread, when its last reference goes
* (pure_list_hold takes one more). Only between events (no change waits to
* be committed or undone). */
PureList *pure_list_share(PureList *, PureRetired *retired);
void pure_list_hold(PureList *copy);
/* Whether copy shares list's items as they are now. */
bool pure_list_current(const PureList *copy, const PureList *list);
/* Which list, and its version: the same pair means the same items. */
void pure_list_stamp(const PureList *, uint64_t *id, uint64_t *version);
/* Free what was retired while no copy that shared it remains. */
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 *);
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);
/* The run holding position at (false past the end), and the run after
* run (false at the end): for reading item after item without finding each.
* Valid until the list changes. */
bool pure_list_run(const PureList *, size_t at, PureRun *);
bool pure_list_next(const PureList *, PureRun *);
/* In a list ordered by field (a keyed list): the first position whose item's
* field does not order below key (numbers by value, texts by bytes), and
* whether that item's field is key. */
size_t pure_list_seek(const PureList *, unsigned field, PureCell key, bool *found);
/* The field a keyed list keeps its items in order of: when it is a number
* 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);
/* 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
* same key (nothing is made). */
PureResult pure_list_sorted(const PureList *, unsigned field, PureList **out, size_t *moved);
/* The stored form of items: each item's fields in order, a number as its
* binary64 bits (little-endian), a text as a u32le length and its bytes.
* pure_list_size is the bytes of all the items so stored, and
* pure_list_encode writes them to out. */
size_t pure_list_size(const PureList *);
void pure_list_encode(const PureList *, unsigned char *out);
/* Append the items stored in bytes; each field is checked. */
PureResult pure_list_read(PureList *, const unsigned char *bytes, size_t size);
/* A stored list journals its changes (from pure_list_journal(list, true)
* on): every insert, remove and set adds a record, a u8 kind (1 insert, 2
* remove, 3 set) and the u32le position, then an insert's item or a set's
* u8 field and cell in stored form. A change there is no room to record does
* not happen. pure_list_changes are the records since pure_list_forget last
* kept none; forgetting down to a length taken earlier drops the records of
* changes undone since (an undo does not journal). pure_list_replay makes
* the changes of records again, in order: a list read from its stored items
* and given its journal is the list that wrote them. */
void pure_list_journal(PureList *, bool journaled);
PureSpan pure_list_changes(const PureList *);
void pure_list_forget(PureList *, size_t size);
PureResult pure_list_replay(PureList *, const unsigned char *bytes, size_t size);
/* Undo the changes logged after mark (a count taken earlier), newest first. */
void pure_undo_rollback(PureUndo *, size_t mark);
void pure_undo_commit(PureUndo *);
void pure_undo_free(PureUndo *);
#endif
|
