git

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 "pq.h"
10

11
#include "reftable-record.h"
12
#include "system.h"
13
#include "basics.h"
14

15
int pq_less(struct pq_entry *a, struct pq_entry *b)
16
{
17
	int cmp = reftable_record_cmp(a->rec, b->rec);
18
	if (cmp == 0)
19
		return a->index > b->index;
20
	return cmp < 0;
21
}
22

23
struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
24
{
25
	size_t i = 0;
26
	struct pq_entry e = pq->heap[0];
27
	pq->heap[0] = pq->heap[pq->len - 1];
28
	pq->len--;
29

30
	while (i < pq->len) {
31
		size_t min = i;
32
		size_t j = 2 * i + 1;
33
		size_t k = 2 * i + 2;
34
		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
35
			min = j;
36
		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
37
			min = k;
38
		if (min == i)
39
			break;
40
		SWAP(pq->heap[i], pq->heap[min]);
41
		i = min;
42
	}
43

44
	return e;
45
}
46

47
void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
48
{
49
	size_t i = 0;
50

51
	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
52
	pq->heap[pq->len++] = *e;
53

54
	i = pq->len - 1;
55
	while (i > 0) {
56
		size_t j = (i - 1) / 2;
57
		if (pq_less(&pq->heap[j], &pq->heap[i]))
58
			break;
59
		SWAP(pq->heap[j], pq->heap[i]);
60
		i = j;
61
	}
62
}
63

64
void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
65
{
66
	FREE_AND_NULL(pq->heap);
67
	memset(pq, 0, sizeof(*pq));
68
}
69