src/revwalk.c

   1 /*
   2  * This file is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License, version 2,
   4  * as published by the Free Software Foundation.
   5  *
   6  * In addition to the permissions in the GNU General Public License,
   7  * the authors give you unlimited permission to link the compiled
   8  * version of this file into combinations with other programs,
   9  * and to distribute those combinations without any restriction
  10  * coming from the use of this file.  (The General Public License
  11  * restrictions do apply in other respects; for example, they cover
  12  * modification of the file, and distribution when not linked into
  13  * a combined executable.)
  14  *
  15  * This file is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; see the file COPYING.  If not, write to
  22  * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  23  * Boston, MA 02110-1301, USA.
  24  */
  25
  26 #include "common.h"
  27 #include "commit.h"
  28 #include "revwalk.h"
  29
  30 static const int default_table_size = 32;
  31
  32 git_revpool *gitrp_alloc(git_odb *db)
  33 {
  34         git_revpool *walk = git__malloc(sizeof(*walk));
  35         if (!walk)
  36                 return NULL;
  37
  38         memset(walk, 0x0, sizeof(git_revpool));
  39
  40         walk->commits = git_revpool_table_create(default_table_size);
  41
  42         walk->db = db;
  43         return walk;
  44 }
  45
  46 void gitrp_free(git_revpool *walk)
  47 {
  48         git_commit_list_clear(&(walk->iterator), 0);
  49         git_commit_list_clear(&(walk->roots), 0);
  50
  51         git_revpool_table_free(walk->commits);
  52
  53         free(walk);
  54 }
  55
  56 void gitrp_sorting(git_revpool *pool, unsigned int sort_mode)
  57 {
  58         if (pool->walking)
  59                 return;
  60
  61         pool->sorting = sort_mode;
  62         gitrp_reset(pool);
  63 }
  64
  65 int gitrp_push(git_revpool *pool, git_commit *commit)
  66 {
  67         if (commit == NULL || commit->seen)
  68                 return GIT_ENOTFOUND;
  69
  70         if (commit->object.pool != pool || pool->walking)
  71                 return GIT_ERROR;
  72
  73         if (!commit->parsed) {
  74                 if (git_commit_parse_existing(commit) < 0)
  75                         return GIT_EOBJCORRUPTED;
  76         }
  77
  78         // Sanity check: make sure that if the commit
  79         // has been manually marked as uninteresting,
  80         // all the parent commits are too.
  81         if (commit->uninteresting)
  82                 git_commit__mark_uninteresting(commit);
  83
  84         if (git_commit_list_push_back(&pool->roots, commit) < 0)
  85                 return GIT_ENOMEM;
  86
  87         return 0;
  88 }
  89
  90 int gitrp_hide(git_revpool *pool, git_commit *commit)
  91 {
  92         if (pool->walking)
  93                 return GIT_ERROR;
  94
  95         git_commit__mark_uninteresting(commit);
  96         return gitrp_push(pool, commit);
  97 }
  98
  99 int gitrp__enroot(git_revpool *pool, git_commit *commit)
 100 {
 101         int error;
 102         git_commit_node *parents;
 103
 104         if (commit->seen)
 105                 return 0;
 106
 107         if (commit->parsed == 0) {
 108                 if (git_commit_parse_existing(commit))
 109                         return GIT_EOBJCORRUPTED;
 110         }
 111
 112         commit->seen = 1;
 113
 114         for (parents = commit->parents.head; parents != NULL; parents = parents->next) {
 115                 parents->commit->in_degree++;
 116
 117                 error = gitrp__enroot(pool, parents->commit);
 118                 if (error < 0)
 119                         return error;
 120         }
 121
 122         if (git_commit_list_push_back(&pool->iterator, commit))
 123                 return GIT_ENOMEM;
 124
 125         return 0;
 126 }
 127
 128 void gitrp__prepare_walk(git_revpool *pool)
 129 {
 130         git_commit_node *it;
 131
 132         for (it = pool->roots.head; it != NULL; it = it->next)
 133                 gitrp__enroot(pool, it->commit);
 134
 135         if (pool->sorting & GIT_RPSORT_TIME)
 136                 git_commit_list_timesort(&pool->iterator);
 137
 138         if (pool->sorting & GIT_RPSORT_TOPOLOGICAL)
 139                 git_commit_list_toposort(&pool->iterator);
 140
 141         if (pool->sorting & GIT_RPSORT_REVERSE)
 142                 pool->next_commit = &git_commit_list_pop_back;
 143         else
 144                 pool->next_commit = &git_commit_list_pop_front;
 145
 146         pool->walking = 1;
 147 }
 148
 149 git_commit *gitrp_next(git_revpool *pool)
 150 {
 151         git_commit *next;
 152
 153         if (!pool->walking)
 154                 gitrp__prepare_walk(pool);
 155
 156         while ((next = pool->next_commit(&pool->iterator)) != NULL) {
 157                 if (!next->uninteresting)
 158                         return next;
 159         }
 160
 161         // No commits left to iterate
 162         gitrp_reset(pool);
 163         return NULL;
 164 }
 165
 166 void gitrp_reset(git_revpool *pool)
 167 {
 168         git_commit *commit;
 169         git_revpool_tableit it;
 170
 171         git_revpool_tableit_init(pool->commits, &it);
 172
 173         while ((commit = (git_commit *)git_revpool_tableit_next(&it)) != NULL) {
 174                 commit->seen = 0;
 175                 commit->topo_delay = 0;
 176                 commit->in_degree = 0;
 177         }
 178
 179         git_commit_list_clear(&pool->iterator, 0);
 180         pool->walking = 0;
 181 }
 182