revwalk.c 19.2 KB
Newer Older
1
/*
schu committed
2
 * Copyright (C) 2009-2012 the libgit2 contributors
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
6 7
 */

8
#include "common.h"
9
#include "commit.h"
Vicent Marti committed
10
#include "odb.h"
11
#include "pqueue.h"
12
#include "pool.h"
13
#include "oidmap.h"
14

15
#include "git2/revwalk.h"
16
#include "git2/merge.h"
17

18 19
#include <regex.h>

20
GIT__USE_OIDMAP;
21

22 23 24 25 26
#define PARENT1  (1 << 0)
#define PARENT2  (1 << 1)
#define RESULT   (1 << 2)
#define STALE    (1 << 3)

27 28 29 30 31 32
typedef struct commit_object {
	git_oid oid;
	uint32_t time;
	unsigned int seen:1,
			 uninteresting:1,
			 topo_delay:1,
33 34
			 parsed:1,
			 flags : 4;
35 36 37 38 39 40 41 42 43 44 45 46 47 48

	unsigned short in_degree;
	unsigned short out_degree;

	struct commit_object **parents;
} commit_object;

typedef struct commit_list {
	commit_object *item;
	struct commit_list *next;
} commit_list;

struct git_revwalk {
	git_repository *repo;
49
	git_odb *odb;
50

51
	git_oidmap *commits;
52
	git_pool commit_pool;
53 54 55 56 57 58 59 60 61 62 63

	commit_list *iterator_topo;
	commit_list *iterator_rand;
	commit_list *iterator_reverse;
	git_pqueue iterator_time;

	int (*get_next)(commit_object **, git_revwalk *);
	int (*enqueue)(git_revwalk *, commit_object *);

	unsigned walking:1;
	unsigned int sorting;
64 65 66 67

	/* merge base calculation */
	commit_object *one;
	git_vector twos;
68 69
};

70 71 72 73 74 75 76 77
static int commit_time_cmp(void *a, void *b)
{
	commit_object *commit_a = (commit_object *)a;
	commit_object *commit_b = (commit_object *)b;

	return (commit_a->time < commit_b->time);
}

78
static commit_list *commit_list_insert(commit_object *item, commit_list **list_p)
79 80
{
	commit_list *new_list = git__malloc(sizeof(commit_list));
81 82 83 84
	if (new_list != NULL) {
		new_list->item = item;
		new_list->next = *list_p;
	}
85 86 87 88
	*list_p = new_list;
	return new_list;
}

89 90 91 92 93 94 95 96 97 98 99 100 101 102
static commit_list *commit_list_insert_by_date(commit_object *item, commit_list **list_p)
{
	commit_list **pp = list_p;
	commit_list *p;

	while ((p = *pp) != NULL) {
		if (commit_time_cmp(p->item, item) < 0)
			break;

		pp = &p->next;
	}

	return commit_list_insert(item, pp);
}
103
static void commit_list_free(commit_list **list_p)
104
{
105 106
	commit_list *list = *list_p;

107 108 109
	if (list == NULL)
		return;

110 111 112
	while (list) {
		commit_list *temp = list;
		list = temp->next;
113
		git__free(temp);
114
	}
115 116

	*list_p = NULL;
117 118
}

119
static commit_object *commit_list_pop(commit_list **stack)
120 121 122 123 124 125
{
	commit_list *top = *stack;
	commit_object *item = top ? top->item : NULL;

	if (top) {
		*stack = top->next;
126
		git__free(top);
127 128 129 130
	}
	return item;
}

131 132 133
#define PARENTS_PER_COMMIT	2
#define COMMIT_ALLOC \
	(sizeof(commit_object) + PARENTS_PER_COMMIT * sizeof(commit_object *))
134 135 136

static commit_object *alloc_commit(git_revwalk *walk)
{
137
	return (commit_object *)git_pool_malloc(&walk->commit_pool, COMMIT_ALLOC);
138 139
}

140 141
static commit_object **alloc_parents(
	git_revwalk *walk, commit_object *commit, size_t n_parents)
142 143
{
	if (n_parents <= PARENTS_PER_COMMIT)
144
		return (commit_object **)((char *)commit + sizeof(commit_object));
145

146
	return (commit_object **)git_pool_malloc(
Russell Belfer committed
147
		&walk->commit_pool, (uint32_t)(n_parents * sizeof(commit_object *)));
148 149
}

150

151
static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
152
{
153
	commit_object *commit;
154 155
	khiter_t pos;
	int ret;
156

157 158 159 160
	/* lookup and reserve space if not already present */
	pos = kh_get(oid, walk->commits, oid);
	if (pos != kh_end(walk->commits))
		return kh_value(walk->commits, pos);
161

162
	commit = alloc_commit(walk);
163 164
	if (commit == NULL)
		return NULL;
165

166
	git_oid_cpy(&commit->oid, oid);
167

168 169 170
	pos = kh_put(oid, walk->commits, &commit->oid, &ret);
	assert(ret != 0);
	kh_value(walk->commits, pos) = commit;
171 172

	return commit;
173
}
174

175 176 177 178 179 180 181 182 183 184 185
static int commit_error(commit_object *commit, const char *msg)
{
	char commit_oid[GIT_OID_HEXSZ + 1];
	git_oid_fmt(commit_oid, &commit->oid);
	commit_oid[GIT_OID_HEXSZ] = '\0';

	giterr_set(GITERR_ODB, "Failed to parse commit %s - %s", commit_oid, msg);

	return -1;
}

186
static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)
187
{
188
	const size_t parent_len = strlen("parent ") + GIT_OID_HEXSZ + 1;
189 190
	unsigned char *buffer = raw->data;
	unsigned char *buffer_end = buffer + raw->len;
191
	unsigned char *parents_start, *committer_start;
192
	int i, parents = 0;
193
	int commit_time;
194

195
	buffer += strlen("tree ") + GIT_OID_HEXSZ + 1;
196

197
	parents_start = buffer;
198
	while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", strlen("parent ")) == 0) {
199 200 201
		parents++;
		buffer += parent_len;
	}
202

203
	commit->parents = alloc_parents(walk, commit, parents);
204
	GITERR_CHECK_ALLOC(commit->parents);
205

206 207 208
	buffer = parents_start;
	for (i = 0; i < parents; ++i) {
		git_oid oid;
209

210 211
		if (git_oid_fromstr(&oid, (char *)buffer + strlen("parent ")) < 0)
			return -1;
212

213 214
		commit->parents[i] = commit_lookup(walk, &oid);
		if (commit->parents[i] == NULL)
215
			return -1;
216

217 218
		buffer += parent_len;
	}
219

220
	commit->out_degree = (unsigned short)parents;
221

222 223 224 225 226
	if ((committer_start = buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
		return commit_error(commit, "object is corrupted");

	buffer++;

227 228
	if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
		return commit_error(commit, "object is corrupted");
229

230 231 232 233 234 235 236
	/* Skip trailing spaces */
	while (buffer > committer_start && git__isspace(*buffer))
		buffer--;

	/* Seek for the begining of the pack of digits */
	while (buffer > committer_start && git__isdigit(*buffer))
		buffer--;
237

238 239 240 241 242 243 244 245 246 247
	/* Skip potential timezone offset */
	if ((buffer > committer_start) && (*buffer == '+' || *buffer == '-')) {
		buffer--;

		while (buffer > committer_start && git__isspace(*buffer))
			buffer--;

		while (buffer > committer_start && git__isdigit(*buffer))
			buffer--;
	}
248

249
	if ((buffer == committer_start) || (git__strtol32(&commit_time, (char *)(buffer + 1), NULL, 10) < 0))
250
		return commit_error(commit, "cannot parse commit time");
251

252
	commit->time = (time_t)commit_time;
253
	commit->parsed = 1;
254
	return 0;
255
}
256

257
static int commit_parse(git_revwalk *walk, commit_object *commit)
258
{
Vicent Marti committed
259
	git_odb_object *obj;
260
	int error;
261

262
	if (commit->parsed)
263
		return 0;
264

265
	if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < 0)
266
		return error;
267

Vicent Marti committed
268
	if (obj->raw.type != GIT_OBJ_COMMIT) {
269
		git_odb_object_free(obj);
270 271
		giterr_set(GITERR_INVALID, "Failed to parse commit. Object is no commit object");
		return -1;
272
	}
273

Vicent Marti committed
274
	error = commit_quick_parse(walk, commit, &obj->raw);
275
	git_odb_object_free(obj);
276
	return error;
277 278
}

279
static int interesting(git_pqueue *list)
280
{
281 282 283 284 285
	unsigned int i;
	for (i = 1; i < git_pqueue_size(list); i++) {
		commit_object *commit = list->d[i];
		if ((commit->flags & STALE) == 0)
			return 1;
286 287
	}

288
	return 0;
289 290 291 292 293 294 295
}

static int merge_bases_many(commit_list **out, git_revwalk *walk, commit_object *one, git_vector *twos)
{
	int error;
	unsigned int i;
	commit_object *two;
296 297
	commit_list *result = NULL, *tmp = NULL;
	git_pqueue list;
298 299 300 301

	/* if the commit is repeated, we have a our merge base already */
	git_vector_foreach(twos, i, two) {
		if (one == two)
302
			return commit_list_insert(one, out) ? 0 : -1;
303 304
	}

305 306 307 308 309
	if (git_pqueue_init(&list, twos->length * 2, commit_time_cmp) < 0)
		return -1;

	if (commit_parse(walk, one) < 0)
	    return -1;
310 311

	one->flags |= PARENT1;
312 313
	if (git_pqueue_insert(&list, one) < 0)
		return -1;
314 315 316 317

	git_vector_foreach(twos, i, two) {
		commit_parse(walk, two);
		two->flags |= PARENT2;
318 319
		if (git_pqueue_insert(&list, two) < 0)
			return -1;
320 321 322
	}

	/* as long as there are non-STALE commits */
323 324
	while (interesting(&list)) {
		commit_object *commit;
325 326
		int flags;

327
		commit = git_pqueue_pop(&list);
328 329 330 331 332

		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
		if (flags == (PARENT1 | PARENT2)) {
			if (!(commit->flags & RESULT)) {
				commit->flags |= RESULT;
333 334
				if (commit_list_insert(commit, &result) == NULL)
					return -1;
335 336 337 338 339 340 341 342 343 344
			}
			/* we mark the parents of a merge stale */
			flags |= STALE;
		}

		for (i = 0; i < commit->out_degree; i++) {
			commit_object *p = commit->parents[i];
			if ((p->flags & flags) == flags)
				continue;

345
			if ((error = commit_parse(walk, p)) < 0)
346 347 348
				return error;

			p->flags |= flags;
349 350
			if (git_pqueue_insert(&list, p) < 0)
				return -1;
351 352 353
		}
	}

354
	git_pqueue_free(&list);
355

356
	/* filter out any stale commits in the results */
357
	tmp = result;
358 359
	result = NULL;

360 361 362 363 364
	while (tmp) {
		struct commit_list *next = tmp->next;
		if (!(tmp->item->flags & STALE))
			if (commit_list_insert_by_date(tmp->item, &result) == NULL)
				return -1;
365

366 367
		git__free(tmp);
		tmp = next;
368 369 370
	}

	*out = result;
371
	return 0;
372 373
}

374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426
int git_merge_base_many(git_oid *out, git_repository *repo, const git_oid input_array[], size_t length)
{
	git_revwalk *walk;
	git_vector list;
	commit_list *result = NULL;
	int error = -1;
	unsigned int i;
	commit_object *commit;

	assert(out && repo && input_array);

	if (length < 2) {
		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %u.", length);
		return -1;
	}

	if (git_vector_init(&list, length - 1, NULL) < 0)
		return -1;

	if (git_revwalk_new(&walk, repo) < 0)
		goto cleanup;

	for (i = 1; i < length; i++) {
		commit = commit_lookup(walk, &input_array[i]);
		if (commit == NULL)
			goto cleanup;

		git_vector_insert(&list, commit);
	}

	commit = commit_lookup(walk, &input_array[0]);
	if (commit == NULL)
		goto cleanup;

	if (merge_bases_many(&result, walk, commit, &list) < 0)
		goto cleanup;

	if (!result) {
		error = GIT_ENOTFOUND;
		goto cleanup;
	}

	git_oid_cpy(out, &result->item->oid);

	error = 0;

cleanup:
	commit_list_free(&result);
	git_revwalk_free(walk);
	git_vector_free(&list);
	return error;
}

427 428 429 430
int git_merge_base(git_oid *out, git_repository *repo, git_oid *one, git_oid *two)
{
	git_revwalk *walk;
	git_vector list;
431
	commit_list *result = NULL;
432 433 434
	commit_object *commit;
	void *contents[1];

435 436
	if (git_revwalk_new(&walk, repo) < 0)
		return -1;
437 438 439

	commit = commit_lookup(walk, two);
	if (commit == NULL)
440
		goto on_error;
441 442 443 444 445 446 447 448 449

	/* This is just one value, so we can do it on the stack */
	memset(&list, 0x0, sizeof(git_vector));
	contents[0] = commit;
	list.length = 1;
	list.contents = contents;

	commit = commit_lookup(walk, one);
	if (commit == NULL)
450
		goto on_error;
451

452 453
	if (merge_bases_many(&result, walk, commit, &list) < 0)
		goto on_error;
454

455 456
	if (!result) {
		git_revwalk_free(walk);
457
		return GIT_ENOTFOUND;
458
	}
459 460 461 462 463

	git_oid_cpy(out, &result->item->oid);
	commit_list_free(&result);
	git_revwalk_free(walk);

464 465 466 467 468
	return 0;

on_error:
	git_revwalk_free(walk);
	return -1;
469 470
}

471
static void mark_uninteresting(commit_object *commit)
472
{
473 474
	unsigned short i;
	assert(commit);
475

476
	commit->uninteresting = 1;
477

478 479 480 481
	/* This means we've reached a merge base, so there's no need to walk any more */
	if ((commit->flags & (RESULT | STALE)) == RESULT)
		return;

482 483 484
	for (i = 0; i < commit->out_degree; ++i)
		if (!commit->parents[i]->uninteresting)
			mark_uninteresting(commit->parents[i]);
485
}
486

487
static int process_commit(git_revwalk *walk, commit_object *commit, int hide)
488
{
489 490
	int error;

491 492 493
	if (hide)
		mark_uninteresting(commit);

494
	if (commit->seen)
495
		return 0;
496

497
	commit->seen = 1;
498

499 500
	if ((error = commit_parse(walk, commit)) < 0)
		return error;
501

502 503
	return walk->enqueue(walk, commit);
}
504

505 506 507
static int process_commit_parents(git_revwalk *walk, commit_object *commit)
{
	unsigned short i;
508
	int error = 0;
509

510 511
	for (i = 0; i < commit->out_degree && !error; ++i)
		error = process_commit(walk, commit->parents[i], commit->uninteresting);
512

513
	return error;
514 515
}

516
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
517
{
518
	commit_object *commit;
519

520 521
	commit = commit_lookup(walk, oid);
	if (commit == NULL)
522
		return -1; /* error already reported by failed lookup */
523

524 525 526 527
	commit->uninteresting = uninteresting;
	if (walk->one == NULL && !uninteresting) {
		walk->one = commit;
	} else {
528 529
		if (git_vector_insert(&walk->twos, commit) < 0)
			return -1;
530 531
	}

532
	return 0;
533 534
}

535 536 537 538 539
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
	return push_commit(walk, oid, 0);
}
540

541

542 543 544 545 546
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
	return push_commit(walk, oid, 1);
}
547

548 549
static int push_ref(git_revwalk *walk, const char *refname, int hide)
{
550
	git_oid oid;
551

552
	if (git_reference_name_to_oid(&oid, walk->repo, refname) < 0)
553 554
		return -1;

555
	return push_commit(walk, &oid, hide);
556 557
}

558 559 560 561 562 563 564 565 566
struct push_cb_data {
	git_revwalk *walk;
	int hide;
};

static int push_glob_cb(const char *refname, void *data_)
{
	struct push_cb_data *data = (struct push_cb_data *)data_;

567
	return push_ref(data->walk, refname, data->hide);
568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587
}

static int push_glob(git_revwalk *walk, const char *glob, int hide)
{
	git_buf buf = GIT_BUF_INIT;
	struct push_cb_data data;
	regex_t preg;

	assert(walk && glob);

	/* refs/ is implied if not given in the glob */
	if (strncmp(glob, GIT_REFS_DIR, strlen(GIT_REFS_DIR))) {
		git_buf_printf(&buf, GIT_REFS_DIR "%s", glob);
	} else {
		git_buf_puts(&buf, glob);
	}

	/* If no '?', '*' or '[' exist, we append '/ *' to the glob */
	memset(&preg, 0x0, sizeof(regex_t));
	if (regcomp(&preg, "[?*[]", REG_EXTENDED)) {
588 589 590
		giterr_set(GITERR_OS, "Regex failed to compile");
		git_buf_free(&buf);
		return -1;
591 592 593 594 595
	}

	if (regexec(&preg, glob, 0, NULL, 0))
		git_buf_puts(&buf, "/*");

596 597
	if (git_buf_oom(&buf))
		goto on_error;
598 599 600 601

	data.walk = walk;
	data.hide = hide;

602 603
	if (git_reference_foreach_glob(
		walk->repo, git_buf_cstr(&buf), GIT_REF_LISTALL, push_glob_cb, &data) < 0)
604
		goto on_error;
605 606 607

	regfree(&preg);
	git_buf_free(&buf);
608 609 610 611 612 613
	return 0;

on_error:
	regfree(&preg);
	git_buf_free(&buf);
	return -1;
614 615 616 617 618 619 620 621 622 623 624 625 626 627
}

int git_revwalk_push_glob(git_revwalk *walk, const char *glob)
{
	assert(walk && glob);
	return push_glob(walk, glob, 0);
}

int git_revwalk_hide_glob(git_revwalk *walk, const char *glob)
{
	assert(walk && glob);
	return push_glob(walk, glob, 1);
}

628 629 630
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
631
	return push_ref(walk, GIT_HEAD_FILE, 0);
632 633 634 635 636
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
637 638 639 640 641 642 643 644 645 646 647 648 649
	return push_ref(walk, GIT_HEAD_FILE, 1);
}

int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
	return push_ref(walk, refname, 0);
}

int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
	return push_ref(walk, refname, 1);
650 651
}

652
static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
653
{
654 655
	return git_pqueue_insert(&walk->iterator_time, commit);
}
656

657 658
static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
{
659
	return commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
660
}
661

662 663 664 665
static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
{
	int error;
	commit_object *next;
666

667
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
668
		if ((error = process_commit_parents(walk, next)) < 0)
669
			return error;
670

671 672
		if (!next->uninteresting) {
			*object_out = next;
673
			return 0;
674
		}
675
	}
676

677
	return GIT_REVWALKOVER;
678 679
}

680
static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
681
{
682 683
	int error;
	commit_object *next;
684

685
	while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
686
		if ((error = process_commit_parents(walk, next)) < 0)
687
			return error;
688

689 690
		if (!next->uninteresting) {
			*object_out = next;
691
			return 0;
692
		}
693 694
	}

695
	return GIT_REVWALKOVER;
696
}
697

698
static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
699
{
700 701
	commit_object *next;
	unsigned short i;
702

703 704 705
	for (;;) {
		next = commit_list_pop(&walk->iterator_topo);
		if (next == NULL)
706
			return GIT_REVWALKOVER;
707

708 709 710 711
		if (next->in_degree > 0) {
			next->topo_delay = 1;
			continue;
		}
712

713 714
		for (i = 0; i < next->out_degree; ++i) {
			commit_object *parent = next->parents[i];
715

716 717
			if (--parent->in_degree == 0 && parent->topo_delay) {
				parent->topo_delay = 0;
718
				if (commit_list_insert(parent, &walk->iterator_topo) == NULL)
719
					return -1;
720 721
			}
		}
722

723
		*object_out = next;
724
		return 0;
725
	}
726 727
}

728
static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
729
{
730
	*object_out = commit_list_pop(&walk->iterator_reverse);
731
	return *object_out ? 0 : GIT_REVWALKOVER;
732
}
733

734

735 736 737
static int prepare_walk(git_revwalk *walk)
{
	int error;
738 739 740 741
	unsigned int i;
	commit_object *next, *two;
	commit_list *bases = NULL;

742 743 744 745 746
	/*
	 * If walk->one is NULL, there were no positive references,
	 * so we know that the walk is already over.
	 */
	if (walk->one == NULL)
747
		return GIT_REVWALKOVER;
748

749
	/* first figure out what the merge bases are */
750 751
	if (merge_bases_many(&bases, walk, walk->one, &walk->twos) < 0)
		return -1;
752 753

	commit_list_free(&bases);
754 755
	if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
		return -1;
756 757

	git_vector_foreach(&walk->twos, i, two) {
758 759
		if (process_commit(walk, two, two->uninteresting) < 0)
			return -1;
760
	}
761

762 763
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
764

765
		while ((error = walk->get_next(&next, walk)) == 0) {
766 767 768 769
			for (i = 0; i < next->out_degree; ++i) {
				commit_object *parent = next->parents[i];
				parent->in_degree++;
			}
770

771
			if (commit_list_insert(next, &walk->iterator_topo) == NULL)
772
				return -1;
773
		}
774

775
		if (error != GIT_REVWALKOVER)
776
			return error;
777

778 779
		walk->get_next = &revwalk_next_toposort;
	}
780

781
	if (walk->sorting & GIT_SORT_REVERSE) {
782

783
		while ((error = walk->get_next(&next, walk)) == 0)
784
			if (commit_list_insert(next, &walk->iterator_reverse) == NULL)
785
				return -1;
786

787
		if (error != GIT_REVWALKOVER)
788
			return error;
789

790 791
		walk->get_next = &revwalk_next_reverse;
	}
792

793
	walk->walking = 1;
794
	return 0;
795
}
796 797


798 799 800 801 802 803 804 805



int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
	git_revwalk *walk;

	walk = git__malloc(sizeof(git_revwalk));
806
	GITERR_CHECK_ALLOC(walk);
807 808 809

	memset(walk, 0x0, sizeof(git_revwalk));

810
	walk->commits = git_oidmap_alloc();
811
	GITERR_CHECK_ALLOC(walk->commits);
812

813 814
	if (git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp) < 0 ||
		git_vector_init(&walk->twos, 4, NULL) < 0 ||
815 816
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
817
		return -1;
818 819 820 821 822 823

	walk->get_next = &revwalk_next_unsorted;
	walk->enqueue = &revwalk_enqueue_unsorted;

	walk->repo = repo;

824
	if (git_repository_odb(&walk->odb, repo) < 0) {
825
		git_revwalk_free(walk);
826
		return -1;
827 828
	}

829
	*revwalk_out = walk;
830
	return 0;
831 832 833 834 835 836 837 838
}

void git_revwalk_free(git_revwalk *walk)
{
	if (walk == NULL)
		return;

	git_revwalk_reset(walk);
839
	git_odb_free(walk->odb);
840

841
	git_oidmap_free(walk->commits);
842
	git_pool_clear(&walk->commit_pool);
843
	git_pqueue_free(&walk->iterator_time);
844
	git_vector_free(&walk->twos);
845
	git__free(walk);
846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871
}

git_repository *git_revwalk_repository(git_revwalk *walk)
{
	assert(walk);
	return walk->repo;
}

void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
{
	assert(walk);

	if (walk->walking)
		git_revwalk_reset(walk);

	walk->sorting = sort_mode;

	if (walk->sorting & GIT_SORT_TIME) {
		walk->get_next = &revwalk_next_timesort;
		walk->enqueue = &revwalk_enqueue_timesort;
	} else {
		walk->get_next = &revwalk_next_unsorted;
		walk->enqueue = &revwalk_enqueue_unsorted;
	}
}

872 873 874 875
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
	commit_object *next;
876

877
	assert(walk && oid);
878

879
	if (!walk->walking) {
880
		if ((error = prepare_walk(walk)) < 0)
881
			return error;
882
	}
883

884
	error = walk->get_next(&next, walk);
885

886
	if (error == GIT_REVWALKOVER) {
887
		git_revwalk_reset(walk);
888
		return GIT_REVWALKOVER;
889
	}
890

891 892
	if (!error)
		git_oid_cpy(oid, &next->oid);
893

894
	return error;
895 896
}

897
void git_revwalk_reset(git_revwalk *walk)
898
{
899
	commit_object *commit;
900

901
	assert(walk);
902

903
	kh_foreach_value(walk->commits, commit, {
904 905 906
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
907
		commit->uninteresting = 0;
908
		});
909

910
	git_pqueue_clear(&walk->iterator_time);
911 912 913
	commit_list_free(&walk->iterator_topo);
	commit_list_free(&walk->iterator_rand);
	commit_list_free(&walk->iterator_reverse);
914
	walk->walking = 0;
915 916 917

	walk->one = NULL;
	git_vector_clear(&walk->twos);
918
}
919