aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/module-list.c134
-rw-r--r--core/module-save.c4
-rw-r--r--core/test-module.c19
-rw-r--r--docs/design/008-module-format.md6
4 files changed, 131 insertions, 32 deletions
diff --git a/core/module-list.c b/core/module-list.c
index c2a831a..522523f 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -642,10 +642,80 @@ static bool decode_cell(const Layout *l, unsigned field, const unsigned char *by
}
/* ---- The journal: records of a stored list's changes, in the order they
- * were made. Each is a u8 kind and the u32le position, then for an insert
- * the item's fields in stored form, for a set the u8 field and its cell. */
+ * were made. Each is a u8 kind and the position, then for an insert the
+ * item's fields, for a set the u8 field and its cell. A record is written
+ * compact (kinds 4-6): the position as a varint (LEB128), a number as the
+ * varint 2 * zigzag(n) when it is an integer n below 2^53 in size (not -0),
+ * else 1 and its binary64 bits (8 bytes, little-endian), a text as a varint
+ * length and its bytes. Records stored before (kinds 1-3, a list's tree
+ * value "PLS2") had a u32le position and cells in stored form. */
+
+enum { FIXED_INSERT = 1, FIXED_REMOVE = 2, FIXED_SET = 3, RECORD_INSERT = 4, RECORD_REMOVE = 5, RECORD_SET = 6,
+ FIXED_HEAD = 5, RECORD_HEAD = 6, JOURNAL_KEPT = 1 << 20 };
+
+static unsigned char *put_varint(unsigned char *out, uint64_t value) {
+ for (; value >= 0x80; value >>= 7) *out++ = (unsigned char)(value | 0x80);
+ *out++ = (unsigned char)value;
+ return out;
+}
+
+static bool get_varint(const unsigned char *bytes, size_t size, size_t *at, uint64_t *value) {
+ *value = 0;
+ for (unsigned shift = 0; shift < 64 && *at < size; shift += 7) {
+ unsigned char byte = bytes[(*at)++];
+ *value |= (uint64_t)(byte & 0x7f) << shift;
+ if (!(byte & 0x80)) return true;
+ }
+ return false;
+}
+
+/* A cell in compact form (the most it takes: compact_bound). */
+static size_t compact_bound(const Layout *l, unsigned field, PureCell cell) { return l->text_fields[field] ? 5 + cell.size : 9; }
-enum { RECORD_INSERT = 1, RECORD_REMOVE = 2, RECORD_SET = 3, RECORD_HEAD = 5, JOURNAL_KEPT = 1 << 20 };
+static unsigned char *put_compact(const Layout *l, unsigned field, PureCell cell, unsigned char *out) {
+ if (l->text_fields[field]) {
+ out = put_varint(out, cell.size);
+ if (cell.size) memcpy(out, cell.text, cell.size);
+ return out + cell.size;
+ }
+ double v = cell.num;
+ if (fabs(v) < 9007199254740992.0 && v == (double)(int64_t)v && !(v == 0 && signbit(v))) {
+ int64_t n = (int64_t)v;
+ uint64_t zigzag = (uint64_t)n << 1 ^ (n < 0 ? UINT64_MAX : 0);
+ return put_varint(out, zigzag << 1);
+ }
+ uint64_t bits;
+ memcpy(&bits, &v, sizeof(bits));
+ *out++ = 1;
+ for (unsigned i = 0; i < 8; ++i) *out++ = (unsigned char)(bits >> (8 * i));
+ return out;
+}
+
+static bool get_compact(const Layout *l, unsigned field, const unsigned char *bytes, size_t size, size_t *at,
+ PureCell *cell) {
+ uint64_t value;
+ *cell = (PureCell){0};
+ if (!get_varint(bytes, size, at, &value)) return false;
+ if (l->text_fields[field]) {
+ if (value > size - *at || !pure_utf8_valid((PureSpan){bytes + *at, (size_t)value})) return false;
+ *cell = (PureCell){0, (unsigned char *)bytes + *at, (size_t)value};
+ *at += (size_t)value;
+ return true;
+ }
+ if (!(value & 1)) { /* an integer */
+ uint64_t zigzag = value >> 1;
+ if (zigzag >= UINT64_C(1) << 54) return false;
+ int64_t n = zigzag & 1 ? -(int64_t)(zigzag >> 1) - 1 : (int64_t)(zigzag >> 1);
+ cell->num = (double)n;
+ return true;
+ }
+ if (value != 1 || size - *at < 8) return false;
+ uint64_t bits = 0;
+ for (unsigned i = 0; i < 8; ++i) bits |= (uint64_t)bytes[*at + i] << (8 * i);
+ *at += 8;
+ memcpy(&cell->num, &bits, sizeof(bits));
+ return isfinite(cell->num);
+}
/* Room for size more bytes at the journal's end, or NULL without memory. */
static unsigned char *journal_room(PureList *list, size_t size) {
@@ -662,8 +732,7 @@ static unsigned char *journal_room(PureList *list, size_t size) {
static unsigned char *record_head(unsigned char *out, unsigned kind, size_t at) {
*out++ = (unsigned char)kind;
- for (unsigned i = 0; i < 4; ++i) *out++ = (unsigned char)(at >> (8 * i));
- return out;
+ return put_varint(out, at);
}
void pure_list_journal(PureList *list, bool journaled) {
@@ -748,27 +817,40 @@ PURE_COLD PureResult pure_list_read(PureList *list, const unsigned char *bytes,
return PURE_OK;
}
+/* A record's cell, compact or as stored before. */
+static bool record_cell(const Layout *l, bool compact, unsigned field, const unsigned char *bytes, size_t size,
+ size_t *at, PureCell *cell) {
+ return compact ? get_compact(l, field, bytes, size, at, cell) : decode_cell(l, field, bytes, size, at, cell);
+}
+
PURE_COLD PureResult pure_list_replay(PureList *list, const unsigned char *bytes, size_t size) {
const Layout *l = &list->layout;
bool journaled = list->journaled;
PureResult result = PURE_OK;
list->journaled = false;
for (size_t at = 0; at < size && result == PURE_OK;) {
- if (size - at < RECORD_HEAD) { result = PURE_STORE_ERROR; break; }
- unsigned kind = bytes[at];
- size_t position = 0;
- for (unsigned i = 0; i < 4; ++i) position |= (size_t)bytes[at + 1 + i] << (8 * i);
- at += RECORD_HEAD;
+ unsigned kind = bytes[at++];
+ bool compact = kind >= RECORD_INSERT;
+ uint64_t position = 0;
+ if (compact) {
+ if (!get_varint(bytes, size, &at, &position)) { result = PURE_STORE_ERROR; break; }
+ } else {
+ if (size - at < FIXED_HEAD - 1) { result = PURE_STORE_ERROR; break; }
+ for (unsigned i = 0; i < 4; ++i) position |= (uint64_t)bytes[at + i] << (8 * i);
+ at += FIXED_HEAD - 1;
+ }
PureCell cells[16];
- if (kind == RECORD_INSERT)
- result = position <= list->count && decode_item(l, bytes, size, &at, cells) ?
- pure_list_insert(list, position, cells, NULL) : PURE_STORE_ERROR;
- else if (kind == RECORD_REMOVE)
- result = position < list->count ? pure_list_remove(list, position, NULL) : PURE_STORE_ERROR;
- else if (kind == RECORD_SET) {
+ unsigned change = compact ? kind - (RECORD_INSERT - FIXED_INSERT) : kind;
+ bool ok = true;
+ if (change == FIXED_INSERT) {
+ for (unsigned f = 0; ok && f < l->fields; ++f) ok = record_cell(l, compact, f, bytes, size, &at, &cells[f]);
+ result = ok && position <= list->count ? pure_list_insert(list, (size_t)position, cells, NULL) : PURE_STORE_ERROR;
+ } else if (change == FIXED_REMOVE)
+ result = position < list->count ? pure_list_remove(list, (size_t)position, NULL) : PURE_STORE_ERROR;
+ else if (change == FIXED_SET) {
unsigned field = at < size ? bytes[at++] : l->fields;
- result = field < l->fields && position < list->count && decode_cell(l, field, bytes, size, &at, &cells[0]) ?
- pure_list_set(list, position, field, cells[0], NULL) : PURE_STORE_ERROR;
+ result = field < l->fields && position < list->count && record_cell(l, compact, field, bytes, size, &at, &cells[0]) ?
+ pure_list_set(list, (size_t)position, field, cells[0], NULL) : PURE_STORE_ERROR;
} else
result = PURE_STORE_ERROR;
}
@@ -784,7 +866,7 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu
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 += cell_bytes(l, f, cells[f]);
+ 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;
Place p;
if (owned < l->fields || (list->journaled && !record) || !prepare(list, at, &p)) {
@@ -798,8 +880,8 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu
}
if (record) {
unsigned char *end = record_head(record, RECORD_INSERT, at);
- for (unsigned f = 0; f < l->fields; ++f) end = encode_cell(l, f, item[f], end);
- list->journal_size += size;
+ 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);
@@ -833,10 +915,7 @@ PureResult pure_list_remove(PureList *list, size_t at, PureUndo *undo) {
return PURE_ALLOCATION;
if (!cells) cells = kept;
for (unsigned f = 0; f < l->fields; ++f) cells[f] = cell_at(l, leaf, within, f);
- if (record) {
- record_head(record, RECORD_REMOVE, at);
- list->journal_size += RECORD_HEAD;
- }
+ if (record) list->journal_size += (size_t)(record_head(record, RECORD_REMOVE, at) - record);
if (undo) undo->cell_count += l->fields;
list->bytes -= cells_bytes(l, cells);
if (!undo) let_go_cells(list, cells);
@@ -866,7 +945,7 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val
PureCell copy;
if (!own_cell(list, field, value, &copy)) return PURE_ALLOCATION;
PureCell old = cell_at(l, leaf, within, field);
- size_t size = RECORD_HEAD + 1 + cell_bytes(l, field, copy);
+ size_t size = RECORD_HEAD + 1 + compact_bound(l, field, copy);
unsigned char *record = list->journaled ? journal_room(list, size) : NULL;
if ((list->journaled && !record) ||
(undo && !log_change(undo, (Entry){.change = CHANGED, .list = list, .at = at, .field = field, .old = old}))) {
@@ -876,8 +955,7 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val
if (record) {
unsigned char *end = record_head(record, RECORD_SET, at);
*end++ = (unsigned char)field;
- encode_cell(l, field, copy, end);
- list->journal_size += size;
+ list->journal_size += (size_t)(put_compact(l, field, copy, end) - record);
}
list->bytes += cell_bytes(l, field, copy) - cell_bytes(l, field, old);
if (l->text_fields[field]) texts(l, leaf, field)[within] = (PureSpan){copy.text, copy.size};
diff --git a/core/module-save.c b/core/module-save.c
index c05394f..ddc2797 100644
--- a/core/module-save.c
+++ b/core/module-save.c
@@ -35,8 +35,8 @@ static const unsigned char values_magic[4] = {'P', 'V', 'S', '1'}, image_magic[4
* log is kept within as many bytes as all their items (and LOG_KEPT) by
* writing the image that holds it back. */
#ifdef PURE_STORE_TEST
-enum { JOURNAL_MIN = 256 };
-#define LOG_KEPT (UINT64_C(64) << 10)
+enum { JOURNAL_MIN = 64 };
+#define LOG_KEPT (UINT64_C(4) << 10)
unsigned long pure_save_test_checkpoints;
#else
enum { JOURNAL_MIN = 1 << 20 };
diff --git a/core/test-module.c b/core/test-module.c
index d361f4f..b2024b5 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -1155,6 +1155,25 @@ static void list_trees(void) {
stored.size = length - 1; /* the last record cut short */
CHECK(!stored_list(&stored, stored_items));
free(stored.bytes);
+ /* Compact records keep every number bit for bit: integers, -0, the edges of 2^53, the rest. */
+ static const uint8_t number_field[1] = {0};
+ static const double edges[] = {0.0, -0.0, 1, -1, 127, -128, 9007199254740991.0, -9007199254740991.0,
+ 9007199254740992.0, -9007199254740994.0, 1e300, -1e-300, 0.1, 3.5e15 + 0.5, 4.9e-324};
+ PureList *numbers = pure_list_new(1, number_field), *read_back = pure_list_new(1, number_field);
+ CHECK(numbers && read_back);
+ pure_list_journal(numbers, true);
+ for (size_t k = 0; k < sizeof(edges) / sizeof(*edges); ++k) {
+ CHECK(pure_list_insert(numbers, k, (PureCell[]){{edges[k], NULL, 0}}, NULL) == PURE_OK);
+ CHECK(pure_list_set(numbers, k, 0, (PureCell){edges[k], NULL, 0}, NULL) == PURE_OK);
+ }
+ PureSpan edge_records = pure_list_changes(numbers);
+ CHECK(edge_records.size < sizeof(edges) / sizeof(*edges) * 2 * 14 && pure_list_replay(read_back, edge_records.data, edge_records.size) == PURE_OK);
+ for (size_t k = 0; k < sizeof(edges) / sizeof(*edges); ++k) {
+ double got = pure_list_get(read_back, k, 0).num;
+ CHECK(!memcmp(&got, &edges[k], sizeof(got)));
+ }
+ pure_list_free(numbers);
+ pure_list_free(read_back);
printf("{\"journal_saves\":%zu,\"journal_rewrites\":%zu}\n", saves, rewrites);
for (; held; --held, first = (first + 1) % SHARES) {
CHECK(same_items(copies[first], &shared[first]));
diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md
index d515c12..ac73f2f 100644
--- a/docs/design/008-module-format.md
+++ b/docs/design/008-module-format.md
@@ -271,8 +271,10 @@ text·리스트가 남을 때만 위치를 유지한다.
`PLI1`, 레코드 필드 수, 필드마다 종류·이름, 그것이 담은 저장의 번호(u64), 항목(수는 binary64, text는 u32 길이와
바이트)이고, 통째로 옆에 써서 동기화한 뒤 이름을 바꿔 끼운다(파일 전체의 다이제스트로 잘림·손상을 거부).
**로그**(`log-0`, `log-1`, ... 구간, `core/log.h`)는 리스트를 바꾼 저장마다 항목 하나다. 항목은 저장 번호, 앞 항목의
- 번호와 다이제스트, 트리도 커밋했는지, 페이로드(바뀐 리스트마다 이름과 변경 기록: 종류 u8(1 삽입, 2 제거, 3 설정),
- 위치 u32, 삽입이면 항목, 설정이면 필드와 값, 모두 그 리스트 이미지의 필드로)다. 구간은 처음 만들 때 통째로 할당하고,
+ 번호와 다이제스트, 트리도 커밋했는지, 페이로드(바뀐 리스트마다 이름과 변경 기록, 모두 그 리스트 이미지의 필드로)다.
+ 기록은 종류 u8(4 삽입, 5 제거, 6 설정)과 위치(varint)이고, 삽입이면 항목, 설정이면 필드 u8과 값이 따른다. 수는
+ 크기가 2^53 미만인 정수(-0 아님)면 varint `2 × zigzag(n)`, 아니면 1과 binary64 8바이트다. text는 varint 길이와
+ 바이트다. 옛 `PLS2`의 기록(종류 1–3)은 위치 u32와 저장 형태의 칸을 썼고, 그대로 읽는다. 구간은 처음 만들 때 통째로 할당하고,
이미지가 모두 담은 항목만 가진 구간은 다시 쓴다. 그래서 덧붙이기는 파일을 키우지도 새 블록을 받지도 않아 동기화가
데이터만 쓴다. 항목은 앞 항목의 다이제스트를 가리키므로 찢긴 쓰기나 재사용한 구간에 남은 옛 바이트는 이어지지 않는다.
- **저장 번호.** 저장마다 번호가 하나 오른다. 로그 항목이 있고 트리도 커밋하는 저장은 그 번호를 트리의 상태 `seq`에
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 13:46:17 +0000