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                 int error = git_commit_parse_existing(commit);
  75                 if (error < 0)
  76                         return error;
  77         }
  78
  79         /*
  80          * Sanity check: make sure that if the commit
  81          * has been manually marked as uninteresting,
  82          * all the parent commits are too.
  83          */
  84         if (commit->uninteresting)
  85                 git_commit__mark_uninteresting(commit);
  86
  87         if (git_commit_list_push_back(&pool->roots, commit) < 0)
  88                 return GIT_ENOMEM;
  89
  90         return 0;
  91 }
  92
  93 int gitrp_hide(git_revpool *pool, git_commit *commit)
  94 {
  95         if (pool->walking)
  96                 return GIT_ERROR;
  97
  98         git_commit__mark_uninteresting(commit);
  99         return gitrp_push(pool, commit);
 100 }
 101
 102 int gitrp__enroot(git_revpool *pool, git_commit *commit)
 103 {
 104         int error;
 105         git_commit_node *parents;
 106
 107         if (commit->seen)
 108                 return 0;
 109
 110         if (commit->parsed == 0) {
 111                 error = git_commit_parse_existing(commit);
 112                 if (error < 0)
 113                         return error;
 114         }
 115
 116         commit->seen = 1;
 117
 118         for (parents = commit->parents.head; parents != NULL; parents = parents->next) {
 119                 parents->commit->in_degree++;
 120
 121                 error = gitrp__enroot(pool, parents->commit);
 122                 if (error < 0)
 123                         return error;
 124         }
 125
 126         if (git_commit_list_push_back(&pool->iterator, commit))
 127                 return GIT_ENOMEM;
 128
 129         return 0;
 130 }
 131
 132 void gitrp__prepare_walk(git_revpool *pool)
 133 {
 134         git_commit_node *it;
 135
 136         for (it = pool->roots.head; it != NULL; it = it->next)
 137                 gitrp__enroot(pool, it->commit);
 138
 139         if (pool->sorting & GIT_RPSORT_TIME)
 140                 git_commit_list_timesort(&pool->iterator);
 141
 142         if (pool->sorting & GIT_RPSORT_TOPOLOGICAL)
 143                 git_commit_list_toposort(&pool->iterator);
 144
 145         if (pool->sorting & GIT_RPSORT_REVERSE)
 146                 pool->next_commit = &git_commit_list_pop_back;
 147         else
 148                 pool->next_commit = &git_commit_list_pop_front;
 149
 150         pool->walking = 1;
 151 }
 152
 153 git_commit *gitrp_next(git_revpool *pool)
 154 {
 155         git_commit *next;
 156
 157         if (!pool->walking)
 158                 gitrp__prepare_walk(pool);
 159
 160         while ((next = pool->next_commit(&pool->iterator)) != NULL) {
 161                 if (!next->uninteresting)
 162                         return next;
 163         }
 164
 165         /* No commits left to iterate */
 166         gitrp_reset(pool);
 167         return NULL;
 168 }
 169
 170 void gitrp_reset(git_revpool *pool)
 171 {
 172         git_commit *commit;
 173         git_revpool_tableit it;
 174
 175         git_revpool_tableit_init(pool->commits, &it);
 176
 177         while ((commit = (git_commit *)git_revpool_tableit_next(&it)) != NULL) {
 178                 commit->seen = 0;
 179                 commit->topo_delay = 0;
 180                 commit->in_degree = 0;
 181         }
 182
 183         git_commit_list_clear(&pool->iterator, 0);
 184         pool->walking = 0;
 185 }
 186