From: Han-Wen Nienhuys via GitGitGadget Date: Mon, 27 Jan 2020 14:22:19 GMT Subject: [PATCH v2 0/5] Reftable support git-core Message-ID: In-Reply-To: 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 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 -+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 -+#include -+#include ++#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 ++#include "system.h" + +#include "reftable.h" + @@ -567,10 +364,7 @@ + +#include "block.h" + -+#include -+#include -+#include -+#include ++#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 ++#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 -+#include -+#include ++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 -+#include -+#include -+#include -+#include -+#include -+#include -+#include -+#include ++#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 -+#include ++#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 ++#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 ++#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 -+#include ++#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 -+#include -+#include -+#include ++#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 -+#include -+#include -+#include ++#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