revwalk.c 19.5 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
	assert(obj->raw.type == GIT_OBJ_COMMIT);
268

Vicent Marti committed
269
	error = commit_quick_parse(walk, commit, &obj->raw);
270
	git_odb_object_free(obj);
271
	return error;
272 273
}

274
static int interesting(git_pqueue *list)
275
{
276
	unsigned int i;
277 278
	/* element 0 isn't used - we need to start at 1 */
	for (i = 1; i < list->size; i++) {
279 280 281
		commit_object *commit = list->d[i];
		if ((commit->flags & STALE) == 0)
			return 1;
282 283
	}

284
	return 0;
285 286 287 288 289 290 291
}

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;
292 293
	commit_list *result = NULL, *tmp = NULL;
	git_pqueue list;
294 295 296 297

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

301 302 303 304 305
	if (git_pqueue_init(&list, twos->length * 2, commit_time_cmp) < 0)
		return -1;

	if (commit_parse(walk, one) < 0)
	    return -1;
306 307

	one->flags |= PARENT1;
308 309
	if (git_pqueue_insert(&list, one) < 0)
		return -1;
310 311 312 313

	git_vector_foreach(twos, i, two) {
		commit_parse(walk, two);
		two->flags |= PARENT2;
314 315
		if (git_pqueue_insert(&list, two) < 0)
			return -1;
316 317 318
	}

	/* as long as there are non-STALE commits */
319 320
	while (interesting(&list)) {
		commit_object *commit;
321 322
		int flags;

323
		commit = git_pqueue_pop(&list);
324 325 326 327 328

		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
		if (flags == (PARENT1 | PARENT2)) {
			if (!(commit->flags & RESULT)) {
				commit->flags |= RESULT;
329 330
				if (commit_list_insert(commit, &result) == NULL)
					return -1;
331 332 333 334 335 336 337 338 339 340
			}
			/* 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;

341
			if ((error = commit_parse(walk, p)) < 0)
342 343 344
				return error;

			p->flags |= flags;
345 346
			if (git_pqueue_insert(&list, p) < 0)
				return -1;
347 348 349
		}
	}

350
	git_pqueue_free(&list);
351

352
	/* filter out any stale commits in the results */
353
	tmp = result;
354 355
	result = NULL;

356 357 358 359 360
	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;
361

362 363
		git__free(tmp);
		tmp = next;
364 365 366
	}

	*out = result;
367
	return 0;
368 369
}

370 371 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
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;
}

423
int git_merge_base(git_oid *out, git_repository *repo, const git_oid *one, const git_oid *two)
424 425 426
{
	git_revwalk *walk;
	git_vector list;
427
	commit_list *result = NULL;
428 429 430
	commit_object *commit;
	void *contents[1];

431 432
	if (git_revwalk_new(&walk, repo) < 0)
		return -1;
433 434 435

	commit = commit_lookup(walk, two);
	if (commit == NULL)
436
		goto on_error;
437 438 439 440 441 442 443 444 445

	/* 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)
446
		goto on_error;
447

448 449
	if (merge_bases_many(&result, walk, commit, &list) < 0)
		goto on_error;
450

451 452
	if (!result) {
		git_revwalk_free(walk);
Russell Belfer committed
453
		giterr_clear();
454
		return GIT_ENOTFOUND;
455
	}
456 457 458 459 460

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

461 462 463 464 465
	return 0;

on_error:
	git_revwalk_free(walk);
	return -1;
466 467
}

468
static void mark_uninteresting(commit_object *commit)
469
{
470 471
	unsigned short i;
	assert(commit);
472

473
	commit->uninteresting = 1;
474

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

479 480 481
	for (i = 0; i < commit->out_degree; ++i)
		if (!commit->parents[i]->uninteresting)
			mark_uninteresting(commit->parents[i]);
482
}
483

484
static int process_commit(git_revwalk *walk, commit_object *commit, int hide)
485
{
486 487
	int error;

488 489 490
	if (hide)
		mark_uninteresting(commit);

491
	if (commit->seen)
492
		return 0;
493

494
	commit->seen = 1;
495

496 497
	if ((error = commit_parse(walk, commit)) < 0)
		return error;
498

499 500
	return walk->enqueue(walk, commit);
}
501

502 503 504
static int process_commit_parents(git_revwalk *walk, commit_object *commit)
{
	unsigned short i;
505
	int error = 0;
506

507 508
	for (i = 0; i < commit->out_degree && !error; ++i)
		error = process_commit(walk, commit->parents[i], commit->uninteresting);
509

510
	return error;
511 512
}

513
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
514
{
515 516
	git_object *obj;
	git_otype type;
517
	commit_object *commit;
518

519 520 521 522 523 524 525 526 527 528 529
	if (git_object_lookup(&obj, walk->repo, oid, GIT_OBJ_ANY) < 0)
		return -1;

	type = git_object_type(obj);
	git_object_free(obj);

	if (type != GIT_OBJ_COMMIT) {
		giterr_set(GITERR_INVALID, "Object is no commit object");
		return -1;
	}

530 531
	commit = commit_lookup(walk, oid);
	if (commit == NULL)
532
		return -1; /* error already reported by failed lookup */
533

534 535 536 537
	commit->uninteresting = uninteresting;
	if (walk->one == NULL && !uninteresting) {
		walk->one = commit;
	} else {
538 539
		if (git_vector_insert(&walk->twos, commit) < 0)
			return -1;
540 541
	}

542
	return 0;
543 544
}

545 546 547 548 549
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
	return push_commit(walk, oid, 0);
}
550

551

552 553 554 555 556
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
	return push_commit(walk, oid, 1);
}
557

558 559
static int push_ref(git_revwalk *walk, const char *refname, int hide)
{
560
	git_oid oid;
561

562
	if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
563 564
		return -1;

565
	return push_commit(walk, &oid, hide);
566 567
}

568 569 570 571 572 573 574 575 576
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_;

577
	return push_ref(data->walk, refname, data->hide);
578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597
}

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)) {
598 599 600
		giterr_set(GITERR_OS, "Regex failed to compile");
		git_buf_free(&buf);
		return -1;
601 602 603 604 605
	}

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

606 607
	if (git_buf_oom(&buf))
		goto on_error;
608 609 610 611

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

612 613
	if (git_reference_foreach_glob(
		walk->repo, git_buf_cstr(&buf), GIT_REF_LISTALL, push_glob_cb, &data) < 0)
614
		goto on_error;
615 616 617

	regfree(&preg);
	git_buf_free(&buf);
618 619 620 621 622 623
	return 0;

on_error:
	regfree(&preg);
	git_buf_free(&buf);
	return -1;
624 625 626 627 628 629 630 631 632 633 634 635 636 637
}

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);
}

638 639 640
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
641
	return push_ref(walk, GIT_HEAD_FILE, 0);
642 643 644 645 646
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
647 648 649 650 651 652 653 654 655 656 657 658 659
	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);
660 661
}

662
static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
663
{
664 665
	return git_pqueue_insert(&walk->iterator_time, commit);
}
666

667 668
static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
{
669
	return commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
670
}
671

672 673 674 675
static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
{
	int error;
	commit_object *next;
676

677
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
678
		if ((error = process_commit_parents(walk, next)) < 0)
679
			return error;
680

681 682
		if (!next->uninteresting) {
			*object_out = next;
683
			return 0;
684
		}
685
	}
686

Russell Belfer committed
687 688
	giterr_clear();
	return GIT_ITEROVER;
689 690
}

691
static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
692
{
693 694
	int error;
	commit_object *next;
695

696
	while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
697
		if ((error = process_commit_parents(walk, next)) < 0)
698
			return error;
699

700 701
		if (!next->uninteresting) {
			*object_out = next;
702
			return 0;
703
		}
704 705
	}

Russell Belfer committed
706 707
	giterr_clear();
	return GIT_ITEROVER;
708
}
709

710
static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
711
{
712 713
	commit_object *next;
	unsigned short i;
714

715 716
	for (;;) {
		next = commit_list_pop(&walk->iterator_topo);
Russell Belfer committed
717 718 719 720
		if (next == NULL) {
			giterr_clear();
			return GIT_ITEROVER;
		}
721

722 723 724 725
		if (next->in_degree > 0) {
			next->topo_delay = 1;
			continue;
		}
726

727 728
		for (i = 0; i < next->out_degree; ++i) {
			commit_object *parent = next->parents[i];
729

730 731
			if (--parent->in_degree == 0 && parent->topo_delay) {
				parent->topo_delay = 0;
732
				if (commit_list_insert(parent, &walk->iterator_topo) == NULL)
733
					return -1;
734 735
			}
		}
736

737
		*object_out = next;
738
		return 0;
739
	}
740 741
}

742
static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
743
{
744
	*object_out = commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
745
	return *object_out ? 0 : GIT_ITEROVER;
746
}
747

748

749 750 751
static int prepare_walk(git_revwalk *walk)
{
	int error;
752 753 754 755
	unsigned int i;
	commit_object *next, *two;
	commit_list *bases = NULL;

756 757 758 759
	/*
	 * If walk->one is NULL, there were no positive references,
	 * so we know that the walk is already over.
	 */
Russell Belfer committed
760 761 762 763
	if (walk->one == NULL) {
		giterr_clear();
		return GIT_ITEROVER;
	}
764

765
	/* first figure out what the merge bases are */
766 767
	if (merge_bases_many(&bases, walk, walk->one, &walk->twos) < 0)
		return -1;
768 769

	commit_list_free(&bases);
770 771
	if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
		return -1;
772 773

	git_vector_foreach(&walk->twos, i, two) {
774 775
		if (process_commit(walk, two, two->uninteresting) < 0)
			return -1;
776
	}
777

778 779
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
780

781
		while ((error = walk->get_next(&next, walk)) == 0) {
782 783 784 785
			for (i = 0; i < next->out_degree; ++i) {
				commit_object *parent = next->parents[i];
				parent->in_degree++;
			}
786

787
			if (commit_list_insert(next, &walk->iterator_topo) == NULL)
788
				return -1;
789
		}
790

Russell Belfer committed
791
		if (error != GIT_ITEROVER)
792
			return error;
793

794 795
		walk->get_next = &revwalk_next_toposort;
	}
796

797
	if (walk->sorting & GIT_SORT_REVERSE) {
798

799
		while ((error = walk->get_next(&next, walk)) == 0)
800
			if (commit_list_insert(next, &walk->iterator_reverse) == NULL)
801
				return -1;
802

Russell Belfer committed
803
		if (error != GIT_ITEROVER)
804
			return error;
805

806 807
		walk->get_next = &revwalk_next_reverse;
	}
808

809
	walk->walking = 1;
810
	return 0;
811
}
812 813


814 815 816 817 818 819 820 821



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

	walk = git__malloc(sizeof(git_revwalk));
822
	GITERR_CHECK_ALLOC(walk);
823 824 825

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

826
	walk->commits = git_oidmap_alloc();
827
	GITERR_CHECK_ALLOC(walk->commits);
828

829 830
	if (git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp) < 0 ||
		git_vector_init(&walk->twos, 4, NULL) < 0 ||
831 832
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
833
		return -1;
834 835 836 837 838 839

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

	walk->repo = repo;

840
	if (git_repository_odb(&walk->odb, repo) < 0) {
841
		git_revwalk_free(walk);
842
		return -1;
843 844
	}

845
	*revwalk_out = walk;
846
	return 0;
847 848 849 850 851 852 853 854
}

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

	git_revwalk_reset(walk);
855
	git_odb_free(walk->odb);
856

857
	git_oidmap_free(walk->commits);
858
	git_pool_clear(&walk->commit_pool);
859
	git_pqueue_free(&walk->iterator_time);
860
	git_vector_free(&walk->twos);
861
	git__free(walk);
862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887
}

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;
	}
}

888 889 890 891
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
	commit_object *next;
892

893
	assert(walk && oid);
894

895
	if (!walk->walking) {
896
		if ((error = prepare_walk(walk)) < 0)
897
			return error;
898
	}
899

900
	error = walk->get_next(&next, walk);
901

Russell Belfer committed
902
	if (error == GIT_ITEROVER) {
903
		git_revwalk_reset(walk);
Russell Belfer committed
904 905
		giterr_clear();
		return GIT_ITEROVER;
906
	}
907

908 909
	if (!error)
		git_oid_cpy(oid, &next->oid);
910

911
	return error;
912 913
}

914
void git_revwalk_reset(git_revwalk *walk)
915
{
916
	commit_object *commit;
917

918
	assert(walk);
919

920
	kh_foreach_value(walk->commits, commit, {
921 922 923
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
924
		commit->uninteresting = 0;
925
		});
926

927
	git_pqueue_clear(&walk->iterator_time);
928 929 930
	commit_list_free(&walk->iterator_topo);
	commit_list_free(&walk->iterator_rand);
	commit_list_free(&walk->iterator_reverse);
931
	walk->walking = 0;
932 933 934

	walk->one = NULL;
	git_vector_clear(&walk->twos);
935
}
936