thodg/libgit2/src/graph.c

• Show log

  Commit

• Hash : e781a0c5
  Author :
  Date : 2016-11-25T15:02:07
  

  graph: flag fields should be declared as unsigned

Download

• src/graph.c

• /*
   * Copyright (C) the libgit2 contributors. All rights reserved.
   *
   * This file is part of libgit2, distributed under the GNU GPL v2 with
   * a Linking Exception. For full terms see the included COPYING file.
   */
  
  #include "revwalk.h"
  #include "merge.h"
  #include "git2/graph.h"
  
  static int interesting(git_pqueue *list, git_commit_list *roots)
  {
  	unsigned int i;
  
  	for (i = 0; i < git_pqueue_size(list); i++) {
  		git_commit_list_node *commit = git_pqueue_get(list, i);
  		if ((commit->flags & STALE) == 0)
  			return 1;
  	}
  
  	while(roots) {
  		if ((roots->item->flags & STALE) == 0)
  			return 1;
  		roots = roots->next;
  	}
  
  	return 0;
  }
  
  static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
  	git_commit_list_node *two)
  {
  	unsigned int i;
  	git_commit_list *roots = NULL;
  	git_pqueue list;
  
  	/* if the commit is repeated, we have a our merge base already */
  	if (one == two) {
  		one->flags |= PARENT1 | PARENT2 | RESULT;
  		return 0;
  	}
  
  	if (git_pqueue_init(&list, 0, 2, git_commit_list_time_cmp) < 0)
  		return -1;
  
  	if (git_commit_list_parse(walk, one) < 0)
  		goto on_error;
  	one->flags |= PARENT1;
  	if (git_pqueue_insert(&list, one) < 0)
  		goto on_error;
  
  	if (git_commit_list_parse(walk, two) < 0)
  		goto on_error;
  	two->flags |= PARENT2;
  	if (git_pqueue_insert(&list, two) < 0)
  		goto on_error;
  
  	/* as long as there are non-STALE commits */
  	while (interesting(&list, roots)) {
  		git_commit_list_node *commit = git_pqueue_pop(&list);
  		unsigned int flags;
  
  		if (commit == NULL)
  			break;
  
  		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
  		if (flags == (PARENT1 | PARENT2)) {
  			if (!(commit->flags & RESULT))
  				commit->flags |= RESULT;
  			/* we mark the parents of a merge stale */
  			flags |= STALE;
  		}
  
  		for (i = 0; i < commit->out_degree; i++) {
  			git_commit_list_node *p = commit->parents[i];
  			if ((p->flags & flags) == flags)
  				continue;
  
  			if (git_commit_list_parse(walk, p) < 0)
  				goto on_error;
  
  			p->flags |= flags;
  			if (git_pqueue_insert(&list, p) < 0)
  				goto on_error;
  		}
  
  		/* Keep track of root commits, to make sure the path gets marked */
  		if (commit->out_degree == 0) {
  			if (git_commit_list_insert(commit, &roots) == NULL)
  				goto on_error;
  		}
  	}
  
  	git_commit_list_free(&roots);
  	git_pqueue_free(&list);
  	return 0;
  
  on_error:
  	git_commit_list_free(&roots);
  	git_pqueue_free(&list);
  	return -1;
  }
  
  
  static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two,
  	size_t *ahead, size_t *behind)
  {
  	git_commit_list_node *commit;
  	git_pqueue pq;
  	int error = 0, i;
  	*ahead = 0;
  	*behind = 0;
  
  	if (git_pqueue_init(&pq, 0, 2, git_commit_list_time_cmp) < 0)
  		return -1;
  
  	if ((error = git_pqueue_insert(&pq, one)) < 0 ||
  		(error = git_pqueue_insert(&pq, two)) < 0)
  		goto done;
  
  	while ((commit = git_pqueue_pop(&pq)) != NULL) {
  		if (commit->flags & RESULT ||
  			(commit->flags & (PARENT1 | PARENT2)) == (PARENT1 | PARENT2))
  			continue;
  		else if (commit->flags & PARENT1)
  			(*ahead)++;
  		else if (commit->flags & PARENT2)
  			(*behind)++;
  
  		for (i = 0; i < commit->out_degree; i++) {
  			git_commit_list_node *p = commit->parents[i];
  			if ((error = git_pqueue_insert(&pq, p)) < 0)
  				goto done;
  		}
  		commit->flags |= RESULT;
  	}
  
  done:
  	git_pqueue_free(&pq);
  	return error;
  }
  
  int git_graph_ahead_behind(size_t *ahead, size_t *behind, git_repository *repo,
  	const git_oid *local, const git_oid *upstream)
  {
  	git_revwalk *walk;
  	git_commit_list_node *commit_u, *commit_l;
  
  	if (git_revwalk_new(&walk, repo) < 0)
  		return -1;
  
  	commit_u = git_revwalk__commit_lookup(walk, upstream);
  	if (commit_u == NULL)
  		goto on_error;
  
  	commit_l = git_revwalk__commit_lookup(walk, local);
  	if (commit_l == NULL)
  		goto on_error;
  
  	if (mark_parents(walk, commit_l, commit_u) < 0)
  		goto on_error;
  	if (ahead_behind(commit_l, commit_u, ahead, behind) < 0)
  		goto on_error;
  
  	git_revwalk_free(walk);
  
  	return 0;
  
  on_error:
  	git_revwalk_free(walk);
  	return -1;
  }
  
  int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor)
  {
  	git_oid merge_base;
  	int error;
  
  	if (git_oid_equal(commit, ancestor))
  		return 0;
  
  	error = git_merge_base(&merge_base, repo, commit, ancestor);
  	/* No merge-base found, it's not a descendant */
  	if (error == GIT_ENOTFOUND)
  		return 0;
  
  	if (error < 0)
  		return error;
  
  	return git_oid_equal(&merge_base, ancestor);
  }
  

Download