Merge branch 'ps/reftable-iteration-perf'

[thirdparty/git.git] / reftable / reader.c

diff --git a/reftable/reader.c b/reftable/reader.c
index add7d57f0b2aadbab72121066f5037a9d4aec1b5..b113daab77336c240d10f64ce9890ff04f5f366a 100644 (file)
--- a/reftable/reader.c
+++ b/reftable/reader.c
@@ -452,13 +452,13 @@ static int reader_start(struct reftable_reader *r, struct table_iter *ti,
 static int reader_seek_linear(struct table_iter *ti,
                              struct reftable_record *want)
 {
-       struct reftable_record rec =
-               reftable_new_record(reftable_record_type(want));
        struct strbuf want_key = STRBUF_INIT;
        struct strbuf got_key = STRBUF_INIT;
        struct table_iter next = TABLE_ITER_INIT;
+       struct reftable_record rec;
        int err = -1;
 
+       reftable_record_init(&rec, reftable_record_type(want));
        reftable_record_key(want, &want_key);
 
        while (1) {
@@ -516,8 +516,38 @@ static int reader_seek_indexed(struct reftable_reader *r,
        if (err < 0)
                goto done;
 
+       /*
+        * The index may consist of multiple levels, where each level may have
+        * multiple index blocks. We start by doing a linear search in the
+        * highest layer that identifies the relevant index block as well as
+        * the record inside that block that corresponds to our wanted key.
+        */
        err = reader_seek_linear(&index_iter, &want_index);
+       if (err < 0)
+               goto done;
+
+       /*
+        * Traverse down the levels until we find a non-index entry.
+        */
        while (1) {
+               /*
+                * In case we seek a record that does not exist the index iter
+                * will tell us that the iterator is over. This works because
+                * the last index entry of the current level will contain the
+                * last key it knows about. So in case our seeked key is larger
+                * than the last indexed key we know that it won't exist.
+                *
+                * There is one subtlety in the layout of the index section
+                * that makes this work as expected: the highest-level index is
+                * at end of the section and will point backwards and thus we
+                * start reading from the end of the index section, not the
+                * beginning.
+                *
+                * If that wasn't the case and the order was reversed then the
+                * linear seek would seek into the lower levels and traverse
+                * all levels of the index only to find out that the key does
+                * not exist.
+                */
                err = table_iter_next(&index_iter, &index_result);
                table_iter_block_done(&index_iter);
                if (err != 0)
@@ -547,8 +577,7 @@ static int reader_seek_indexed(struct reftable_reader *r,
 
        if (err == 0) {
                struct table_iter empty = TABLE_ITER_INIT;
-               struct table_iter *malloced =
-                       reftable_calloc(sizeof(struct table_iter));
+               struct table_iter *malloced = reftable_calloc(1, sizeof(*malloced));
                *malloced = empty;
                table_iter_copy_from(malloced, &next);
                iterator_from_table_iter(it, malloced);
@@ -643,8 +672,7 @@ void reader_close(struct reftable_reader *r)
 int reftable_new_reader(struct reftable_reader **p,
                        struct reftable_block_source *src, char const *name)
 {
-       struct reftable_reader *rd =
-               reftable_calloc(sizeof(struct reftable_reader));
+       struct reftable_reader *rd = reftable_calloc(1, sizeof(*rd));
        int err = init_reader(rd, src, name);
        if (err == 0) {
                *p = rd;
@@ -719,7 +747,7 @@ static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,
                                              uint8_t *oid)
 {
        struct table_iter ti_empty = TABLE_ITER_INIT;
-       struct table_iter *ti = reftable_calloc(sizeof(struct table_iter));
+       struct table_iter *ti = reftable_calloc(1, sizeof(*ti));
        struct filtering_ref_iterator *filter = NULL;
        struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;
        int oid_len = hash_size(r->hash_id);