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 277 278 279 280
	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;
281 282
	}

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

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

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

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

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

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

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

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

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

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

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

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

349
	git_pqueue_free(&list);
350

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

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

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

	*out = result;
366
	return 0;
367 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
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;
}

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

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

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

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

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

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

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

460 461 462 463 464
	return 0;

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

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

472
	commit->uninteresting = 1;
473

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

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

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

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

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

493
	commit->seen = 1;
494

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

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

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

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

509
	return error;
510 511
}

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

518 519 520 521 522 523 524 525 526 527 528
	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;
	}

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

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

541
	return 0;
542 543
}

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

550

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

747

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


813 814 815 816 817 818 819 820



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

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

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

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

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

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

	walk->repo = repo;

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

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

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

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

856
	git_oidmap_free(walk->commits);
857
	git_pool_clear(&walk->commit_pool);
858
	git_pqueue_free(&walk->iterator_time);
859
	git_vector_free(&walk->twos);
860
	git__free(walk);
861 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
}

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

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

892
	assert(walk && oid);
893

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

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

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

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

910
	return error;
911 912
}

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

917
	assert(walk);
918

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

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

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