diff options
Diffstat (limited to 'reftable/merged.c')
| -rw-r--r-- | reftable/merged.c | 220 |
1 files changed, 107 insertions, 113 deletions
diff --git a/reftable/merged.c b/reftable/merged.c index 5ded470..f85a24c 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -11,33 +11,45 @@ https://developers.google.com/open-source/licenses/bsd #include "constants.h" #include "iter.h" #include "pq.h" -#include "reader.h" #include "record.h" #include "generic.h" #include "reftable-merged.h" #include "reftable-error.h" #include "system.h" +struct merged_subiter { + struct reftable_iterator iter; + struct reftable_record rec; +}; + +struct merged_iter { + struct merged_subiter *subiters; + struct merged_iter_pqueue pq; + uint32_t hash_id; + size_t stack_len; + uint8_t typ; + int suppress_deletions; + ssize_t advance_index; +}; + static int merged_iter_init(struct merged_iter *mi) { - int i = 0; - for (i = 0; i < mi->stack_len; i++) { - struct reftable_record rec = reftable_new_record(mi->typ); - int err = iterator_next(&mi->stack[i], &rec); - if (err < 0) { + for (size_t i = 0; i < mi->stack_len; i++) { + struct pq_entry e = { + .index = i, + .rec = &mi->subiters[i].rec, + }; + int err; + + reftable_record_init(&mi->subiters[i].rec, mi->typ); + err = iterator_next(&mi->subiters[i].iter, + &mi->subiters[i].rec); + if (err < 0) return err; - } + if (err > 0) + continue; - if (err > 0) { - reftable_iterator_destroy(&mi->stack[i]); - reftable_record_release(&rec); - } else { - struct pq_entry e = { - .rec = rec, - .index = i, - }; - merged_iter_pqueue_add(&mi->pq, &e); - } + merged_iter_pqueue_add(&mi->pq, &e); } return 0; @@ -46,56 +58,68 @@ static int merged_iter_init(struct merged_iter *mi) static void merged_iter_close(void *p) { struct merged_iter *mi = p; - int i = 0; + merged_iter_pqueue_release(&mi->pq); - for (i = 0; i < mi->stack_len; i++) { - reftable_iterator_destroy(&mi->stack[i]); + for (size_t i = 0; i < mi->stack_len; i++) { + reftable_iterator_destroy(&mi->subiters[i].iter); + reftable_record_release(&mi->subiters[i].rec); } - reftable_free(mi->stack); + reftable_free(mi->subiters); } -static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi, - size_t idx) +static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx) { struct pq_entry e = { - .rec = reftable_new_record(mi->typ), .index = idx, + .rec = &mi->subiters[idx].rec, }; - int err = iterator_next(&mi->stack[idx], &e.rec); - if (err < 0) - return err; + int err; - if (err > 0) { - reftable_iterator_destroy(&mi->stack[idx]); - reftable_record_release(&e.rec); - return 0; - } + err = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec); + if (err) + return err; merged_iter_pqueue_add(&mi->pq, &e); return 0; } -static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx) -{ - if (iterator_is_null(&mi->stack[idx])) - return 0; - return merged_iter_advance_nonnull_subiter(mi, idx); -} - static int merged_iter_next_entry(struct merged_iter *mi, struct reftable_record *rec) { - struct strbuf entry_key = STRBUF_INIT; struct pq_entry entry = { 0 }; - int err = 0; + int err = 0, empty; + + empty = merged_iter_pqueue_is_empty(mi->pq); + + if (mi->advance_index >= 0) { + /* + * When there are no pqueue entries then we only have a single + * subiter left. There is no need to use the pqueue in that + * case anymore as we know that the subiter will return entries + * in the correct order already. + * + * While this may sound like a very specific edge case, it may + * happen more frequently than you think. Most repositories + * will end up having a single large base table that contains + * most of the refs. It's thus likely that we exhaust all + * subiters but the one from that base ref. + */ + if (empty) + return iterator_next(&mi->subiters[mi->advance_index].iter, + rec); + + err = merged_iter_advance_subiter(mi, mi->advance_index); + if (err < 0) + return err; + if (!err) + empty = 0; + mi->advance_index = -1; + } - if (merged_iter_pqueue_is_empty(mi->pq)) + if (empty) return 1; entry = merged_iter_pqueue_remove(&mi->pq); - err = merged_iter_advance_subiter(mi, entry.index); - if (err < 0) - return err; /* One can also use reftable as datacenter-local storage, where the ref @@ -105,57 +129,38 @@ static int merged_iter_next_entry(struct merged_iter *mi, such a deployment, the loop below must be changed to collect all entries for the same key, and return new the newest one. */ - reftable_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 strbuf k = STRBUF_INIT; - int err = 0, cmp = 0; - - reftable_record_key(&top.rec, &k); + int cmp; - cmp = strbuf_cmp(&k, &entry_key); - strbuf_release(&k); - - if (cmp > 0) { + cmp = reftable_record_cmp(top.rec, entry.rec); + if (cmp > 0) break; - } merged_iter_pqueue_remove(&mi->pq); err = merged_iter_advance_subiter(mi, top.index); - if (err < 0) { + if (err < 0) return err; - } - reftable_record_release(&top.rec); } - reftable_record_copy_from(rec, &entry.rec, hash_size(mi->hash_id)); - reftable_record_release(&entry.rec); - strbuf_release(&entry_key); + mi->advance_index = entry.index; + SWAP(*rec, *entry.rec); return 0; } -static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec) +static int merged_iter_next_void(void *p, struct reftable_record *rec) { + struct merged_iter *mi = p; while (1) { int err = merged_iter_next_entry(mi, rec); - if (err == 0 && mi->suppress_deletions && - reftable_record_is_deletion(rec)) { + if (err) + return err; + if (mi->suppress_deletions && reftable_record_is_deletion(rec)) continue; - } - - return err; + return 0; } } -static int merged_iter_next_void(void *p, struct reftable_record *rec) -{ - struct merged_iter *mi = p; - if (merged_iter_pqueue_is_empty(mi->pq)) - return 1; - - return merged_iter_next(mi, rec); -} - static struct reftable_iterator_vtable merged_iter_vtable = { .next = &merged_iter_next_void, .close = &merged_iter_close, @@ -170,14 +175,14 @@ static void iterator_from_merged_iter(struct reftable_iterator *it, } int reftable_new_merged_table(struct reftable_merged_table **dest, - struct reftable_table *stack, int n, + struct reftable_table *stack, size_t n, uint32_t hash_id) { struct reftable_merged_table *m = NULL; uint64_t last_max = 0; uint64_t first_min = 0; - int i = 0; - for (i = 0; i < n; i++) { + + for (size_t i = 0; i < n; i++) { uint64_t min = reftable_table_min_update_index(&stack[i]); uint64_t max = reftable_table_max_update_index(&stack[i]); @@ -192,7 +197,7 @@ int reftable_new_merged_table(struct reftable_merged_table **dest, } } - m = reftable_calloc(sizeof(struct reftable_merged_table)); + REFTABLE_CALLOC_ARRAY(m, 1); m->stack = stack; m->stack_len = n; m->min = first_min; @@ -241,48 +246,37 @@ static int merged_table_seek_record(struct reftable_merged_table *mt, struct reftable_iterator *it, struct reftable_record *rec) { - struct reftable_iterator *iters = reftable_calloc( - sizeof(struct reftable_iterator) * mt->stack_len); struct merged_iter merged = { - .stack = iters, .typ = reftable_record_type(rec), .hash_id = mt->hash_id, .suppress_deletions = mt->suppress_deletions, + .advance_index = -1, }; - int n = 0; - int err = 0; - int i = 0; - for (i = 0; i < mt->stack_len && err == 0; i++) { - int e = reftable_table_seek_record(&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++) { - reftable_iterator_destroy(&iters[i]); - } - reftable_free(iters); - return err; + struct merged_iter *p; + int err; + + REFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len); + for (size_t i = 0; i < mt->stack_len; i++) { + err = reftable_table_seek_record(&mt->stack[i], + &merged.subiters[merged.stack_len].iter, rec); + if (err < 0) + goto out; + if (!err) + merged.stack_len++; } - merged.stack_len = n; err = merged_iter_init(&merged); - if (err < 0) { + if (err < 0) + goto out; + + p = reftable_malloc(sizeof(struct merged_iter)); + *p = merged; + iterator_from_merged_iter(it, p); + +out: + if (err < 0) merged_iter_close(&merged); - return err; - } else { - struct merged_iter *p = - reftable_malloc(sizeof(struct merged_iter)); - *p = merged; - iterator_from_merged_iter(it, p); - } - return 0; + return err; } int reftable_merged_table_seek_ref(struct reftable_merged_table *mt, |