summaryrefslogtreecommitdiffstats
path: root/reftable/record.c
diff options
context:
space:
mode:
Diffstat (limited to 'reftable/record.c')
-rw-r--r--reftable/record.c1314
1 files changed, 1314 insertions, 0 deletions
diff --git a/reftable/record.c b/reftable/record.c
new file mode 100644
index 0000000..fbaa1fb
--- /dev/null
+++ b/reftable/record.c
@@ -0,0 +1,1314 @@
+/*
+Copyright 2020 Google LLC
+
+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
+*/
+
+/* record.c - methods for different types of records. */
+
+#include "record.h"
+
+#include "system.h"
+#include "constants.h"
+#include "reftable-error.h"
+#include "basics.h"
+
+static struct reftable_record_vtable *
+reftable_record_vtable(struct reftable_record *rec);
+static void *reftable_record_data(struct reftable_record *rec);
+
+int get_var_int(uint64_t *dest, struct string_view *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 string_view *dest, uint64_t val)
+{
+ uint8_t buf[10] = { 0 };
+ int i = 9;
+ int n = 0;
+ buf[i] = (uint8_t)(val & 0x7f);
+ i--;
+ while (1) {
+ val >>= 7;
+ if (!val) {
+ break;
+ }
+ val--;
+ buf[i] = 0x80 | (uint8_t)(val & 0x7f);
+ i--;
+ }
+
+ n = sizeof(buf) - i - 1;
+ if (dest->len < n)
+ return -1;
+ memcpy(dest->buf, &buf[i + 1], n);
+ return n;
+}
+
+int reftable_is_block_type(uint8_t typ)
+{
+ switch (typ) {
+ case BLOCK_TYPE_REF:
+ case BLOCK_TYPE_LOG:
+ case BLOCK_TYPE_OBJ:
+ case BLOCK_TYPE_INDEX:
+ return 1;
+ }
+ return 0;
+}
+
+uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)
+{
+ switch (rec->value_type) {
+ case REFTABLE_REF_VAL1:
+ return rec->value.val1;
+ case REFTABLE_REF_VAL2:
+ return rec->value.val2.value;
+ default:
+ return NULL;
+ }
+}
+
+uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec)
+{
+ switch (rec->value_type) {
+ case REFTABLE_REF_VAL2:
+ return rec->value.val2.target_value;
+ default:
+ return NULL;
+ }
+}
+
+static int decode_string(struct strbuf *dest, struct string_view in)
+{
+ int start_len = in.len;
+ uint64_t tsize = 0;
+ int n = get_var_int(&tsize, &in);
+ if (n <= 0)
+ return -1;
+ string_view_consume(&in, n);
+ if (in.len < tsize)
+ return -1;
+
+ strbuf_reset(dest);
+ strbuf_add(dest, in.buf, tsize);
+ string_view_consume(&in, tsize);
+
+ return start_len - in.len;
+}
+
+static int encode_string(char *str, struct string_view s)
+{
+ struct string_view start = s;
+ int l = strlen(str);
+ int n = put_var_int(&s, l);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+ if (s.len < l)
+ return -1;
+ memcpy(s.buf, str, l);
+ string_view_consume(&s, l);
+
+ return start.len - s.len;
+}
+
+int reftable_encode_key(int *restart, struct string_view dest,
+ struct strbuf prev_key, struct strbuf key,
+ uint8_t extra)
+{
+ struct string_view 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;
+ string_view_consume(&dest, n);
+
+ *restart = (prefix_len == 0);
+
+ n = put_var_int(&dest, suffix_len << 3 | (uint64_t)extra);
+ if (n < 0)
+ return -1;
+ string_view_consume(&dest, n);
+
+ if (dest.len < suffix_len)
+ return -1;
+ memcpy(dest.buf, key.buf + prefix_len, suffix_len);
+ string_view_consume(&dest, suffix_len);
+
+ return start.len - dest.len;
+}
+
+int reftable_decode_key(struct strbuf *key, uint8_t *extra,
+ struct strbuf last_key, struct string_view 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;
+ string_view_consume(&in, n);
+
+ if (prefix_len > last_key.len)
+ return -1;
+
+ n = get_var_int(&suffix_len, &in);
+ if (n <= 0)
+ return -1;
+ string_view_consume(&in, n);
+
+ *extra = (uint8_t)(suffix_len & 0x7);
+ suffix_len >>= 3;
+
+ if (in.len < suffix_len)
+ return -1;
+
+ strbuf_reset(key);
+ strbuf_add(key, last_key.buf, prefix_len);
+ strbuf_add(key, in.buf, suffix_len);
+ string_view_consume(&in, suffix_len);
+
+ return start_len - in.len;
+}
+
+static void reftable_ref_record_key(const void *r, struct strbuf *dest)
+{
+ const struct reftable_ref_record *rec =
+ (const struct reftable_ref_record *)r;
+ strbuf_reset(dest);
+ strbuf_addstr(dest, rec->refname);
+}
+
+static void reftable_ref_record_copy_from(void *rec, const void *src_rec,
+ int hash_size)
+{
+ struct reftable_ref_record *ref = rec;
+ const struct reftable_ref_record *src = src_rec;
+ assert(hash_size > 0);
+
+ /* This is simple and correct, but we could probably reuse the hash
+ * fields. */
+ reftable_ref_record_release(ref);
+ if (src->refname) {
+ ref->refname = xstrdup(src->refname);
+ }
+ ref->update_index = src->update_index;
+ ref->value_type = src->value_type;
+ switch (src->value_type) {
+ case REFTABLE_REF_DELETION:
+ break;
+ case REFTABLE_REF_VAL1:
+ ref->value.val1 = reftable_malloc(hash_size);
+ memcpy(ref->value.val1, src->value.val1, hash_size);
+ break;
+ case REFTABLE_REF_VAL2:
+ ref->value.val2.value = reftable_malloc(hash_size);
+ memcpy(ref->value.val2.value, src->value.val2.value, hash_size);
+ ref->value.val2.target_value = reftable_malloc(hash_size);
+ memcpy(ref->value.val2.target_value,
+ src->value.val2.target_value, hash_size);
+ break;
+ case REFTABLE_REF_SYMREF:
+ ref->value.symref = xstrdup(src->value.symref);
+ break;
+ }
+}
+
+static char hexdigit(int c)
+{
+ if (c <= 9)
+ return '0' + c;
+ return 'a' + (c - 10);
+}
+
+static void hex_format(char *dest, uint8_t *src, int hash_size)
+{
+ assert(hash_size > 0);
+ if (src) {
+ 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;
+ }
+}
+
+static void reftable_ref_record_print_sz(const struct reftable_ref_record *ref,
+ int hash_size)
+{
+ char hex[GIT_MAX_HEXSZ + 1] = { 0 }; /* BUG */
+ printf("ref{%s(%" PRIu64 ") ", ref->refname, ref->update_index);
+ switch (ref->value_type) {
+ case REFTABLE_REF_SYMREF:
+ printf("=> %s", ref->value.symref);
+ break;
+ case REFTABLE_REF_VAL2:
+ hex_format(hex, ref->value.val2.value, hash_size);
+ printf("val 2 %s", hex);
+ hex_format(hex, ref->value.val2.target_value,
+ hash_size);
+ printf("(T %s)", hex);
+ break;
+ case REFTABLE_REF_VAL1:
+ hex_format(hex, ref->value.val1, hash_size);
+ printf("val 1 %s", hex);
+ break;
+ case REFTABLE_REF_DELETION:
+ printf("delete");
+ break;
+ }
+ printf("}\n");
+}
+
+void reftable_ref_record_print(const struct reftable_ref_record *ref,
+ uint32_t hash_id) {
+ reftable_ref_record_print_sz(ref, hash_size(hash_id));
+}
+
+static void reftable_ref_record_release_void(void *rec)
+{
+ reftable_ref_record_release(rec);
+}
+
+void reftable_ref_record_release(struct reftable_ref_record *ref)
+{
+ switch (ref->value_type) {
+ case REFTABLE_REF_SYMREF:
+ reftable_free(ref->value.symref);
+ break;
+ case REFTABLE_REF_VAL2:
+ reftable_free(ref->value.val2.target_value);
+ reftable_free(ref->value.val2.value);
+ break;
+ case REFTABLE_REF_VAL1:
+ reftable_free(ref->value.val1);
+ break;
+ case REFTABLE_REF_DELETION:
+ break;
+ default:
+ abort();
+ }
+
+ reftable_free(ref->refname);
+ memset(ref, 0, sizeof(struct reftable_ref_record));
+}
+
+static uint8_t reftable_ref_record_val_type(const void *rec)
+{
+ const struct reftable_ref_record *r =
+ (const struct reftable_ref_record *)rec;
+ return r->value_type;
+}
+
+static int reftable_ref_record_encode(const void *rec, struct string_view s,
+ int hash_size)
+{
+ const struct reftable_ref_record *r =
+ (const struct reftable_ref_record *)rec;
+ struct string_view start = s;
+ int n = put_var_int(&s, r->update_index);
+ assert(hash_size > 0);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+
+ switch (r->value_type) {
+ case REFTABLE_REF_SYMREF:
+ n = encode_string(r->value.symref, s);
+ if (n < 0) {
+ return -1;
+ }
+ string_view_consume(&s, n);
+ break;
+ case REFTABLE_REF_VAL2:
+ if (s.len < 2 * hash_size) {
+ return -1;
+ }
+ memcpy(s.buf, r->value.val2.value, hash_size);
+ string_view_consume(&s, hash_size);
+ memcpy(s.buf, r->value.val2.target_value, hash_size);
+ string_view_consume(&s, hash_size);
+ break;
+ case REFTABLE_REF_VAL1:
+ if (s.len < hash_size) {
+ return -1;
+ }
+ memcpy(s.buf, r->value.val1, hash_size);
+ string_view_consume(&s, hash_size);
+ break;
+ case REFTABLE_REF_DELETION:
+ break;
+ default:
+ abort();
+ }
+
+ return start.len - s.len;
+}
+
+static int reftable_ref_record_decode(void *rec, struct strbuf key,
+ uint8_t val_type, struct string_view in,
+ int hash_size)
+{
+ struct reftable_ref_record *r = rec;
+ struct string_view start = in;
+ uint64_t update_index = 0;
+ int n = get_var_int(&update_index, &in);
+ if (n < 0)
+ return n;
+ string_view_consume(&in, n);
+
+ reftable_ref_record_release(r);
+
+ assert(hash_size > 0);
+
+ r->refname = reftable_realloc(r->refname, key.len + 1);
+ memcpy(r->refname, key.buf, key.len);
+ r->update_index = update_index;
+ r->refname[key.len] = 0;
+ r->value_type = val_type;
+ switch (val_type) {
+ case REFTABLE_REF_VAL1:
+ if (in.len < hash_size) {
+ return -1;
+ }
+
+ r->value.val1 = reftable_malloc(hash_size);
+ memcpy(r->value.val1, in.buf, hash_size);
+ string_view_consume(&in, hash_size);
+ break;
+
+ case REFTABLE_REF_VAL2:
+ if (in.len < 2 * hash_size) {
+ return -1;
+ }
+
+ r->value.val2.value = reftable_malloc(hash_size);
+ memcpy(r->value.val2.value, in.buf, hash_size);
+ string_view_consume(&in, hash_size);
+
+ r->value.val2.target_value = reftable_malloc(hash_size);
+ memcpy(r->value.val2.target_value, in.buf, hash_size);
+ string_view_consume(&in, hash_size);
+ break;
+
+ case REFTABLE_REF_SYMREF: {
+ struct strbuf dest = STRBUF_INIT;
+ int n = decode_string(&dest, in);
+ if (n < 0) {
+ return -1;
+ }
+ string_view_consume(&in, n);
+ r->value.symref = dest.buf;
+ } break;
+
+ case REFTABLE_REF_DELETION:
+ break;
+ default:
+ abort();
+ break;
+ }
+
+ return start.len - in.len;
+}
+
+static int reftable_ref_record_is_deletion_void(const void *p)
+{
+ return reftable_ref_record_is_deletion(
+ (const struct reftable_ref_record *)p);
+}
+
+
+static int reftable_ref_record_equal_void(const void *a,
+ const void *b, int hash_size)
+{
+ struct reftable_ref_record *ra = (struct reftable_ref_record *) a;
+ struct reftable_ref_record *rb = (struct reftable_ref_record *) b;
+ return reftable_ref_record_equal(ra, rb, hash_size);
+}
+
+static void reftable_ref_record_print_void(const void *rec,
+ int hash_size)
+{
+ reftable_ref_record_print_sz((struct reftable_ref_record *) rec, hash_size);
+}
+
+static struct reftable_record_vtable reftable_ref_record_vtable = {
+ .key = &reftable_ref_record_key,
+ .type = BLOCK_TYPE_REF,
+ .copy_from = &reftable_ref_record_copy_from,
+ .val_type = &reftable_ref_record_val_type,
+ .encode = &reftable_ref_record_encode,
+ .decode = &reftable_ref_record_decode,
+ .release = &reftable_ref_record_release_void,
+ .is_deletion = &reftable_ref_record_is_deletion_void,
+ .equal = &reftable_ref_record_equal_void,
+ .print = &reftable_ref_record_print_void,
+};
+
+static void reftable_obj_record_key(const void *r, struct strbuf *dest)
+{
+ const struct reftable_obj_record *rec =
+ (const struct reftable_obj_record *)r;
+ strbuf_reset(dest);
+ strbuf_add(dest, rec->hash_prefix, rec->hash_prefix_len);
+}
+
+static void reftable_obj_record_release(void *rec)
+{
+ struct reftable_obj_record *obj = rec;
+ FREE_AND_NULL(obj->hash_prefix);
+ FREE_AND_NULL(obj->offsets);
+ memset(obj, 0, sizeof(struct reftable_obj_record));
+}
+
+static void reftable_obj_record_print(const void *rec, int hash_size)
+{
+ const struct reftable_obj_record *obj = rec;
+ char hex[GIT_MAX_HEXSZ + 1] = { 0 };
+ struct strbuf offset_str = STRBUF_INIT;
+ int i;
+
+ for (i = 0; i < obj->offset_len; i++)
+ strbuf_addf(&offset_str, "%" PRIu64 " ", obj->offsets[i]);
+ hex_format(hex, obj->hash_prefix, obj->hash_prefix_len);
+ printf("prefix %s (len %d), offsets [%s]\n",
+ hex, obj->hash_prefix_len, offset_str.buf);
+ strbuf_release(&offset_str);
+}
+
+static void reftable_obj_record_copy_from(void *rec, const void *src_rec,
+ int hash_size)
+{
+ struct reftable_obj_record *obj = rec;
+ const struct reftable_obj_record *src =
+ (const struct reftable_obj_record *)src_rec;
+
+ reftable_obj_record_release(obj);
+ obj->hash_prefix = reftable_malloc(src->hash_prefix_len);
+ obj->hash_prefix_len = src->hash_prefix_len;
+ if (src->hash_prefix_len)
+ memcpy(obj->hash_prefix, src->hash_prefix, obj->hash_prefix_len);
+
+ obj->offsets = reftable_malloc(src->offset_len * sizeof(uint64_t));
+ obj->offset_len = src->offset_len;
+ COPY_ARRAY(obj->offsets, src->offsets, src->offset_len);
+}
+
+static uint8_t reftable_obj_record_val_type(const void *rec)
+{
+ const struct reftable_obj_record *r = rec;
+ if (r->offset_len > 0 && r->offset_len < 8)
+ return r->offset_len;
+ return 0;
+}
+
+static int reftable_obj_record_encode(const void *rec, struct string_view s,
+ int hash_size)
+{
+ const struct reftable_obj_record *r = rec;
+ struct string_view start = s;
+ int i = 0;
+ int n = 0;
+ uint64_t last = 0;
+ if (r->offset_len == 0 || r->offset_len >= 8) {
+ n = put_var_int(&s, r->offset_len);
+ if (n < 0) {
+ return -1;
+ }
+ string_view_consume(&s, n);
+ }
+ if (r->offset_len == 0)
+ return start.len - s.len;
+ n = put_var_int(&s, r->offsets[0]);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+
+ last = r->offsets[0];
+ for (i = 1; i < r->offset_len; i++) {
+ int n = put_var_int(&s, r->offsets[i] - last);
+ if (n < 0) {
+ return -1;
+ }
+ string_view_consume(&s, n);
+ last = r->offsets[i];
+ }
+ return start.len - s.len;
+}
+
+static int reftable_obj_record_decode(void *rec, struct strbuf key,
+ uint8_t val_type, struct string_view in,
+ int hash_size)
+{
+ struct string_view start = in;
+ struct reftable_obj_record *r = rec;
+ uint64_t count = val_type;
+ int n = 0;
+ uint64_t last;
+ int j;
+ r->hash_prefix = reftable_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;
+ }
+
+ string_view_consume(&in, n);
+ }
+
+ r->offsets = NULL;
+ r->offset_len = 0;
+ if (count == 0)
+ return start.len - in.len;
+
+ r->offsets = reftable_malloc(count * sizeof(uint64_t));
+ r->offset_len = count;
+
+ n = get_var_int(&r->offsets[0], &in);
+ if (n < 0)
+ return n;
+ string_view_consume(&in, n);
+
+ last = r->offsets[0];
+ j = 1;
+ while (j < count) {
+ uint64_t delta = 0;
+ int n = get_var_int(&delta, &in);
+ if (n < 0) {
+ return n;
+ }
+ string_view_consume(&in, n);
+
+ last = r->offsets[j] = (delta + last);
+ j++;
+ }
+ return start.len - in.len;
+}
+
+static int not_a_deletion(const void *p)
+{
+ return 0;
+}
+
+static int reftable_obj_record_equal_void(const void *a, const void *b, int hash_size)
+{
+ struct reftable_obj_record *ra = (struct reftable_obj_record *) a;
+ struct reftable_obj_record *rb = (struct reftable_obj_record *) b;
+
+ if (ra->hash_prefix_len != rb->hash_prefix_len
+ || ra->offset_len != rb->offset_len)
+ return 0;
+
+ if (ra->hash_prefix_len &&
+ memcmp(ra->hash_prefix, rb->hash_prefix, ra->hash_prefix_len))
+ return 0;
+ if (ra->offset_len &&
+ memcmp(ra->offsets, rb->offsets, ra->offset_len * sizeof(uint64_t)))
+ return 0;
+
+ return 1;
+}
+
+static struct reftable_record_vtable reftable_obj_record_vtable = {
+ .key = &reftable_obj_record_key,
+ .type = BLOCK_TYPE_OBJ,
+ .copy_from = &reftable_obj_record_copy_from,
+ .val_type = &reftable_obj_record_val_type,
+ .encode = &reftable_obj_record_encode,
+ .decode = &reftable_obj_record_decode,
+ .release = &reftable_obj_record_release,
+ .is_deletion = &not_a_deletion,
+ .equal = &reftable_obj_record_equal_void,
+ .print = &reftable_obj_record_print,
+};
+
+static void reftable_log_record_print_sz(struct reftable_log_record *log,
+ int hash_size)
+{
+ char hex[GIT_MAX_HEXSZ + 1] = { 0 };
+
+ switch (log->value_type) {
+ case REFTABLE_LOG_DELETION:
+ printf("log{%s(%" PRIu64 ") delete\n", log->refname,
+ log->update_index);
+ break;
+ case REFTABLE_LOG_UPDATE:
+ printf("log{%s(%" PRIu64 ") %s <%s> %" PRIu64 " %04d\n",
+ log->refname, log->update_index,
+ log->value.update.name ? log->value.update.name : "",
+ log->value.update.email ? log->value.update.email : "",
+ log->value.update.time,
+ log->value.update.tz_offset);
+ hex_format(hex, log->value.update.old_hash, hash_size);
+ printf("%s => ", hex);
+ hex_format(hex, log->value.update.new_hash, hash_size);
+ printf("%s\n\n%s\n}\n", hex,
+ log->value.update.message ? log->value.update.message : "");
+ break;
+ }
+}
+
+void reftable_log_record_print(struct reftable_log_record *log,
+ uint32_t hash_id)
+{
+ reftable_log_record_print_sz(log, hash_size(hash_id));
+}
+
+static void reftable_log_record_key(const void *r, struct strbuf *dest)
+{
+ const struct reftable_log_record *rec =
+ (const struct reftable_log_record *)r;
+ int len = strlen(rec->refname);
+ uint8_t i64[8];
+ uint64_t ts = 0;
+ strbuf_reset(dest);
+ strbuf_add(dest, (uint8_t *)rec->refname, len + 1);
+
+ ts = (~ts) - rec->update_index;
+ put_be64(&i64[0], ts);
+ strbuf_add(dest, i64, sizeof(i64));
+}
+
+static void reftable_log_record_copy_from(void *rec, const void *src_rec,
+ int hash_size)
+{
+ struct reftable_log_record *dst = rec;
+ const struct reftable_log_record *src =
+ (const struct reftable_log_record *)src_rec;
+
+ reftable_log_record_release(dst);
+ *dst = *src;
+ if (dst->refname) {
+ dst->refname = xstrdup(dst->refname);
+ }
+ switch (dst->value_type) {
+ case REFTABLE_LOG_DELETION:
+ break;
+ case REFTABLE_LOG_UPDATE:
+ if (dst->value.update.email) {
+ dst->value.update.email =
+ xstrdup(dst->value.update.email);
+ }
+ if (dst->value.update.name) {
+ dst->value.update.name =
+ xstrdup(dst->value.update.name);
+ }
+ if (dst->value.update.message) {
+ dst->value.update.message =
+ xstrdup(dst->value.update.message);
+ }
+
+ if (dst->value.update.new_hash) {
+ dst->value.update.new_hash = reftable_malloc(hash_size);
+ memcpy(dst->value.update.new_hash,
+ src->value.update.new_hash, hash_size);
+ }
+ if (dst->value.update.old_hash) {
+ dst->value.update.old_hash = reftable_malloc(hash_size);
+ memcpy(dst->value.update.old_hash,
+ src->value.update.old_hash, hash_size);
+ }
+ break;
+ }
+}
+
+static void reftable_log_record_release_void(void *rec)
+{
+ struct reftable_log_record *r = rec;
+ reftable_log_record_release(r);
+}
+
+void reftable_log_record_release(struct reftable_log_record *r)
+{
+ reftable_free(r->refname);
+ switch (r->value_type) {
+ case REFTABLE_LOG_DELETION:
+ break;
+ case REFTABLE_LOG_UPDATE:
+ reftable_free(r->value.update.new_hash);
+ reftable_free(r->value.update.old_hash);
+ reftable_free(r->value.update.name);
+ reftable_free(r->value.update.email);
+ reftable_free(r->value.update.message);
+ break;
+ }
+ memset(r, 0, sizeof(struct reftable_log_record));
+}
+
+static uint8_t reftable_log_record_val_type(const void *rec)
+{
+ const struct reftable_log_record *log =
+ (const struct reftable_log_record *)rec;
+
+ return reftable_log_record_is_deletion(log) ? 0 : 1;
+}
+
+static uint8_t zero[GIT_SHA256_RAWSZ] = { 0 };
+
+static int reftable_log_record_encode(const void *rec, struct string_view s,
+ int hash_size)
+{
+ const struct reftable_log_record *r = rec;
+ struct string_view start = s;
+ int n = 0;
+ uint8_t *oldh = NULL;
+ uint8_t *newh = NULL;
+ if (reftable_log_record_is_deletion(r))
+ return 0;
+
+ oldh = r->value.update.old_hash;
+ newh = r->value.update.new_hash;
+ if (!oldh) {
+ oldh = zero;
+ }
+ if (!newh) {
+ newh = zero;
+ }
+
+ if (s.len < 2 * hash_size)
+ return -1;
+
+ memcpy(s.buf, oldh, hash_size);
+ memcpy(s.buf + hash_size, newh, hash_size);
+ string_view_consume(&s, 2 * hash_size);
+
+ n = encode_string(r->value.update.name ? r->value.update.name : "", s);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+
+ n = encode_string(r->value.update.email ? r->value.update.email : "",
+ s);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+
+ n = put_var_int(&s, r->value.update.time);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+
+ if (s.len < 2)
+ return -1;
+
+ put_be16(s.buf, r->value.update.tz_offset);
+ string_view_consume(&s, 2);
+
+ n = encode_string(
+ r->value.update.message ? r->value.update.message : "", s);
+ if (n < 0)
+ return -1;
+ string_view_consume(&s, n);
+
+ return start.len - s.len;
+}
+
+static int reftable_log_record_decode(void *rec, struct strbuf key,
+ uint8_t val_type, struct string_view in,
+ int hash_size)
+{
+ struct string_view start = in;
+ struct reftable_log_record *r = rec;
+ uint64_t max = 0;
+ uint64_t ts = 0;
+ struct strbuf dest = STRBUF_INIT;
+ int n;
+
+ if (key.len <= 9 || key.buf[key.len - 9] != 0)
+ return REFTABLE_FORMAT_ERROR;
+
+ r->refname = reftable_realloc(r->refname, key.len - 8);
+ memcpy(r->refname, key.buf, key.len - 8);
+ ts = get_be64(key.buf + key.len - 8);
+
+ r->update_index = (~max) - ts;
+
+ if (val_type != r->value_type) {
+ switch (r->value_type) {
+ case REFTABLE_LOG_UPDATE:
+ FREE_AND_NULL(r->value.update.old_hash);
+ FREE_AND_NULL(r->value.update.new_hash);
+ FREE_AND_NULL(r->value.update.message);
+ FREE_AND_NULL(r->value.update.email);
+ FREE_AND_NULL(r->value.update.name);
+ break;
+ case REFTABLE_LOG_DELETION:
+ break;
+ }
+ }
+
+ r->value_type = val_type;
+ if (val_type == REFTABLE_LOG_DELETION)
+ return 0;
+
+ if (in.len < 2 * hash_size)
+ return REFTABLE_FORMAT_ERROR;
+
+ r->value.update.old_hash =
+ reftable_realloc(r->value.update.old_hash, hash_size);
+ r->value.update.new_hash =
+ reftable_realloc(r->value.update.new_hash, hash_size);
+
+ memcpy(r->value.update.old_hash, in.buf, hash_size);
+ memcpy(r->value.update.new_hash, in.buf + hash_size, hash_size);
+
+ string_view_consume(&in, 2 * hash_size);
+
+ n = decode_string(&dest, in);
+ if (n < 0)
+ goto done;
+ string_view_consume(&in, n);
+
+ r->value.update.name =
+ reftable_realloc(r->value.update.name, dest.len + 1);
+ memcpy(r->value.update.name, dest.buf, dest.len);
+ r->value.update.name[dest.len] = 0;
+
+ strbuf_reset(&dest);
+ n = decode_string(&dest, in);
+ if (n < 0)
+ goto done;
+ string_view_consume(&in, n);
+
+ r->value.update.email =
+ reftable_realloc(r->value.update.email, dest.len + 1);
+ memcpy(r->value.update.email, dest.buf, dest.len);
+ r->value.update.email[dest.len] = 0;
+
+ ts = 0;
+ n = get_var_int(&ts, &in);
+ if (n < 0)
+ goto done;
+ string_view_consume(&in, n);
+ r->value.update.time = ts;
+ if (in.len < 2)
+ goto done;
+
+ r->value.update.tz_offset = get_be16(in.buf);
+ string_view_consume(&in, 2);
+
+ strbuf_reset(&dest);
+ n = decode_string(&dest, in);
+ if (n < 0)
+ goto done;
+ string_view_consume(&in, n);
+
+ r->value.update.message =
+ reftable_realloc(r->value.update.message, dest.len + 1);
+ memcpy(r->value.update.message, dest.buf, dest.len);
+ r->value.update.message[dest.len] = 0;
+
+ strbuf_release(&dest);
+ return start.len - in.len;
+
+done:
+ strbuf_release(&dest);
+ return REFTABLE_FORMAT_ERROR;
+}
+
+static int null_streq(char *a, char *b)
+{
+ char *empty = "";
+ if (!a)
+ a = empty;
+
+ if (!b)
+ b = empty;
+
+ return 0 == strcmp(a, b);
+}
+
+static int zero_hash_eq(uint8_t *a, uint8_t *b, int sz)
+{
+ if (!a)
+ a = zero;
+
+ if (!b)
+ b = zero;
+
+ return !memcmp(a, b, sz);
+}
+
+static int reftable_log_record_equal_void(const void *a,
+ const void *b, int hash_size)
+{
+ return reftable_log_record_equal((struct reftable_log_record *) a,
+ (struct reftable_log_record *) b,
+ hash_size);
+}
+
+int reftable_log_record_equal(const struct reftable_log_record *a,
+ const struct reftable_log_record *b, int hash_size)
+{
+ if (!(null_streq(a->refname, b->refname) &&
+ a->update_index == b->update_index &&
+ a->value_type == b->value_type))
+ return 0;
+
+ switch (a->value_type) {
+ case REFTABLE_LOG_DELETION:
+ return 1;
+ case REFTABLE_LOG_UPDATE:
+ return null_streq(a->value.update.name, b->value.update.name) &&
+ a->value.update.time == b->value.update.time &&
+ a->value.update.tz_offset == b->value.update.tz_offset &&
+ null_streq(a->value.update.email,
+ b->value.update.email) &&
+ null_streq(a->value.update.message,
+ b->value.update.message) &&
+ zero_hash_eq(a->value.update.old_hash,
+ b->value.update.old_hash, hash_size) &&
+ zero_hash_eq(a->value.update.new_hash,
+ b->value.update.new_hash, hash_size);
+ }
+
+ abort();
+}
+
+static int reftable_log_record_is_deletion_void(const void *p)
+{
+ return reftable_log_record_is_deletion(
+ (const struct reftable_log_record *)p);
+}
+
+static void reftable_log_record_print_void(const void *rec, int hash_size)
+{
+ reftable_log_record_print_sz((struct reftable_log_record*)rec, hash_size);
+}
+
+static struct reftable_record_vtable reftable_log_record_vtable = {
+ .key = &reftable_log_record_key,
+ .type = BLOCK_TYPE_LOG,
+ .copy_from = &reftable_log_record_copy_from,
+ .val_type = &reftable_log_record_val_type,
+ .encode = &reftable_log_record_encode,
+ .decode = &reftable_log_record_decode,
+ .release = &reftable_log_record_release_void,
+ .is_deletion = &reftable_log_record_is_deletion_void,
+ .equal = &reftable_log_record_equal_void,
+ .print = &reftable_log_record_print_void,
+};
+
+static void reftable_index_record_key(const void *r, struct strbuf *dest)
+{
+ const struct reftable_index_record *rec = r;
+ strbuf_reset(dest);
+ strbuf_addbuf(dest, &rec->last_key);
+}
+
+static void reftable_index_record_copy_from(void *rec, const void *src_rec,
+ int hash_size)
+{
+ struct reftable_index_record *dst = rec;
+ const struct reftable_index_record *src = src_rec;
+
+ strbuf_reset(&dst->last_key);
+ strbuf_addbuf(&dst->last_key, &src->last_key);
+ dst->offset = src->offset;
+}
+
+static void reftable_index_record_release(void *rec)
+{
+ struct reftable_index_record *idx = rec;
+ strbuf_release(&idx->last_key);
+}
+
+static uint8_t reftable_index_record_val_type(const void *rec)
+{
+ return 0;
+}
+
+static int reftable_index_record_encode(const void *rec, struct string_view out,
+ int hash_size)
+{
+ const struct reftable_index_record *r =
+ (const struct reftable_index_record *)rec;
+ struct string_view start = out;
+
+ int n = put_var_int(&out, r->offset);
+ if (n < 0)
+ return n;
+
+ string_view_consume(&out, n);
+
+ return start.len - out.len;
+}
+
+static int reftable_index_record_decode(void *rec, struct strbuf key,
+ uint8_t val_type, struct string_view in,
+ int hash_size)
+{
+ struct string_view start = in;
+ struct reftable_index_record *r = rec;
+ int n = 0;
+
+ strbuf_reset(&r->last_key);
+ strbuf_addbuf(&r->last_key, &key);
+
+ n = get_var_int(&r->offset, &in);
+ if (n < 0)
+ return n;
+
+ string_view_consume(&in, n);
+ return start.len - in.len;
+}
+
+static int reftable_index_record_equal(const void *a, const void *b, int hash_size)
+{
+ struct reftable_index_record *ia = (struct reftable_index_record *) a;
+ struct reftable_index_record *ib = (struct reftable_index_record *) b;
+
+ return ia->offset == ib->offset && !strbuf_cmp(&ia->last_key, &ib->last_key);
+}
+
+static void reftable_index_record_print(const void *rec, int hash_size)
+{
+ const struct reftable_index_record *idx = rec;
+ /* TODO: escape null chars? */
+ printf("\"%s\" %" PRIu64 "\n", idx->last_key.buf, idx->offset);
+}
+
+static struct reftable_record_vtable reftable_index_record_vtable = {
+ .key = &reftable_index_record_key,
+ .type = BLOCK_TYPE_INDEX,
+ .copy_from = &reftable_index_record_copy_from,
+ .val_type = &reftable_index_record_val_type,
+ .encode = &reftable_index_record_encode,
+ .decode = &reftable_index_record_decode,
+ .release = &reftable_index_record_release,
+ .is_deletion = &not_a_deletion,
+ .equal = &reftable_index_record_equal,
+ .print = &reftable_index_record_print,
+};
+
+void reftable_record_key(struct reftable_record *rec, struct strbuf *dest)
+{
+ reftable_record_vtable(rec)->key(reftable_record_data(rec), dest);
+}
+
+uint8_t reftable_record_type(struct reftable_record *rec)
+{
+ return rec->type;
+}
+
+int reftable_record_encode(struct reftable_record *rec, struct string_view dest,
+ int hash_size)
+{
+ return reftable_record_vtable(rec)->encode(reftable_record_data(rec),
+ dest, hash_size);
+}
+
+void reftable_record_copy_from(struct reftable_record *rec,
+ struct reftable_record *src, int hash_size)
+{
+ assert(src->type == rec->type);
+
+ reftable_record_vtable(rec)->copy_from(reftable_record_data(rec),
+ reftable_record_data(src),
+ hash_size);
+}
+
+uint8_t reftable_record_val_type(struct reftable_record *rec)
+{
+ return reftable_record_vtable(rec)->val_type(reftable_record_data(rec));
+}
+
+int reftable_record_decode(struct reftable_record *rec, struct strbuf key,
+ uint8_t extra, struct string_view src, int hash_size)
+{
+ return reftable_record_vtable(rec)->decode(reftable_record_data(rec),
+ key, extra, src, hash_size);
+}
+
+void reftable_record_release(struct reftable_record *rec)
+{
+ reftable_record_vtable(rec)->release(reftable_record_data(rec));
+}
+
+int reftable_record_is_deletion(struct reftable_record *rec)
+{
+ return reftable_record_vtable(rec)->is_deletion(
+ reftable_record_data(rec));
+}
+
+int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size)
+{
+ if (a->type != b->type)
+ return 0;
+ return reftable_record_vtable(a)->equal(
+ reftable_record_data(a), reftable_record_data(b), hash_size);
+}
+
+static int hash_equal(uint8_t *a, uint8_t *b, int hash_size)
+{
+ if (a && b)
+ return !memcmp(a, b, hash_size);
+
+ return a == b;
+}
+
+int reftable_ref_record_equal(const struct reftable_ref_record *a,
+ const struct reftable_ref_record *b, int hash_size)
+{
+ assert(hash_size > 0);
+ if (!null_streq(a->refname, b->refname))
+ return 0;
+
+ if (a->update_index != b->update_index ||
+ a->value_type != b->value_type)
+ return 0;
+
+ switch (a->value_type) {
+ case REFTABLE_REF_SYMREF:
+ return !strcmp(a->value.symref, b->value.symref);
+ case REFTABLE_REF_VAL2:
+ return hash_equal(a->value.val2.value, b->value.val2.value,
+ hash_size) &&
+ hash_equal(a->value.val2.target_value,
+ b->value.val2.target_value, hash_size);
+ case REFTABLE_REF_VAL1:
+ return hash_equal(a->value.val1, b->value.val1, hash_size);
+ case REFTABLE_REF_DELETION:
+ return 1;
+ default:
+ abort();
+ }
+}
+
+int reftable_ref_record_compare_name(const void *a, const void *b)
+{
+ return strcmp(((struct reftable_ref_record *)a)->refname,
+ ((struct reftable_ref_record *)b)->refname);
+}
+
+int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref)
+{
+ return ref->value_type == REFTABLE_REF_DELETION;
+}
+
+int reftable_log_record_compare_key(const void *a, const void *b)
+{
+ const struct reftable_log_record *la = a;
+ const struct reftable_log_record *lb = b;
+
+ int cmp = strcmp(la->refname, lb->refname);
+ if (cmp)
+ return cmp;
+ if (la->update_index > lb->update_index)
+ return -1;
+ return (la->update_index < lb->update_index) ? 1 : 0;
+}
+
+int reftable_log_record_is_deletion(const struct reftable_log_record *log)
+{
+ return (log->value_type == REFTABLE_LOG_DELETION);
+}
+
+void string_view_consume(struct string_view *s, int n)
+{
+ s->buf += n;
+ s->len -= n;
+}
+
+static void *reftable_record_data(struct reftable_record *rec)
+{
+ switch (rec->type) {
+ case BLOCK_TYPE_REF:
+ return &rec->u.ref;
+ case BLOCK_TYPE_LOG:
+ return &rec->u.log;
+ case BLOCK_TYPE_INDEX:
+ return &rec->u.idx;
+ case BLOCK_TYPE_OBJ:
+ return &rec->u.obj;
+ }
+ abort();
+}
+
+static struct reftable_record_vtable *
+reftable_record_vtable(struct reftable_record *rec)
+{
+ switch (rec->type) {
+ case BLOCK_TYPE_REF:
+ return &reftable_ref_record_vtable;
+ case BLOCK_TYPE_LOG:
+ return &reftable_log_record_vtable;
+ case BLOCK_TYPE_INDEX:
+ return &reftable_index_record_vtable;
+ case BLOCK_TYPE_OBJ:
+ return &reftable_obj_record_vtable;
+ }
+ abort();
+}
+
+struct reftable_record reftable_new_record(uint8_t typ)
+{
+ struct reftable_record clean = {
+ .type = typ,
+ };
+
+ /* the following is involved, but the naive solution (just return
+ * `clean` as is, except for BLOCK_TYPE_INDEX), returns a garbage
+ * clean.u.obj.offsets pointer on Windows VS CI. Go figure.
+ */
+ switch (typ) {
+ case BLOCK_TYPE_OBJ:
+ {
+ struct reftable_obj_record obj = { 0 };
+ clean.u.obj = obj;
+ break;
+ }
+ case BLOCK_TYPE_INDEX:
+ {
+ struct reftable_index_record idx = {
+ .last_key = STRBUF_INIT,
+ };
+ clean.u.idx = idx;
+ break;
+ }
+ case BLOCK_TYPE_REF:
+ {
+ struct reftable_ref_record ref = { 0 };
+ clean.u.ref = ref;
+ break;
+ }
+ case BLOCK_TYPE_LOG:
+ {
+ struct reftable_log_record log = { 0 };
+ clean.u.log = log;
+ break;
+ }
+ }
+ return clean;
+}
+
+void reftable_record_print(struct reftable_record *rec, int hash_size)
+{
+ printf("'%c': ", rec->type);
+ reftable_record_vtable(rec)->print(reftable_record_data(rec), hash_size);
+}