commit_list.c 4.94 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3 4 5 6 7 8
 *
 * 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 "commit_list.h"
9

10 11 12
#include "revwalk.h"
#include "pool.h"
#include "odb.h"
13
#include "commit.h"
14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
int git_commit_list_generation_cmp(const void *a, const void *b)
{
	uint32_t generation_a = ((git_commit_list_node *) a)->generation;
	uint32_t generation_b = ((git_commit_list_node *) b)->generation;

	if (!generation_a || !generation_b) {
		/* Fall back to comparing by timestamps if at least one commit lacks a generation. */
		return git_commit_list_time_cmp(a, b);
	}

	if (generation_a < generation_b)
		return 1;
	if (generation_a > generation_b)
		return -1;

	return 0;
}

33
int git_commit_list_time_cmp(const void *a, const void *b)
34
{
35 36
	int64_t time_a = ((git_commit_list_node *) a)->time;
	int64_t time_b = ((git_commit_list_node *) b)->time;
37

38 39 40 41 42 43
	if (time_a < time_b)
		return 1;
	if (time_a > time_b)
		return -1;

	return 0;
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
}

git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p)
{
	git_commit_list *new_list = git__malloc(sizeof(git_commit_list));
	if (new_list != NULL) {
		new_list->item = item;
		new_list->next = *list_p;
	}
	*list_p = new_list;
	return new_list;
}

git_commit_list *git_commit_list_insert_by_date(git_commit_list_node *item, git_commit_list **list_p)
{
	git_commit_list **pp = list_p;
	git_commit_list *p;

	while ((p = *pp) != NULL) {
63
		if (git_commit_list_time_cmp(p->item, item) > 0)
64 65 66 67 68 69 70 71 72 73
			break;

		pp = &p->next;
	}

	return git_commit_list_insert(item, pp);
}

git_commit_list_node *git_commit_list_alloc_node(git_revwalk *walk)
{
74
	return (git_commit_list_node *)git_pool_mallocz(&walk->commit_pool, 1);
75 76 77 78 79
}

static git_commit_list_node **alloc_parents(
	git_revwalk *walk, git_commit_list_node *commit, size_t n_parents)
{
80 81
	size_t bytes;

82 83 84
	if (n_parents <= PARENTS_PER_COMMIT)
		return (git_commit_list_node **)((char *)commit + sizeof(git_commit_list_node));

85 86 87 88
	if (git__multiply_sizet_overflow(&bytes, n_parents, sizeof(git_commit_list_node *)))
		return NULL;

	return (git_commit_list_node **)git_pool_malloc(&walk->commit_pool, bytes);
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
}


void git_commit_list_free(git_commit_list **list_p)
{
	git_commit_list *list = *list_p;

	if (list == NULL)
		return;

	while (list) {
		git_commit_list *temp = list;
		list = temp->next;
		git__free(temp);
	}

	*list_p = NULL;
}

git_commit_list_node *git_commit_list_pop(git_commit_list **stack)
{
	git_commit_list *top = *stack;
	git_commit_list_node *item = top ? top->item : NULL;

	if (top) {
		*stack = top->next;
		git__free(top);
	}
	return item;
}

Vicent Marti committed
120 121
static int commit_quick_parse(
	git_revwalk *walk,
122 123
	git_commit_list_node *node,
	git_odb_object *obj)
124
{
125 126 127 128
	git_oid *parent_oid;
	git_commit *commit;
	int error;
	size_t i;
129

130 131 132
	commit = git__calloc(1, sizeof(*commit));
	GIT_ERROR_CHECK_ALLOC(commit);
	commit->object.repo = walk->repo;
133

134 135 136
	if ((error = git_commit__parse_ext(commit, obj, GIT_COMMIT_PARSE_QUICK)) < 0) {
		git__free(commit);
		return error;
137 138
	}

139 140 141 142 143
	if (!git__is_uint16(git_array_size(commit->parent_ids))) {
		git__free(commit);
		git_error_set(GIT_ERROR_INVALID, "commit has more than 2^16 parents");
		return -1;
	}
144

145
	node->generation = 0;
146
	node->time = commit->committer->when.time;
147
	node->out_degree = (uint16_t) git_array_size(commit->parent_ids);
148 149
	node->parents = alloc_parents(walk, node, node->out_degree);
	GIT_ERROR_CHECK_ALLOC(node->parents);
150

151 152
	git_array_foreach(commit->parent_ids, i, parent_oid) {
		node->parents[i] = git_revwalk__commit_lookup(walk, parent_oid);
153 154
	}

155 156 157
	git_commit__free(commit);

	node->parsed = 1;
158 159 160 161 162 163 164

	return 0;
}

int git_commit_list_parse(git_revwalk *walk, git_commit_list_node *commit)
{
	git_odb_object *obj;
165
	git_commit_graph_file *cgraph_file = NULL;
166 167 168 169 170
	int error;

	if (commit->parsed)
		return 0;

171
	/* Let's try to use the commit graph first. */
172 173
	git_odb__get_commit_graph_file(&cgraph_file, walk->odb);
	if (cgraph_file) {
174 175
		git_commit_graph_entry e;

176
		error = git_commit_graph_entry_find(&e, cgraph_file, &commit->oid, GIT_OID_RAWSZ);
177 178 179 180 181 182 183 184 185 186
		if (error == 0 && git__is_uint16(e.parent_count)) {
			size_t i;
			commit->generation = (uint32_t)e.generation;
			commit->time = e.commit_time;
			commit->out_degree = (uint16_t)e.parent_count;
			commit->parents = alloc_parents(walk, commit, commit->out_degree);
			GIT_ERROR_CHECK_ALLOC(commit->parents);

			for (i = 0; i < commit->out_degree; ++i) {
				git_commit_graph_entry parent;
187
				error = git_commit_graph_entry_parent(&parent, cgraph_file, &e, i);
188 189 190 191 192 193 194 195 196
				if (error < 0)
					return error;
				commit->parents[i] = git_revwalk__commit_lookup(walk, &parent.sha1);
			}
			commit->parsed = 1;
			return 0;
		}
	}

197 198 199
	if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < 0)
		return error;

200
	if (obj->cached.type != GIT_OBJECT_COMMIT) {
201
		git_error_set(GIT_ERROR_INVALID, "object is no commit object");
202 203
		error = -1;
	} else
204
		error = commit_quick_parse(walk, commit, obj);
205

206 207 208 209
	git_odb_object_free(obj);
	return error;
}