Merge branch 'ja/worktree-orphan' into maint-2.42
[git/debian.git] / reftable / pq_test.c
blob011b5c75028a9d8dbad15f23ddb99d39e09ca9cb
1 /*
2 Copyright 2020 Google LLC
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 */
9 #include "system.h"
11 #include "basics.h"
12 #include "constants.h"
13 #include "pq.h"
14 #include "record.h"
15 #include "reftable-tests.h"
16 #include "test_framework.h"
18 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
20 int i;
21 for (i = 1; i < pq.len; i++) {
22 int parent = (i - 1) / 2;
24 EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
28 static void test_pq(void)
30 char *names[54] = { NULL };
31 int N = ARRAY_SIZE(names) - 1;
33 struct merged_iter_pqueue pq = { NULL };
34 char *last = NULL;
36 int i = 0;
37 for (i = 0; i < N; i++) {
38 char name[100];
39 snprintf(name, sizeof(name), "%02d", i);
40 names[i] = xstrdup(name);
43 i = 1;
44 do {
45 struct pq_entry e = { .rec = { .type = BLOCK_TYPE_REF,
46 .u.ref = {
47 .refname = names[i],
48 } } };
49 merged_iter_pqueue_add(&pq, &e);
50 merged_iter_pqueue_check(pq);
51 i = (i * 7) % N;
52 } while (i != 1);
54 while (!merged_iter_pqueue_is_empty(pq)) {
55 struct pq_entry e = merged_iter_pqueue_remove(&pq);
56 struct reftable_record *rec = &e.rec;
57 merged_iter_pqueue_check(pq);
59 EXPECT(reftable_record_type(rec) == BLOCK_TYPE_REF);
60 if (last) {
61 EXPECT(strcmp(last, rec->u.ref.refname) < 0);
63 // this is names[i], so don't dealloc.
64 last = rec->u.ref.refname;
65 rec->u.ref.refname = NULL;
66 reftable_record_release(rec);
68 for (i = 0; i < N; i++) {
69 reftable_free(names[i]);
72 merged_iter_pqueue_release(&pq);
75 int pq_test_main(int argc, const char *argv[])
77 RUN_TEST(test_pq);
78 return 0;