@leroysheep / LeeRoySheep
Code Commits Pulls CI/CD 81,348
maint
bisect jch maint master next seen test todo
c 156 lines 3.65 KB
Raw
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 #include "unit-test.h"
10 #include "lib-reftable.h"
11 #include "reftable/constants.h"
12 #include "reftable/pq.h"
13 #include "strbuf.h"
14
15 static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
16 {
17 for (size_t i = 1; i < pq->len; i++) {
18 size_t parent = (i - 1) / 2;
19 cl_assert(pq_less(&pq->heap[parent], &pq->heap[i]) != 0);
20 }
21 }
22
23 static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
24 {
25 int cmp;
26 cl_assert_equal_i(reftable_record_cmp(a->rec, b->rec, &cmp), 0);
27 return !cmp && (a->index == b->index);
28 }
29
30 void test_reftable_pq__record(void)
31 {
32 struct merged_iter_pqueue pq = { 0 };
33 struct reftable_record recs[54];
34 size_t N = ARRAY_SIZE(recs) - 1, i;
35 char *last = NULL;
36
37 for (i = 0; i < N; i++) {
38 cl_assert(!reftable_record_init(&recs[i],
39 REFTABLE_BLOCK_TYPE_REF));
40 recs[i].u.ref.refname = xstrfmt("%02"PRIuMAX, (uintmax_t)i);
41 }
42
43 i = 1;
44 do {
45 struct pq_entry e = {
46 .rec = &recs[i],
47 };
48
49 merged_iter_pqueue_add(&pq, &e);
50 merged_iter_pqueue_check(&pq);
51 i = (i * 7) % N;
52 } while (i != 1);
53
54 while (!merged_iter_pqueue_is_empty(pq)) {
55 struct pq_entry top = merged_iter_pqueue_top(pq);
56 struct pq_entry e;
57
58 cl_assert_equal_i(merged_iter_pqueue_remove(&pq, &e), 0);
59 merged_iter_pqueue_check(&pq);
60
61 cl_assert(pq_entry_equal(&top, &e));
62 cl_assert(reftable_record_type(e.rec) == REFTABLE_BLOCK_TYPE_REF);
63 if (last)
64 cl_assert(strcmp(last, e.rec->u.ref.refname) < 0);
65 last = e.rec->u.ref.refname;
66 }
67
68 for (i = 0; i < N; i++)
69 reftable_record_release(&recs[i]);
70 merged_iter_pqueue_release(&pq);
71 }
72
73 void test_reftable_pq__index(void)
74 {
75 struct merged_iter_pqueue pq = { 0 };
76 struct reftable_record recs[13];
77 char *last = NULL;
78 size_t N = ARRAY_SIZE(recs), i;
79
80 for (i = 0; i < N; i++) {
81 cl_assert(!reftable_record_init(&recs[i],
82 REFTABLE_BLOCK_TYPE_REF));
83 recs[i].u.ref.refname = (char *) "refs/heads/master";
84 }
85
86 i = 1;
87 do {
88 struct pq_entry e = {
89 .rec = &recs[i],
90 .index = i,
91 };
92
93 merged_iter_pqueue_add(&pq, &e);
94 merged_iter_pqueue_check(&pq);
95 i = (i * 7) % N;
96 } while (i != 1);
97
98 for (i = N - 1; i > 0; i--) {
99 struct pq_entry top = merged_iter_pqueue_top(pq);
100 struct pq_entry e;
101
102 cl_assert_equal_i(merged_iter_pqueue_remove(&pq, &e), 0);
103 merged_iter_pqueue_check(&pq);
104
105 cl_assert(pq_entry_equal(&top, &e));
106 cl_assert(reftable_record_type(e.rec) == REFTABLE_BLOCK_TYPE_REF);
107 cl_assert_equal_i(e.index, i);
108 if (last)
109 cl_assert_equal_s(last, e.rec->u.ref.refname);
110 last = e.rec->u.ref.refname;
111 }
112
113 merged_iter_pqueue_release(&pq);
114 }
115
116 void test_reftable_pq__merged_iter_pqueue_top(void)
117 {
118 struct merged_iter_pqueue pq = { 0 };
119 struct reftable_record recs[13];
120 size_t N = ARRAY_SIZE(recs), i;
121
122 for (i = 0; i < N; i++) {
123 cl_assert(!reftable_record_init(&recs[i],
124 REFTABLE_BLOCK_TYPE_REF));
125 recs[i].u.ref.refname = (char *) "refs/heads/master";
126 }
127
128 i = 1;
129 do {
130 struct pq_entry e = {
131 .rec = &recs[i],
132 .index = i,
133 };
134
135 merged_iter_pqueue_add(&pq, &e);
136 merged_iter_pqueue_check(&pq);
137 i = (i * 7) % N;
138 } while (i != 1);
139
140 for (i = N - 1; i > 0; i--) {
141 struct pq_entry top = merged_iter_pqueue_top(pq);
142 struct pq_entry e;
143
144 cl_assert_equal_i(merged_iter_pqueue_remove(&pq, &e), 0);
145
146 merged_iter_pqueue_check(&pq);
147 cl_assert(pq_entry_equal(&top, &e) != 0);
148 cl_assert(reftable_record_equal(top.rec, &recs[i], REFTABLE_HASH_SIZE_SHA1) != 0);
149 for (size_t j = 0; i < pq.len; j++) {
150 cl_assert(pq_less(&top, &pq.heap[j]) != 0);
151 cl_assert(top.index > j);
152 }
153 }
154
155 merged_iter_pqueue_release(&pq);
156 }