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 void gitrp_push(git_revpool *pool, git_commit *commit)
  66 {
  67         if (commit == NULL || commit->seen)
  68                 return;
  69
  70         if (commit->object.pool != pool || pool->walking)
  71                 return;
  72
  73         if (!commit->parsed) {
  74                 if (git_commit_parse_existing(commit) < 0)
  75                         return;
  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         git_commit_list_push_back(&pool->roots, commit);
  85 }
  86
  87 void gitrp_hide(git_revpool *pool, git_commit *commit)
  88 {
  89         if (pool->walking)
  90                 return;
  91
  92         git_commit__mark_uninteresting(commit);
  93         gitrp_push(pool, commit);
  94 }
  95
  96 void gitrp__enroot(git_revpool *pool, git_commit *commit)
  97 {
  98         git_commit_node *parents;
  99
 100         if (commit->seen)
 101                 return;
 102
 103         if (commit->parsed == 0)
 104                 git_commit_parse_existing(commit);
 105
 106         commit->seen = 1;
 107
 108         for (parents = commit->parents.head; parents != NULL; parents = parents->next) {
 109                 parents->commit->in_degree++;
 110                 gitrp__enroot(pool, parents->commit);
 111         }
 112
 113         git_commit_list_push_back(&pool->iterator, commit);
 114 }
 115
 116 void gitrp__prepare_walk(git_revpool *pool)
 117 {
 118         git_commit_node *it;
 119
 120         for (it = pool->roots.head; it != NULL; it = it->next)
 121                 gitrp__enroot(pool, it->commit);
 122
 123         if (pool->sorting & GIT_RPSORT_TIME)
 124                 git_commit_list_timesort(&pool->iterator);
 125
 126         if (pool->sorting & GIT_RPSORT_TOPOLOGICAL)
 127                 git_commit_list_toposort(&pool->iterator);
 128
 129         if (pool->sorting & GIT_RPSORT_REVERSE)
 130                 pool->next_commit = &git_commit_list_pop_back;
 131         else
 132                 pool->next_commit = &git_commit_list_pop_front;
 133
 134         pool->walking = 1;
 135 }
 136
 137 git_commit *gitrp_next(git_revpool *pool)
 138 {
 139         git_commit *next;
 140
 141         if (!pool->walking)
 142                 gitrp__prepare_walk(pool);
 143
 144         while ((next = pool->next_commit(&pool->iterator)) != NULL) {
 145                 if (!next->uninteresting)
 146                         return next;
 147         }
 148
 149         // No commits left to iterate
 150         gitrp_reset(pool);
 151         return NULL;
 152 }
 153
 154 void gitrp_reset(git_revpool *pool)
 155 {
 156         git_commit *commit;
 157         git_revpool_tableit it;
 158
 159         git_revpool_tableit_init(pool->commits, &it);
 160
 161         while ((commit = (git_commit *)git_revpool_tableit_next(&it)) != NULL) {
 162                 commit->seen = 0;
 163                 commit->topo_delay = 0;
 164                 commit->in_degree = 0;
 165         }
 166
 167         git_commit_list_clear(&pool->iterator, 0);
 168         pool->walking = 0;
 169 }
 170