thodg/libgit2/src/graph.c

• Show log

  Commit

• Hash : 0c7f49dd
  Author :
  Date : 2017-06-30T13:39:01
  

  Make sure to always include "common.h" first
  
  Next to including several files, our "common.h" header also declares
  various macros which are then used throughout the project. As such, we
  have to make sure to always include this file first in all
  implementation files. Otherwise, we might encounter problems or even
  silent behavioural differences due to macros or defines not being
  defined as they should be. So in fact, our header and implementation
  files should make sure to always include "common.h" first.
  
  This commit does so by establishing a common include pattern. Header
  files inside of "src" will now always include "common.h" as its first
  other file, separated by a newline from all the other includes to make
  it stand out as special. There are two cases for the implementation
  files. If they do have a matching header file, they will always include
  this one first, leading to "common.h" being transitively included as
  first file. If they do not have a matching header file, they instead
  include "common.h" as first file themselves.
  
  This fixes the outlined problems and will become our standard practice
  for header and source files inside of the "src/" from now on.
  

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 "common.h"
  
  #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