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