src/commit_list.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "commit_list.h"
   9
  10 #include "revwalk.h"
  11 #include "pool.h"
  12 #include "odb.h"
  13 #include "commit.h"
  14
  15 int git_commit_list_generation_cmp(const void *a, const void *b)
  16 {
  17         uint32_t generation_a = ((git_commit_list_node *) a)->generation;
  18         uint32_t generation_b = ((git_commit_list_node *) b)->generation;
  19
  20         if (!generation_a || !generation_b) {
  21                 /* Fall back to comparing by timestamps if at least one commit lacks a generation. */
  22                 return git_commit_list_time_cmp(a, b);
  23         }
  24
  25         if (generation_a < generation_b)
  26                 return 1;
  27         if (generation_a > generation_b)
  28                 return -1;
  29
  30         return 0;
  31 }
  32
  33 int git_commit_list_time_cmp(const void *a, const void *b)
  34 {
  35         int64_t time_a = ((git_commit_list_node *) a)->time;
  36         int64_t time_b = ((git_commit_list_node *) b)->time;
  37
  38         if (time_a < time_b)
  39                 return 1;
  40         if (time_a > time_b)
  41                 return -1;
  42
  43         return 0;
  44 }
  45
  46 git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p)
  47 {
  48         git_commit_list *new_list = git__malloc(sizeof(git_commit_list));
  49         if (new_list != NULL) {
  50                 new_list->item = item;
  51                 new_list->next = *list_p;
  52         }
  53         *list_p = new_list;
  54         return new_list;
  55 }
  56
  57 git_commit_list *git_commit_list_insert_by_date(git_commit_list_node *item, git_commit_list **list_p)
  58 {
  59         git_commit_list **pp = list_p;
  60         git_commit_list *p;
  61
  62         while ((p = *pp) != NULL) {
  63                 if (git_commit_list_time_cmp(p->item, item) > 0)
  64                         break;
  65
  66                 pp = &p->next;
  67         }
  68
  69         return git_commit_list_insert(item, pp);
  70 }
  71
  72 git_commit_list_node *git_commit_list_alloc_node(git_revwalk *walk)
  73 {
  74         return (git_commit_list_node *)git_pool_mallocz(&walk->commit_pool, 1);
  75 }
  76
  77 static git_commit_list_node **alloc_parents(
  78         git_revwalk *walk, git_commit_list_node *commit, size_t n_parents)
  79 {
  80         size_t bytes;
  81
  82         if (n_parents <= PARENTS_PER_COMMIT)
  83                 return (git_commit_list_node **)((char *)commit + sizeof(git_commit_list_node));
  84
  85         if (git__multiply_sizet_overflow(&bytes, n_parents, sizeof(git_commit_list_node *)))
  86                 return NULL;
  87
  88         return (git_commit_list_node **)git_pool_malloc(&walk->commit_pool, bytes);
  89 }
  90
  91
  92 void git_commit_list_free(git_commit_list **list_p)
  93 {
  94         git_commit_list *list = *list_p;
  95
  96         if (list == NULL)
  97                 return;
  98
  99         while (list) {
 100                 git_commit_list *temp = list;
 101                 list = temp->next;
 102                 git__free(temp);
 103         }
 104
 105         *list_p = NULL;
 106 }
 107
 108 git_commit_list_node *git_commit_list_pop(git_commit_list **stack)
 109 {
 110         git_commit_list *top = *stack;
 111         git_commit_list_node *item = top ? top->item : NULL;
 112
 113         if (top) {
 114                 *stack = top->next;
 115                 git__free(top);
 116         }
 117         return item;
 118 }
 119
 120 static int commit_quick_parse(
 121         git_revwalk *walk,
 122         git_commit_list_node *node,
 123         git_odb_object *obj)
 124 {
 125         git_oid *parent_oid;
 126         git_commit *commit;
 127         size_t i;
 128
 129         commit = git__calloc(1, sizeof(*commit));
 130         GIT_ERROR_CHECK_ALLOC(commit);
 131         commit->object.repo = walk->repo;
 132
 133         if (git_commit__parse_ext(commit, obj, GIT_COMMIT_PARSE_QUICK) < 0) {
 134                 git__free(commit);
 135                 return -1;
 136         }
 137
 138         if (!git__is_uint16(git_array_size(commit->parent_ids))) {
 139                 git__free(commit);
 140                 git_error_set(GIT_ERROR_INVALID, "commit has more than 2^16 parents");
 141                 return -1;
 142         }
 143
 144         node->generation = 0;
 145         node->time = commit->committer->when.time;
 146         node->out_degree = (uint16_t) git_array_size(commit->parent_ids);
 147         node->parents = alloc_parents(walk, node, node->out_degree);
 148         GIT_ERROR_CHECK_ALLOC(node->parents);
 149
 150         git_array_foreach(commit->parent_ids, i, parent_oid) {
 151                 node->parents[i] = git_revwalk__commit_lookup(walk, parent_oid);
 152         }
 153
 154         git_commit__free(commit);
 155
 156         node->parsed = 1;
 157
 158         return 0;
 159 }
 160
 161 int git_commit_list_parse(git_revwalk *walk, git_commit_list_node *commit)
 162 {
 163         git_odb_object *obj;
 164         git_commit_graph_file *cgraph_file = NULL;
 165         int error;
 166
 167         if (commit->parsed)
 168                 return 0;
 169
 170         /* Let's try to use the commit graph first. */
 171         git_odb__get_commit_graph_file(&cgraph_file, walk->odb);
 172         if (cgraph_file) {
 173                 git_commit_graph_entry e;
 174
 175                 error = git_commit_graph_entry_find(&e, cgraph_file, &commit->oid, GIT_OID_RAWSZ);
 176                 if (error == 0 && git__is_uint16(e.parent_count)) {
 177                         size_t i;
 178                         commit->generation = (uint32_t)e.generation;
 179                         commit->time = e.commit_time;
 180                         commit->out_degree = (uint16_t)e.parent_count;
 181                         commit->parents = alloc_parents(walk, commit, commit->out_degree);
 182                         GIT_ERROR_CHECK_ALLOC(commit->parents);
 183
 184                         for (i = 0; i < commit->out_degree; ++i) {
 185                                 git_commit_graph_entry parent;
 186                                 error = git_commit_graph_entry_parent(&parent, cgraph_file, &e, i);
 187                                 if (error < 0)
 188                                         return error;
 189                                 commit->parents[i] = git_revwalk__commit_lookup(walk, &parent.sha1);
 190                         }
 191                         commit->parsed = 1;
 192                         return 0;
 193                 }
 194         }
 195
 196         if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < 0)
 197                 return error;
 198
 199         if (obj->cached.type != GIT_OBJECT_COMMIT) {
 200                 git_error_set(GIT_ERROR_INVALID, "object is no commit object");
 201                 error = -1;
 202         } else
 203                 error = commit_quick_parse(walk, commit, obj);
 204
 205         git_odb_object_free(obj);
 206         return error;
 207 }
 208