summaryrefslogtreecommitdiffstats
path: root/reftable/merged.c
diff options
context:
space:
mode:
Diffstat (limited to 'reftable/merged.c')
-rw-r--r--reftable/merged.c220
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,