git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
8918d158e2d46ea46274483feec66ed1d4e7a3f4 blob 2147 bytes (raw)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
/*
Copyright 2020 Google LLC

Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file or at
https://developers.google.com/open-source/licenses/bsd
*/

#include "pq.h"

#include "reftable-record.h"
#include "system.h"
#include "basics.h"

static int pq_less(struct pq_entry a, struct pq_entry b)
{
	struct strbuf ak = STRBUF_INIT;
	struct strbuf bk = STRBUF_INIT;
	int cmp = 0;
	reftable_record_key(&a.rec, &ak);
	reftable_record_key(&b.rec, &bk);

	cmp = strbuf_cmp(&ak, &bk);

	strbuf_release(&ak);
	strbuf_release(&bk);

	if (cmp == 0)
		return a.index > b.index;

	return cmp < 0;
}

struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)
{
	return pq.heap[0];
}

int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)
{
	return pq.len == 0;
}

void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
{
	int i = 0;
	for (i = 1; i < pq.len; i++) {
		int parent = (i - 1) / 2;

		assert(pq_less(pq.heap[parent], pq.heap[i]));
	}
}

struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
{
	int i = 0;
	struct pq_entry e = pq->heap[0];
	pq->heap[0] = pq->heap[pq->len - 1];
	pq->len--;

	i = 0;
	while (i < pq->len) {
		int min = i;
		int j = 2 * i + 1;
		int k = 2 * i + 2;
		if (j < pq->len && pq_less(pq->heap[j], pq->heap[i])) {
			min = j;
		}
		if (k < pq->len && pq_less(pq->heap[k], pq->heap[min])) {
			min = k;
		}

		if (min == i) {
			break;
		}

		SWAP(pq->heap[i], pq->heap[min]);
		i = min;
	}

	return e;
}

void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)
{
	int i = 0;
	if (pq->len == pq->cap) {
		pq->cap = 2 * pq->cap + 1;
		pq->heap = reftable_realloc(pq->heap,
					    pq->cap * sizeof(struct pq_entry));
	}

	pq->heap[pq->len++] = e;
	i = pq->len - 1;
	while (i > 0) {
		int j = (i - 1) / 2;
		if (pq_less(pq->heap[j], pq->heap[i])) {
			break;
		}

		SWAP(pq->heap[j], pq->heap[i]);

		i = j;
	}
}

void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
{
	int i = 0;
	for (i = 0; i < pq->len; i++) {
		reftable_record_destroy(&pq->heap[i].rec);
	}
	FREE_AND_NULL(pq->heap);
	pq->len = pq->cap = 0;
}
debug log:

solving 8918d158e2d4 ...
found 8918d158e2d4 in https://public-inbox.org/git/0a6119d910a3f83e6c9c421acd1316b496e6612b.1618255553.git.gitgitgadget@gmail.com/ ||
	https://public-inbox.org/git/84578b666a40068c739d8131ddcd53136d83719b.1618832277.git.gitgitgadget@gmail.com/ ||
	https://public-inbox.org/git/28aa69f7bbcba22b67d7a0300ce62538e3189b95.1615580397.git.gitgitgadget@gmail.com/

applying [1/3] https://public-inbox.org/git/0a6119d910a3f83e6c9c421acd1316b496e6612b.1618255553.git.gitgitgadget@gmail.com/
diff --git a/reftable/pq.c b/reftable/pq.c
new file mode 100644
index 000000000000..8918d158e2d4

Checking patch reftable/pq.c...
Applied patch reftable/pq.c cleanly.

skipping https://public-inbox.org/git/84578b666a40068c739d8131ddcd53136d83719b.1618832277.git.gitgitgadget@gmail.com/ for 8918d158e2d4
skipping https://public-inbox.org/git/28aa69f7bbcba22b67d7a0300ce62538e3189b95.1615580397.git.gitgitgadget@gmail.com/ for 8918d158e2d4
index at:
100644 8918d158e2d46ea46274483feec66ed1d4e7a3f4	reftable/pq.c

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).