[PATCH v2 0/5] Reftable support git-core
- From
Han-Wen Nienhuys via GitGitGadget <gitgitgadget@gmail.com>
- Date
- Jan 27, 2020, 14:22 UTC
- Message-ID
- <pull.539.v2.git.1580134944.gitgitgadget@gmail.com>
- In-Reply-To
- <pull.539.git.1579808479.gitgitgadget@gmail.com>
This adds the reftable library, and hooks it up as a ref backend.
At this point, I am mainly interested in feedback on the spots marked with XXX in the Git source code, in particular, how to handle reflog expiry in this backend.
v2
* address Jun's nits. * address Dscho's portability comments * more background in commit messages.
Han-Wen Nienhuys (5): setup.c: enable repo detection for reftable create .git/refs in files-backend.c Document how ref iterators and symrefs interact Add reftable library Reftable support for git-core
Makefile | 23 +- builtin/init-db.c | 2 - refs.c | 18 +- refs.h | 2 + refs/files-backend.c | 4 + refs/refs-internal.h | 4 + refs/reftable-backend.c | 812 +++++++++++++++++++++++++++ reftable/LICENSE | 31 ++ reftable/README.md | 17 + reftable/VERSION | 5 + reftable/basics.c | 196 +++++++ reftable/basics.h | 38 ++ reftable/block.c | 401 ++++++++++++++ reftable/block.h | 71 +++ reftable/block_test.c | 151 +++++ reftable/blocksource.h | 20 + reftable/bytes.c | 0 reftable/config.h | 1 + reftable/constants.h | 27 + reftable/dump.c | 97 ++++ reftable/file.c | 97 ++++ reftable/iter.c | 230 ++++++++ reftable/iter.h | 56 ++ reftable/merged.c | 288 ++++++++++ reftable/merged.h | 34 ++ reftable/merged_test.c | 258 +++++++++ reftable/pq.c | 124 +++++ reftable/pq.h | 34 ++ reftable/reader.c | 710 ++++++++++++++++++++++++ reftable/reader.h | 52 ++ reftable/record.c | 1110 +++++++++++++++++++++++++++++++++++++ reftable/record.h | 79 +++ reftable/record_test.c | 332 +++++++++++ reftable/reftable.h | 399 +++++++++++++ reftable/reftable_test.c | 481 ++++++++++++++++ reftable/slice.c | 199 +++++++ reftable/slice.h | 39 ++ reftable/slice_test.c | 38 ++ reftable/stack.c | 985 ++++++++++++++++++++++++++++++++ reftable/stack.h | 40 ++ reftable/stack_test.c | 281 ++++++++++ reftable/system.h | 36 ++ reftable/test_framework.c | 67 +++ reftable/test_framework.h | 64 +++ reftable/tree.c | 66 +++ reftable/tree.h | 24 + reftable/tree_test.c | 61 ++ reftable/writer.c | 624 +++++++++++++++++++++ reftable/writer.h | 46 ++ setup.c | 20 +- 50 files changed, 8782 insertions(+), 12 deletions(-) create mode 100644 refs/reftable-backend.c create mode 100644 reftable/LICENSE create mode 100644 reftable/README.md create mode 100644 reftable/VERSION create mode 100644 reftable/basics.c create mode 100644 reftable/basics.h create mode 100644 reftable/block.c create mode 100644 reftable/block.h create mode 100644 reftable/block_test.c create mode 100644 reftable/blocksource.h create mode 100644 reftable/bytes.c create mode 100644 reftable/config.h create mode 100644 reftable/constants.h create mode 100644 reftable/dump.c create mode 100644 reftable/file.c create mode 100644 reftable/iter.c create mode 100644 reftable/iter.h create mode 100644 reftable/merged.c create mode 100644 reftable/merged.h create mode 100644 reftable/merged_test.c create mode 100644 reftable/pq.c create mode 100644 reftable/pq.h create mode 100644 reftable/reader.c create mode 100644 reftable/reader.h create mode 100644 reftable/record.c create mode 100644 reftable/record.h create mode 100644 reftable/record_test.c create mode 100644 reftable/reftable.h create mode 100644 reftable/reftable_test.c create mode 100644 reftable/slice.c create mode 100644 reftable/slice.h create mode 100644 reftable/slice_test.c create mode 100644 reftable/stack.c create mode 100644 reftable/stack.h create mode 100644 reftable/stack_test.c create mode 100644 reftable/system.h create mode 100644 reftable/test_framework.c create mode 100644 reftable/test_framework.h create mode 100644 reftable/tree.c create mode 100644 reftable/tree.h create mode 100644 reftable/tree_test.c create mode 100644 reftable/writer.c create mode 100644 reftable/writer.h
base-commit: bc7a3d4dc04dd719e7c8c35ebd7a6e6651c5c5b6 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-539%2Fhanwen%2Freftable-v2 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-539/hanwen/reftable-v2 Pull-Request: https://github.com/gitgitgadget/git/pull/539
Range-diff vs v1:
1: fd2baf1628 = 1: 174b98f6db setup.c: enable repo detection for reftable
2: bc643d0b0c = 2: d7d642dcf6 create .git/refs in files-backend.c
3: 1a01e0b1b5 = 3: 9cf185b51f Document how ref iterators and symrefs interact
4: 3c86bd1d7e ! 4: 2106ff286b Add reftable library
@@ -2,23 +2,92 @@
Add reftable library
+ Reftable is a new format for storing the ref database. It provides the
+ following benefits:
+
+ * Simple and fast atomic ref transactions, including multiple refs and reflogs.
+ * Compact storage of ref data.
+ * Fast look ups of ref data.
+ * Case-sensitive ref names on Windows/OSX, regardless of file system
+ * Eliminates file/directory conflicts in ref names
+
+ Further context and motivation can be found in background reading:
+
+ * Spec: https://github.com/eclipse/jgit/blob/master/Documentation/technical/reftable.md
+
+ * Original discussion on JGit-dev: https://www.eclipse.org/lists/jgit-dev/msg03389.html
+
+ * First design discussion on git@vger: https://public-inbox.org/git/CAJo=hJtTp2eA3z9wW9cHo-nA7kK40vVThqh6inXpbCcqfdMP9g@mail.gmail.com/
+
+ * Last design discussion on git@vger: https://public-inbox.org/git/CAJo=hJsZcAM9sipdVr7TMD-FD2V2W6_pvMQ791EGCDsDkQ033w@mail.gmail.com/
+
+ * First attempt at implementation: https://public-inbox.org/git/CAP8UFD0PPZSjBnxCA7ez91vBuatcHKQ+JUWvTD1iHcXzPBjPBg@mail.gmail.com/
+
+ * libgit2 support issue: https://github.com/libgit2/libgit2/issues
+
+ * GitLab support issue: https://gitlab.com/gitlab-org/git/issues/6
+
+ * go-git support issue: https://github.com/src-d/go-git/issues/1059
+
Signed-off-by: Han-Wen Nienhuys <hanwen@google.com>
Change-Id: Id396ff42be8b42b9e11f194a32e2f95b8250c109
+ diff --git a/reftable/LICENSE b/reftable/LICENSE
+ new file mode 100644
+ --- /dev/null
+ +++ b/reftable/LICENSE
+@@
++BSD License
++
++Copyright (c) 2020, Google LLC
++All rights reserved.
++
++Redistribution and use in source and binary forms, with or without
++modification, are permitted provided that the following conditions are
++met:
++
++* Redistributions of source code must retain the above copyright notice,
++this list of conditions and the following disclaimer.
++
++* Redistributions in binary form must reproduce the above copyright
++notice, this list of conditions and the following disclaimer in the
++documentation and/or other materials provided with the distribution.
++
++* Neither the name of Google LLC nor the names of its contributors may
++be used to endorse or promote products derived from this software
++without specific prior written permission.
++
++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
++"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
++LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
++A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
++OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
++SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
++LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
++DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
++THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
++(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
++OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
diff --git a/reftable/README.md b/reftable/README.md
new file mode 100644
--- /dev/null
+++ b/reftable/README.md
@@
-+The source code in this directory comes from https://github.com/google/reftable
-+and can be updated by doing:
+
-+ rm -rf reftable-repo && \
-+ git clone https://github.com/google/reftable reftable-repo && \
++The source code in this directory comes from https://github.com/google/reftable.
++
++The VERSION file keeps track of the current version of the reftable library.
++
++To update the library, do:
++
++ ((cd reftable-repo && git fetch origin && git checkout origin/master ) ||
++ git clone https://github.com/google/reftable reftable-repo) && \
+ cp reftable-repo/c/*.[ch] reftable/ && \
-+ cp reftable-repo/LICENSE reftable/
++ cp reftable-repo/LICENSE reftable/ &&
+ git --git-dir reftable-repo/.git show --no-patch origin/master \
-+ > reftable/VERSION
++ > reftable/VERSION && \
++ echo '/* empty */' > reftable/config.h
+
+Bugfixes should be accompanied by a test and applied to upstream project at
+https://github.com/google/reftable.
@@ -28,299 +97,11 @@
--- /dev/null
+++ b/reftable/VERSION
@@
-+commit 887250932a9c39a15aee26aef59df2300c77c03f
++commit c616d53b88657c3a5fe4d2e7243a48effc34c626
+Author: Han-Wen Nienhuys <hanwen@google.com>
-+Date: Wed Jan 22 19:50:16 2020 +0100
-+
-+ C: implement reflog expiry
-+
-+diff --git a/c/reftable.h b/c/reftable.h
-+index 2f44973..d760af9 100644
-+--- a/c/reftable.h
-++++ b/c/reftable.h
-+@@ -359,8 +359,17 @@ void stack_destroy(struct stack *st);
-+ /* reloads the stack if necessary. */
-+ int stack_reload(struct stack *st);
-+
-+-/* compacts all reftables into a giant table. */
-+-int stack_compact_all(struct stack *st);
-++/* Policy for expiring reflog entries. */
-++struct log_expiry_config {
-++ /* Drop entries older than this timestamp */
-++ uint64_t time;
-++
-++ /* Drop older entries */
-++ uint64_t min_update_index;
-++};
-++
-++/* compacts all reftables into a giant table. Expire reflog entries if config is non-NULL */
-++int stack_compact_all(struct stack *st, struct log_expiry_config *config);
-+
-+ /* heuristically compact unbalanced table stack. */
-+ int stack_auto_compact(struct stack *st);
-+diff --git a/c/stack.c b/c/stack.c
-+index d67828f..641ac52 100644
-+--- a/c/stack.c
-++++ b/c/stack.c
-+@@ -119,7 +119,7 @@ static struct reader **stack_copy_readers(struct stack *st, int cur_len) {
-+ return cur;
-+ }
-+
-+-static int stack_reload_once(struct stack *st, char **names) {
-++static int stack_reload_once(struct stack *st, char **names, bool reuse_open) {
-+ int cur_len = st->merged == NULL ? 0 : st->merged->stack_len;
-+ struct reader **cur = stack_copy_readers(st, cur_len);
-+ int err = 0;
-+@@ -136,7 +136,7 @@ static int stack_reload_once(struct stack *st, char **names) {
-+
-+ // this is linear; we assume compaction keeps the number of tables
-+ // under control so this is not quadratic.
-+- for (int j = 0; j < cur_len; j++) {
-++ for (int j = 0; reuse_open && j < cur_len; j++) {
-+ if (cur[j] != NULL && 0 == strcmp(cur[j]->name, name)) {
-+ rd = cur[j];
-+ cur[j] = NULL;
-+@@ -207,7 +207,7 @@ static int tv_cmp(struct timeval *a, struct timeval *b) {
-+ return udiff;
-+ }
-+
-+-int stack_reload(struct stack *st) {
-++static int stack_reload_maybe_reuse(struct stack *st, bool reuse_open) {
-+ struct timeval deadline = {};
-+ int err = gettimeofday(&deadline, NULL);
-+ int64_t delay = 0;
-+@@ -238,7 +238,7 @@ int stack_reload(struct stack *st) {
-+ free_names(names);
-+ return err;
-+ }
-+- err = stack_reload_once(st, names);
-++ err = stack_reload_once(st, names, reuse_open);
-+ if (err == 0) {
-+ free_names(names);
-+ break;
-+@@ -269,6 +269,10 @@ int stack_reload(struct stack *st) {
-+ return 0;
-+ }
-+
-++int stack_reload(struct stack *st) {
-++ return stack_reload_maybe_reuse(st, true);
-++}
-++
-+ // -1 = error
-+ // 0 = up to date
-+ // 1 = changed.
-+@@ -471,7 +475,7 @@ uint64_t stack_next_update_index(struct stack *st) {
-+ }
-+
-+ static int stack_compact_locked(struct stack *st, int first, int last,
-+- struct slice *temp_tab) {
-++ struct slice *temp_tab, struct log_expiry_config *config) {
-+ struct slice next_name = {};
-+ int tab_fd = -1;
-+ struct writer *wr = NULL;
-+@@ -488,7 +492,7 @@ static int stack_compact_locked(struct stack *st, int first, int last,
-+ tab_fd = mkstemp((char *)slice_as_string(temp_tab));
-+ wr = new_writer(fd_writer, &tab_fd, &st->config);
-+
-+- err = stack_write_compact(st, wr, first, last);
-++ err = stack_write_compact(st, wr, first, last, config);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+@@ -515,7 +519,7 @@ static int stack_compact_locked(struct stack *st, int first, int last,
-+ }
-+
-+ int stack_write_compact(struct stack *st, struct writer *wr, int first,
-+- int last) {
-++ int last, struct log_expiry_config *config) {
-+ int subtabs_len = last - first + 1;
-+ struct reader **subtabs = calloc(sizeof(struct reader *), last - first + 1);
-+ struct merged_table *mt = NULL;
-+@@ -580,6 +584,16 @@ int stack_write_compact(struct stack *st, struct writer *wr, int first,
-+ continue;
-+ }
-+
-++ // XXX collect stats?
-++
-++ if (config != NULL && config->time > 0 && log.time < config->time) {
-++ continue;
-++ }
-++
-++ if (config != NULL && config->min_update_index > 0 && log.update_index < config->min_update_index) {
-++ continue;
-++ }
-++
-+ err = writer_add_log(wr, &log);
-+ if (err < 0) {
-+ break;
-+@@ -599,7 +613,7 @@ int stack_write_compact(struct stack *st, struct writer *wr, int first,
-+ }
-+
-+ // < 0: error. 0 == OK, > 0 attempt failed; could retry.
-+-static int stack_compact_range(struct stack *st, int first, int last) {
-++static int stack_compact_range(struct stack *st, int first, int last, struct log_expiry_config *expiry) {
-+ struct slice temp_tab_name = {};
-+ struct slice new_table_name = {};
-+ struct slice lock_file_name = {};
-+@@ -612,7 +626,7 @@ static int stack_compact_range(struct stack *st, int first, int last) {
-+ char **delete_on_success = calloc(sizeof(char *), compact_count + 1);
-+ char **subtable_locks = calloc(sizeof(char *), compact_count + 1);
-+
-+- if (first >= last) {
-++ if (first > last || (expiry == NULL && first == last)) {
-+ err = 0;
-+ goto exit;
-+ }
-+@@ -676,7 +690,7 @@ static int stack_compact_range(struct stack *st, int first, int last) {
-+ }
-+ have_lock = false;
-+
-+- err = stack_compact_locked(st, first, last, &temp_tab_name);
-++ err = stack_compact_locked(st, first, last, &temp_tab_name, expiry);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+@@ -739,10 +753,12 @@ static int stack_compact_range(struct stack *st, int first, int last) {
-+ have_lock = false;
-+
-+ for (char **p = delete_on_success; *p; p++) {
-+- unlink(*p);
-++ if (0 != strcmp(*p, slice_as_string(&new_table_path))) {
-++ unlink(*p);
-++ }
-+ }
-+
-+- err = stack_reload(st);
-++ err = stack_reload_maybe_reuse(st, first < last);
-+ exit:
-+ for (char **p = subtable_locks; *p; p++) {
-+ unlink(*p);
-+@@ -764,12 +780,12 @@ static int stack_compact_range(struct stack *st, int first, int last) {
-+ return err;
-+ }
-+
-+-int stack_compact_all(struct stack *st) {
-+- return stack_compact_range(st, 0, st->merged->stack_len - 1);
-++int stack_compact_all(struct stack *st, struct log_expiry_config *config) {
-++ return stack_compact_range(st, 0, st->merged->stack_len - 1, config);
-+ }
-+
-+-static int stack_compact_range_stats(struct stack *st, int first, int last) {
-+- int err = stack_compact_range(st, first, last);
-++static int stack_compact_range_stats(struct stack *st, int first, int last, struct log_expiry_config *config) {
-++ int err = stack_compact_range(st, first, last, config);
-+ if (err > 0) {
-+ st->stats.failures++;
-+ }
-+@@ -856,7 +872,7 @@ int stack_auto_compact(struct stack *st) {
-+ struct segment seg = suggest_compaction_segment(sizes, st->merged->stack_len);
-+ free(sizes);
-+ if (segment_size(&seg) > 0) {
-+- return stack_compact_range_stats(st, seg.start, seg.end - 1);
-++ return stack_compact_range_stats(st, seg.start, seg.end - 1, NULL);
-+ }
-+
-+ return 0;
-+diff --git a/c/stack.h b/c/stack.h
-+index 8cb2cb0..092a03b 100644
-+--- a/c/stack.h
-++++ b/c/stack.h
-+@@ -25,7 +25,7 @@ int read_lines(const char *filename, char ***lines);
-+ int stack_try_add(struct stack *st,
-+ int (*write_table)(struct writer *wr, void *arg), void *arg);
-+ int stack_write_compact(struct stack *st, struct writer *wr, int first,
-+- int last);
-++ int last, struct log_expiry_config *config);
-+ int fastlog2(uint64_t sz);
-+
-+ struct segment {
-+diff --git a/c/stack_test.c b/c/stack_test.c
-+index c49d8b8..8c0cde0 100644
-+--- a/c/stack_test.c
-++++ b/c/stack_test.c
-+@@ -121,7 +121,7 @@ void test_stack_add(void) {
-+ assert_err(err);
-+ }
-+
-+- err = stack_compact_all(st);
-++ err = stack_compact_all(st, NULL);
-+ assert_err(err);
-+
-+ for (int i = 0; i < N; i++) {
-+@@ -186,7 +186,73 @@ void test_suggest_compaction_segment(void) {
-+ }
-+ }
-+
-++void test_reflog_expire(void) {
-++ char dir[256] = "/tmp/stack.XXXXXX";
-++ assert(mkdtemp(dir));
-++ printf("%s\n", dir);
-++ char fn[256] = "";
-++ strcat(fn, dir);
-++ strcat(fn, "/refs");
-++
-++ struct write_options cfg = {};
-++ struct stack *st = NULL;
-++ int err = new_stack(&st, dir, fn, cfg);
-++ assert_err(err);
-++
-++ struct log_record logs[20] = {};
-++ int N = ARRAYSIZE(logs) -1;
-++ for (int i = 1; i <= N; i++) {
-++ char buf[256];
-++ sprintf(buf, "branch%02d", i);
-++
-++ logs[i].ref_name = strdup(buf);
-++ logs[i].update_index = i;
-++ logs[i].time = i;
-++ logs[i].new_hash = malloc(SHA1_SIZE);
-++ logs[i].email = strdup("identity@invalid");
-++ set_test_hash(logs[i].new_hash, i);
-++ }
-++
-++ for (int i = 1; i <= N; i++) {
-++ int err = stack_add(st, &write_test_log, &logs[i]);
-++ assert_err(err);
-++ }
-++
-++ err = stack_compact_all(st, NULL);
-++ assert_err(err);
-++
-++ struct log_expiry_config expiry = {
-++ .time = 10,
-++ };
-++ err = stack_compact_all(st, &expiry);
-++ assert_err(err);
-++
-++ struct log_record log = {};
-++ err = stack_read_log(st, logs[9].ref_name, &log);
-++ assert(err == 1);
-++
-++ err = stack_read_log(st, logs[11].ref_name, &log);
-++ assert_err(err);
-++
-++ expiry.min_update_index = 15;
-++ err = stack_compact_all(st, &expiry);
-++ assert_err(err);
-++
-++ err = stack_read_log(st, logs[14].ref_name, &log);
-++ assert(err == 1);
-++
-++ err = stack_read_log(st, logs[16].ref_name, &log);
-++ assert_err(err);
-++
-++ // cleanup
-++ stack_destroy(st);
-++ for (int i = 0; i < N; i++) {
-++ log_record_clear(&logs[i]);
-++ }
-++}
-++
-+ int main() {
-++ add_test_case("test_reflog_expire", test_reflog_expire);
-+ add_test_case("test_suggest_compaction_segment",
-+ &test_suggest_compaction_segment);
-+ add_test_case("test_sizes_to_segments", &test_sizes_to_segments);
++Date: Mon Jan 27 15:05:43 2020 +0100
++
++ C: ban // comments
diff --git a/reftable/basics.c b/reftable/basics.c
new file mode 100644
@@ -337,175 +118,191 @@
+
+#include "basics.h"
+
-+#include <stdio.h>
-+#include <stdlib.h>
-+#include <string.h>
++#include "system.h"
+
-+void put_u24(byte *out, uint32_t i) {
-+ out[0] = (byte)((i >> 16) & 0xff);
-+ out[1] = (byte)((i >> 8) & 0xff);
-+ out[2] = (byte)((i)&0xff);
++void put_u24(byte *out, uint32_t i)
++{
++ out[0] = (byte)((i >> 16) & 0xff);
++ out[1] = (byte)((i >> 8) & 0xff);
++ out[2] = (byte)((i)&0xff);
+}
+
-+uint32_t get_u24(byte *in) {
-+ return (uint32_t)(in[0]) << 16 | (uint32_t)(in[1]) << 8 | (uint32_t)(in[2]);
++uint32_t get_u24(byte *in)
++{
++ return (uint32_t)(in[0]) << 16 | (uint32_t)(in[1]) << 8 |
++ (uint32_t)(in[2]);
+}
+
-+void put_u32(byte *out, uint32_t i) {
-+ out[0] = (byte)((i >> 24) & 0xff);
-+ out[1] = (byte)((i >> 16) & 0xff);
-+ out[2] = (byte)((i >> 8) & 0xff);
-+ out[3] = (byte)((i)&0xff);
++void put_u32(byte *out, uint32_t i)
++{
++ out[0] = (byte)((i >> 24) & 0xff);
++ out[1] = (byte)((i >> 16) & 0xff);
++ out[2] = (byte)((i >> 8) & 0xff);
++ out[3] = (byte)((i)&0xff);
+}
+
-+uint32_t get_u32(byte *in) {
-+ return (uint32_t)(in[0]) << 24 | (uint32_t)(in[1]) << 16 |
-+ (uint32_t)(in[2]) << 8 | (uint32_t)(in[3]);
++uint32_t get_u32(byte *in)
++{
++ return (uint32_t)(in[0]) << 24 | (uint32_t)(in[1]) << 16 |
++ (uint32_t)(in[2]) << 8 | (uint32_t)(in[3]);
+}
+
-+void put_u64(byte *out, uint64_t v) {
-+ for (int i = sizeof(uint64_t); i--;) {
-+ out[i] = (byte)(v & 0xff);
-+ v >>= 8;
-+ }
++void put_u64(byte *out, uint64_t v)
++{
++ int i = 0;
++ for (i = sizeof(uint64_t); i--;) {
++ out[i] = (byte)(v & 0xff);
++ v >>= 8;
++ }
+}
+
-+uint64_t get_u64(byte *out) {
-+ uint64_t v = 0;
-+ for (int i = 0; i < sizeof(uint64_t); i++) {
-+ v = (v << 8) | (byte)(out[i] & 0xff);
-+ }
-+ return v;
++uint64_t get_u64(byte *out)
++{
++ uint64_t v = 0;
++ int i = 0;
++ for (i = 0; i < sizeof(uint64_t); i++) {
++ v = (v << 8) | (byte)(out[i] & 0xff);
++ }
++ return v;
+}
+
-+void put_u16(byte *out, uint16_t i) {
-+ out[0] = (byte)((i >> 8) & 0xff);
-+ out[1] = (byte)((i)&0xff);
++void put_u16(byte *out, uint16_t i)
++{
++ out[0] = (byte)((i >> 8) & 0xff);
++ out[1] = (byte)((i)&0xff);
+}
+
-+uint16_t get_u16(byte *in) {
-+ return (uint32_t)(in[0]) << 8 | (uint32_t)(in[1]);
++uint16_t get_u16(byte *in)
++{
++ return (uint32_t)(in[0]) << 8 | (uint32_t)(in[1]);
+}
+
+/*
+ find smallest index i in [0, sz) at which f(i) is true, assuming
+ that f is ascending. Return sz if f(i) is false for all indices.
+*/
-+int binsearch(int sz, int (*f)(int k, void *args), void *args) {
-+ int lo = 0;
-+ int hi = sz;
-+
-+ /* invariant: (hi == sz) || f(hi) == true
-+ (lo == 0 && f(0) == true) || fi(lo) == false
-+ */
-+ while (hi - lo > 1) {
-+ int mid = lo + (hi - lo) / 2;
-+
-+ int val = f(mid, args);
-+ if (val) {
-+ hi = mid;
-+ } else {
-+ lo = mid;
-+ }
-+ }
-+
-+ if (lo == 0) {
-+ if (f(0, args)) {
-+ return 0;
-+ } else {
-+ return 1;
-+ }
-+ }
-+
-+ return hi;
-+}
-+
-+void free_names(char **a) {
-+ char **p = a;
-+ if (p == NULL) {
-+ return;
-+ }
-+ while (*p) {
-+ free(*p);
-+ p++;
-+ }
-+ free(a);
-+}
-+
-+int names_length(char **names) {
-+ int len = 0;
-+ for (char **p = names; *p; p++) {
-+ len++;
-+ }
-+ return len;
++int binsearch(int sz, int (*f)(int k, void *args), void *args)
++{
++ int lo = 0;
++ int hi = sz;
++
++ /* invariant: (hi == sz) || f(hi) == true
++ (lo == 0 && f(0) == true) || fi(lo) == false
++ */
++ while (hi - lo > 1) {
++ int mid = lo + (hi - lo) / 2;
++
++ int val = f(mid, args);
++ if (val) {
++ hi = mid;
++ } else {
++ lo = mid;
++ }
++ }
++
++ if (lo == 0) {
++ if (f(0, args)) {
++ return 0;
++ } else {
++ return 1;
++ }
++ }
++
++ return hi;
++}
++
++void free_names(char **a)
++{
++ char **p = a;
++ if (p == NULL) {
++ return;
++ }
++ while (*p) {
++ free(*p);
++ p++;
++ }
++ free(a);
++}
++
++int names_length(char **names)
++{
++ int len = 0;
++ for (char **p = names; *p; p++) {
++ len++;
++ }
++ return len;
+}
+
+/* parse a newline separated list of names. Empty names are discarded. */
-+void parse_names(char *buf, int size, char ***namesp) {
-+ char **names = NULL;
-+ int names_cap = 0;
-+ int names_len = 0;
-+
-+ char *p = buf;
-+ char *end = buf + size;
-+ while (p < end) {
-+ char *next = strchr(p, '\n');
-+ if (next != NULL) {
-+ *next = 0;
-+ } else {
-+ next = end;
-+ }
-+ if (p < next) {
-+ if (names_len == names_cap) {
-+ names_cap = 2 * names_cap + 1;
-+ names = realloc(names, names_cap * sizeof(char *));
-+ }
-+ names[names_len++] = strdup(p);
-+ }
-+ p = next + 1;
-+ }
-+
-+ if (names_len == names_cap) {
-+ names_cap = 2 * names_cap + 1;
-+ names = realloc(names, names_cap * sizeof(char *));
-+ }
-+
-+ names[names_len] = NULL;
-+ *namesp = names;
-+}
-+
-+int names_equal(char **a, char **b) {
-+ while (*a && *b) {
-+ if (0 != strcmp(*a, *b)) {
-+ return 0;
-+ }
-+
-+ a++;
-+ b++;
-+ }
-+
-+ return *a == *b;
-+}
-+
-+const char *error_str(int err) {
-+ switch (err) {
-+ case IO_ERROR:
-+ return "I/O error";
-+ case FORMAT_ERROR:
-+ return "FORMAT_ERROR";
-+ case NOT_EXIST_ERROR:
-+ return "NOT_EXIST_ERROR";
-+ case LOCK_ERROR:
-+ return "LOCK_ERROR";
-+ case API_ERROR:
-+ return "API_ERROR";
-+ case ZLIB_ERROR:
-+ return "ZLIB_ERROR";
-+ case -1:
-+ return "general error";
-+ default:
-+ return "unknown error code";
-+ }
++void parse_names(char *buf, int size, char ***namesp)
++{
++ char **names = NULL;
++ int names_cap = 0;
++ int names_len = 0;
++
++ char *p = buf;
++ char *end = buf + size;
++ while (p < end) {
++ char *next = strchr(p, '\n');
++ if (next != NULL) {
++ *next = 0;
++ } else {
++ next = end;
++ }
++ if (p < next) {
++ if (names_len == names_cap) {
++ names_cap = 2 * names_cap + 1;
++ names = realloc(names,
++ names_cap * sizeof(char *));
++ }
++ names[names_len++] = strdup(p);
++ }
++ p = next + 1;
++ }
++
++ if (names_len == names_cap) {
++ names_cap = 2 * names_cap + 1;
++ names = realloc(names, names_cap * sizeof(char *));
++ }
++
++ names[names_len] = NULL;
++ *namesp = names;
++}
++
++int names_equal(char **a, char **b)
++{
++ while (*a && *b) {
++ if (strcmp(*a, *b)) {
++ return 0;
++ }
++
++ a++;
++ b++;
++ }
++
++ return *a == *b;
++}
++
++const char *error_str(int err)
++{
++ switch (err) {
++ case IO_ERROR:
++ return "I/O error";
++ case FORMAT_ERROR:
++ return "FORMAT_ERROR";
++ case NOT_EXIST_ERROR:
++ return "NOT_EXIST_ERROR";
++ case LOCK_ERROR:
++ return "LOCK_ERROR";
++ case API_ERROR:
++ return "API_ERROR";
++ case ZLIB_ERROR:
++ return "ZLIB_ERROR";
++ case -1:
++ return "general error";
++ default:
++ return "unknown error code";
++ }
+}
diff --git a/reftable/basics.h b/reftable/basics.h
@@ -524,7 +321,7 @@
+#ifndef BASICS_H
+#define BASICS_H
+
-+#include <stdint.h>
++#include "system.h"
+
+#include "reftable.h"
+
@@ -567,10 +364,7 @@
+
+#include "block.h"
+
-+#include <assert.h>
-+#include <stdio.h>
-+#include <stdlib.h>
-+#include <string.h>
++#include "system.h"
+
+#include "blocksource.h"
+#include "constants.h"
@@ -579,365 +373,387 @@
+#include "zlib.h"
+
+int block_writer_register_restart(struct block_writer *w, int n, bool restart,
-+ struct slice key);
++ struct slice key);
+
+void block_writer_init(struct block_writer *bw, byte typ, byte *buf,
-+ uint32_t block_size, uint32_t header_off,
-+ int hash_size) {
-+ bw->buf = buf;
-+ bw->hash_size = hash_size;
-+ bw->block_size = block_size;
-+ bw->header_off = header_off;
-+ bw->buf[header_off] = typ;
-+ bw->next = header_off + 4;
-+ bw->restart_interval = 16;
-+ bw->entries = 0;
++ uint32_t block_size, uint32_t header_off, int hash_size)
++{
++ bw->buf = buf;
++ bw->hash_size = hash_size;
++ bw->block_size = block_size;
++ bw->header_off = header_off;
++ bw->buf[header_off] = typ;
++ bw->next = header_off + 4;
++ bw->restart_interval = 16;
++ bw->entries = 0;
+}
+
-+byte block_writer_type(struct block_writer *bw) {
-+ return bw->buf[bw->header_off];
++byte block_writer_type(struct block_writer *bw)
++{
++ return bw->buf[bw->header_off];
+}
+
+/* adds the record to the block. Returns -1 if it does not fit, 0 on
+ success */
-+int block_writer_add(struct block_writer *w, struct record rec) {
-+ struct slice empty = {};
-+ struct slice last =
-+ w->entries % w->restart_interval == 0 ? empty : w->last_key;
-+ struct slice out = {
-+ .buf = w->buf + w->next,
-+ .len = w->block_size - w->next,
-+ };
-+
-+ struct slice start = out;
-+
-+ bool restart = false;
-+ struct slice key = {};
-+ int n = 0;
-+
-+ record_key(rec, &key);
-+ n = encode_key(&restart, out, last, key, record_val_type(rec));
-+ if (n < 0) {
-+ goto err;
-+ }
-+ out.buf += n;
-+ out.len -= n;
-+
-+ n = record_encode(rec, out, w->hash_size);
-+ if (n < 0) {
-+ goto err;
-+ }
-+
-+ out.buf += n;
-+ out.len -= n;
-+
-+ if (block_writer_register_restart(w, start.len - out.len, restart, key) < 0) {
-+ goto err;
-+ }
-+
-+ free(slice_yield(&key));
-+ return 0;
++int block_writer_add(struct block_writer *w, struct record rec)
++{
++ struct slice empty = {};
++ struct slice last = w->entries % w->restart_interval == 0 ? empty :
++ w->last_key;
++ struct slice out = {
++ .buf = w->buf + w->next,
++ .len = w->block_size - w->next,
++ };
++
++ struct slice start = out;
++
++ bool restart = false;
++ struct slice key = {};
++ int n = 0;
++
++ record_key(rec, &key);
++ n = encode_key(&restart, out, last, key, record_val_type(rec));
++ if (n < 0) {
++ goto err;
++ }
++ out.buf += n;
++ out.len -= n;
++
++ n = record_encode(rec, out, w->hash_size);
++ if (n < 0) {
++ goto err;
++ }
++
++ out.buf += n;
++ out.len -= n;
++
++ if (block_writer_register_restart(w, start.len - out.len, restart,
++ key) < 0) {
++ goto err;
++ }
++
++ free(slice_yield(&key));
++ return 0;
+
+err:
-+ free(slice_yield(&key));
-+ return -1;
++ free(slice_yield(&key));
++ return -1;
+}
+
+int block_writer_register_restart(struct block_writer *w, int n, bool restart,
-+ struct slice key) {
-+ int rlen = w->restart_len;
-+ if (rlen >= MAX_RESTARTS) {
-+ restart = false;
-+ }
-+
-+ if (restart) {
-+ rlen++;
-+ }
-+ if (2 + 3 * rlen + n > w->block_size - w->next) {
-+ return -1;
-+ }
-+ if (restart) {
-+ if (w->restart_len == w->restart_cap) {
-+ w->restart_cap = w->restart_cap * 2 + 1;
-+ w->restarts = realloc(w->restarts, sizeof(uint32_t) * w->restart_cap);
-+ }
-+
-+ w->restarts[w->restart_len++] = w->next;
-+ }
-+
-+ w->next += n;
-+ slice_copy(&w->last_key, key);
-+ w->entries++;
-+ return 0;
-+}
-+
-+int block_writer_finish(struct block_writer *w) {
-+ for (int i = 0; i < w->restart_len; i++) {
-+ put_u24(w->buf + w->next, w->restarts[i]);
-+ w->next += 3;
-+ }
-+
-+ put_u16(w->buf + w->next, w->restart_len);
-+ w->next += 2;
-+ put_u24(w->buf + 1 + w->header_off, w->next);
-+
-+ if (block_writer_type(w) == BLOCK_TYPE_LOG) {
-+ int block_header_skip = 4 + w->header_off;
-+ struct slice compressed = {};
-+ uLongf dest_len = 0, src_len = 0;
-+ slice_resize(&compressed, w->next - block_header_skip);
-+
-+ dest_len = compressed.len;
-+ src_len = w->next - block_header_skip;
-+
-+ if (Z_OK != compress2(compressed.buf, &dest_len, w->buf + block_header_skip,
-+ src_len, 9)) {
-+ free(slice_yield(&compressed));
-+ return ZLIB_ERROR;
-+ }
-+ memcpy(w->buf + block_header_skip, compressed.buf, dest_len);
-+ w->next = dest_len + block_header_skip;
-+ }
-+ return w->next;
-+}
-+
-+byte block_reader_type(struct block_reader *r) {
-+ return r->block.data[r->header_off];
++ struct slice key)
++{
++ int rlen = w->restart_len;
++ if (rlen >= MAX_RESTARTS) {
++ restart = false;
++ }
++
++ if (restart) {
++ rlen++;
++ }
++ if (2 + 3 * rlen + n > w->block_size - w->next) {
++ return -1;
++ }
++ if (restart) {
++ if (w->restart_len == w->restart_cap) {
++ w->restart_cap = w->restart_cap * 2 + 1;
++ w->restarts = realloc(
++ w->restarts, sizeof(uint32_t) * w->restart_cap);
++ }
++
++ w->restarts[w->restart_len++] = w->next;
++ }
++
++ w->next += n;
++ slice_copy(&w->last_key, key);
++ w->entries++;
++ return 0;
++}
++
++int block_writer_finish(struct block_writer *w)
++{
++ int i = 0;
++ for (i = 0; i < w->restart_len; i++) {
++ put_u24(w->buf + w->next, w->restarts[i]);
++ w->next += 3;
++ }
++
++ put_u16(w->buf + w->next, w->restart_len);
++ w->next += 2;
++ put_u24(w->buf + 1 + w->header_off, w->next);
++
++ if (block_writer_type(w) == BLOCK_TYPE_LOG) {
++ int block_header_skip = 4 + w->header_off;
++ struct slice compressed = {};
++ uLongf dest_len = 0, src_len = 0;
++ slice_resize(&compressed, w->next - block_header_skip);
++
++ dest_len = compressed.len;
++ src_len = w->next - block_header_skip;
++
++ if (Z_OK != compress2(compressed.buf, &dest_len,
++ w->buf + block_header_skip, src_len, 9)) {
++ free(slice_yield(&compressed));
++ return ZLIB_ERROR;
++ }
++ memcpy(w->buf + block_header_skip, compressed.buf, dest_len);
++ w->next = dest_len + block_header_skip;
++ }
++ return w->next;
++}
++
++byte block_reader_type(struct block_reader *r)
++{
++ return r->block.data[r->header_off];
+}
+
+int block_reader_init(struct block_reader *br, struct block *block,
-+ uint32_t header_off, uint32_t table_block_size,
-+ int hash_size) {
-+ uint32_t full_block_size = table_block_size;
-+ byte typ = block->data[header_off];
-+ uint32_t sz = get_u24(block->data + header_off + 1);
-+
-+ if (!is_block_type(typ)) {
-+ return FORMAT_ERROR;
-+ }
-+
-+ if (typ == BLOCK_TYPE_LOG) {
-+ struct slice uncompressed = {};
-+ int block_header_skip = 4 + header_off;
-+ uLongf dst_len = sz - block_header_skip;
-+ uLongf src_len = block->len - block_header_skip;
-+
-+ slice_resize(&uncompressed, sz);
-+ memcpy(uncompressed.buf, block->data, block_header_skip);
-+
-+ if (Z_OK != uncompress2(uncompressed.buf + block_header_skip, &dst_len,
-+ block->data + block_header_skip, &src_len)) {
-+ free(slice_yield(&uncompressed));
-+ return ZLIB_ERROR;
-+ }
-+
-+ block_source_return_block(block->source, block);
-+ block->data = uncompressed.buf;
-+ block->len = dst_len; /* XXX: 4 bytes missing? */
-+ block->source = malloc_block_source();
-+ full_block_size = src_len + block_header_skip;
-+ } else if (full_block_size == 0) {
-+ full_block_size = sz;
-+ } else if (sz < full_block_size && sz < block->len && block->data[sz] != 0) {
-+ // If the block is smaller than the full block size,
-+ // it is padded (data followed by '\0') or the next
-+ // block is unaligned.
-+ full_block_size = sz;
-+ }
-+
-+ {
-+ uint16_t restart_count = get_u16(block->data + sz - 2);
-+ uint32_t restart_start = sz - 2 - 3 * restart_count;
-+
-+ byte *restart_bytes = block->data + restart_start;
-+
-+ // transfer ownership.
-+ br->block = *block;
-+ block->data = NULL;
-+ block->len = 0;
-+
-+ br->hash_size = hash_size;
-+ br->block_len = restart_start;
-+ br->full_block_size = full_block_size;
-+ br->header_off = header_off;
-+ br->restart_count = restart_count;
-+ br->restart_bytes = restart_bytes;
-+ }
-+
-+ return 0;
-+}
-+
-+static uint32_t block_reader_restart_offset(struct block_reader *br, int i) {
-+ return get_u24(br->restart_bytes + 3 * i);
-+}
-+
-+void block_reader_start(struct block_reader *br, struct block_iter *it) {
-+ it->br = br;
-+ slice_resize(&it->last_key, 0);
-+ it->next_off = br->header_off + 4;
++ uint32_t header_off, uint32_t table_block_size,
++ int hash_size)
++{
++ uint32_t full_block_size = table_block_size;
++ byte typ = block->data[header_off];
++ uint32_t sz = get_u24(block->data + header_off + 1);
++
++ if (!is_block_type(typ)) {
++ return FORMAT_ERROR;
++ }
++
++ if (typ == BLOCK_TYPE_LOG) {
++ struct slice uncompressed = {};
++ int block_header_skip = 4 + header_off;
++ uLongf dst_len = sz - block_header_skip;
++ uLongf src_len = block->len - block_header_skip;
++
++ slice_resize(&uncompressed, sz);
++ memcpy(uncompressed.buf, block->data, block_header_skip);
++
++ if (Z_OK !=
++ uncompress2(uncompressed.buf + block_header_skip, &dst_len,
++ block->data + block_header_skip, &src_len)) {
++ free(slice_yield(&uncompressed));
++ return ZLIB_ERROR;
++ }
++
++ block_source_return_block(block->source, block);
++ block->data = uncompressed.buf;
++ block->len = dst_len; /* XXX: 4 bytes missing? */
++ block->source = malloc_block_source();
++ full_block_size = src_len + block_header_skip;
++ } else if (full_block_size == 0) {
++ full_block_size = sz;
++ } else if (sz < full_block_size && sz < block->len &&
++ block->data[sz] != 0) {
++ /* If the block is smaller than the full block size, it is
++ padded (data followed by '\0') or the next block is
++ unaligned. */
++ full_block_size = sz;
++ }
++
++ {
++ uint16_t restart_count = get_u16(block->data + sz - 2);
++ uint32_t restart_start = sz - 2 - 3 * restart_count;
++
++ byte *restart_bytes = block->data + restart_start;
++
++ /* transfer ownership. */
++ br->block = *block;
++ block->data = NULL;
++ block->len = 0;
++
++ br->hash_size = hash_size;
++ br->block_len = restart_start;
++ br->full_block_size = full_block_size;
++ br->header_off = header_off;
++ br->restart_count = restart_count;
++ br->restart_bytes = restart_bytes;
++ }
++
++ return 0;
++}
++
++static uint32_t block_reader_restart_offset(struct block_reader *br, int i)
++{
++ return get_u24(br->restart_bytes + 3 * i);
++}
++
++void block_reader_start(struct block_reader *br, struct block_iter *it)
++{
++ it->br = br;
++ slice_resize(&it->last_key, 0);
++ it->next_off = br->header_off + 4;
+}
+
+struct restart_find_args {
-+ struct slice key;
-+ struct block_reader *r;
-+ int error;
++ struct slice key;
++ struct block_reader *r;
++ int error;
+};
+
-+static int restart_key_less(int idx, void *args) {
-+ struct restart_find_args *a = (struct restart_find_args *)args;
-+ uint32_t off = block_reader_restart_offset(a->r, idx);
-+ struct slice in = {
-+ .buf = a->r->block.data + off,
-+ .len = a->r->block_len - off,
-+ };
-+
-+ /* the restart key is verbatim in the block, so this could avoid the
-+ alloc for decoding the key */
-+ struct slice rkey = {};
-+ struct slice last_key = {};
-+ byte unused_extra;
-+ int n = decode_key(&rkey, &unused_extra, last_key, in);
-+ if (n < 0) {
-+ a->error = 1;
-+ return -1;
-+ }
-+
-+ {
-+ int result = slice_compare(a->key, rkey);
-+ free(slice_yield(&rkey));
-+ return result;
-+ }
-+}
-+
-+void block_iter_copy_from(struct block_iter *dest, struct block_iter *src) {
-+ dest->br = src->br;
-+ dest->next_off = src->next_off;
-+ slice_copy(&dest->last_key, src->last_key);
-+}
-+
-+// return < 0 for error, 0 for OK, > 0 for EOF.
-+int block_iter_next(struct block_iter *it, struct record rec) {
-+ if (it->next_off >= it->br->block_len) {
-+ return 1;
-+ }
-+
-+ {
-+ struct slice in = {
-+ .buf = it->br->block.data + it->next_off,
-+ .len = it->br->block_len - it->next_off,
-+ };
-+ struct slice start = in;
-+ struct slice key = {};
-+ byte extra;
-+ int n = decode_key(&key, &extra, it->last_key, in);
-+ if (n < 0) {
-+ return -1;
-+ }
-+
-+ in.buf += n;
-+ in.len -= n;
-+ n = record_decode(rec, key, extra, in, it->br->hash_size);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ in.buf += n;
-+ in.len -= n;
-+
-+ slice_copy(&it->last_key, key);
-+ it->next_off += start.len - in.len;
-+ free(slice_yield(&key));
-+ return 0;
-+ }
-+}
-+
-+int block_reader_first_key(struct block_reader *br, struct slice *key) {
-+ struct slice empty = {};
-+ int off = br->header_off + 4;
-+ struct slice in = {
-+ .buf = br->block.data + off,
-+ .len = br->block_len - off,
-+ };
-+
-+ byte extra = 0;
-+ int n = decode_key(key, &extra, empty, in);
-+ if (n < 0) {
-+ return n;
-+ }
-+ return 0;
-+}
-+
-+int block_iter_seek(struct block_iter *it, struct slice want) {
-+ return block_reader_seek(it->br, it, want);
-+}
-+
-+void block_iter_close(struct block_iter *it) {
-+ free(slice_yield(&it->last_key));
++static int restart_key_less(int idx, void *args)
++{
++ struct restart_find_args *a = (struct restart_find_args *)args;
++ uint32_t off = block_reader_restart_offset(a->r, idx);
++ struct slice in = {
++ .buf = a->r->block.data + off,
++ .len = a->r->block_len - off,
++ };
++
++ /* the restart key is verbatim in the block, so this could avoid the
++ alloc for decoding the key */
++ struct slice rkey = {};
++ struct slice last_key = {};
++ byte unused_extra;
++ int n = decode_key(&rkey, &unused_extra, last_key, in);
++ if (n < 0) {
++ a->error = 1;
++ return -1;
++ }
++
++ {
++ int result = slice_compare(a->key, rkey);
++ free(slice_yield(&rkey));
++ return result;
++ }
++}
++
++void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)
++{
++ dest->br = src->br;
++ dest->next_off = src->next_off;
++ slice_copy(&dest->last_key, src->last_key);
++}
++
++/* return < 0 for error, 0 for OK, > 0 for EOF. */
++int block_iter_next(struct block_iter *it, struct record rec)
++{
++ if (it->next_off >= it->br->block_len) {
++ return 1;
++ }
++
++ {
++ struct slice in = {
++ .buf = it->br->block.data + it->next_off,
++ .len = it->br->block_len - it->next_off,
++ };
++ struct slice start = in;
++ struct slice key = {};
++ byte extra;
++ int n = decode_key(&key, &extra, it->last_key, in);
++ if (n < 0) {
++ return -1;
++ }
++
++ in.buf += n;
++ in.len -= n;
++ n = record_decode(rec, key, extra, in, it->br->hash_size);
++ if (n < 0) {
++ return -1;
++ }
++ in.buf += n;
++ in.len -= n;
++
++ slice_copy(&it->last_key, key);
++ it->next_off += start.len - in.len;
++ free(slice_yield(&key));
++ return 0;
++ }
++}
++
++int block_reader_first_key(struct block_reader *br, struct slice *key)
++{
++ struct slice empty = {};
++ int off = br->header_off + 4;
++ struct slice in = {
++ .buf = br->block.data + off,
++ .len = br->block_len - off,
++ };
++
++ byte extra = 0;
++ int n = decode_key(key, &extra, empty, in);
++ if (n < 0) {
++ return n;
++ }
++ return 0;
++}
++
++int block_iter_seek(struct block_iter *it, struct slice want)
++{
++ return block_reader_seek(it->br, it, want);
++}
++
++void block_iter_close(struct block_iter *it)
++{
++ free(slice_yield(&it->last_key));
+}
+
+int block_reader_seek(struct block_reader *br, struct block_iter *it,
-+ struct slice want) {
-+ struct restart_find_args args = {
-+ .key = want,
-+ .r = br,
-+ };
-+
-+ int i = binsearch(br->restart_count, &restart_key_less, &args);
-+ if (args.error) {
-+ return -1;
-+ }
-+
-+ it->br = br;
-+ if (i > 0) {
-+ i--;
-+ it->next_off = block_reader_restart_offset(br, i);
-+ } else {
-+ it->next_off = br->header_off + 4;
-+ }
-+
-+ {
-+ struct record rec = new_record(block_reader_type(br));
-+ struct slice key = {};
-+ int result = 0;
-+ int err = 0;
-+ struct block_iter next = {};
-+ while (true) {
-+ block_iter_copy_from(&next, it);
-+
-+ err = block_iter_next(&next, rec);
-+ if (err < 0) {
-+ result = -1;
-+ goto exit;
-+ }
-+
-+ record_key(rec, &key);
-+ if (err > 0 || slice_compare(key, want) >= 0) {
-+ result = 0;
-+ goto exit;
-+ }
-+
-+ block_iter_copy_from(it, &next);
-+ }
-+
-+ exit:
-+ free(slice_yield(&key));
-+ free(slice_yield(&next.last_key));
-+ record_clear(rec);
-+ free(record_yield(&rec));
-+
-+ return result;
-+ }
-+}
-+
-+void block_writer_reset(struct block_writer *bw) {
-+ bw->restart_len = 0;
-+ bw->last_key.len = 0;
-+}
-+
-+void block_writer_clear(struct block_writer *bw) {
-+ free(bw->restarts);
-+ bw->restarts = NULL;
-+ free(slice_yield(&bw->last_key));
-+ // the block is not owned.
++ struct slice want)
++{
++ struct restart_find_args args = {
++ .key = want,
++ .r = br,
++ };
++
++ int i = binsearch(br->restart_count, &restart_key_less, &args);
++ if (args.error) {
++ return -1;
++ }
++
++ it->br = br;
++ if (i > 0) {
++ i--;
++ it->next_off = block_reader_restart_offset(br, i);
++ } else {
++ it->next_off = br->header_off + 4;
++ }
++
++ {
++ struct record rec = new_record(block_reader_type(br));
++ struct slice key = {};
++ int result = 0;
++ int err = 0;
++ struct block_iter next = {};
++ while (true) {
++ block_iter_copy_from(&next, it);
++
++ err = block_iter_next(&next, rec);
++ if (err < 0) {
++ result = -1;
++ goto exit;
++ }
++
++ record_key(rec, &key);
++ if (err > 0 || slice_compare(key, want) >= 0) {
++ result = 0;
++ goto exit;
++ }
++
++ block_iter_copy_from(it, &next);
++ }
++
++ exit:
++ free(slice_yield(&key));
++ free(slice_yield(&next.last_key));
++ record_clear(rec);
++ free(record_yield(&rec));
++
++ return result;
++ }
++}
++
++void block_writer_reset(struct block_writer *bw)
++{
++ bw->restart_len = 0;
++ bw->last_key.len = 0;
++}
++
++void block_writer_clear(struct block_writer *bw)
++{
++ free(bw->restarts);
++ bw->restarts = NULL;
++ free(slice_yield(&bw->last_key));
++ /* the block is not owned. */
+}
diff --git a/reftable/block.h b/reftable/block.h
@@ -961,22 +777,22 @@
+#include "reftable.h"
+
+struct block_writer {
-+ byte *buf;
-+ uint32_t block_size;
-+ uint32_t header_off;
-+ int restart_interval;
-+ int hash_size;
-+
-+ uint32_t next;
-+ uint32_t *restarts;
-+ uint32_t restart_len;
-+ uint32_t restart_cap;
-+ struct slice last_key;
-+ int entries;
++ byte *buf;
++ uint32_t block_size;
++ uint32_t header_off;
++ int restart_interval;
++ int hash_size;
++
++ uint32_t next;
++ uint32_t *restarts;
++ uint32_t restart_len;
++ uint32_t restart_cap;
++ struct slice last_key;
++ int entries;
+};
+
+void block_writer_init(struct block_writer *bw, byte typ, byte *buf,
-+ uint32_t block_size, uint32_t header_off, int hash_size);
++ uint32_t block_size, uint32_t header_off, int hash_size);
+byte block_writer_type(struct block_writer *bw);
+int block_writer_add(struct block_writer *w, struct record rec);
+int block_writer_finish(struct block_writer *w);
@@ -984,29 +800,29 @@
+void block_writer_clear(struct block_writer *bw);
+
+struct block_reader {
-+ uint32_t header_off;
-+ struct block block;
-+ int hash_size;
-+
-+ // size of the data, excluding restart data.
-+ uint32_t block_len;
-+ byte *restart_bytes;
-+ uint32_t full_block_size;
-+ uint16_t restart_count;
++ uint32_t header_off;
++ struct block block;
++ int hash_size;
++
++ /* size of the data, excluding restart data. */
++ uint32_t block_len;
++ byte *restart_bytes;
++ uint32_t full_block_size;
++ uint16_t restart_count;
+};
+
+struct block_iter {
-+ struct block_reader *br;
-+ struct slice last_key;
-+ uint32_t next_off;
++ struct block_reader *br;
++ struct slice last_key;
++ uint32_t next_off;
+};
+
+int block_reader_init(struct block_reader *br, struct block *bl,
-+ uint32_t header_off, uint32_t table_block_size,
-+ int hash_size);
++ uint32_t header_off, uint32_t table_block_size,
++ int hash_size);
+void block_reader_start(struct block_reader *br, struct block_iter *it);
+int block_reader_seek(struct block_reader *br, struct block_iter *it,
-+ struct slice want);
++ struct slice want);
+byte block_reader_type(struct block_reader *r);
+int block_reader_first_key(struct block_reader *br, struct slice *key);
+
@@ -1032,7 +848,7 @@
+
+#include "block.h"
+
-+#include <string.h>
++#include "system.h"
+
+#include "basics.h"
+#include "constants.h"
@@ -1041,131 +857,137 @@
+#include "test_framework.h"
+
+struct binsearch_args {
-+ int key;
-+ int *arr;
++ int key;
++ int *arr;
+};
+
-+static int binsearch_func(int i, void *void_args) {
-+ struct binsearch_args *args = (struct binsearch_args *)void_args;
-+
-+ return args->key < args->arr[i];
-+}
-+
-+void test_binsearch() {
-+ int arr[] = {2, 4, 6, 8, 10};
-+ int sz = ARRAYSIZE(arr);
-+ struct binsearch_args args = {
-+ .arr = arr,
-+ };
-+
-+ for (int i = 1; i < 11; i++) {
-+ args.key = i;
-+ int res = binsearch(sz, &binsearch_func, &args);
-+
-+ if (res < sz) {
-+ assert(args.key < arr[res]);
-+ if (res > 0) {
-+ assert(args.key >= arr[res - 1]);
-+ }
-+ } else {
-+ assert(args.key == 10 || args.key == 11);
-+ }
-+ }
-+}
-+
-+void test_block_read_write() {
-+ const int header_off = 21; // random
-+ const int N = 30;
-+ char *names[N];
-+ const int block_size = 1024;
-+ struct block block = {};
-+ block.data = calloc(block_size, 1);
-+ block.len = block_size;
-+
-+ struct block_writer bw = {};
-+ block_writer_init(&bw, BLOCK_TYPE_REF, block.data, block_size, header_off,
-+ SHA1_SIZE);
-+ struct ref_record ref = {};
-+ struct record rec = {};
-+ record_from_ref(&rec, &ref);
-+
-+ for (int i = 0; i < N; i++) {
-+ char name[100];
-+ sprintf(name, "branch%02d", i);
-+
-+ byte hash[SHA1_SIZE];
-+ memset(hash, i, sizeof(hash));
-+
-+ ref.ref_name = name;
-+ ref.value = hash;
-+ names[i] = strdup(name);
-+ int n = block_writer_add(&bw, rec);
-+ ref.ref_name = NULL;
-+ ref.value = NULL;
-+ assert(n == 0);
-+ }
-+
-+ int n = block_writer_finish(&bw);
-+ assert(n > 0);
-+
-+ block_writer_clear(&bw);
-+
-+ struct block_reader br = {};
-+ block_reader_init(&br, &block, header_off, block_size, SHA1_SIZE);
-+
-+ struct block_iter it = {};
-+ block_reader_start(&br, &it);
-+
-+ int j = 0;
-+ while (true) {
-+ int r = block_iter_next(&it, rec);
-+ assert(r >= 0);
-+ if (r > 0) {
-+ break;
-+ }
-+ assert_streq(names[j], ref.ref_name);
-+ j++;
-+ }
-+
-+ record_clear(rec);
-+ block_iter_close(&it);
-+
-+ struct slice want = {};
-+ for (int i = 0; i < N; i++) {
-+ slice_set_string(&want, names[i]);
-+
-+ struct block_iter it = {};
-+ int n = block_reader_seek(&br, &it, want);
-+ assert(n == 0);
-+
-+ n = block_iter_next(&it, rec);
-+ assert(n == 0);
-+
-+ assert_streq(names[i], ref.ref_name);
-+
-+ want.len--;
-+ n = block_reader_seek(&br, &it, want);
-+ assert(n == 0);
-+
-+ n = block_iter_next(&it, rec);
-+ assert(n == 0);
-+ assert_streq(names[10 * (i / 10)], ref.ref_name);
-+
-+ block_iter_close(&it);
-+ }
-+
-+ record_clear(rec);
-+ free(block.data);
-+ free(slice_yield(&want));
-+ for (int i = 0; i < N; i++) {
-+ free(names[i]);
-+ }
-+}
-+
-+int main() {
-+ add_test_case("binsearch", &test_binsearch);
-+ add_test_case("block_read_write", &test_block_read_write);
-+ test_main();
++static int binsearch_func(int i, void *void_args)
++{
++ struct binsearch_args *args = (struct binsearch_args *)void_args;
++
++ return args->key < args->arr[i];
++}
++
++void test_binsearch()
++{
++ int arr[] = { 2, 4, 6, 8, 10 };
++ int sz = ARRAYSIZE(arr);
++ struct binsearch_args args = {
++ .arr = arr,
++ };
++
++ int i = 0;
++ for (i = 1; i < 11; i++) {
++ args.key = i;
++ int res = binsearch(sz, &binsearch_func, &args);
++
++ if (res < sz) {
++ assert(args.key < arr[res]);
++ if (res > 0) {
++ assert(args.key >= arr[res - 1]);
++ }
++ } else {
++ assert(args.key == 10 || args.key == 11);
++ }
++ }
++}
++
++void test_block_read_write()
++{
++ const int header_off = 21; /* random */
++ const int N = 30;
++ char *names[N];
++ const int block_size = 1024;
++ struct block block = {};
++ block.data = calloc(block_size, 1);
++ block.len = block_size;
++
++ struct block_writer bw = {};
++ block_writer_init(&bw, BLOCK_TYPE_REF, block.data, block_size,
++ header_off, SHA1_SIZE);
++ struct ref_record ref = {};
++ struct record rec = {};
++ record_from_ref(&rec, &ref);
++
++ int i = 0;
++ for (i = 0; i < N; i++) {
++ char name[100];
++ snprintf(name, sizeof(name), "branch%02d", i);
++
++ byte hash[SHA1_SIZE];
++ memset(hash, i, sizeof(hash));
++
++ ref.ref_name = name;
++ ref.value = hash;
++ names[i] = strdup(name);
++ int n = block_writer_add(&bw, rec);
++ ref.ref_name = NULL;
++ ref.value = NULL;
++ assert(n == 0);
++ }
++
++ int n = block_writer_finish(&bw);
++ assert(n > 0);
++
++ block_writer_clear(&bw);
++
++ struct block_reader br = {};
++ block_reader_init(&br, &block, header_off, block_size, SHA1_SIZE);
++
++ struct block_iter it = {};
++ block_reader_start(&br, &it);
++
++ int j = 0;
++ while (true) {
++ int r = block_iter_next(&it, rec);
++ assert(r >= 0);
++ if (r > 0) {
++ break;
++ }
++ assert_streq(names[j], ref.ref_name);
++ j++;
++ }
++
++ record_clear(rec);
++ block_iter_close(&it);
++
++ struct slice want = {};
++ for (i = 0; i < N; i++) {
++ slice_set_string(&want, names[i]);
++
++ struct block_iter it = {};
++ int n = block_reader_seek(&br, &it, want);
++ assert(n == 0);
++
++ n = block_iter_next(&it, rec);
++ assert(n == 0);
++
++ assert_streq(names[i], ref.ref_name);
++
++ want.len--;
++ n = block_reader_seek(&br, &it, want);
++ assert(n == 0);
++
++ n = block_iter_next(&it, rec);
++ assert(n == 0);
++ assert_streq(names[10 * (i / 10)], ref.ref_name);
++
++ block_iter_close(&it);
++ }
++
++ record_clear(rec);
++ free(block.data);
++ free(slice_yield(&want));
++ for (i = 0; i < N; i++) {
++ free(names[i]);
++ }
++}
++
++int main()
++{
++ add_test_case("binsearch", &test_binsearch);
++ add_test_case("block_read_write", &test_block_read_write);
++ test_main();
+}
diff --git a/reftable/blocksource.h b/reftable/blocksource.h
@@ -1188,7 +1010,7 @@
+
+uint64_t block_source_size(struct block_source source);
+int block_source_read_block(struct block_source source, struct block *dest,
-+ uint64_t off, uint32_t size);
++ uint64_t off, uint32_t size);
+void block_source_return_block(struct block_source source, struct block *ret);
+void block_source_close(struct block_source source);
+
@@ -1197,6 +1019,13 @@
diff --git a/reftable/bytes.c b/reftable/bytes.c
new file mode 100644
+ diff --git a/reftable/config.h b/reftable/config.h
+ new file mode 100644
+ --- /dev/null
+ +++ b/reftable/config.h
+@@
++/* empty */
+
diff --git a/reftable/constants.h b/reftable/constants.h
new file mode 100644
--- /dev/null
@@ -1235,107 +1064,102 @@
--- /dev/null
+++ b/reftable/dump.c
@@
-+// Copyright 2020 Google Inc. All rights reserved.
-+//
-+// Licensed under the Apache License, Version 2.0 (the "License");
-+// you may not use this file except in compliance with the License.
-+// You may obtain a copy of the License at
-+//
-+// http://www.apache.org/licenses/LICENSE-2.0
-+//
-+// Unless required by applicable law or agreed to in writing, software
-+// distributed under the License is distributed on an "AS IS" BASIS,
-+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-+// See the License for the specific language governing permissions and
-+// limitations under the License.
++/*
++Copyright 2020 Google LLC
+
-+#include <stdio.h>
-+#include <string.h>
-+#include <unistd.h>
++Use of this source code is governed by a BSD-style
++license that can be found in the LICENSE file or at
++https://developers.google.com/open-source/licenses/bsd
++*/
++
++#include "system.h"
+
+#include "reftable.h"
+
-+static int dump_table(const char *tablename) {
-+ struct block_source src = {};
-+ int err = block_source_from_file(&src, tablename);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ struct reader *r = NULL;
-+ err = new_reader(&r, src, tablename);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ {
-+ struct iterator it = {};
-+ err = reader_seek_ref(r, &it, "");
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ struct ref_record ref = {};
-+ while (1) {
-+ err = iterator_next_ref(it, &ref);
-+ if (err > 0) {
-+ break;
-+ }
-+ if (err < 0) {
-+ return err;
-+ }
-+ ref_record_print(&ref, 20);
-+ }
-+ iterator_destroy(&it);
-+ ref_record_clear(&ref);
-+ }
-+
-+ {
-+ struct iterator it = {};
-+ err = reader_seek_log(r, &it, "");
-+ if (err < 0) {
-+ return err;
-+ }
-+ struct log_record log = {};
-+ while (1) {
-+ err = iterator_next_log(it, &log);
-+ if (err > 0) {
-+ break;
-+ }
-+ if (err < 0) {
-+ return err;
-+ }
-+ log_record_print(&log, 20);
-+ }
-+ iterator_destroy(&it);
-+ log_record_clear(&log);
-+ }
-+ return 0;
-+}
-+
-+int main(int argc, char *argv[]) {
-+ int opt;
-+ const char *table = NULL;
-+ while ((opt = getopt(argc, argv, "t:")) != -1) {
-+ switch (opt) {
-+ case 't':
-+ table = strdup(optarg);
-+ break;
-+ case '?':
-+ printf("usage: %s [-table tablefile]\n", argv[0]);
-+ return 2;
-+ break;
-+ }
-+ }
-+
-+ if (table != NULL) {
-+ int err = dump_table(table);
-+ if (err < 0) {
-+ fprintf(stderr, "%s: %s: %s\n", argv[0], table, error_str(err));
-+ return 1;
-+ }
-+ }
-+ return 0;
++static int dump_table(const char *tablename)
++{
++ struct block_source src = {};
++ int err = block_source_from_file(&src, tablename);
++ if (err < 0) {
++ return err;
++ }
++
++ struct reader *r = NULL;
++ err = new_reader(&r, src, tablename);
++ if (err < 0) {
++ return err;
++ }
++
++ {
++ struct iterator it = {};
++ err = reader_seek_ref(r, &it, "");
++ if (err < 0) {
++ return err;
++ }
++
++ struct ref_record ref = {};
++ while (1) {
++ err = iterator_next_ref(it, &ref);
++ if (err > 0) {
++ break;
++ }
++ if (err < 0) {
++ return err;
++ }
++ ref_record_print(&ref, 20);
++ }
++ iterator_destroy(&it);
++ ref_record_clear(&ref);
++ }
++
++ {
++ struct iterator it = {};
++ err = reader_seek_log(r, &it, "");
++ if (err < 0) {
++ return err;
++ }
++ struct log_record log = {};
++ while (1) {
++ err = iterator_next_log(it, &log);
++ if (err > 0) {
++ break;
++ }
++ if (err < 0) {
++ return err;
++ }
++ log_record_print(&log, 20);
++ }
++ iterator_destroy(&it);
++ log_record_clear(&log);
++ }
++ return 0;
++}
++
++int main(int argc, char *argv[])
++{
++ int opt;
++ const char *table = NULL;
++ while ((opt = getopt(argc, argv, "t:")) != -1) {
++ switch (opt) {
++ case 't':
++ table = strdup(optarg);
++ break;
++ case '?':
++ printf("usage: %s [-table tablefile]\n", argv[0]);
++ return 2;
++ break;
++ }
++ }
++
++ if (table != NULL) {
++ int err = dump_table(table);
++ if (err < 0) {
++ fprintf(stderr, "%s: %s: %s\n", argv[0], table,
++ error_str(err));
++ return 1;
++ }
++ }
++ return 0;
+}
diff --git a/reftable/file.c b/reftable/file.c
@@ -1351,15 +1175,7 @@
+https://developers.google.com/open-source/licenses/bsd
+*/
+
-+#include <assert.h>
-+#include <errno.h>
-+#include <fcntl.h>
-+#include <stdio.h>
-+#include <stdlib.h>
-+#include <string.h>
-+#include <sys/stat.h>
-+#include <sys/types.h>
-+#include <unistd.h>
++#include "system.h"
+
+#include "block.h"
+#include "iter.h"
@@ -1368,78 +1184,85 @@
+#include "tree.h"
+
+struct file_block_source {
-+ int fd;
-+ uint64_t size;
++ int fd;
++ uint64_t size;
+};
+
-+static uint64_t file_size(void *b) {
-+ return ((struct file_block_source *)b)->size;
++static uint64_t file_size(void *b)
++{
++ return ((struct file_block_source *)b)->size;
+}
+
-+static void file_return_block(void *b, struct block *dest) {
-+ memset(dest->data, 0xff, dest->len);
-+ free(dest->data);
++static void file_return_block(void *b, struct block *dest)
++{
++ memset(dest->data, 0xff, dest->len);
++ free(dest->data);
+}
+
-+static void file_close(void *b) {
-+ int fd = ((struct file_block_source *)b)->fd;
-+ if (fd > 0) {
-+ close(fd);
-+ ((struct file_block_source *)b)->fd = 0;
-+ }
++static void file_close(void *b)
++{
++ int fd = ((struct file_block_source *)b)->fd;
++ if (fd > 0) {
++ close(fd);
++ ((struct file_block_source *)b)->fd = 0;
++ }
+
-+ free(b);
++ free(b);
+}
+
+static int file_read_block(void *v, struct block *dest, uint64_t off,
-+ uint32_t size) {
-+ struct file_block_source *b = (struct file_block_source *)v;
-+ assert(off + size <= b->size);
-+ dest->data = malloc(size);
-+ if (pread(b->fd, dest->data, size, off) != size) {
-+ return -1;
-+ }
-+ dest->len = size;
-+ return size;
++ uint32_t size)
++{
++ struct file_block_source *b = (struct file_block_source *)v;
++ assert(off + size <= b->size);
++ dest->data = malloc(size);
++ if (pread(b->fd, dest->data, size, off) != size) {
++ return -1;
++ }
++ dest->len = size;
++ return size;
+}
+
+struct block_source_vtable file_vtable = {
-+ .size = &file_size,
-+ .read_block = &file_read_block,
-+ .return_block = &file_return_block,
-+ .close = &file_close,
++ .size = &file_size,
++ .read_block = &file_read_block,
++ .return_block = &file_return_block,
++ .close = &file_close,
+};
+
-+int block_source_from_file(struct block_source *bs, const char *name) {
-+ struct stat st = {};
-+ int err = 0;
-+ int fd = open(name, O_RDONLY);
-+ if (fd < 0) {
-+ if (errno == ENOENT) {
-+ return NOT_EXIST_ERROR;
-+ }
-+ return -1;
-+ }
-+
-+ err = fstat(fd, &st);
-+ if (err < 0) {
-+ return -1;
-+ }
-+
-+ {
-+ struct file_block_source *p = calloc(sizeof(struct file_block_source), 1);
-+ p->size = st.st_size;
-+ p->fd = fd;
-+
-+ bs->ops = &file_vtable;
-+ bs->arg = p;
-+ }
-+ return 0;
-+}
-+
-+int fd_writer(void *arg, byte *data, int sz) {
-+ int *fdp = (int *)arg;
-+ return write(*fdp, data, sz);
++int block_source_from_file(struct block_source *bs, const char *name)
++{
++ struct stat st = {};
++ int err = 0;
++ int fd = open(name, O_RDONLY);
++ if (fd < 0) {
++ if (errno == ENOENT) {
++ return NOT_EXIST_ERROR;
++ }
++ return -1;
++ }
++
++ err = fstat(fd, &st);
++ if (err < 0) {
++ return -1;
++ }
++
++ {
++ struct file_block_source *p =
++ calloc(sizeof(struct file_block_source), 1);
++ p->size = st.st_size;
++ p->fd = fd;
++
++ bs->ops = &file_vtable;
++ bs->arg = p;
++ }
++ return 0;
++}
++
++int fd_writer(void *arg, byte *data, int sz)
++{
++ int *fdp = (int *)arg;
++ return write(*fdp, data, sz);
+}
diff --git a/reftable/iter.c b/reftable/iter.c
@@ -1457,206 +1280,225 @@
+
+#include "iter.h"
+
-+#include <stdlib.h>
-+#include <string.h>
++#include "system.h"
+
+#include "block.h"
+#include "constants.h"
+#include "reader.h"
+#include "reftable.h"
+
-+bool iterator_is_null(struct iterator it) { return it.ops == NULL; }
++bool iterator_is_null(struct iterator it)
++{
++ return it.ops == NULL;
++}
+
-+static int empty_iterator_next(void *arg, struct record rec) { return 1; }
++static int empty_iterator_next(void *arg, struct record rec)
++{
++ return 1;
++}
+
-+static void empty_iterator_close(void *arg) {}
++static void empty_iterator_close(void *arg)
++{
++}
+
+struct iterator_vtable empty_vtable = {
-+ .next = &empty_iterator_next,
-+ .close = &empty_iterator_close,
++ .next = &empty_iterator_next,
++ .close = &empty_iterator_close,
+};
+
-+void iterator_set_empty(struct iterator *it) {
-+ it->iter_arg = NULL;
-+ it->ops = &empty_vtable;
++void iterator_set_empty(struct iterator *it)
++{
++ it->iter_arg = NULL;
++ it->ops = &empty_vtable;
+}
+
-+int iterator_next(struct iterator it, struct record rec) {
-+ return it.ops->next(it.iter_arg, rec);
++int iterator_next(struct iterator it, struct record rec)
++{
++ return it.ops->next(it.iter_arg, rec);
+}
+
-+void iterator_destroy(struct iterator *it) {
-+ if (it->ops == NULL) {
-+ return;
-+ }
-+ it->ops->close(it->iter_arg);
-+ it->ops = NULL;
-+ free(it->iter_arg);
-+ it->iter_arg = NULL;
++void iterator_destroy(struct iterator *it)
++{
++ if (it->ops == NULL) {
++ return;
++ }
++ it->ops->close(it->iter_arg);
++ it->ops = NULL;
++ free(it->iter_arg);
++ it->iter_arg = NULL;
+}
+
-+int iterator_next_ref(struct iterator it, struct ref_record *ref) {
-+ struct record rec = {};
-+ record_from_ref(&rec, ref);
-+ return iterator_next(it, rec);
++int iterator_next_ref(struct iterator it, struct ref_record *ref)
++{
++ struct record rec = {};
++ record_from_ref(&rec, ref);
++ return iterator_next(it, rec);
+}
+
-+int iterator_next_log(struct iterator it, struct log_record *log) {
-+ struct record rec = {};
-+ record_from_log(&rec, log);
-+ return iterator_next(it, rec);
++int iterator_next_log(struct iterator it, struct log_record *log)
++{
++ struct record rec = {};
++ record_from_log(&rec, log);
++ return iterator_next(it, rec);
+}
+
-+static void filtering_ref_iterator_close(void *iter_arg) {
-+ struct filtering_ref_iterator *fri =
-+ (struct filtering_ref_iterator *)iter_arg;
-+ free(slice_yield(&fri->oid));
-+ iterator_destroy(&fri->it);
++static void filtering_ref_iterator_close(void *iter_arg)
++{
++ struct filtering_ref_iterator *fri =
++ (struct filtering_ref_iterator *)iter_arg;
++ free(slice_yield(&fri->oid));
++ iterator_destroy(&fri->it);
+}
+
-+static int filtering_ref_iterator_next(void *iter_arg, struct record rec) {
-+ struct filtering_ref_iterator *fri =
-+ (struct filtering_ref_iterator *)iter_arg;
-+ struct ref_record *ref = (struct ref_record *)rec.data;
++static int filtering_ref_iterator_next(void *iter_arg, struct record rec)
++{
++ struct filtering_ref_iterator *fri =
++ (struct filtering_ref_iterator *)iter_arg;
++ struct ref_record *ref = (struct ref_record *)rec.data;
+
-+ while (true) {
-+ int err = iterator_next_ref(fri->it, ref);
-+ if (err != 0) {
-+ return err;
-+ }
++ while (true) {
++ int err = iterator_next_ref(fri->it, ref);
++ if (err != 0) {
++ return err;
++ }
+
-+ if (fri->double_check) {
-+ struct iterator it = {};
++ if (fri->double_check) {
++ struct iterator it = {};
+
-+ int err = reader_seek_ref(fri->r, &it, ref->ref_name);
-+ if (err == 0) {
-+ err = iterator_next_ref(it, ref);
-+ }
++ int err = reader_seek_ref(fri->r, &it, ref->ref_name);
++ if (err == 0) {
++ err = iterator_next_ref(it, ref);
++ }
+
-+ iterator_destroy(&it);
++ iterator_destroy(&it);
+
-+ if (err < 0) {
-+ return err;
-+ }
++ if (err < 0) {
++ return err;
++ }
+
-+ if (err > 0) {
-+ continue;
-+ }
-+ }
++ if (err > 0) {
++ continue;
++ }
++ }
+
-+ if ((ref->target_value != NULL &&
-+ 0 == memcmp(fri->oid.buf, ref->target_value, fri->oid.len)) ||
-+ (ref->value != NULL &&
-+ 0 == memcmp(fri->oid.buf, ref->value, fri->oid.len))) {
-+ return 0;
-+ }
-+ }
++ if ((ref->target_value != NULL &&
++ !memcmp(fri->oid.buf, ref->target_value, fri->oid.len)) ||
++ (ref->value != NULL &&
++ !memcmp(fri->oid.buf, ref->value, fri->oid.len))) {
++ return 0;
++ }
++ }
+}
+
+struct iterator_vtable filtering_ref_iterator_vtable = {
-+ .next = &filtering_ref_iterator_next,
-+ .close = &filtering_ref_iterator_close,
++ .next = &filtering_ref_iterator_next,
++ .close = &filtering_ref_iterator_close,
+};
+
+void iterator_from_filtering_ref_iterator(struct iterator *it,
-+ struct filtering_ref_iterator *fri) {
-+ it->iter_arg = fri;
-+ it->ops = &filtering_ref_iterator_vtable;
-+}
-+
-+static void indexed_table_ref_iter_close(void *p) {
-+ struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p;
-+ block_iter_close(&it->cur);
-+ reader_return_block(it->r, &it->block_reader.block);
-+ free(slice_yield(&it->oid));
-+}
-+
-+static int indexed_table_ref_iter_next_block(
-+ struct indexed_table_ref_iter *it) {
-+ if (it->offset_idx == it->offset_len) {
-+ it->finished = true;
-+ return 1;
-+ }
-+
-+ reader_return_block(it->r, &it->block_reader.block);
-+
-+ {
-+ uint64_t off = it->offsets[it->offset_idx++];
-+ int err =
-+ reader_init_block_reader(it->r, &it->block_reader, off, BLOCK_TYPE_REF);
-+ if (err < 0) {
-+ return err;
-+ }
-+ if (err > 0) {
-+ // indexed block does not exist.
-+ return FORMAT_ERROR;
-+ }
-+ }
-+ block_reader_start(&it->block_reader, &it->cur);
-+ return 0;
-+}
-+
-+static int indexed_table_ref_iter_next(void *p, struct record rec) {
-+ struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p;
-+ struct ref_record *ref = (struct ref_record *)rec.data;
-+
-+ while (true) {
-+ int err = block_iter_next(&it->cur, rec);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ if (err > 0) {
-+ err = indexed_table_ref_iter_next_block(it);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ if (it->finished) {
-+ return 1;
-+ }
-+ continue;
-+ }
-+
-+ if (0 == memcmp(it->oid.buf, ref->target_value, it->oid.len) ||
-+ 0 == memcmp(it->oid.buf, ref->value, it->oid.len)) {
-+ return 0;
-+ }
-+ }
++ struct filtering_ref_iterator *fri)
++{
++ it->iter_arg = fri;
++ it->ops = &filtering_ref_iterator_vtable;
++}
++
++static void indexed_table_ref_iter_close(void *p)
++{
++ struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p;
++ block_iter_close(&it->cur);
++ reader_return_block(it->r, &it->block_reader.block);
++ free(slice_yield(&it->oid));
++}
++
++static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)
++{
++ if (it->offset_idx == it->offset_len) {
++ it->finished = true;
++ return 1;
++ }
++
++ reader_return_block(it->r, &it->block_reader.block);
++
++ {
++ uint64_t off = it->offsets[it->offset_idx++];
++ int err = reader_init_block_reader(it->r, &it->block_reader,
++ off, BLOCK_TYPE_REF);
++ if (err < 0) {
++ return err;
++ }
++ if (err > 0) {
++ /* indexed block does not exist. */
++ return FORMAT_ERROR;
++ }
++ }
++ block_reader_start(&it->block_reader, &it->cur);
++ return 0;
++}
++
++static int indexed_table_ref_iter_next(void *p, struct record rec)
++{
++ struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p;
++ struct ref_record *ref = (struct ref_record *)rec.data;
++
++ while (true) {
++ int err = block_iter_next(&it->cur, rec);
++ if (err < 0) {
++ return err;
++ }
++
++ if (err > 0) {
++ err = indexed_table_ref_iter_next_block(it);
++ if (err < 0) {
++ return err;
++ }
++
++ if (it->finished) {
++ return 1;
++ }
++ continue;
++ }
++
++ if (!memcmp(it->oid.buf, ref->target_value, it->oid.len) ||
++ !memcmp(it->oid.buf, ref->value, it->oid.len)) {
++ return 0;
++ }
++ }
+}
+
+int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest,
-+ struct reader *r, byte *oid, int oid_len,
-+ uint64_t *offsets, int offset_len) {
-+ struct indexed_table_ref_iter *itr =
-+ calloc(sizeof(struct indexed_table_ref_iter), 1);
-+ int err = 0;
++ struct reader *r, byte *oid, int oid_len,
++ uint64_t *offsets, int offset_len)
++{
++ struct indexed_table_ref_iter *itr =
++ calloc(sizeof(struct indexed_table_ref_iter), 1);
++ int err = 0;
+
-+ itr->r = r;
-+ slice_resize(&itr->oid, oid_len);
-+ memcpy(itr->oid.buf, oid, oid_len);
++ itr->r = r;
++ slice_resize(&itr->oid, oid_len);
++ memcpy(itr->oid.buf, oid, oid_len);
+
-+ itr->offsets = offsets;
-+ itr->offset_len = offset_len;
++ itr->offsets = offsets;
++ itr->offset_len = offset_len;
+
-+ err = indexed_table_ref_iter_next_block(itr);
-+ if (err < 0) {
-+ free(itr);
-+ } else {
-+ *dest = itr;
-+ }
-+ return err;
++ err = indexed_table_ref_iter_next_block(itr);
++ if (err < 0) {
++ free(itr);
++ } else {
++ *dest = itr;
++ }
++ return err;
+}
+
+struct iterator_vtable indexed_table_ref_iter_vtable = {
-+ .next = &indexed_table_ref_iter_next,
-+ .close = &indexed_table_ref_iter_close,
++ .next = &indexed_table_ref_iter_next,
++ .close = &indexed_table_ref_iter_close,
+};
+
+void iterator_from_indexed_table_ref_iter(struct iterator *it,
-+ struct indexed_table_ref_iter *itr) {
-+ it->iter_arg = itr;
-+ it->ops = &indexed_table_ref_iter_vtable;
++ struct indexed_table_ref_iter *itr)
++{
++ it->iter_arg = itr;
++ it->ops = &indexed_table_ref_iter_vtable;
+}
diff --git a/reftable/iter.h b/reftable/iter.h
@@ -1680,8 +1522,8 @@
+#include "slice.h"
+
+struct iterator_vtable {
-+ int (*next)(void *iter_arg, struct record rec);
-+ void (*close)(void *iter_arg);
++ int (*next)(void *iter_arg, struct record rec);
++ void (*close)(void *iter_arg);
+};
+
+void iterator_set_empty(struct iterator *it);
@@ -1689,35 +1531,35 @@
+bool iterator_is_null(struct iterator it);
+
+struct filtering_ref_iterator {
-+ struct reader *r;
-+ struct slice oid;
-+ bool double_check;
-+ struct iterator it;
++ struct reader *r;
++ struct slice oid;
++ bool double_check;
++ struct iterator it;
+};
+
+void iterator_from_filtering_ref_iterator(struct iterator *,
-+ struct filtering_ref_iterator *);
++ struct filtering_ref_iterator *);
+
+struct indexed_table_ref_iter {
-+ struct reader *r;
-+ struct slice oid;
-+
-+ // mutable
-+ uint64_t *offsets;
-+
-+ // Points to the next offset to read.
-+ int offset_idx;
-+ int offset_len;
-+ struct block_reader block_reader;
-+ struct block_iter cur;
-+ bool finished;
++ struct reader *r;
++ struct slice oid;
++
++ /* mutable */
++ uint64_t *offsets;
++
++ /* Points to the next offset to read. */
++ int offset_idx;
++ int offset_len;
++ struct block_reader block_reader;
++ struct block_iter cur;
++ bool finished;
+};
+
+void iterator_from_indexed_table_ref_iter(struct iterator *it,
-+ struct indexed_table_ref_iter *itr);
++ struct indexed_table_ref_iter *itr);
+int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest,
-+ struct reader *r, byte *oid, int oid_len,
-+ uint64_t *offsets, int offset_len);
++ struct reader *r, byte *oid, int oid_len,
++ uint64_t *offsets, int offset_len);
+
+#endif
@@ -1736,257 +1578,283 @@
+
+#include "merged.h"
+
-+#include <stdlib.h>
++#include "system.h"
+
+#include "constants.h"
+#include "iter.h"
+#include "pq.h"
+#include "reader.h"
+
-+static int merged_iter_init(struct merged_iter *mi) {
-+ for (int i = 0; i < mi->stack_len; i++) {
-+ struct record rec = new_record(mi->typ);
-+ int err = iterator_next(mi->stack[i], rec);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ if (err > 0) {
-+ iterator_destroy(&mi->stack[i]);
-+ record_clear(rec);
-+ free(record_yield(&rec));
-+ } else {
-+ struct pq_entry e = {
-+ .rec = rec,
-+ .index = i,
-+ };
-+ merged_iter_pqueue_add(&mi->pq, e);
-+ }
-+ }
-+
-+ return 0;
-+}
-+
-+static void merged_iter_close(void *p) {
-+ struct merged_iter *mi = (struct merged_iter *)p;
-+ merged_iter_pqueue_clear(&mi->pq);
-+ for (int i = 0; i < mi->stack_len; i++) {
-+ iterator_destroy(&mi->stack[i]);
-+ }
-+ free(mi->stack);
-+}
-+
-+static int merged_iter_advance_subiter(struct merged_iter *mi, int idx) {
-+ if (iterator_is_null(mi->stack[idx])) {
-+ return 0;
-+ }
-+
-+ {
-+ struct record rec = new_record(mi->typ);
-+ struct pq_entry e = {
-+ .rec = rec,
-+ .index = idx,
-+ };
-+ int err = iterator_next(mi->stack[idx], rec);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ if (err > 0) {
-+ iterator_destroy(&mi->stack[idx]);
-+ record_clear(rec);
-+ free(record_yield(&rec));
-+ return 0;
-+ }
-+
-+ merged_iter_pqueue_add(&mi->pq, e);
-+ }
-+ return 0;
-+}
-+
-+static int merged_iter_next(struct merged_iter *mi, struct record rec) {
-+ struct slice entry_key = {};
-+ struct pq_entry entry = merged_iter_pqueue_remove(&mi->pq);
-+ int err = merged_iter_advance_subiter(mi, entry.index);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ record_key(entry.rec, &entry_key);
-+ while (!merged_iter_pqueue_is_empty(mi->pq)) {
-+ struct pq_entry top = merged_iter_pqueue_top(mi->pq);
-+ struct slice k = {};
-+ int err = 0, cmp = 0;
-+
-+ record_key(top.rec, &k);
-+
-+ cmp = slice_compare(k, entry_key);
-+ free(slice_yield(&k));
-+
-+ if (cmp > 0) {
-+ break;
-+ }
-+
-+ merged_iter_pqueue_remove(&mi->pq);
-+ err = merged_iter_advance_subiter(mi, top.index);
-+ if (err < 0) {
-+ return err;
-+ }
-+ record_clear(top.rec);
-+ free(record_yield(&top.rec));
-+ }
-+
-+ record_copy_from(rec, entry.rec, mi->hash_size);
-+ record_clear(entry.rec);
-+ free(record_yield(&entry.rec));
-+ free(slice_yield(&entry_key));
-+ return 0;
-+}
-+
-+static int merged_iter_next_void(void *p, struct record rec) {
-+ struct merged_iter *mi = (struct merged_iter *)p;
-+ if (merged_iter_pqueue_is_empty(mi->pq)) {
-+ return 1;
-+ }
-+
-+ return merged_iter_next(mi, rec);
++static int merged_iter_init(struct merged_iter *mi)
++{
++ int i = 0;
++ for (i = 0; i < mi->stack_len; i++) {
++ struct record rec = new_record(mi->typ);
++ int err = iterator_next(mi->stack[i], rec);
++ if (err < 0) {
++ return err;
++ }
++
++ if (err > 0) {
++ iterator_destroy(&mi->stack[i]);
++ record_clear(rec);
++ free(record_yield(&rec));
++ } else {
++ struct pq_entry e = {
++ .rec = rec,
++ .index = i,
++ };
++ merged_iter_pqueue_add(&mi->pq, e);
++ }
++ }
++
++ return 0;
++}
++
++static void merged_iter_close(void *p)
++{
++ struct merged_iter *mi = (struct merged_iter *)p;
++ int i = 0;
++ merged_iter_pqueue_clear(&mi->pq);
++ for (i = 0; i < mi->stack_len; i++) {
++ iterator_destroy(&mi->stack[i]);
++ }
++ free(mi->stack);
++}
++
++static int merged_iter_advance_subiter(struct merged_iter *mi, int idx)
++{
++ if (iterator_is_null(mi->stack[idx])) {
++ return 0;
++ }
++
++ {
++ struct record rec = new_record(mi->typ);
++ struct pq_entry e = {
++ .rec = rec,
++ .index = idx,
++ };
++ int err = iterator_next(mi->stack[idx], rec);
++ if (err < 0) {
++ return err;
++ }
++
++ if (err > 0) {
++ iterator_destroy(&mi->stack[idx]);
++ record_clear(rec);
++ free(record_yield(&rec));
++ return 0;
++ }
++
++ merged_iter_pqueue_add(&mi->pq, e);
++ }
++ return 0;
++}
++
++static int merged_iter_next(struct merged_iter *mi, struct record rec)
++{
++ struct slice entry_key = {};
++ struct pq_entry entry = merged_iter_pqueue_remove(&mi->pq);
++ int err = merged_iter_advance_subiter(mi, entry.index);
++ if (err < 0) {
++ return err;
++ }
++
++ record_key(entry.rec, &entry_key);
++ while (!merged_iter_pqueue_is_empty(mi->pq)) {
++ struct pq_entry top = merged_iter_pqueue_top(mi->pq);
++ struct slice k = {};
++ int err = 0, cmp = 0;
++
++ record_key(top.rec, &k);
++
++ cmp = slice_compare(k, entry_key);
++ free(slice_yield(&k));
++
++ if (cmp > 0) {
++ break;
++ }
++
++ merged_iter_pqueue_remove(&mi->pq);
++ err = merged_iter_advance_subiter(mi, top.index);
++ if (err < 0) {
++ return err;
++ }
++ record_clear(top.rec);
++ free(record_yield(&top.rec));
++ }
++
++ record_copy_from(rec, entry.rec, mi->hash_size);
++ record_clear(entry.rec);
++ free(record_yield(&entry.rec));
++ free(slice_yield(&entry_key));
++ return 0;
++}
++
++static int merged_iter_next_void(void *p, struct record rec)
++{
++ struct merged_iter *mi = (struct merged_iter *)p;
++ if (merged_iter_pqueue_is_empty(mi->pq)) {
++ return 1;
++ }
++
++ return merged_iter_next(mi, rec);
+}
+
+struct iterator_vtable merged_iter_vtable = {
-+ .next = &merged_iter_next_void,
-+ .close = &merged_iter_close,
++ .next = &merged_iter_next_void,
++ .close = &merged_iter_close,
+};
+
+static void iterator_from_merged_iter(struct iterator *it,
-+ struct merged_iter *mi) {
-+ it->iter_arg = mi;
-+ it->ops = &merged_iter_vtable;
-+}
-+
-+int new_merged_table(struct merged_table **dest, struct reader **stack, int n) {
-+ uint64_t last_max = 0;
-+ uint64_t first_min = 0;
-+ for (int i = 0; i < n; i++) {
-+ struct reader *r = stack[i];
-+ if (i > 0 && last_max >= reader_min_update_index(r)) {
-+ return FORMAT_ERROR;
-+ }
-+ if (i == 0) {
-+ first_min = reader_min_update_index(r);
-+ }
-+
-+ last_max = reader_max_update_index(r);
-+ }
-+
-+ {
-+ struct merged_table m = {
-+ .stack = stack,
-+ .stack_len = n,
-+ .min = first_min,
-+ .max = last_max,
-+ .hash_size = SHA1_SIZE,
-+ };
-+
-+ *dest = calloc(sizeof(struct merged_table), 1);
-+ **dest = m;
-+ }
-+ return 0;
-+}
-+
-+void merged_table_close(struct merged_table *mt) {
-+ for (int i = 0; i < mt->stack_len; i++) {
-+ reader_free(mt->stack[i]);
-+ }
-+ free(mt->stack);
-+ mt->stack = NULL;
-+ mt->stack_len = 0;
++ struct merged_iter *mi)
++{
++ it->iter_arg = mi;
++ it->ops = &merged_iter_vtable;
++}
++
++int new_merged_table(struct merged_table **dest, struct reader **stack, int n)
++{
++ uint64_t last_max = 0;
++ uint64_t first_min = 0;
++ int i = 0;
++ for (i = 0; i < n; i++) {
++ struct reader *r = stack[i];
++ if (i > 0 && last_max >= reader_min_update_index(r)) {
++ return FORMAT_ERROR;
++ }
++ if (i == 0) {
++ first_min = reader_min_update_index(r);
++ }
++
++ last_max = reader_max_update_index(r);
++ }
++
++ {
++ struct merged_table m = {
++ .stack = stack,
++ .stack_len = n,
++ .min = first_min,
++ .max = last_max,
++ .hash_size = SHA1_SIZE,
++ };
++
++ *dest = calloc(sizeof(struct merged_table), 1);
++ **dest = m;
++ }
++ return 0;
++}
++
++void merged_table_close(struct merged_table *mt)
++{
++ int i = 0;
++ for (i = 0; i < mt->stack_len; i++) {
++ reader_free(mt->stack[i]);
++ }
++ free(mt->stack);
++ mt->stack = NULL;
++ mt->stack_len = 0;
+}
+
+/* clears the list of subtable, without affecting the readers themselves. */
-+void merged_table_clear(struct merged_table *mt) {
-+ free(mt->stack);
-+ mt->stack = NULL;
-+ mt->stack_len = 0;
++void merged_table_clear(struct merged_table *mt)
++{
++ free(mt->stack);
++ mt->stack = NULL;
++ mt->stack_len = 0;
+}
+
-+void merged_table_free(struct merged_table *mt) {
-+ if (mt == NULL) {
-+ return;
-+ }
-+ merged_table_clear(mt);
-+ free(mt);
++void merged_table_free(struct merged_table *mt)
++{
++ if (mt == NULL) {
++ return;
++ }
++ merged_table_clear(mt);
++ free(mt);
+}
+
-+uint64_t merged_max_update_index(struct merged_table *mt) { return mt->max; }
++uint64_t merged_max_update_index(struct merged_table *mt)
++{
++ return mt->max;
++}
+
-+uint64_t merged_min_update_index(struct merged_table *mt) { return mt->min; }
++uint64_t merged_min_update_index(struct merged_table *mt)
++{
++ return mt->min;
++}
+
+static int merged_table_seek_record(struct merged_table *mt,
-+ struct iterator *it, struct record rec) {
-+ struct iterator *iters = calloc(sizeof(struct iterator), mt->stack_len);
-+ struct merged_iter merged = {
-+ .stack = iters,
-+ .typ = record_type(rec),
-+ .hash_size = mt->hash_size,
-+ };
-+ int n = 0;
-+ int err = 0;
-+ for (int i = 0; i < mt->stack_len && err == 0; i++) {
-+ int e = reader_seek(mt->stack[i], &iters[n], rec);
-+ if (e < 0) {
-+ err = e;
-+ }
-+ if (e == 0) {
-+ n++;
-+ }
-+ }
-+ if (err < 0) {
-+ for (int i = 0; i < n; i++) {
-+ iterator_destroy(&iters[i]);
-+ }
-+ free(iters);
-+ return err;
-+ }
-+
-+ merged.stack_len = n, err = merged_iter_init(&merged);
-+ if (err < 0) {
-+ merged_iter_close(&merged);
-+ return err;
-+ }
-+
-+ {
-+ struct merged_iter *p = malloc(sizeof(struct merged_iter));
-+ *p = merged;
-+ iterator_from_merged_iter(it, p);
-+ }
-+ return 0;
++ struct iterator *it, struct record rec)
++{
++ struct iterator *iters = calloc(sizeof(struct iterator), mt->stack_len);
++ struct merged_iter merged = {
++ .stack = iters,
++ .typ = record_type(rec),
++ .hash_size = mt->hash_size,
++ };
++ int n = 0;
++ int err = 0;
++ int i = 0;
++ for (i = 0; i < mt->stack_len && err == 0; i++) {
++ int e = reader_seek(mt->stack[i], &iters[n], rec);
++ if (e < 0) {
++ err = e;
++ }
++ if (e == 0) {
++ n++;
++ }
++ }
++ if (err < 0) {
++ int i = 0;
++ for (i = 0; i < n; i++) {
++ iterator_destroy(&iters[i]);
++ }
++ free(iters);
++ return err;
++ }
++
++ merged.stack_len = n, err = merged_iter_init(&merged);
++ if (err < 0) {
++ merged_iter_close(&merged);
++ return err;
++ }
++
++ {
++ struct merged_iter *p = malloc(sizeof(struct merged_iter));
++ *p = merged;
++ iterator_from_merged_iter(it, p);
++ }
++ return 0;
+}
+
+int merged_table_seek_ref(struct merged_table *mt, struct iterator *it,
-+ const char *name) {
-+ struct ref_record ref = {
-+ .ref_name = (char *)name,
-+ };
-+ struct record rec = {};
-+ record_from_ref(&rec, &ref);
-+ return merged_table_seek_record(mt, it, rec);
++ const char *name)
++{
++ struct ref_record ref = {
++ .ref_name = (char *)name,
++ };
++ struct record rec = {};
++ record_from_ref(&rec, &ref);
++ return merged_table_seek_record(mt, it, rec);
+}
+
+int merged_table_seek_log_at(struct merged_table *mt, struct iterator *it,
-+ const char *name, uint64_t update_index) {
-+ struct log_record log = {
-+ .ref_name = (char *)name,
-+ .update_index = update_index,
-+ };
-+ struct record rec = {};
-+ record_from_log(&rec, &log);
-+ return merged_table_seek_record(mt, it, rec);
++ const char *name, uint64_t update_index)
++{
++ struct log_record log = {
++ .ref_name = (char *)name,
++ .update_index = update_index,
++ };
++ struct record rec = {};
++ record_from_log(&rec, &log);
++ return merged_table_seek_record(mt, it, rec);
+}
+
+int merged_table_seek_log(struct merged_table *mt, struct iterator *it,
-+ const char *name) {
-+ uint64_t max = ~((uint64_t)0);
-+ return merged_table_seek_log_at(mt, it, name, max);
++ const char *name)
++{
++ uint64_t max = ~((uint64_t)0);
++ return merged_table_seek_log_at(mt, it, name, max);
+}
diff --git a/reftable/merged.h b/reftable/merged.h
@@ -2009,20 +1877,20 @@
+#include "reftable.h"
+
+struct merged_table {
-+ struct reader **stack;
-+ int stack_len;
-+ int hash_size;
++ struct reader **stack;
++ int stack_len;
++ int hash_size;
+
-+ uint64_t min;
-+ uint64_t max;
++ uint64_t min;
++ uint64_t max;
+};
+
+struct merged_iter {
-+ struct iterator *stack;
-+ int hash_size;
-+ int stack_len;
-+ byte typ;
-+ struct merged_iter_pqueue pq;
++ struct iterator *stack;
++ int hash_size;
++ int stack_len;
++ byte typ;
++ struct merged_iter_pqueue pq;
+} merged_iter;
+
+void merged_table_clear(struct merged_table *mt);
@@ -2044,7 +1912,7 @@
+
+#include "merged.h"
+
-+#include <string.h>
++#include "system.h"
+
+#include "basics.h"
+#include "block.h"
@@ -2055,231 +1923,242 @@
+#include "reftable.h"
+#include "test_framework.h"
+
-+void test_pq(void) {
-+ char *names[54] = {};
-+ int N = ARRAYSIZE(names) - 1;
-+
-+ for (int i = 0; i < N; i++) {
-+ char name[100];
-+ sprintf(name, "%02d", i);
-+ names[i] = strdup(name);
-+ }
-+
-+ struct merged_iter_pqueue pq = {};
-+
-+ int i = 1;
-+ do {
-+ struct record rec = new_record(BLOCK_TYPE_REF);
-+ record_as_ref(rec)->ref_name = names[i];
-+
-+ struct pq_entry e = {
-+ .rec = rec,
-+ };
-+ merged_iter_pqueue_add(&pq, e);
-+ merged_iter_pqueue_check(pq);
-+ i = (i * 7) % N;
-+ } while (i != 1);
-+
-+ const char *last = NULL;
-+ while (!merged_iter_pqueue_is_empty(pq)) {
-+ struct pq_entry e = merged_iter_pqueue_remove(&pq);
-+ merged_iter_pqueue_check(pq);
-+ struct ref_record *ref = record_as_ref(e.rec);
-+
-+ if (last != NULL) {
-+ assert(strcmp(last, ref->ref_name) < 0);
-+ }
-+ last = ref->ref_name;
-+ ref->ref_name = NULL;
-+ free(ref);
-+ }
-+
-+ for (int i = 0; i < N; i++) {
-+ free(names[i]);
-+ }
-+
-+ merged_iter_pqueue_clear(&pq);
-+}
-+
-+void write_test_table(struct slice *buf, struct ref_record refs[], int n) {
-+ int min = 0xffffffff;
-+ int max = 0;
-+ for (int i = 0; i < n; i++) {
-+ uint64_t ui = refs[i].update_index;
-+ if (ui > max) {
-+ max = ui;
-+ }
-+ if (ui < min) {
-+ min = ui;
-+ }
-+ }
-+
-+ struct write_options opts = {
-+ .block_size = 256,
-+ };
-+
-+ struct writer *w = new_writer(&slice_write_void, buf, &opts);
-+ writer_set_limits(w, min, max);
-+
-+ for (int i = 0; i < n; i++) {
-+ uint64_t before = refs[i].update_index;
-+ int n = writer_add_ref(w, &refs[i]);
-+ assert(n == 0);
-+ assert(before == refs[i].update_index);
-+ }
-+
-+ int err = writer_close(w);
-+ assert(err == 0);
-+
-+ writer_free(w);
-+ w = NULL;
++void test_pq(void)
++{
++ char *names[54] = {};
++ int N = ARRAYSIZE(names) - 1;
++
++ int i = 0;
++ for (i = 0; i < N; i++) {
++ char name[100];
++ snprintf(name, sizeof(name), "%02d", i);
++ names[i] = strdup(name);
++ }
++
++ struct merged_iter_pqueue pq = {};
++
++ i = 1;
++ do {
++ struct record rec = new_record(BLOCK_TYPE_REF);
++ record_as_ref(rec)->ref_name = names[i];
++
++ struct pq_entry e = {
++ .rec = rec,
++ };
++ merged_iter_pqueue_add(&pq, e);
++ merged_iter_pqueue_check(pq);
++ i = (i * 7) % N;
++ } while (i != 1);
++
++ const char *last = NULL;
++ while (!merged_iter_pqueue_is_empty(pq)) {
++ struct pq_entry e = merged_iter_pqueue_remove(&pq);
++ merged_iter_pqueue_check(pq);
++ struct ref_record *ref = record_as_ref(e.rec);
++
++ if (last != NULL) {
++ assert(strcmp(last, ref->ref_name) < 0);
++ }
++ last = ref->ref_name;
++ ref->ref_name = NULL;
++ free(ref);
++ }
++
++ for (i = 0; i < N; i++) {
++ free(names[i]);
++ }
++
++ merged_iter_pqueue_clear(&pq);
++}
++
++void write_test_table(struct slice *buf, struct ref_record refs[], int n)
++{
++ int min = 0xffffffff;
++ int max = 0;
++ int i = 0;
++ for (i = 0; i < n; i++) {
++ uint64_t ui = refs[i].update_index;
++ if (ui > max) {
++ max = ui;
++ }
++ if (ui < min) {
++ min = ui;
++ }
++ }
++
++ struct write_options opts = {
++ .block_size = 256,
++ };
++
++ struct writer *w = new_writer(&slice_write_void, buf, &opts);
++ writer_set_limits(w, min, max);
++
++ for (i = 0; i < n; i++) {
++ uint64_t before = refs[i].update_index;
++ int n = writer_add_ref(w, &refs[i]);
++ assert(n == 0);
++ assert(before == refs[i].update_index);
++ }
++
++ int err = writer_close(w);
++ assert(err == 0);
++
++ writer_free(w);
++ w = NULL;
+}
+
+static struct merged_table *merged_table_from_records(struct ref_record **refs,
-+ int *sizes,
-+ struct slice *buf,
-+ int n) {
-+ struct block_source *source = calloc(n, sizeof(*source));
-+ struct reader **rd = calloc(n, sizeof(*rd));
-+ for (int i = 0; i < n; i++) {
-+ write_test_table(&buf[i], refs[i], sizes[i]);
-+ block_source_from_slice(&source[i], &buf[i]);
-+
-+ int err = new_reader(&rd[i], source[i], "name");
-+ assert(err == 0);
-+ }
-+
-+ struct merged_table *mt = NULL;
-+ int err = new_merged_table(&mt, rd, n);
-+ assert(err == 0);
-+ return mt;
-+}
-+
-+void test_merged_between(void) {
-+ byte hash1[SHA1_SIZE];
-+ byte hash2[SHA1_SIZE];
-+
-+ set_test_hash(hash1, 1);
-+ set_test_hash(hash2, 2);
-+ struct ref_record r1[] = {{
-+ .ref_name = "b",
-+ .update_index = 1,
-+ .value = hash1,
-+ }};
-+ struct ref_record r2[] = {{
-+ .ref_name = "a",
-+ .update_index = 2,
-+ }};
-+
-+ struct ref_record *refs[] = {r1, r2};
-+ int sizes[] = {1, 1};
-+ struct slice bufs[2] = {};
-+ struct merged_table *mt = merged_table_from_records(refs, sizes, bufs, 2);
-+
-+ struct iterator it = {};
-+ int err = merged_table_seek_ref(mt, &it, "a");
-+ assert(err == 0);
-+
-+ struct ref_record ref = {};
-+ err = iterator_next_ref(it, &ref);
-+ assert_err(err);
-+ assert(ref.update_index == 2);
-+}
-+
-+void test_merged(void) {
-+ byte hash1[SHA1_SIZE];
-+ byte hash2[SHA1_SIZE];
-+
-+ set_test_hash(hash1, 1);
-+ set_test_hash(hash2, 2);
-+ struct ref_record r1[] = {{
-+ .ref_name = "a",
-+ .update_index = 1,
-+ .value = hash1,
-+ },
-+ {
-+ .ref_name = "b",
-+ .update_index = 1,
-+ .value = hash1,
-+ },
-+ {
-+ .ref_name = "c",
-+ .update_index = 1,
-+ .value = hash1,
-+ }};
-+ struct ref_record r2[] = {{
-+ .ref_name = "a",
-+ .update_index = 2,
-+ }};
-+ struct ref_record r3[] = {
-+ {
-+ .ref_name = "c",
-+ .update_index = 3,
-+ .value = hash2,
-+ },
-+ {
-+ .ref_name = "d",
-+ .update_index = 3,
-+ .value = hash1,
-+ },
-+ };
-+
-+ struct ref_record *refs[] = {r1, r2, r3};
-+ int sizes[3] = {3, 1, 2};
-+ struct slice bufs[3] = {};
-+
-+ struct merged_table *mt = merged_table_from_records(refs, sizes, bufs, 3);
-+
-+ struct iterator it = {};
-+ int err = merged_table_seek_ref(mt, &it, "a");
-+ assert(err == 0);
-+
-+ struct ref_record *out = NULL;
-+ int len = 0;
-+ int cap = 0;
-+ while (len < 100) { // cap loops/recursion.
-+ struct ref_record ref = {};
-+ int err = iterator_next_ref(it, &ref);
-+ if (err > 0) {
-+ break;
-+ }
-+ if (len == cap) {
-+ cap = 2 * cap + 1;
-+ out = realloc(out, sizeof(struct ref_record) * cap);
-+ }
-+ out[len++] = ref;
-+ }
-+ iterator_destroy(&it);
-+
-+ struct ref_record want[] = {
-+ r2[0],
-+ r1[1],
-+ r3[0],
-+ r3[1],
-+ };
-+ assert(ARRAYSIZE(want) == len);
-+ for (int i = 0; i < len; i++) {
-+ assert(ref_record_equal(&want[i], &out[i], SHA1_SIZE));
-+ }
-+ for (int i = 0; i < len; i++) {
-+ ref_record_clear(&out[i]);
-+ }
-+ free(out);
-+
-+ for (int i = 0; i < 3; i++) {
-+ free(slice_yield(&bufs[i]));
-+ }
-+ merged_table_close(mt);
-+ merged_table_free(mt);
-+}
-+
-+// XXX test refs_for(oid)
-+
-+int main() {
-+ add_test_case("test_merged_between", &test_merged_between);
-+ add_test_case("test_pq", &test_pq);
-+ add_test_case("test_merged", &test_merged);
-+ test_main();
++ int *sizes,
++ struct slice *buf, int n)
++{
++ struct block_source *source = calloc(n, sizeof(*source));
++ struct reader **rd = calloc(n, sizeof(*rd));
++ int i = 0;
++ for (i = 0; i < n; i++) {
++ write_test_table(&buf[i], refs[i], sizes[i]);
++ block_source_from_slice(&source[i], &buf[i]);
++
++ int err = new_reader(&rd[i], source[i], "name");
++ assert(err == 0);
++ }
++
++ struct merged_table *mt = NULL;
++ int err = new_merged_table(&mt, rd, n);
++ assert(err == 0);
++ return mt;
++}
++
++void test_merged_between(void)
++{
++ byte hash1[SHA1_SIZE];
++ byte hash2[SHA1_SIZE];
++
++ set_test_hash(hash1, 1);
++ set_test_hash(hash2, 2);
++ struct ref_record r1[] = { {
++ .ref_name = "b",
++ .update_index = 1,
++ .value = hash1,
++ } };
++ struct ref_record r2[] = { {
++ .ref_name = "a",
++ .update_index = 2,
++ } };
++
++ struct ref_record *refs[] = { r1, r2 };
++ int sizes[] = { 1, 1 };
++ struct slice bufs[2] = {};
++ struct merged_table *mt =
++ merged_table_from_records(refs, sizes, bufs, 2);
++
++ struct iterator it = {};
++ int err = merged_table_seek_ref(mt, &it, "a");
++ assert(err == 0);
++
++ struct ref_record ref = {};
++ err = iterator_next_ref(it, &ref);
++ assert_err(err);
++ assert(ref.update_index == 2);
++}
++
++void test_merged(void)
++{
++ byte hash1[SHA1_SIZE];
++ byte hash2[SHA1_SIZE];
++
++ set_test_hash(hash1, 1);
++ set_test_hash(hash2, 2);
++ struct ref_record r1[] = { {
++ .ref_name = "a",
++ .update_index = 1,
++ .value = hash1,
++ },
++ {
++ .ref_name = "b",
++ .update_index = 1,
++ .value = hash1,
++ },
++ {
++ .ref_name = "c",
++ .update_index = 1,
++ .value = hash1,
++ } };
++ struct ref_record r2[] = { {
++ .ref_name = "a",
++ .update_index = 2,
++ } };
++ struct ref_record r3[] = {
++ {
++ .ref_name = "c",
++ .update_index = 3,
++ .value = hash2,
++ },
++ {
++ .ref_name = "d",
++ .update_index = 3,
++ .value = hash1,
++ },
++ };
++
++ struct ref_record *refs[] = { r1, r2, r3 };
++ int sizes[3] = { 3, 1, 2 };
++ struct slice bufs[3] = {};
++
++ struct merged_table *mt =
++ merged_table_from_records(refs, sizes, bufs, 3);
++
++ struct iterator it = {};
++ int err = merged_table_seek_ref(mt, &it, "a");
++ assert(err == 0);
++
++ struct ref_record *out = NULL;
++ int len = 0;
++ int cap = 0;
++ while (len < 100) { /* cap loops/recursion. */
++ struct ref_record ref = {};
++ int err = iterator_next_ref(it, &ref);
++ if (err > 0) {
++ break;
++ }
++ if (len == cap) {
++ cap = 2 * cap + 1;
++ out = realloc(out, sizeof(struct ref_record) * cap);
++ }
++ out[len++] = ref;
++ }
++ iterator_destroy(&it);
++
++ struct ref_record want[] = {
++ r2[0],
++ r1[1],
++ r3[0],
++ r3[1],
++ };
++ assert(ARRAYSIZE(want) == len);
++ int i = 0;
++ for (i = 0; i < len; i++) {
++ assert(ref_record_equal(&want[i], &out[i], SHA1_SIZE));
++ }
++ for (i = 0; i < len; i++) {
++ ref_record_clear(&out[i]);
++ }
++ free(out);
++
++ for (i = 0; i < 3; i++) {
++ free(slice_yield(&bufs[i]));
++ }
++ merged_table_close(mt);
++ merged_table_free(mt);
++}
++
++/* XXX test refs_for(oid) */
++
++int main()
++{
++ add_test_case("test_merged_between", &test_merged_between);
++ add_test_case("test_pq", &test_pq);
++ add_test_case("test_merged", &test_merged);
++ test_main();
+}
diff --git a/reftable/pq.c b/reftable/pq.c
@@ -2297,111 +2176,119 @@
+
+#include "pq.h"
+
-+#include <assert.h>
-+#include <stdlib.h>
++#include "system.h"
+
-+int pq_less(struct pq_entry a, struct pq_entry b) {
-+ struct slice ak = {};
-+ struct slice bk = {};
-+ int cmp = 0;
-+ record_key(a.rec, &ak);
-+ record_key(b.rec, &bk);
++int pq_less(struct pq_entry a, struct pq_entry b)
++{
++ struct slice ak = {};
++ struct slice bk = {};
++ int cmp = 0;
++ record_key(a.rec, &ak);
++ record_key(b.rec, &bk);
+
-+ cmp = slice_compare(ak, bk);
++ cmp = slice_compare(ak, bk);
++
++ free(slice_yield(&ak));
++ free(slice_yield(&bk));
+
-+ free(slice_yield(&ak));
-+ free(slice_yield(&bk));
++ if (cmp == 0) {
++ return a.index > b.index;
++ }
+
-+ if (cmp == 0) {
-+ return a.index > b.index;
-+ }
-+
-+ return cmp < 0;
++ return cmp < 0;
+}
+
-+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq) {
-+ return pq.heap[0];
++struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)
++{
++ return pq.heap[0];
+}
+
-+bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq) {
-+ return pq.len == 0;
++bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)
++{
++ return pq.len == 0;
+}
+
-+void merged_iter_pqueue_check(struct merged_iter_pqueue pq) {
-+ for (int i = 1; i < pq.len; i++) {
-+ int parent = (i - 1) / 2;
++void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
++{
++ int i = 0;
++ for (i = 1; i < pq.len; i++) {
++ int parent = (i - 1) / 2;
+
-+ assert(pq_less(pq.heap[parent], pq.heap[i]));
-+ }
++ assert(pq_less(pq.heap[parent], pq.heap[i]));
++ }
+}
+
-+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) {
-+ int i = 0;
-+ struct pq_entry e = pq->heap[0];
-+ pq->heap[0] = pq->heap[pq->len - 1];
-+ pq->len--;
++struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
++{
++ int i = 0;
++ struct pq_entry e = pq->heap[0];
++ pq->heap[0] = pq->heap[pq->len - 1];
++ pq->len--;
+
-+ i = 0;
-+ while (i < pq->len) {
-+ int min = i;
-+ int j = 2 * i + 1;
-+ int k = 2 * i + 2;
-+ if (j < pq->len && pq_less(pq->heap[j], pq->heap[i])) {
-+ min = j;
-+ }
-+ if (k < pq->len && pq_less(pq->heap[k], pq->heap[min])) {
-+ min = k;
-+ }
++ i = 0;
++ while (i < pq->len) {
++ int min = i;
++ int j = 2 * i + 1;
++ int k = 2 * i + 2;
++ if (j < pq->len && pq_less(pq->heap[j], pq->heap[i])) {
++ min = j;
++ }
++ if (k < pq->len && pq_less(pq->heap[k], pq->heap[min])) {
++ min = k;
++ }
+
-+ if (min == i) {
-+ break;
-+ }
++ if (min == i) {
++ break;
++ }
+
-+ {
-+ struct pq_entry tmp = pq->heap[min];
-+ pq->heap[min] = pq->heap[i];
-+ pq->heap[i] = tmp;
-+ }
++ {
++ struct pq_entry tmp = pq->heap[min];
++ pq->heap[min] = pq->heap[i];
++ pq->heap[i] = tmp;
++ }
+
-+ i = min;
-+ }
++ i = min;
++ }
+
-+ return e;
++ return e;
+}
+
-+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e) {
-+ int i = 0;
-+ if (pq->len == pq->cap) {
-+ pq->cap = 2 * pq->cap + 1;
-+ pq->heap = realloc(pq->heap, pq->cap * sizeof(struct pq_entry));
-+ }
-+
-+ pq->heap[pq->len++] = e;
-+ i = pq->len - 1;
-+ while (i > 0) {
-+ int j = (i - 1) / 2;
-+ if (pq_less(pq->heap[j], pq->heap[i])) {
-+ break;
-+ }
++void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)
++{
++ int i = 0;
++ if (pq->len == pq->cap) {
++ pq->cap = 2 * pq->cap + 1;
++ pq->heap = realloc(pq->heap, pq->cap * sizeof(struct pq_entry));
++ }
+
-+ {
-+ struct pq_entry tmp = pq->heap[j];
-+ pq->heap[j] = pq->heap[i];
-+ pq->heap[i] = tmp;
-+ }
++ pq->heap[pq->len++] = e;
++ i = pq->len - 1;
++ while (i > 0) {
++ int j = (i - 1) / 2;
++ if (pq_less(pq->heap[j], pq->heap[i])) {
++ break;
++ }
+
-+ i = j;
-+ }
-+}
++ {
++ struct pq_entry tmp = pq->heap[j];
++ pq->heap[j] = pq->heap[i];
++ pq->heap[i] = tmp;
++ }
+
-+void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq) {
-+ for (int i = 0; i < pq->len; i++) {
-+ record_clear(pq->heap[i].rec);
-+ free(record_yield(&pq->heap[i].rec));
-+ }
-+ free(pq->heap);
-+ pq->heap = NULL;
-+ pq->len = pq->cap = 0;
++ i = j;
++ }
++}
++
++void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq)
++{
++ int i = 0;
++ for (i = 0; i < pq->len; i++) {
++ record_clear(pq->heap[i].rec);
++ free(record_yield(&pq->heap[i].rec));
++ }
++ free(pq->heap);
++ pq->heap = NULL;
++ pq->len = pq->cap = 0;
+}
diff --git a/reftable/pq.h b/reftable/pq.h
@@ -2423,16 +2310,16 @@
+#include "record.h"
+
+struct pq_entry {
-+ struct record rec;
-+ int index;
++ struct record rec;
++ int index;
+};
+
+int pq_less(struct pq_entry a, struct pq_entry b);
+
+struct merged_iter_pqueue {
-+ struct pq_entry *heap;
-+ int len;
-+ int cap;
++ struct pq_entry *heap;
++ int len;
++ int cap;
+};
+
+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
@@ -2459,10 +2346,7 @@
+
+#include "reader.h"
+
-+#include <stdio.h>
-+#include <stdlib.h>
-+#include <string.h>
-+#include <zlib.h>
++#include "system.h"
+
+#include "block.h"
+#include "constants.h"
@@ -2471,655 +2355,696 @@
+#include "reftable.h"
+#include "tree.h"
+
-+uint64_t block_source_size(struct block_source source) {
-+ return source.ops->size(source.arg);
++uint64_t block_source_size(struct block_source source)
++{
++ return source.ops->size(source.arg);
+}
+
+int block_source_read_block(struct block_source source, struct block *dest,
-+ uint64_t off, uint32_t size) {
-+ int result = source.ops->read_block(source.arg, dest, off, size);
-+ dest->source = source;
-+ return result;
++ uint64_t off, uint32_t size)
++{
++ int result = source.ops->read_block(source.arg, dest, off, size);
++ dest->source = source;
++ return result;
+}
+
-+void block_source_return_block(struct block_source source,
-+ struct block *blockp) {
-+ source.ops->return_block(source.arg, blockp);
-+ blockp->data = NULL;
-+ blockp->len = 0;
-+ blockp->source.ops = NULL;
-+ blockp->source.arg = NULL;
++void block_source_return_block(struct block_source source, struct block *blockp)
++{
++ source.ops->return_block(source.arg, blockp);
++ blockp->data = NULL;
++ blockp->len = 0;
++ blockp->source.ops = NULL;
++ blockp->source.arg = NULL;
+}
+
-+void block_source_close(struct block_source *source) {
-+ if (source->ops == NULL) {
-+ return;
-+ }
++void block_source_close(struct block_source *source)
++{
++ if (source->ops == NULL) {
++ return;
++ }
+
-+ source->ops->close(source->arg);
-+ source->ops = NULL;
++ source->ops->close(source->arg);
++ source->ops = NULL;
+}
+
-+static struct reader_offsets *reader_offsets_for(struct reader *r, byte typ) {
-+ switch (typ) {
-+ case BLOCK_TYPE_REF:
-+ return &r->ref_offsets;
-+ case BLOCK_TYPE_LOG:
-+ return &r->log_offsets;
-+ case BLOCK_TYPE_OBJ:
-+ return &r->obj_offsets;
-+ }
-+ abort();
++static struct reader_offsets *reader_offsets_for(struct reader *r, byte typ)
++{
++ switch (typ) {
++ case BLOCK_TYPE_REF:
++ return &r->ref_offsets;
++ case BLOCK_TYPE_LOG:
++ return &r->log_offsets;
++ case BLOCK_TYPE_OBJ:
++ return &r->obj_offsets;
++ }
++ abort();
+}
+
+static int reader_get_block(struct reader *r, struct block *dest, uint64_t off,
-+ uint32_t sz) {
-+ if (off >= r->size) {
-+ return 0;
-+ }
-+
-+ if (off + sz > r->size) {
-+ sz = r->size - off;
-+ }
-+
-+ return block_source_read_block(r->source, dest, off, sz);
-+}
-+
-+void reader_return_block(struct reader *r, struct block *p) {
-+ block_source_return_block(r->source, p);
-+}
-+
-+const char *reader_name(struct reader *r) { return r->name; }
-+
-+static int parse_footer(struct reader *r, byte *footer, byte *header) {
-+ byte *f = footer;
-+ int err = 0;
-+ if (memcmp(f, "REFT", 4)) {
-+ err = FORMAT_ERROR;
-+ goto exit;
-+ }
-+ f += 4;
-+
-+ if (0 != memcmp(footer, header, HEADER_SIZE)) {
-+ err = FORMAT_ERROR;
-+ goto exit;
-+ }
-+
-+ {
-+ byte version = *f++;
-+ if (version != 1) {
-+ err = FORMAT_ERROR;
-+ goto exit;
-+ }
-+ }
-+
-+ r->block_size = get_u24(f);
-+
-+ f += 3;
-+ r->min_update_index = get_u64(f);
-+ f += 8;
-+ r->max_update_index = get_u64(f);
-+ f += 8;
-+
-+ r->ref_offsets.index_offset = get_u64(f);
-+ f += 8;
-+
-+ r->obj_offsets.offset = get_u64(f);
-+ f += 8;
-+
-+ r->object_id_len = r->obj_offsets.offset & ((1 << 5) - 1);
-+ r->obj_offsets.offset >>= 5;
-+
-+ r->obj_offsets.index_offset = get_u64(f);
-+ f += 8;
-+ r->log_offsets.offset = get_u64(f);
-+ f += 8;
-+ r->log_offsets.index_offset = get_u64(f);
-+ f += 8;
-+
-+ {
-+ uint32_t computed_crc = crc32(0, footer, f - footer);
-+ uint32_t file_crc = get_u32(f);
-+ f += 4;
-+ if (computed_crc != file_crc) {
-+ err = FORMAT_ERROR;
-+ goto exit;
-+ }
-+ }
-+
-+ {
-+ byte first_block_typ = header[HEADER_SIZE];
-+ r->ref_offsets.present = (first_block_typ == BLOCK_TYPE_REF);
-+ r->ref_offsets.offset = 0;
-+ r->log_offsets.present =
-+ (first_block_typ == BLOCK_TYPE_LOG || r->log_offsets.offset > 0);
-+ r->obj_offsets.present = r->obj_offsets.offset > 0;
-+ }
-+ err = 0;
++ uint32_t sz)
++{
++ if (off >= r->size) {
++ return 0;
++ }
++
++ if (off + sz > r->size) {
++ sz = r->size - off;
++ }
++
++ return block_source_read_block(r->source, dest, off, sz);
++}
++
++void reader_return_block(struct reader *r, struct block *p)
++{
++ block_source_return_block(r->source, p);
++}
++
++const char *reader_name(struct reader *r)
++{
++ return r->name;
++}
++
++static int parse_footer(struct reader *r, byte *footer, byte *header)
++{
++ byte *f = footer;
++ int err = 0;
++ if (memcmp(f, "REFT", 4)) {
++ err = FORMAT_ERROR;
++ goto exit;
++ }
++ f += 4;
++
++ if (memcmp(footer, header, HEADER_SIZE)) {
++ err = FORMAT_ERROR;
++ goto exit;
++ }
++
++ {
++ byte version = *f++;
++ if (version != 1) {
++ err = FORMAT_ERROR;
++ goto exit;
++ }
++ }
++
++ r->block_size = get_u24(f);
++
++ f += 3;
++ r->min_update_index = get_u64(f);
++ f += 8;
++ r->max_update_index = get_u64(f);
++ f += 8;
++
++ r->ref_offsets.index_offset = get_u64(f);
++ f += 8;
++
++ r->obj_offsets.offset = get_u64(f);
++ f += 8;
++
++ r->object_id_len = r->obj_offsets.offset & ((1 << 5) - 1);
++ r->obj_offsets.offset >>= 5;
++
++ r->obj_offsets.index_offset = get_u64(f);
++ f += 8;
++ r->log_offsets.offset = get_u64(f);
++ f += 8;
++ r->log_offsets.index_offset = get_u64(f);
++ f += 8;
++
++ {
++ uint32_t computed_crc = crc32(0, footer, f - footer);
++ uint32_t file_crc = get_u32(f);
++ f += 4;
++ if (computed_crc != file_crc) {
++ err = FORMAT_ERROR;
++ goto exit;
++ }
++ }
++
++ {
++ byte first_block_typ = header[HEADER_SIZE];
++ r->ref_offsets.present = (first_block_typ == BLOCK_TYPE_REF);
++ r->ref_offsets.offset = 0;
++ r->log_offsets.present = (first_block_typ == BLOCK_TYPE_LOG ||
++ r->log_offsets.offset > 0);
++ r->obj_offsets.present = r->obj_offsets.offset > 0;
++ }
++ err = 0;
+exit:
-+ return err;
-+}
-+
-+int init_reader(struct reader *r, struct block_source source,
-+ const char *name) {
-+ struct block footer = {};
-+ struct block header = {};
-+ int err = 0;
-+
-+ memset(r, 0, sizeof(struct reader));
-+ r->size = block_source_size(source) - FOOTER_SIZE;
-+ r->source = source;
-+ r->name = strdup(name);
-+ r->hash_size = SHA1_SIZE;
-+
-+ err = block_source_read_block(source, &footer, r->size, FOOTER_SIZE);
-+ if (err != FOOTER_SIZE) {
-+ err = IO_ERROR;
-+ goto exit;
-+ }
-+
-+ // Need +1 to read type of first block.
-+ err = reader_get_block(r, &header, 0, HEADER_SIZE + 1);
-+ if (err != HEADER_SIZE + 1) {
-+ err = IO_ERROR;
-+ goto exit;
-+ }
-+
-+ err = parse_footer(r, footer.data, header.data);
++ return err;
++}
++
++int init_reader(struct reader *r, struct block_source source, const char *name)
++{
++ struct block footer = {};
++ struct block header = {};
++ int err = 0;
++
++ memset(r, 0, sizeof(struct reader));
++ r->size = block_source_size(source) - FOOTER_SIZE;
++ r->source = source;
++ r->name = strdup(name);
++ r->hash_size = SHA1_SIZE;
++
++ err = block_source_read_block(source, &footer, r->size, FOOTER_SIZE);
++ if (err != FOOTER_SIZE) {
++ err = IO_ERROR;
++ goto exit;
++ }
++
++ /* Need +1 to read type of first block. */
++ err = reader_get_block(r, &header, 0, HEADER_SIZE + 1);
++ if (err != HEADER_SIZE + 1) {
++ err = IO_ERROR;
++ goto exit;
++ }
++
++ err = parse_footer(r, footer.data, header.data);
+exit:
-+ block_source_return_block(r->source, &footer);
-+ block_source_return_block(r->source, &header);
-+ return err;
++ block_source_return_block(r->source, &footer);
++ block_source_return_block(r->source, &header);
++ return err;
+}
+
+struct table_iter {
-+ struct reader *r;
-+ byte typ;
-+ uint64_t block_off;
-+ struct block_iter bi;
-+ bool finished;
++ struct reader *r;
++ byte typ;
++ uint64_t block_off;
++ struct block_iter bi;
++ bool finished;
+};
+
+static void table_iter_copy_from(struct table_iter *dest,
-+ struct table_iter *src) {
-+ dest->r = src->r;
-+ dest->typ = src->typ;
-+ dest->block_off = src->block_off;
-+ dest->finished = src->finished;
-+ block_iter_copy_from(&dest->bi, &src->bi);
++ struct table_iter *src)
++{
++ dest->r = src->r;
++ dest->typ = src->typ;
++ dest->block_off = src->block_off;
++ dest->finished = src->finished;
++ block_iter_copy_from(&dest->bi, &src->bi);
+}
+
-+static int table_iter_next_in_block(struct table_iter *ti, struct record rec) {
-+ int res = block_iter_next(&ti->bi, rec);
-+ if (res == 0 && record_type(rec) == BLOCK_TYPE_REF) {
-+ ((struct ref_record *)rec.data)->update_index += ti->r->min_update_index;
-+ }
++static int table_iter_next_in_block(struct table_iter *ti, struct record rec)
++{
++ int res = block_iter_next(&ti->bi, rec);
++ if (res == 0 && record_type(rec) == BLOCK_TYPE_REF) {
++ ((struct ref_record *)rec.data)->update_index +=
++ ti->r->min_update_index;
++ }
+
-+ return res;
++ return res;
+}
+
-+static void table_iter_block_done(struct table_iter *ti) {
-+ if (ti->bi.br == NULL) {
-+ return;
-+ }
-+ reader_return_block(ti->r, &ti->bi.br->block);
-+ free(ti->bi.br);
-+ ti->bi.br = NULL;
++static void table_iter_block_done(struct table_iter *ti)
++{
++ if (ti->bi.br == NULL) {
++ return;
++ }
++ reader_return_block(ti->r, &ti->bi.br->block);
++ free(ti->bi.br);
++ ti->bi.br = NULL;
+
-+ ti->bi.last_key.len = 0;
-+ ti->bi.next_off = 0;
++ ti->bi.last_key.len = 0;
++ ti->bi.next_off = 0;
+}
+
-+static int32_t extract_block_size(byte *data, byte *typ, uint64_t off) {
-+ int32_t result = 0;
++static int32_t extract_block_size(byte *data, byte *typ, uint64_t off)
++{
++ int32_t result = 0;
+
-+ if (off == 0) {
-+ data += 24;
-+ }
++ if (off == 0) {
++ data += 24;
++ }
+
-+ *typ = data[0];
-+ if (is_block_type(*typ)) {
-+ result = get_u24(data + 1);
-+ }
-+ return result;
++ *typ = data[0];
++ if (is_block_type(*typ)) {
++ result = get_u24(data + 1);
++ }
++ return result;
+}
+
+int reader_init_block_reader(struct reader *r, struct block_reader *br,
-+ uint64_t next_off, byte want_typ) {
-+ int32_t guess_block_size = r->block_size ? r->block_size : DEFAULT_BLOCK_SIZE;
-+ struct block block = {};
-+ byte block_typ = 0;
-+ int err = 0;
-+ uint32_t header_off = next_off ? 0 : HEADER_SIZE;
-+ int32_t block_size = 0;
-+
-+ if (next_off >= r->size) {
-+ return 1;
-+ }
-+
-+ err = reader_get_block(r, &block, next_off, guess_block_size);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ block_size = extract_block_size(block.data, &block_typ, next_off);
-+ if (block_size < 0) {
-+ return block_size;
-+ }
-+
-+ if (want_typ != BLOCK_TYPE_ANY && block_typ != want_typ) {
-+ reader_return_block(r, &block);
-+ return 1;
-+ }
-+
-+ if (block_size > guess_block_size) {
-+ reader_return_block(r, &block);
-+ err = reader_get_block(r, &block, next_off, block_size);
-+ if (err < 0) {
-+ return err;
-+ }
-+ }
-+
-+ return block_reader_init(br, &block, header_off, r->block_size, r->hash_size);
++ uint64_t next_off, byte want_typ)
++{
++ int32_t guess_block_size = r->block_size ? r->block_size :
++ DEFAULT_BLOCK_SIZE;
++ struct block block = {};
++ byte block_typ = 0;
++ int err = 0;
++ uint32_t header_off = next_off ? 0 : HEADER_SIZE;
++ int32_t block_size = 0;
++
++ if (next_off >= r->size) {
++ return 1;
++ }
++
++ err = reader_get_block(r, &block, next_off, guess_block_size);
++ if (err < 0) {
++ return err;
++ }
++
++ block_size = extract_block_size(block.data, &block_typ, next_off);
++ if (block_size < 0) {
++ return block_size;
++ }
++
++ if (want_typ != BLOCK_TYPE_ANY && block_typ != want_typ) {
++ reader_return_block(r, &block);
++ return 1;
++ }
++
++ if (block_size > guess_block_size) {
++ reader_return_block(r, &block);
++ err = reader_get_block(r, &block, next_off, block_size);
++ if (err < 0) {
++ return err;
++ }
++ }
++
++ return block_reader_init(br, &block, header_off, r->block_size,
++ r->hash_size);
+}
+
+static int table_iter_next_block(struct table_iter *dest,
-+ struct table_iter *src) {
-+ uint64_t next_block_off = src->block_off + src->bi.br->full_block_size;
-+ struct block_reader br = {};
-+ int err = 0;
-+
-+ dest->r = src->r;
-+ dest->typ = src->typ;
-+ dest->block_off = next_block_off;
-+
-+ err = reader_init_block_reader(src->r, &br, next_block_off, src->typ);
-+ if (err > 0) {
-+ dest->finished = true;
-+ return 1;
-+ }
-+ if (err != 0) {
-+ return err;
-+ }
-+
-+ {
-+ struct block_reader *brp = malloc(sizeof(struct block_reader));
-+ *brp = br;
-+
-+ dest->finished = false;
-+ block_reader_start(brp, &dest->bi);
-+ }
-+ return 0;
-+}
-+
-+static int table_iter_next(struct table_iter *ti, struct record rec) {
-+ if (record_type(rec) != ti->typ) {
-+ return API_ERROR;
-+ }
-+
-+ while (true) {
-+ struct table_iter next = {};
-+ int err = 0;
-+ if (ti->finished) {
-+ return 1;
-+ }
-+
-+ err = table_iter_next_in_block(ti, rec);
-+ if (err <= 0) {
-+ return err;
-+ }
-+
-+ err = table_iter_next_block(&next, ti);
-+ if (err != 0) {
-+ ti->finished = true;
-+ }
-+ table_iter_block_done(ti);
-+ if (err != 0) {
-+ return err;
-+ }
-+ table_iter_copy_from(ti, &next);
-+ block_iter_close(&next.bi);
-+ }
-+}
-+
-+static int table_iter_next_void(void *ti, struct record rec) {
-+ return table_iter_next((struct table_iter *)ti, rec);
-+}
-+
-+static void table_iter_close(void *p) {
-+ struct table_iter *ti = (struct table_iter *)p;
-+ table_iter_block_done(ti);
-+ block_iter_close(&ti->bi);
++ struct table_iter *src)
++{
++ uint64_t next_block_off = src->block_off + src->bi.br->full_block_size;
++ struct block_reader br = {};
++ int err = 0;
++
++ dest->r = src->r;
++ dest->typ = src->typ;
++ dest->block_off = next_block_off;
++
++ err = reader_init_block_reader(src->r, &br, next_block_off, src->typ);
++ if (err > 0) {
++ dest->finished = true;
++ return 1;
++ }
++ if (err != 0) {
++ return err;
++ }
++
++ {
++ struct block_reader *brp = malloc(sizeof(struct block_reader));
++ *brp = br;
++
++ dest->finished = false;
++ block_reader_start(brp, &dest->bi);
++ }
++ return 0;
++}
++
++static int table_iter_next(struct table_iter *ti, struct record rec)
++{
++ if (record_type(rec) != ti->typ) {
++ return API_ERROR;
++ }
++
++ while (true) {
++ struct table_iter next = {};
++ int err = 0;
++ if (ti->finished) {
++ return 1;
++ }
++
++ err = table_iter_next_in_block(ti, rec);
++ if (err <= 0) {
++ return err;
++ }
++
++ err = table_iter_next_block(&next, ti);
++ if (err != 0) {
++ ti->finished = true;
++ }
++ table_iter_block_done(ti);
++ if (err != 0) {
++ return err;
++ }
++ table_iter_copy_from(ti, &next);
++ block_iter_close(&next.bi);
++ }
++}
++
++static int table_iter_next_void(void *ti, struct record rec)
++{
++ return table_iter_next((struct table_iter *)ti, rec);
++}
++
++static void table_iter_close(void *p)
++{
++ struct table_iter *ti = (struct table_iter *)p;
++ table_iter_block_done(ti);
++ block_iter_close(&ti->bi);
+}
+
+struct iterator_vtable table_iter_vtable = {
-+ .next = &table_iter_next_void,
-+ .close = &table_iter_close,
++ .next = &table_iter_next_void,
++ .close = &table_iter_close,
+};
+
-+static void iterator_from_table_iter(struct iterator *it,
-+ struct table_iter *ti) {
-+ it->iter_arg = ti;
-+ it->ops = &table_iter_vtable;
++static void iterator_from_table_iter(struct iterator *it, struct table_iter *ti)
++{
++ it->iter_arg = ti;
++ it->ops = &table_iter_vtable;
+}
+
+static int reader_table_iter_at(struct reader *r, struct table_iter *ti,
-+ uint64_t off, byte typ) {
-+ struct block_reader br = {};
-+ struct block_reader *brp = NULL;
++ uint64_t off, byte typ)
++{
++ struct block_reader br = {};
++ struct block_reader *brp = NULL;
+
-+ int err = reader_init_block_reader(r, &br, off, typ);
-+ if (err != 0) {
-+ return err;
-+ }
++ int err = reader_init_block_reader(r, &br, off, typ);
++ if (err != 0) {
++ return err;
++ }
+
-+ brp = malloc(sizeof(struct block_reader));
-+ *brp = br;
-+ ti->r = r;
-+ ti->typ = block_reader_type(brp);
-+ ti->block_off = off;
-+ block_reader_start(brp, &ti->bi);
-+ return 0;
++ brp = malloc(sizeof(struct block_reader));
++ *brp = br;
++ ti->r = r;
++ ti->typ = block_reader_type(brp);
++ ti->block_off = off;
++ block_reader_start(brp, &ti->bi);
++ return 0;
+}
+
+static int reader_start(struct reader *r, struct table_iter *ti, byte typ,
-+ bool index) {
-+ struct reader_offsets *offs = reader_offsets_for(r, typ);
-+ uint64_t off = offs->offset;
-+ if (index) {
-+ off = offs->index_offset;
-+ if (off == 0) {
-+ return 1;
-+ }
-+ typ = BLOCK_TYPE_INDEX;
-+ }
++ bool index)
++{
++ struct reader_offsets *offs = reader_offsets_for(r, typ);
++ uint64_t off = offs->offset;
++ if (index) {
++ off = offs->index_offset;
++ if (off == 0) {
++ return 1;
++ }
++ typ = BLOCK_TYPE_INDEX;
++ }
+
-+ return reader_table_iter_at(r, ti, off, typ);
++ return reader_table_iter_at(r, ti, off, typ);
+}
+
+static int reader_seek_linear(struct reader *r, struct table_iter *ti,
-+ struct record want) {
-+ struct record rec = new_record(record_type(want));
-+ struct slice want_key = {};
-+ struct slice got_key = {};
-+ struct table_iter next = {};
-+ int err = -1;
-+ record_key(want, &want_key);
-+
-+ while (true) {
-+ err = table_iter_next_block(&next, ti);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+
-+ if (err > 0) {
-+ break;
-+ }
-+
-+ err = block_reader_first_key(next.bi.br, &got_key);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+ {
-+ int cmp = slice_compare(got_key, want_key);
-+ if (cmp > 0) {
-+ table_iter_block_done(&next);
-+ break;
-+ }
-+ }
-+
-+ table_iter_block_done(ti);
-+ table_iter_copy_from(ti, &next);
-+ }
-+
-+ err = block_iter_seek(&ti->bi, want_key);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+ err = 0;
++ struct record want)
++{
++ struct record rec = new_record(record_type(want));
++ struct slice want_key = {};
++ struct slice got_key = {};
++ struct table_iter next = {};
++ int err = -1;
++ record_key(want, &want_key);
++
++ while (true) {
++ err = table_iter_next_block(&next, ti);
++ if (err < 0) {
++ goto exit;
++ }
++
++ if (err > 0) {
++ break;
++ }
++
++ err = block_reader_first_key(next.bi.br, &got_key);
++ if (err < 0) {
++ goto exit;
++ }
++ {
++ int cmp = slice_compare(got_key, want_key);
++ if (cmp > 0) {
++ table_iter_block_done(&next);
++ break;
++ }
++ }
++
++ table_iter_block_done(ti);
++ table_iter_copy_from(ti, &next);
++ }
++
++ err = block_iter_seek(&ti->bi, want_key);
++ if (err < 0) {
++ goto exit;
++ }
++ err = 0;
+
+exit:
-+ block_iter_close(&next.bi);
-+ record_clear(rec);
-+ free(record_yield(&rec));
-+ free(slice_yield(&want_key));
-+ free(slice_yield(&got_key));
-+ return err;
++ block_iter_close(&next.bi);
++ record_clear(rec);
++ free(record_yield(&rec));
++ free(slice_yield(&want_key));
++ free(slice_yield(&got_key));
++ return err;
+}
+
+static int reader_seek_indexed(struct reader *r, struct iterator *it,
-+ struct record rec) {
-+ struct index_record want_index = {};
-+ struct record want_index_rec = {};
-+ struct index_record index_result = {};
-+ struct record index_result_rec = {};
-+ struct table_iter index_iter = {};
-+ struct table_iter next = {};
-+ int err = 0;
-+
-+ record_key(rec, &want_index.last_key);
-+ record_from_index(&want_index_rec, &want_index);
-+ record_from_index(&index_result_rec, &index_result);
-+
-+ err = reader_start(r, &index_iter, record_type(rec), true);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+
-+ err = reader_seek_linear(r, &index_iter, want_index_rec);
-+ while (true) {
-+ err = table_iter_next(&index_iter, index_result_rec);
-+ table_iter_block_done(&index_iter);
-+ if (err != 0) {
-+ goto exit;
-+ }
-+
-+ err = reader_table_iter_at(r, &next, index_result.offset, 0);
-+ if (err != 0) {
-+ goto exit;
-+ }
-+
-+ err = block_iter_seek(&next.bi, want_index.last_key);
-+ if (err < 0) {
-+ goto exit;
-+ }
-+
-+ if (next.typ == record_type(rec)) {
-+ err = 0;
-+ break;
-+ }
-+
-+ if (next.typ != BLOCK_TYPE_INDEX) {
-+ err = FORMAT_ERROR;
-+ break;
-+ }
-+
-+ table_iter_copy_from(&index_iter, &next);
-+ }
-+
-+ if (err == 0) {
-+ struct table_iter *malloced = calloc(sizeof(struct table_iter), 1);
-+ table_iter_copy_from(malloced, &next);
-+ iterator_from_table_iter(it, malloced);
-+ }
++ struct record rec)
++{
++ struct index_record want_index = {};
++ struct record want_index_rec = {};
++ struct index_record index_result = {};
++ struct record index_result_rec = {};
++ struct table_iter index_iter = {};
++ struct table_iter next = {};
++ int err = 0;
++
++ record_key(rec, &want_index.last_key);
++ record_from_index(&want_index_rec, &want_index);
++ record_from_index(&index_result_rec, &index_result);
++
++ err = reader_start(r, &index_iter, record_type(rec), true);
++ if (err < 0) {
++ goto exit;
++ }
++
++ err = reader_seek_linear(r, &index_iter, want_index_rec);
++ while (true) {
++ err = table_iter_next(&index_iter, index_result_rec);
++ table_iter_block_done(&index_iter);
++ if (err != 0) {
++ goto exit;
++ }
++
++ err = reader_table_iter_at(r, &next, index_result.offset, 0);
++ if (err != 0) {
++ goto exit;
++ }
++
++ err = block_iter_seek(&next.bi, want_index.last_key);
++ if (err < 0) {
++ goto exit;
++ }
++
++ if (next.typ == record_type(rec)) {
++ err = 0;
++ break;
++ }
++
++ if (next.typ != BLOCK_TYPE_INDEX) {
++ err = FORMAT_ERROR;
++ break;
++ }
++
++ table_iter_copy_from(&index_iter, &next);
++ }
++
++ if (err == 0) {
++ struct table_iter *malloced =
++ calloc(sizeof(struct table_iter), 1);
++ table_iter_copy_from(malloced, &next);
++ iterator_from_table_iter(it, malloced);
++ }
+exit:
-+ block_iter_close(&next.bi);
-+ table_iter_close(&index_iter);
-+ record_clear(want_index_rec);
-+ record_clear(index_result_rec);
-+ return err;
++ block_iter_close(&next.bi);
++ table_iter_close(&index_iter);
++ record_clear(want_index_rec);
++ record_clear(index_result_rec);
++ return err;
+}
+
+static int reader_seek_internal(struct reader *r, struct iterator *it,
-+ struct record rec) {
-+ struct reader_offsets *offs = reader_offsets_for(r, record_type(rec));
-+ uint64_t idx = offs->index_offset;
-+ struct table_iter ti = {};
-+ int err = 0;
-+ if (idx > 0) {
-+ return reader_seek_indexed(r, it, rec);
-+ }
-+
-+ err = reader_start(r, &ti, record_type(rec), false);
-+ if (err < 0) {
-+ return err;
-+ }
-+ err = reader_seek_linear(r, &ti, rec);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ {
-+ struct table_iter *p = malloc(sizeof(struct table_iter));
-+ *p = ti;
-+ iterator_from_table_iter(it, p);
-+ }
-+
-+ return 0;
-+}
-+
-+int reader_seek(struct reader *r, struct iterator *it, struct record rec) {
-+ byte typ = record_type(rec);
-+
-+ struct reader_offsets *offs = reader_offsets_for(r, typ);
-+ if (!offs->present) {
-+ iterator_set_empty(it);
-+ return 0;
-+ }
-+
-+ return reader_seek_internal(r, it, rec);
-+}
-+
-+int reader_seek_ref(struct reader *r, struct iterator *it, const char *name) {
-+ struct ref_record ref = {
-+ .ref_name = (char *)name,
-+ };
-+ struct record rec = {};
-+ record_from_ref(&rec, &ref);
-+ return reader_seek(r, it, rec);
++ struct record rec)
++{
++ struct reader_offsets *offs = reader_offsets_for(r, record_type(rec));
++ uint64_t idx = offs->index_offset;
++ struct table_iter ti = {};
++ int err = 0;
++ if (idx > 0) {
++ return reader_seek_indexed(r, it, rec);
++ }
++
++ err = reader_start(r, &ti, record_type(rec), false);
++ if (err < 0) {
++ return err;
++ }
++ err = reader_seek_linear(r, &ti, rec);
++ if (err < 0) {
++ return err;
++ }
++
++ {
++ struct table_iter *p = malloc(sizeof(struct table_iter));
++ *p = ti;
++ iterator_from_table_iter(it, p);
++ }
++
++ return 0;
++}
++
++int reader_seek(struct reader *r, struct iterator *it, struct record rec)
++{
++ byte typ = record_type(rec);
++
++ struct reader_offsets *offs = reader_offsets_for(r, typ);
++ if (!offs->present) {
++ iterator_set_empty(it);
++ return 0;
++ }
++
++ return reader_seek_internal(r, it, rec);
++}
++
++int reader_seek_ref(struct reader *r, struct iterator *it, const char *name)
++{
++ struct ref_record ref = {
++ .ref_name = (char *)name,
++ };
++ struct record rec = {};
++ record_from_ref(&rec, &ref);
++ return reader_seek(r, it, rec);
+}
+
+int reader_seek_log_at(struct reader *r, struct iterator *it, const char *name,
-+ uint64_t update_index) {
-+ struct log_record log = {
-+ .ref_name = (char *)name,
-+ .update_index = update_index,
-+ };
-+ struct record rec = {};
-+ record_from_log(&rec, &log);
-+ return reader_seek(r, it, rec);
++ uint64_t update_index)
++{
++ struct log_record log = {
++ .ref_name = (char *)name,
++ .update_index = update_index,
++ };
++ struct record rec = {};
++ record_from_log(&rec, &log);
++ return reader_seek(r, it, rec);
+}
+
-+int reader_seek_log(struct reader *r, struct iterator *it, const char *name) {
-+ uint64_t max = ~((uint64_t)0);
-+ return reader_seek_log_at(r, it, name, max);
++int reader_seek_log(struct reader *r, struct iterator *it, const char *name)
++{
++ uint64_t max = ~((uint64_t)0);
++ return reader_seek_log_at(r, it, name, max);
+}
+
-+void reader_close(struct reader *r) {
-+ block_source_close(&r->source);
-+ free(r->name);
-+ r->name = NULL;
++void reader_close(struct reader *r)
++{
++ block_source_close(&r->source);
++ free(r->name);
++ r->name = NULL;
+}
+
-+int new_reader(struct reader **p, struct block_source src, char const *name) {
-+ struct reader *rd = calloc(sizeof(struct reader), 1);
-+ int err = init_reader(rd, src, name);
-+ if (err == 0) {
-+ *p = rd;
-+ } else {
-+ free(rd);
-+ }
-+ return err;
++int new_reader(struct reader **p, struct block_source src, char const *name)
++{
++ struct reader *rd = calloc(sizeof(struct reader), 1);
++ int err = init_reader(rd, src, name);
++ if (err == 0) {
++ *p = rd;
++ } else {
++ free(rd);
++ }
++ return err;
+}
+
-+void reader_free(struct reader *r) {
-+ reader_close(r);
-+ free(r);
++void reader_free(struct reader *r)
++{
++ reader_close(r);
++ free(r);
+}
+
+static int reader_refs_for_indexed(struct reader *r, struct iterator *it,
-+ byte *oid) {
-+ struct obj_record want = {
-+ .hash_prefix = oid,
-+ .hash_prefix_len = r->object_id_len,
-+ };
-+ struct record want_rec = {};
-+ struct iterator oit = {};
-+ struct obj_record got = {};
-+ struct record got_rec = {};
-+ int err = 0;
-+
-+ record_from_obj(&want_rec, &want);
-+
-+ err = reader_seek(r, &oit, want_rec);
-+ if (err != 0) {
-+ return err;
-+ }
-+
-+ record_from_obj(&got_rec, &got);
-+ err = iterator_next(oit, got_rec);
-+ iterator_destroy(&oit);
-+ if (err < 0) {
-+ return err;
-+ }
-+
-+ if (err > 0 || memcmp(want.hash_prefix, got.hash_prefix, r->object_id_len)) {
-+ iterator_set_empty(it);
-+ return 0;
-+ }
-+
-+ {
-+ struct indexed_table_ref_iter *itr = NULL;
-+ err = new_indexed_table_ref_iter(&itr, r, oid, r->hash_size, got.offsets,
-+ got.offset_len);
-+ if (err < 0) {
-+ record_clear(got_rec);
-+ return err;
-+ }
-+ got.offsets = NULL;
-+ record_clear(got_rec);
-+
-+ iterator_from_indexed_table_ref_iter(it, itr);
-+ }
-+
-+ return 0;
++ byte *oid)
++{
++ struct obj_record want = {
++ .hash_prefix = oid,
++ .hash_prefix_len = r->object_id_len,
++ };
++ struct record want_rec = {};
++ struct iterator oit = {};
++ struct obj_record got = {};
++ struct record got_rec = {};
++ int err = 0;
++
++ record_from_obj(&want_rec, &want);
++
++ err = reader_seek(r, &oit, want_rec);
++ if (err != 0) {
++ return err;
++ }
++
++ record_from_obj(&got_rec, &got);
++ err = iterator_next(oit, got_rec);
++ iterator_destroy(&oit);
++ if (err < 0) {
++ return err;
++ }
++
++ if (err > 0 ||
++ memcmp(want.hash_prefix, got.hash_prefix, r->object_id_len)) {
++ iterator_set_empty(it);
++ return 0;
++ }
++
++ {
++ struct indexed_table_ref_iter *itr = NULL;
++ err = new_indexed_table_ref_iter(&itr, r, oid, r->hash_size,
++ got.offsets, got.offset_len);
++ if (err < 0) {
++ record_clear(got_rec);
++ return err;
++ }
++ got.offsets = NULL;
++ record_clear(got_rec);
++
++ iterator_from_indexed_table_ref_iter(it, itr);
++ }
++
++ return 0;
+}
+
+static int reader_refs_for_unindexed(struct reader *r, struct iterator *it,
-+ byte *oid, int oid_len) {
-+ struct table_iter *ti = calloc(sizeof(struct table_iter), 1);
-+ struct filtering_ref_iterator *filter = NULL;
-+ int err = reader_start(r, ti, BLOCK_TYPE_REF, false);
-+ if (err < 0) {
-+ free(ti);
-+ return err;
-+ }
-+
-+ filter = calloc(sizeof(struct filtering_ref_iterator), 1);
-+ slice_resize(&filter->oid, oid_len);
-+ memcpy(filter->oid.buf, oid, oid_len);
-+ filter->r = r;
-+ filter->double_check = false;
-+ iterator_from_table_iter(&filter->it, ti);
-+
-+ iterator_from_filtering_ref_iterator(it, filter);
-+ return 0;
++ byte *oid, int oid_len)
++{
++ struct table_iter *ti = calloc(sizeof(struct table_iter), 1);
++ struct filtering_ref_iterator *filter = NULL;
++ int err = reader_start(r, ti, BLOCK_TYPE_REF, false);
++ if (err < 0) {
++ free(ti);
++ return err;
++ }
++
++ filter = calloc(sizeof(struct filtering_ref_iterator), 1);
++ slice_resize(&filter->oid, oid_len);
++ memcpy(filter->oid.buf, oid, oid_len);
++ filter->r = r;
++ filter->double_check = false;
++ iterator_from_table_iter(&filter->it, ti);
++
++ iterator_from_filtering_ref_iterator(it, filter);
++ return 0;
+}
+
+int reader_refs_for(struct reader *r, struct iterator *it, byte *oid,
-+ int oid_len) {
-+ if (r->obj_offsets.present) {
-+ return reader_refs_for_indexed(r, it, oid);
-+ }
-+ return reader_refs_for_unindexed(r, it, oid, oid_len);
++ int oid_len)
++{
++ if (r->obj_offsets.present) {
++ return reader_refs_for_indexed(r, it, oid);
++ }
++ return reader_refs_for_unindexed(r, it, oid, oid_len);
+}
+
-+uint64_t reader_max_update_index(struct reader *r) {
-+ return r->max_update_index;
++uint64_t reader_max_update_index(struct reader *r)
++{
++ return r->max_update_index;
+}
+
-+uint64_t reader_min_update_index(struct reader *r) {
-+ return r->min_update_index;
++uint64_t reader_min_update_index(struct reader *r)
++{
++ return r->min_update_index;
+}
diff --git a/reftable/reader.h b/reftable/reader.h
@@ -3145,29 +3070,29 @@
+uint64_t block_source_size(struct block_source source);
+
+int block_source_read_block(struct block_source source, struct block *dest,
-+ uint64_t off, uint32_t size);
++ uint64_t off, uint32_t size);
+void block_source_return_block(struct block_source source, struct block *ret);
+void block_source_close(struct block_source *source);
+
+struct reader_offsets {
-+ bool present;
-+ uint64_t offset;
-+ uint64_t index_offset;
++ bool present;
++ uint64_t offset;
++ uint64_t index_offset;
+};
+
+struct reader {
-+ struct block_source source;
-+ char *name;
-+ int hash_size;
-+ uint64_t size;
-+ uint32_t block_size;
-+ uint64_t min_update_index;
-+ uint64_t max_update_index;
-+ int object_id_len;
-+
-+ struct reader_offsets ref_offsets;
-+ struct reader_offsets obj_offsets;
-+ struct reader_offsets log_offsets;
++ struct block_source source;
++ char *name;
++ int hash_size;
++ uint64_t size;
++ uint32_t block_size;
++ uint64_t min_update_index;
++ uint64_t max_update_index;
++ int object_id_len;
++
++ struct reader_offsets ref_offsets;
++ struct reader_offsets obj_offsets;
++ struct reader_offsets log_offsets;
+};
+
+int init_reader(struct reader *r, struct block_source source, const char *name);
@@ -3176,7 +3101,7 @@
+const char *reader_name(struct reader *r);
+void reader_return_block(struct reader *r, struct block *p);
+int reader_init_block_reader(struct reader *r, struct block_reader *br,
-+ uint64_t next_off, byte want_typ);
++ uint64_t next_off, byte want_typ);
+
+#endif
@@ -3195,1025 +3120,1105 @@
+
+#include "record.h"
+
-+#include <assert.h>
-+#include <stdio.h>
-+#include <stdlib.h>
-+#include <string.h>
++#include "system.h"
+
+#include "constants.h"
+#include "reftable.h"
+
-+int is_block_type(byte typ) {
-+ switch (typ) {
-+ case BLOCK_TYPE_REF:
-+ case BLOCK_TYPE_LOG:
-+ case BLOCK_TYPE_OBJ:
-+ case BLOCK_TYPE_INDEX:
-+ return true;
-+ }
-+ return false;
-+}
-+
-+int get_var_int(uint64_t *dest, struct slice in) {
-+ int ptr = 0;
-+ uint64_t val;
-+
-+ if (in.len == 0) {
-+ return -1;
-+ }
-+ val = in.buf[ptr] & 0x7f;
-+
-+ while (in.buf[ptr] & 0x80) {
-+ ptr++;
-+ if (ptr > in.len) {
-+ return -1;
-+ }
-+ val = (val + 1) << 7 | (uint64_t)(in.buf[ptr] & 0x7f);
-+ }
-+
-+ *dest = val;
-+ return ptr + 1;
-+}
-+
-+int put_var_int(struct slice dest, uint64_t val) {
-+ byte buf[10] = {};
-+ int i = 9;
-+ buf[i] = (byte)(val & 0x7f);
-+ i--;
-+ while (true) {
-+ val >>= 7;
-+ if (!val) {
-+ break;
-+ }
-+ val--;
-+ buf[i] = 0x80 | (byte)(val & 0x7f);
-+ i--;
-+ }
-+
-+ {
-+ int n = sizeof(buf) - i - 1;
-+ if (dest.len < n) {
-+ return -1;
-+ }
-+ memcpy(dest.buf, &buf[i + 1], n);
-+ return n;
-+ }
-+}
-+
-+int common_prefix_size(struct slice a, struct slice b) {
-+ int p = 0;
-+ while (p < a.len && p < b.len) {
-+ if (a.buf[p] != b.buf[p]) {
-+ break;
-+ }
-+ p++;
-+ }
-+
-+ return p;
-+}
-+
-+static int decode_string(struct slice *dest, struct slice in) {
-+ int start_len = in.len;
-+ uint64_t tsize = 0;
-+ int n = get_var_int(&tsize, in);
-+ if (n <= 0) {
-+ return -1;
-+ }
-+ in.buf += n;
-+ in.len -= n;
-+ if (in.len < tsize) {
-+ return -1;
-+ }
-+
-+ slice_resize(dest, tsize + 1);
-+ dest->buf[tsize] = 0;
-+ memcpy(dest->buf, in.buf, tsize);
-+ in.buf += tsize;
-+ in.len -= tsize;
-+
-+ return start_len - in.len;
++int is_block_type(byte typ)
++{
++ switch (typ) {
++ case BLOCK_TYPE_REF:
++ case BLOCK_TYPE_LOG:
++ case BLOCK_TYPE_OBJ:
++ case BLOCK_TYPE_INDEX:
++ return true;
++ }
++ return false;
++}
++
++int get_var_int(uint64_t *dest, struct slice in)
++{
++ int ptr = 0;
++ uint64_t val;
++
++ if (in.len == 0) {
++ return -1;
++ }
++ val = in.buf[ptr] & 0x7f;
++
++ while (in.buf[ptr] & 0x80) {
++ ptr++;
++ if (ptr > in.len) {
++ return -1;
++ }
++ val = (val + 1) << 7 | (uint64_t)(in.buf[ptr] & 0x7f);
++ }
++
++ *dest = val;
++ return ptr + 1;
++}
++
++int put_var_int(struct slice dest, uint64_t val)
++{
++ byte buf[10] = {};
++ int i = 9;
++ buf[i] = (byte)(val & 0x7f);
++ i--;
++ while (true) {
++ val >>= 7;
++ if (!val) {
++ break;
++ }
++ val--;
++ buf[i] = 0x80 | (byte)(val & 0x7f);
++ i--;
++ }
++
++ {
++ int n = sizeof(buf) - i - 1;
++ if (dest.len < n) {
++ return -1;
++ }
++ memcpy(dest.buf, &buf[i + 1], n);
++ return n;
++ }
++}
++
++int common_prefix_size(struct slice a, struct slice b)
++{
++ int p = 0;
++ while (p < a.len && p < b.len) {
++ if (a.buf[p] != b.buf[p]) {
++ break;
++ }
++ p++;
++ }
++
++ return p;
++}
++
++static int decode_string(struct slice *dest, struct slice in)
++{
++ int start_len = in.len;
++ uint64_t tsize = 0;
++ int n = get_var_int(&tsize, in);
++ if (n <= 0) {
++ return -1;
++ }
++ in.buf += n;
++ in.len -= n;
++ if (in.len < tsize) {
++ return -1;
++ }
++
++ slice_resize(dest, tsize + 1);
++ dest->buf[tsize] = 0;
++ memcpy(dest->buf, in.buf, tsize);
++ in.buf += tsize;
++ in.len -= tsize;
++
++ return start_len - in.len;
+}
+
+int encode_key(bool *restart, struct slice dest, struct slice prev_key,
-+ struct slice key, byte extra) {
-+ struct slice start = dest;
-+ int prefix_len = common_prefix_size(prev_key, key);
-+ uint64_t suffix_len = key.len - prefix_len;
-+ int n = put_var_int(dest, (uint64_t)prefix_len);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ dest.buf += n;
-+ dest.len -= n;
-+
-+ *restart = (prefix_len == 0);
-+
-+ n = put_var_int(dest, suffix_len << 3 | (uint64_t)extra);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ dest.buf += n;
-+ dest.len -= n;
-+
-+ if (dest.len < suffix_len) {
-+ return -1;
-+ }
-+ memcpy(dest.buf, key.buf + prefix_len, suffix_len);
-+ dest.buf += suffix_len;
-+ dest.len -= suffix_len;
-+
-+ return start.len - dest.len;
-+}
-+
-+static byte ref_record_type(void) { return BLOCK_TYPE_REF; }
-+
-+static void ref_record_key(const void *r, struct slice *dest) {
-+ const struct ref_record *rec = (const struct ref_record *)r;
-+ slice_set_string(dest, rec->ref_name);
-+}
-+
-+static void ref_record_copy_from(void *rec, const void *src_rec,
-+ int hash_size) {
-+ struct ref_record *ref = (struct ref_record *)rec;
-+ struct ref_record *src = (struct ref_record *)src_rec;
-+ assert(hash_size > 0);
-+
-+ // This is simple and correct, but we could probably reuse the hash fields.
-+ ref_record_clear(ref);
-+ if (src->ref_name != NULL) {
-+ ref->ref_name = strdup(src->ref_name);
-+ }
-+
-+ if (src->target != NULL) {
-+ ref->target = strdup(src->target);
-+ }
-+
-+ if (src->target_value != NULL) {
-+ ref->target_value = malloc(hash_size);
-+ memcpy(ref->target_value, src->target_value, hash_size);
-+ }
-+
-+ if (src->value != NULL) {
-+ ref->value = malloc(hash_size);
-+ memcpy(ref->value, src->value, hash_size);
-+ }
-+ ref->update_index = src->update_index;
-+}
-+
-+static char hexdigit(int c) {
-+ if (c <= 9) {
-+ return '0' + c;
-+ }
-+ return 'a' + (c - 10);
-+}
-+
-+static void hex_format(char *dest, byte *src, int hash_size) {
-+ assert(hash_size > 0);
-+ if (src != NULL) {
-+ for (int i = 0; i < hash_size; i++) {
-+ dest[2 * i] = hexdigit(src[i] >> 4);
-+ dest[2 * i + 1] = hexdigit(src[i] & 0xf);
-+ }
-+ dest[2 * hash_size] = 0;
-+ }
-+}
-+
-+void ref_record_print(struct ref_record *ref, int hash_size) {
-+ char hex[SHA256_SIZE + 1] = {};
-+
-+ printf("ref{%s(%ld) ", ref->ref_name, ref->update_index);
-+ if (ref->value != NULL) {
-+ hex_format(hex, ref->value, hash_size);
-+ printf("%s", hex);
-+ }
-+ if (ref->target_value != NULL) {
-+ hex_format(hex, ref->target_value, hash_size);
-+ printf(" (T %s)", hex);
-+ }
-+ if (ref->target != NULL) {
-+ printf("=> %s", ref->target);
-+ }
-+ printf("}\n");
-+}
-+
-+static void ref_record_clear_void(void *rec) {
-+ ref_record_clear((struct ref_record *)rec);
-+}
-+
-+void ref_record_clear(struct ref_record *ref) {
-+ free(ref->ref_name);
-+ free(ref->target);
-+ free(ref->target_value);
-+ free(ref->value);
-+ memset(ref, 0, sizeof(struct ref_record));
-+}
-+
-+static byte ref_record_val_type(const void *rec) {
-+ const struct ref_record *r = (const struct ref_record *)rec;
-+ if (r->value != NULL) {
-+ if (r->target_value != NULL) {
-+ return 2;
-+ } else {
-+ return 1;
-+ }
-+ } else if (r->target != NULL) {
-+ return 3;
-+ }
-+ return 0;
-+}
-+
-+static int encode_string(char *str, struct slice s) {
-+ struct slice start = s;
-+ int l = strlen(str);
-+ int n = put_var_int(s, l);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+ if (s.len < l) {
-+ return -1;
-+ }
-+ memcpy(s.buf, str, l);
-+ s.buf += l;
-+ s.len -= l;
-+
-+ return start.len - s.len;
-+}
-+
-+static int ref_record_encode(const void *rec, struct slice s, int hash_size) {
-+ const struct ref_record *r = (const struct ref_record *)rec;
-+ struct slice start = s;
-+ int n = put_var_int(s, r->update_index);
-+ assert(hash_size > 0);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+
-+ if (r->value != NULL) {
-+ if (s.len < hash_size) {
-+ return -1;
-+ }
-+ memcpy(s.buf, r->value, hash_size);
-+ s.buf += hash_size;
-+ s.len -= hash_size;
-+ }
-+
-+ if (r->target_value != NULL) {
-+ if (s.len < hash_size) {
-+ return -1;
-+ }
-+ memcpy(s.buf, r->target_value, hash_size);
-+ s.buf += hash_size;
-+ s.len -= hash_size;
-+ }
-+
-+ if (r->target != NULL) {
-+ int n = encode_string(r->target, s);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+ }
-+
-+ return start.len - s.len;
++ struct slice key, byte extra)
++{
++ struct slice start = dest;
++ int prefix_len = common_prefix_size(prev_key, key);
++ uint64_t suffix_len = key.len - prefix_len;
++ int n = put_var_int(dest, (uint64_t)prefix_len);
++ if (n < 0) {
++ return -1;
++ }
++ dest.buf += n;
++ dest.len -= n;
++
++ *restart = (prefix_len == 0);
++
++ n = put_var_int(dest, suffix_len << 3 | (uint64_t)extra);
++ if (n < 0) {
++ return -1;
++ }
++ dest.buf += n;
++ dest.len -= n;
++
++ if (dest.len < suffix_len) {
++ return -1;
++ }
++ memcpy(dest.buf, key.buf + prefix_len, suffix_len);
++ dest.buf += suffix_len;
++ dest.len -= suffix_len;
++
++ return start.len - dest.len;
++}
++
++static byte ref_record_type(void)
++{
++ return BLOCK_TYPE_REF;
++}
++
++static void ref_record_key(const void *r, struct slice *dest)
++{
++ const struct ref_record *rec = (const struct ref_record *)r;
++ slice_set_string(dest, rec->ref_name);
++}
++
++static void ref_record_copy_from(void *rec, const void *src_rec, int hash_size)
++{
++ struct ref_record *ref = (struct ref_record *)rec;
++ struct ref_record *src = (struct ref_record *)src_rec;
++ assert(hash_size > 0);
++
++ /* This is simple and correct, but we could probably reuse the hash
++ fields. */
++ ref_record_clear(ref);
++ if (src->ref_name != NULL) {
++ ref->ref_name = strdup(src->ref_name);
++ }
++
++ if (src->target != NULL) {
++ ref->target = strdup(src->target);
++ }
++
++ if (src->target_value != NULL) {
++ ref->target_value = malloc(hash_size);
++ memcpy(ref->target_value, src->target_value, hash_size);
++ }
++
++ if (src->value != NULL) {
++ ref->value = malloc(hash_size);
++ memcpy(ref->value, src->value, hash_size);
++ }
++ ref->update_index = src->update_index;
++}
++
++static char hexdigit(int c)
++{
++ if (c <= 9) {
++ return '0' + c;
++ }
++ return 'a' + (c - 10);
++}
++
++static void hex_format(char *dest, byte *src, int hash_size)
++{
++ assert(hash_size > 0);
++ if (src != NULL) {
++ int i = 0;
++ for (i = 0; i < hash_size; i++) {
++ dest[2 * i] = hexdigit(src[i] >> 4);
++ dest[2 * i + 1] = hexdigit(src[i] & 0xf);
++ }
++ dest[2 * hash_size] = 0;
++ }
++}
++
++void ref_record_print(struct ref_record *ref, int hash_size)
++{
++ char hex[SHA256_SIZE + 1] = {};
++
++ printf("ref{%s(%" PRIdMAX ") ", ref->ref_name, ref->update_index);
++ if (ref->value != NULL) {
++ hex_format(hex, ref->value, hash_size);
++ printf("%s", hex);
++ }
++ if (ref->target_value != NULL) {
++ hex_format(hex, ref->target_value, hash_size);
++ printf(" (T %s)", hex);
++ }
++ if (ref->target != NULL) {
++ printf("=> %s", ref->target);
++ }
++ printf("}\n");
++}
++
++static void ref_record_clear_void(void *rec)
++{
++ ref_record_clear((struct ref_record *)rec);
++}
++
++void ref_record_clear(struct ref_record *ref)
++{
++ free(ref->ref_name);
++ free(ref->target);
++ free(ref->target_value);
++ free(ref->value);
++ memset(ref, 0, sizeof(struct ref_record));
++}
++
++static byte ref_record_val_type(const void *rec)
++{
++ const struct ref_record *r = (const struct ref_record *)rec;
++ if (r->value != NULL) {
++ if (r->target_value != NULL) {
++ return 2;
++ } else {
++ return 1;
++ }
++ } else if (r->target != NULL) {
++ return 3;
++ }
++ return 0;
++}
++
++static int encode_string(char *str, struct slice s)
++{
++ struct slice start = s;
++ int l = strlen(str);
++ int n = put_var_int(s, l);
++ if (n < 0) {
++ return -1;
++ }
++ s.buf += n;
++ s.len -= n;
++ if (s.len < l) {
++ return -1;
++ }
++ memcpy(s.buf, str, l);
++ s.buf += l;
++ s.len -= l;
++
++ return start.len - s.len;
++}
++
++static int ref_record_encode(const void *rec, struct slice s, int hash_size)
++{
++ const struct ref_record *r = (const struct ref_record *)rec;
++ struct slice start = s;
++ int n = put_var_int(s, r->update_index);
++ assert(hash_size > 0);
++ if (n < 0) {
++ return -1;
++ }
++ s.buf += n;
++ s.len -= n;
++
++ if (r->value != NULL) {
++ if (s.len < hash_size) {
++ return -1;
++ }
++ memcpy(s.buf, r->value, hash_size);
++ s.buf += hash_size;
++ s.len -= hash_size;
++ }
++
++ if (r->target_value != NULL) {
++ if (s.len < hash_size) {
++ return -1;
++ }
++ memcpy(s.buf, r->target_value, hash_size);
++ s.buf += hash_size;
++ s.len -= hash_size;
++ }
++
++ if (r->target != NULL) {
++ int n = encode_string(r->target, s);
++ if (n < 0) {
++ return -1;
++ }
++ s.buf += n;
++ s.len -= n;
++ }
++
++ return start.len - s.len;
+}
+
+static int ref_record_decode(void *rec, struct slice key, byte val_type,
-+ struct slice in, int hash_size) {
-+ struct ref_record *r = (struct ref_record *)rec;
-+ struct slice start = in;
-+ bool seen_value = false;
-+ bool seen_target_value = false;
-+ bool seen_target = false;
-+
-+ int n = get_var_int(&r->update_index, in);
-+ if (n < 0) {
-+ return n;
-+ }
-+ assert(hash_size > 0);
-+
-+ in.buf += n;
-+ in.len -= n;
-+
-+ r->ref_name = realloc(r->ref_name, key.len + 1);
-+ memcpy(r->ref_name, key.buf, key.len);
-+ r->ref_name[key.len] = 0;
-+
-+ switch (val_type) {
-+ case 1:
-+ case 2:
-+ if (in.len < hash_size) {
-+ return -1;
-+ }
-+
-+ if (r->value == NULL) {
-+ r->value = malloc(hash_size);
-+ }
-+ seen_value = true;
-+ memcpy(r->value, in.buf, hash_size);
-+ in.buf += hash_size;
-+ in.len -= hash_size;
-+ if (val_type == 1) {
-+ break;
-+ }
-+ if (r->target_value == NULL) {
-+ r->target_value = malloc(hash_size);
-+ }
-+ seen_target_value = true;
-+ memcpy(r->target_value, in.buf, hash_size);
-+ in.buf += hash_size;
-+ in.len -= hash_size;
-+ break;
-+ case 3: {
-+ struct slice dest = {};
-+ int n = decode_string(&dest, in);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ in.buf += n;
-+ in.len -= n;
-+ seen_target = true;
-+ r->target = (char *)slice_as_string(&dest);
-+ } break;
-+
-+ case 0:
-+ break;
-+ default:
-+ abort();
-+ break;
-+ }
-+
-+ if (!seen_target && r->target != NULL) {
-+ free(r->target);
-+ r->target = NULL;
-+ }
-+ if (!seen_target_value && r->target_value != NULL) {
-+ free(r->target_value);
-+ r->target_value = NULL;
-+ }
-+ if (!seen_value && r->value != NULL) {
-+ free(r->value);
-+ r->value = NULL;
-+ }
-+
-+ return start.len - in.len;
++ struct slice in, int hash_size)
++{
++ struct ref_record *r = (struct ref_record *)rec;
++ struct slice start = in;
++ bool seen_value = false;
++ bool seen_target_value = false;
++ bool seen_target = false;
++
++ int n = get_var_int(&r->update_index, in);
++ if (n < 0) {
++ return n;
++ }
++ assert(hash_size > 0);
++
++ in.buf += n;
++ in.len -= n;
++
++ r->ref_name = realloc(r->ref_name, key.len + 1);
++ memcpy(r->ref_name, key.buf, key.len);
++ r->ref_name[key.len] = 0;
++
++ switch (val_type) {
++ case 1:
++ case 2:
++ if (in.len < hash_size) {
++ return -1;
++ }
++
++ if (r->value == NULL) {
++ r->value = malloc(hash_size);
++ }
++ seen_value = true;
++ memcpy(r->value, in.buf, hash_size);
++ in.buf += hash_size;
++ in.len -= hash_size;
++ if (val_type == 1) {
++ break;
++ }
++ if (r->target_value == NULL) {
++ r->target_value = malloc(hash_size);
++ }
++ seen_target_value = true;
++ memcpy(r->target_value, in.buf, hash_size);
++ in.buf += hash_size;
++ in.len -= hash_size;
++ break;
++ case 3: {
++ struct slice dest = {};
++ int n = decode_string(&dest, in);
++ if (n < 0) {
++ return -1;
++ }
++ in.buf += n;
++ in.len -= n;
++ seen_target = true;
++ r->target = (char *)slice_as_string(&dest);
++ } break;
++
++ case 0:
++ break;
++ default:
++ abort();
++ break;
++ }
++
++ if (!seen_target && r->target != NULL) {
++ free(r->target);
++ r->target = NULL;
++ }
++ if (!seen_target_value && r->target_value != NULL) {
++ free(r->target_value);
++ r->target_value = NULL;
++ }
++ if (!seen_value && r->value != NULL) {
++ free(r->value);
++ r->value = NULL;
++ }
++
++ return start.len - in.len;
+}
+
+int decode_key(struct slice *key, byte *extra, struct slice last_key,
-+ struct slice in) {
-+ int start_len = in.len;
-+ uint64_t prefix_len = 0;
-+ uint64_t suffix_len = 0;
-+ int n = get_var_int(&prefix_len, in);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ in.buf += n;
-+ in.len -= n;
-+
-+ if (prefix_len > last_key.len) {
-+ return -1;
-+ }
-+
-+ n = get_var_int(&suffix_len, in);
-+ if (n <= 0) {
-+ return -1;
-+ }
-+ in.buf += n;
-+ in.len -= n;
-+
-+ *extra = (byte)(suffix_len & 0x7);
-+ suffix_len >>= 3;
-+
-+ if (in.len < suffix_len) {
-+ return -1;
-+ }
-+
-+ slice_resize(key, suffix_len + prefix_len);
-+ memcpy(key->buf, last_key.buf, prefix_len);
-+
-+ memcpy(key->buf + prefix_len, in.buf, suffix_len);
-+ in.buf += suffix_len;
-+ in.len -= suffix_len;
-+
-+ return start_len - in.len;
++ struct slice in)
++{
++ int start_len = in.len;
++ uint64_t prefix_len = 0;
++ uint64_t suffix_len = 0;
++ int n = get_var_int(&prefix_len, in);
++ if (n < 0) {
++ return -1;
++ }
++ in.buf += n;
++ in.len -= n;
++
++ if (prefix_len > last_key.len) {
++ return -1;
++ }
++
++ n = get_var_int(&suffix_len, in);
++ if (n <= 0) {
++ return -1;
++ }
++ in.buf += n;
++ in.len -= n;
++
++ *extra = (byte)(suffix_len & 0x7);
++ suffix_len >>= 3;
++
++ if (in.len < suffix_len) {
++ return -1;
++ }
++
++ slice_resize(key, suffix_len + prefix_len);
++ memcpy(key->buf, last_key.buf, prefix_len);
++
++ memcpy(key->buf + prefix_len, in.buf, suffix_len);
++ in.buf += suffix_len;
++ in.len -= suffix_len;
++
++ return start_len - in.len;
+}
+
+struct record_vtable ref_record_vtable = {
-+ .key = &ref_record_key,
-+ .type = &ref_record_type,
-+ .copy_from = &ref_record_copy_from,
-+ .val_type = &ref_record_val_type,
-+ .encode = &ref_record_encode,
-+ .decode = &ref_record_decode,
-+ .clear = &ref_record_clear_void,
++ .key = &ref_record_key,
++ .type = &ref_record_type,
++ .copy_from = &ref_record_copy_from,
++ .val_type = &ref_record_val_type,
++ .encode = &ref_record_encode,
++ .decode = &ref_record_decode,
++ .clear = &ref_record_clear_void,
+};
+
-+static byte obj_record_type(void) { return BLOCK_TYPE_OBJ; }
-+
-+static void obj_record_key(const void *r, struct slice *dest) {
-+ const struct obj_record *rec = (const struct obj_record *)r;
-+ slice_resize(dest, rec->hash_prefix_len);
-+ memcpy(dest->buf, rec->hash_prefix, rec->hash_prefix_len);
-+}
-+
-+static void obj_record_copy_from(void *rec, const void *src_rec,
-+ int hash_size) {
-+ struct obj_record *ref = (struct obj_record *)rec;
-+ const struct obj_record *src = (const struct obj_record *)src_rec;
-+
-+ *ref = *src;
-+ ref->hash_prefix = malloc(ref->hash_prefix_len);
-+ memcpy(ref->hash_prefix, src->hash_prefix, ref->hash_prefix_len);
-+
-+ {
-+ int olen = ref->offset_len * sizeof(uint64_t);
-+ ref->offsets = malloc(olen);
-+ memcpy(ref->offsets, src->offsets, olen);
-+ }
-+}
-+
-+static void obj_record_clear(void *rec) {
-+ struct obj_record *ref = (struct obj_record *)rec;
-+ free(ref->hash_prefix);
-+ free(ref->offsets);
-+ memset(ref, 0, sizeof(struct obj_record));
-+}
-+
-+static byte obj_record_val_type(const void *rec) {
-+ struct obj_record *r = (struct obj_record *)rec;
-+ if (r->offset_len > 0 && r->offset_len < 8) {
-+ return r->offset_len;
-+ }
-+ return 0;
-+}
-+
-+static int obj_record_encode(const void *rec, struct slice s, int hash_size) {
-+ struct obj_record *r = (struct obj_record *)rec;
-+ struct slice start = s;
-+ int n = 0;
-+ if (r->offset_len == 0 || r->offset_len >= 8) {
-+ n = put_var_int(s, r->offset_len);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+ }
-+ if (r->offset_len == 0) {
-+ return start.len - s.len;
-+ }
-+ n = put_var_int(s, r->offsets[0]);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+
-+ {
-+ uint64_t last = r->offsets[0];
-+ for (int i = 1; i < r->offset_len; i++) {
-+ int n = put_var_int(s, r->offsets[i] - last);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+ last = r->offsets[i];
-+ }
-+ }
-+ return start.len - s.len;
++static byte obj_record_type(void)
++{
++ return BLOCK_TYPE_OBJ;
++}
++
++static void obj_record_key(const void *r, struct slice *dest)
++{
++ const struct obj_record *rec = (const struct obj_record *)r;
++ slice_resize(dest, rec->hash_prefix_len);
++ memcpy(dest->buf, rec->hash_prefix, rec->hash_prefix_len);
++}
++
++static void obj_record_copy_from(void *rec, const void *src_rec, int hash_size)
++{
++ struct obj_record *ref = (struct obj_record *)rec;
++ const struct obj_record *src = (const struct obj_record *)src_rec;
++
++ *ref = *src;
++ ref->hash_prefix = malloc(ref->hash_prefix_len);
++ memcpy(ref->hash_prefix, src->hash_prefix, ref->hash_prefix_len);
++
++ {
++ int olen = ref->offset_len * sizeof(uint64_t);
++ ref->offsets = malloc(olen);
++ memcpy(ref->offsets, src->offsets, olen);
++ }
++}
++
++static void obj_record_clear(void *rec)
++{
++ struct obj_record *ref = (struct obj_record *)rec;
++ free(ref->hash_prefix);
++ free(ref->offsets);
++ memset(ref, 0, sizeof(struct obj_record));
++}
++
++static byte obj_record_val_type(const void *rec)
++{
++ struct obj_record *r = (struct obj_record *)rec;
++ if (r->offset_len > 0 && r->offset_len < 8) {
++ return r->offset_len;
++ }
++ return 0;
++}
++
++static int obj_record_encode(const void *rec, struct slice s, int hash_size)
++{
++ struct obj_record *r = (struct obj_record *)rec;
++ struct slice start = s;
++ int n = 0;
++ if (r->offset_len == 0 || r->offset_len >= 8) {
++ n = put_var_int(s, r->offset_len);
++ if (n < 0) {
++ return -1;
++ }
++ s.buf += n;
++ s.len -= n;
++ }
++ if (r->offset_len == 0) {
++ return start.len - s.len;
++ }
++ n = put_var_int(s, r->offsets[0]);
++ if (n < 0) {
++ return -1;
++ }
++ s.buf += n;
++ s.len -= n;
++
++ {
++ uint64_t last = r->offsets[0];
++ int i = 0;
++ for (i = 1; i < r->offset_len; i++) {
++ int n = put_var_int(s, r->offsets[i] - last);
++ if (n < 0) {
++ return -1;
++ }
++ s.buf += n;
++ s.len -= n;
++ last = r->offsets[i];
++ }
++ }
++ return start.len - s.len;
+}
+
+static int obj_record_decode(void *rec, struct slice key, byte val_type,
-+ struct slice in, int hash_size) {
-+ struct slice start = in;
-+ struct obj_record *r = (struct obj_record *)rec;
-+ uint64_t count = val_type;
-+ int n = 0;
-+ r->hash_prefix = malloc(key.len);
-+ memcpy(r->hash_prefix, key.buf, key.len);
-+ r->hash_prefix_len = key.len;
-+
-+ if (val_type == 0) {
-+ n = get_var_int(&count, in);
-+ if (n < 0) {
-+ return n;
-+ }
-+
-+ in.buf += n;
-+ in.len -= n;
-+ }
-+
-+ r->offsets = NULL;
-+ r->offset_len = 0;
-+ if (count == 0) {
-+ return start.len - in.len;
-+ }
-+
-+ r->offsets = malloc(count * sizeof(uint64_t));
-+ r->offset_len = count;
-+
-+ n = get_var_int(&r->offsets[0], in);
-+ if (n < 0) {
-+ return n;
-+ }
-+
-+ in.buf += n;
-+ in.len -= n;
-+
-+ {
-+ uint64_t last = r->offsets[0];
-+ int j = 1;
-+ while (j < count) {
-+ uint64_t delta = 0;
-+ int n = get_var_int(&delta, in);
-+ if (n < 0) {
-+ return n;
-+ }
-+
-+ in.buf += n;
-+ in.len -= n;
-+
-+ last = r->offsets[j] = (delta + last);
-+ j++;
-+ }
-+ }
-+ return start.len - in.len;
++ struct slice in, int hash_size)
++{
++ struct slice start = in;
++ struct obj_record *r = (struct obj_record *)rec;
++ uint64_t count = val_type;
++ int n = 0;
++ r->hash_prefix = malloc(key.len);
++ memcpy(r->hash_prefix, key.buf, key.len);
++ r->hash_prefix_len = key.len;
++
++ if (val_type == 0) {
++ n = get_var_int(&count, in);
++ if (n < 0) {
++ return n;
++ }
++
++ in.buf += n;
++ in.len -= n;
++ }
++
++ r->offsets = NULL;
++ r->offset_len = 0;
++ if (count == 0) {
++ return start.len - in.len;
++ }
++
++ r->offsets = malloc(count * sizeof(uint64_t));
++ r->offset_len = count;
++
++ n = get_var_int(&r->offsets[0], in);
++ if (n < 0) {
++ return n;
++ }
++
++ in.buf += n;
++ in.len -= n;
++
++ {
++ uint64_t last = r->offsets[0];
++ int j = 1;
++ while (j < count) {
++ uint64_t delta = 0;
++ int n = get_var_int(&delta, in);
++ if (n < 0) {
++ return n;
++ }
++
++ in.buf += n;
++ in.len -= n;
++
++ last = r->offsets[j] = (delta + last);
++ j++;
++ }
++ }
++ return start.len - in.len;
+}
+
+struct record_vtable obj_record_vtable = {
-+ .key = &obj_record_key,
-+ .type = &obj_record_type,
-+ .copy_from = &obj_record_copy_from,
-+ .val_type = &obj_record_val_type,
-+ .encode = &obj_record_encode,
-+ .decode = &obj_record_decode,
-+ .clear = &obj_record_clear,
++ .key = &obj_record_key,
++ .type = &obj_record_type,
++ .copy_from = &obj_record_copy_from,
++ .val_type = &obj_record_val_type,
++ .encode = &obj_record_encode,
++ .decode = &obj_record_decode,
++ .clear = &obj_record_clear,
+};
+
-+void log_record_print(struct log_record *log, int hash_size) {
-+ char hex[SHA256_SIZE + 1] = {};
-+
-+ printf("log{%s(%ld) %s <%s> %lu %04d\n", log->ref_name, log->update_index,
-+ log->name, log->email, log->time, log->tz_offset);
-+ hex_format(hex, log->old_hash, hash_size);
-+ printf("%s => ", hex);
-+ hex_format(hex, log->new_hash, hash_size);
-+ printf("%s\n\n%s\n}\n", hex, log->message);
++void log_record_print(struct log_record *log, int hash_size)
++{
++ char hex[SHA256_SIZE + 1] = {};
++
++ printf("log{%s(%" PRIdMAX ") %s <%s> %lu %04d\n", log->ref_name,
++ log->update_index, log->name, log->email, log->time,
++ log->tz_offset);
++ hex_format(hex, log->old_hash, hash_size);
++ printf("%s => ", hex);
++ hex_format(hex, log->new_hash, hash_size);
++ printf("%s\n\n%s\n}\n", hex, log->message);
++}
++
++static byte log_record_type(void)
++{
++ return BLOCK_TYPE_LOG;
++}
++
++static void log_record_key(const void *r, struct slice *dest)
++{
++ const struct log_record *rec = (const struct log_record *)r;
++ int len = strlen(rec->ref_name);
++ uint64_t ts = 0;
++ slice_resize(dest, len + 9);
++ memcpy(dest->buf, rec->ref_name, len + 1);
++ ts = (~ts) - rec->update_index;
++ put_u64(dest->buf + 1 + len, ts);
++}
++
++static void log_record_copy_from(void *rec, const void *src_rec, int hash_size)
++{
++ struct log_record *dst = (struct log_record *)rec;
++ const struct log_record *src = (const struct log_record *)src_rec;
++
++ *dst = *src;
++ dst->ref_name = strdup(dst->ref_name);
++ dst->email = strdup(dst->email);
++ dst->name = strdup(dst->name);
++ dst->message = strdup(dst->message);
++ if (dst->new_hash != NULL) {
++ dst->new_hash = malloc(hash_size);
++ memcpy(dst->new_hash, src->new_hash, hash_size);
++ }
++ if (dst->old_hash != NULL) {
++ dst->old_hash = malloc(hash_size);
++ memcpy(dst->old_hash, src->old_hash, hash_size);
++ }
++}
++
++static void log_record_clear_void(void *rec)
++{
++ struct log_record *r = (struct log_record *)rec;
++ log_record_clear(r);
++}
++
++void log_record_clear(struct log_record *r)
++{
++ free(r->ref_name);
++ free(r->new_hash);
++ free(r->old_hash);
++ free(r->name);
++ free(r->email);
++ free(r->message);
++ memset(r, 0, sizeof(struct log_record));
++}
++
++static byte log_record_val_type(const void *rec)
++{
++ return 1;
+}
+
-+static byte log_record_type(void) { return BLOCK_TYPE_LOG; }
-+
-+static void log_record_key(const void *r, struct slice *dest) {
-+ const struct log_record *rec = (const struct log_record *)r;
-+ int len = strlen(rec->ref_name);
-+ uint64_t ts = 0;
-+ slice_resize(dest, len + 9);
-+ memcpy(dest->buf, rec->ref_name, len + 1);
-+ ts = (~ts) - rec->update_index;
-+ put_u64(dest->buf + 1 + len, ts);
-+}
-+
-+static void log_record_copy_from(void *rec, const void *src_rec,
-+ int hash_size) {
-+ struct log_record *dst = (struct log_record *)rec;
-+ const struct log_record *src = (const struct log_record *)src_rec;
-+
-+ *dst = *src;
-+ dst->ref_name = strdup(dst->ref_name);
-+ dst->email = strdup(dst->email);
-+ dst->name = strdup(dst->name);
-+ dst->message = strdup(dst->message);
-+ if (dst->new_hash != NULL) {
-+ dst->new_hash = malloc(hash_size);
-+ memcpy(dst->new_hash, src->new_hash, hash_size);
-+ }
-+ if (dst->old_hash != NULL) {
-+ dst->old_hash = malloc(hash_size);
-+ memcpy(dst->old_hash, src->old_hash, hash_size);
-+ }
-+}
-+
-+static void log_record_clear_void(void *rec) {
-+ struct log_record *r = (struct log_record *)rec;
-+ log_record_clear(r);
-+}
-+
-+void log_record_clear(struct log_record *r) {
-+ free(r->ref_name);
-+ free(r->new_hash);
-+ free(r->old_hash);
-+ free(r->name);
-+ free(r->email);
-+ free(r->message);
-+ memset(r, 0, sizeof(struct log_record));
-+}
-+
-+static byte log_record_val_type(const void *rec) { return 1; }
-+
+static byte zero[SHA256_SIZE] = {};
+
-+static int log_record_encode(const void *rec, struct slice s, int hash_size) {
-+ struct log_record *r = (struct log_record *)rec;
-+ struct slice start = s;
-+ int n = 0;
-+ byte *oldh = r->old_hash;
-+ byte *newh = r->new_hash;
-+ if (oldh == NULL) {
-+ oldh = zero;
-+ }
-+ if (newh == NULL) {
-+ newh = zero;
-+ }
-+
-+ if (s.len < 2 * hash_size) {
-+ return -1;
-+ }
-+
-+ memcpy(s.buf, oldh, hash_size);
-+ memcpy(s.buf + hash_size, newh, hash_size);
-+ s.buf += 2 * hash_size;
-+ s.len -= 2 * hash_size;
-+
-+ n = encode_string(r->name ? r->name : "", s);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.len -= n;
-+ s.buf += n;
-+
-+ n = encode_string(r->email ? r->email : "", s);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.len -= n;
-+ s.buf += n;
-+
-+ n = put_var_int(s, r->time);
-+ if (n < 0) {
-+ return -1;
-+ }
-+ s.buf += n;
-+ s.len -= n;
-+
-+ if (s.len < 2) {
-+ return