From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 27 Jul 2014 22:14:14 +0000 (-0700)
Subject: Merge branch 'jk/stable-prio-queue'
X-Git-Tag: v2.1.0-rc0~3
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/4799593e26f09e4209249caf9536001036618ac2?hp=-c

Merge branch 'jk/stable-prio-queue'

* jk/stable-prio-queue:
t5539: update a flaky test
paint_down_to_common: use prio_queue
prio-queue: make output stable with respect to insertion
prio-queue: factor out compare and swap operations
---

4799593e26f09e4209249caf9536001036618ac2
diff --combined commit.c
index dce3d69dfd,1fc60c0109..2274e43fdf
--- a/commit.c
+++ b/commit.c
@@@ -18,6 -18,19 +18,6 @@@ int save_commit_buffer = 1
  
  const char *commit_type = "commit";
  
 -static struct commit *check_commit(struct object *obj,
 -				   const unsigned char *sha1,
 -				   int quiet)
 -{
 -	if (obj->type != OBJ_COMMIT) {
 -		if (!quiet)
 -			error("Object %s is a %s, not a commit",
 -			      sha1_to_hex(sha1), typename(obj->type));
 -		return NULL;
 -	}
 -	return (struct commit *) obj;
 -}
 -
  struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
  					      int quiet)
  {
@@@ -25,7 -38,7 +25,7 @@@
  
  	if (!obj)
  		return NULL;
 -	return check_commit(obj, sha1, quiet);
 +	return object_as_type(obj, OBJ_COMMIT, quiet);
  }
  
  struct commit *lookup_commit_reference(const unsigned char *sha1)
@@@ -48,9 -61,13 +48,9 @@@ struct commit *lookup_commit_or_die(con
  struct commit *lookup_commit(const unsigned char *sha1)
  {
  	struct object *obj = lookup_object(sha1);
 -	if (!obj) {
 -		struct commit *c = alloc_commit_node();
 -		return create_object(sha1, OBJ_COMMIT, c);
 -	}
 -	if (!obj->type)
 -		obj->type = OBJ_COMMIT;
 -	return check_commit(obj, sha1, 0);
 +	if (!obj)
 +		return create_object(sha1, alloc_commit_node());
 +	return object_as_type(obj, OBJ_COMMIT, 0);
  }
  
  struct commit *lookup_commit_reference_by_name(const char *name)
@@@ -430,7 -447,12 +430,7 @@@ struct commit_list *copy_commit_list(st
  	struct commit_list *head = NULL;
  	struct commit_list **pp = &head;
  	while (list) {
 -		struct commit_list *new;
 -		new = xmalloc(sizeof(struct commit_list));
 -		new->item = list->item;
 -		new->next = NULL;
 -		*pp = new;
 -		pp = &new->next;
 +		pp = commit_list_append(list->item, pp);
  		list = list->next;
  	}
  	return head;
@@@ -764,45 -786,41 +764,41 @@@ void sort_in_topological_order(struct c
  
  static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
  
- static struct commit *interesting(struct commit_list *list)
+ static int queue_has_nonstale(struct prio_queue *queue)
  {
- 	while (list) {
- 		struct commit *commit = list->item;
- 		list = list->next;
- 		if (commit->object.flags & STALE)
- 			continue;
- 		return commit;
+ 	int i;
+ 	for (i = 0; i < queue->nr; i++) {
+ 		struct commit *commit = queue->array[i].data;
+ 		if (!(commit->object.flags & STALE))
+ 			return 1;
  	}
- 	return NULL;
+ 	return 0;
  }
  
  /* all input commits in one and twos[] must have been parsed! */
  static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
  {
- 	struct commit_list *list = NULL;
+ 	struct prio_queue queue = { compare_commits_by_commit_date };
  	struct commit_list *result = NULL;
  	int i;
  
  	one->object.flags |= PARENT1;
- 	commit_list_insert_by_date(one, &list);
- 	if (!n)
- 		return list;
+ 	if (!n) {
+ 		commit_list_append(one, &result);
+ 		return result;
+ 	}
+ 	prio_queue_put(&queue, one);
+ 
  	for (i = 0; i < n; i++) {
  		twos[i]->object.flags |= PARENT2;
- 		commit_list_insert_by_date(twos[i], &list);
+ 		prio_queue_put(&queue, twos[i]);
  	}
  
- 	while (interesting(list)) {
- 		struct commit *commit;
+ 	while (queue_has_nonstale(&queue)) {
+ 		struct commit *commit = prio_queue_get(&queue);
  		struct commit_list *parents;
- 		struct commit_list *next;
  		int flags;
  
- 		commit = list->item;
- 		next = list->next;
- 		free(list);
- 		list = next;
- 
  		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
  		if (flags == (PARENT1 | PARENT2)) {
  			if (!(commit->object.flags & RESULT)) {
@@@ -821,11 -839,11 +817,11 @@@
  			if (parse_commit(p))
  				return NULL;
  			p->object.flags |= flags;
- 			commit_list_insert_by_date(p, &list);
+ 			prio_queue_put(&queue, p);
  		}
  	}
  
- 	free_commit_list(list);
+ 	clear_prio_queue(&queue);
  	return result;
  }
  
@@@ -970,7 -988,12 +966,7 @@@ struct commit_list *get_merge_bases_man
  	}
  
  	/* There are more than one */
 -	cnt = 0;
 -	list = result;
 -	while (list) {
 -		list = list->next;
 -		cnt++;
 -	}
 +	cnt = commit_list_count(result);
  	rslt = xcalloc(cnt, sizeof(*rslt));
  	for (list = result, i = 0; list; list = list->next)
  		rslt[i++] = list->item;
@@@ -1288,19 -1311,6 +1284,19 @@@ struct commit_extra_header *read_commit
  	return extra;
  }
  
 +void for_each_mergetag(each_mergetag_fn fn, struct commit *commit, void *data)
 +{
 +	struct commit_extra_header *extra, *to_free;
 +
 +	to_free = read_commit_extra_headers(commit, NULL);
 +	for (extra = to_free; extra; extra = extra->next) {
 +		if (strcmp(extra->key, "mergetag"))
 +			continue; /* not a merge tag */
 +		fn(commit, extra, data);
 +	}
 +	free_commit_extra_headers(to_free);
 +}
 +
  static inline int standard_header_field(const char *field, size_t len)
  {
  	return ((len == 4 && !memcmp(field, "tree ", 5)) ||