git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
81f7745f3612eb75a917df2d3e0c7efd99d5b980 blob 2138 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.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_clear(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 81f7745f36 ...
found 81f7745f36 in https://public-inbox.org/git/4e38db7f48295c4e6d729880f5f1a63b0f90274e.1601568664.git.gitgitgadget@gmail.com/

applying [1/1] https://public-inbox.org/git/4e38db7f48295c4e6d729880f5f1a63b0f90274e.1601568664.git.gitgitgadget@gmail.com/
diff --git a/reftable/pq.c b/reftable/pq.c
new file mode 100644
index 0000000000..81f7745f36

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

index at:
100644 81f7745f3612eb75a917df2d3e0c7efd99d5b980	reftable/pq.c

git@vger.kernel.org list mirror (unofficial, one of many)

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V1 git git/ https://public-inbox.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://7fh6tueqddpjyxjmgtdiueylzoqt6pt7hec3pukyptlmohoowvhde4yd.onion/inbox.comp.version-control.git
	nntp://ie5yzdi7fg72h7s4sdcztq5evakq23rdt33mfyfcddc5u3ndnw24ogqd.onion/inbox.comp.version-control.git
	nntp://4uok3hntl7oi7b4uf4rtfwefqeexfzil2w6kgk2jn5z2f764irre7byd.onion/inbox.comp.version-control.git
	nntp://news.gmane.io/gmane.comp.version-control.git
 note: .onion URLs require Tor: https://www.torproject.org/

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

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

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git