]> git.ipfire.org Git - thirdparty/git.git/blame - reftable/pq_test.c
Merge branch 'jk/clone-allow-bare-and-o-together'
[thirdparty/git.git] / reftable / pq_test.c
CommitLineData
3b34f636
HWN
1/*
2Copyright 2020 Google LLC
3
4Use of this source code is governed by a BSD-style
5license that can be found in the LICENSE file or at
6https://developers.google.com/open-source/licenses/bsd
7*/
8
9#include "system.h"
10
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"
17
18void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
19{
20 int i;
21 for (i = 1; i < pq.len; i++) {
22 int parent = (i - 1) / 2;
23
24 EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
25 }
26}
27
28static void test_pq(void)
29{
30 char *names[54] = { NULL };
31 int N = ARRAY_SIZE(names) - 1;
32
33 struct merged_iter_pqueue pq = { NULL };
66c0daba 34 char *last = NULL;
3b34f636
HWN
35
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);
41 }
42
43 i = 1;
44 do {
66c0daba
HWN
45 struct pq_entry e = { .rec = { .type = BLOCK_TYPE_REF,
46 .u.ref = {
47 .refname = names[i],
48 } } };
c18eecbe 49 merged_iter_pqueue_add(&pq, &e);
3b34f636
HWN
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 e = merged_iter_pqueue_remove(&pq);
66c0daba 56 struct reftable_record *rec = &e.rec;
3b34f636
HWN
57 merged_iter_pqueue_check(pq);
58
66c0daba 59 EXPECT(reftable_record_type(rec) == BLOCK_TYPE_REF);
3b34f636 60 if (last) {
66c0daba 61 EXPECT(strcmp(last, rec->u.ref.refname) < 0);
3b34f636 62 }
66c0daba
HWN
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);
3b34f636 67 }
3b34f636
HWN
68 for (i = 0; i < N; i++) {
69 reftable_free(names[i]);
70 }
71
72 merged_iter_pqueue_release(&pq);
73}
74
75int pq_test_main(int argc, const char *argv[])
76{
77 RUN_TEST(test_pq);
78 return 0;
79}