reftable/record.h

   1 /*
   2 Copyright 2020 Google LLC
   3
   4 Use of this source code is governed by a BSD-style
   5 license that can be found in the LICENSE file or at
   6 https://developers.google.com/open-source/licenses/bsd
   7 */
   8
   9 #ifndef RECORD_H
  10 #define RECORD_H
  11
  12 #include "basics.h"
  13 #include "system.h"
  14
  15 #include <stdint.h>
  16
  17 #include "reftable-record.h"
  18
  19 /*
  20  * A substring of existing string data. This structure takes no responsibility
  21  * for the lifetime of the data it points to.
  22  */
  23 struct string_view {
  24         uint8_t *buf;
  25         size_t len;
  26 };
  27
  28 /* Advance `s.buf` by `n`, and decrease length. */
  29 static inline void string_view_consume(struct string_view *s, int n)
  30 {
  31         s->buf += n;
  32         s->len -= n;
  33 }
  34
  35 /* utilities for de/encoding varints */
  36
  37 int get_var_int(uint64_t *dest, struct string_view *in);
  38 int put_var_int(struct string_view *dest, uint64_t val);
  39
  40 /* Methods for records. */
  41 struct reftable_record_vtable {
  42         /* encode the key of to a uint8_t reftable_buf. */
  43         int (*key)(const void *rec, struct reftable_buf *dest);
  44
  45         /* The record type of ('r' for ref). */
  46         uint8_t type;
  47
  48         int (*copy_from)(void *dest, const void *src, int hash_size);
  49
  50         /* a value of [0..7], indicating record subvariants (eg. ref vs. symref
  51          * vs ref deletion) */
  52         uint8_t (*val_type)(const void *rec);
  53
  54         /* encodes rec into dest, returning how much space was used. */
  55         int (*encode)(const void *rec, struct string_view dest, int hash_size);
  56
  57         /* decode data from `src` into the record. */
  58         int (*decode)(void *rec, struct reftable_buf key, uint8_t extra,
  59                       struct string_view src, int hash_size,
  60                       struct reftable_buf *scratch);
  61
  62         /* deallocate and null the record. */
  63         void (*release)(void *rec);
  64
  65         /* is this a tombstone? */
  66         int (*is_deletion)(const void *rec);
  67
  68         /* Are two records equal? This assumes they have the same type. Returns 0 for non-equal. */
  69         int (*equal)(const void *a, const void *b, int hash_size);
  70
  71         /*
  72          * Compare keys of two records with each other. The records must have
  73          * the same type.
  74          */
  75         int (*cmp)(const void *a, const void *b);
  76
  77         /* Print on stdout, for debugging. */
  78         void (*print)(const void *rec, int hash_size);
  79 };
  80
  81 /* returns true for recognized block types. Block start with the block type. */
  82 int reftable_is_block_type(uint8_t typ);
  83
  84 /* Encode `key` into `dest`. Sets `is_restart` to indicate a restart. Returns
  85  * number of bytes written. */
  86 int reftable_encode_key(int *is_restart, struct string_view dest,
  87                         struct reftable_buf prev_key, struct reftable_buf key,
  88                         uint8_t extra);
  89
  90 /* Decode a record's key lengths. */
  91 int reftable_decode_keylen(struct string_view in,
  92                            uint64_t *prefix_len,
  93                            uint64_t *suffix_len,
  94                            uint8_t *extra);
  95
  96 /*
  97  * Decode into `last_key` and `extra` from `in`. `last_key` is expected to
  98  * contain the decoded key of the preceding record, if any.
  99  */
 100 int reftable_decode_key(struct reftable_buf *last_key, uint8_t *extra,
 101                         struct string_view in);
 102
 103 /* reftable_index_record are used internally to speed up lookups. */
 104 struct reftable_index_record {
 105         uint64_t offset; /* Offset of block */
 106         struct reftable_buf last_key; /* Last key of the block. */
 107 };
 108
 109 /* reftable_obj_record stores an object ID => ref mapping. */
 110 struct reftable_obj_record {
 111         uint8_t *hash_prefix; /* leading bytes of the object ID */
 112         int hash_prefix_len; /* number of leading bytes. Constant
 113                               * across a single table. */
 114         uint64_t *offsets; /* a vector of file offsets. */
 115         int offset_len;
 116 };
 117
 118 /* record is a generic wrapper for different types of records. It is normally
 119  * created on the stack, or embedded within another struct. If the type is
 120  * known, a fresh instance can be initialized explicitly. Otherwise, use
 121  * `reftable_record_init()` to initialize generically (as the index_record is
 122  * not valid as 0-initialized structure)
 123  */
 124 struct reftable_record {
 125         uint8_t type;
 126         union {
 127                 struct reftable_ref_record ref;
 128                 struct reftable_log_record log;
 129                 struct reftable_obj_record obj;
 130                 struct reftable_index_record idx;
 131         } u;
 132 };
 133
 134 /* Initialize the reftable record for the given type */
 135 void reftable_record_init(struct reftable_record *rec, uint8_t typ);
 136
 137 /* see struct record_vtable */
 138 int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b);
 139 int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size);
 140 int reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest);
 141 int reftable_record_copy_from(struct reftable_record *rec,
 142                               struct reftable_record *src, int hash_size);
 143 uint8_t reftable_record_val_type(struct reftable_record *rec);
 144 int reftable_record_encode(struct reftable_record *rec, struct string_view dest,
 145                            int hash_size);
 146 int reftable_record_decode(struct reftable_record *rec, struct reftable_buf key,
 147                            uint8_t extra, struct string_view src,
 148                            int hash_size, struct reftable_buf *scratch);
 149 int reftable_record_is_deletion(struct reftable_record *rec);
 150
 151 static inline uint8_t reftable_record_type(struct reftable_record *rec)
 152 {
 153         return rec->type;
 154 }
 155
 156 /* frees and zeroes out the embedded record */
 157 void reftable_record_release(struct reftable_record *rec);
 158
 159 /* for qsort. */
 160 int reftable_ref_record_compare_name(const void *a, const void *b);
 161
 162 /* for qsort. */
 163 int reftable_log_record_compare_key(const void *a, const void *b);
 164
 165 #endif