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 #include "hashtable.h"
  30 #include "pqueue.h"
  31
  32 typedef struct commit_object {
  33         git_oid oid;
  34         uint32_t time;
  35         unsigned int seen:1,
  36                          uninteresting:1,
  37                          topo_delay:1,
  38                          parsed:1;
  39
  40         unsigned short in_degree;
  41         unsigned short out_degree;
  42
  43         struct commit_object **parents;
  44 } commit_object;
  45
  46 typedef struct commit_list {
  47         commit_object *item;
  48         struct commit_list *next;
  49 } commit_list;
  50
  51 struct git_revwalk {
  52         git_repository *repo;
  53
  54         git_hashtable *commits;
  55         git_vector pending;
  56
  57         commit_list *iterator_topo;
  58         commit_list *iterator_rand;
  59         commit_list *iterator_reverse;
  60         git_pqueue iterator_time;
  61
  62         int (*get_next)(commit_object **, git_revwalk *);
  63         int (*enqueue)(git_revwalk *, commit_object *);
  64
  65         git_vector memory_alloc;
  66         size_t chunk_size;
  67
  68         unsigned walking:1;
  69         unsigned int sorting;
  70 };
  71
  72 commit_list *commit_list_insert(commit_object *item, commit_list **list_p)
  73 {
  74         commit_list *new_list = git__malloc(sizeof(commit_list));
  75         new_list->item = item;
  76         new_list->next = *list_p;
  77         *list_p = new_list;
  78         return new_list;
  79 }
  80
  81 void commit_list_free(commit_list *list)
  82 {
  83         while (list) {
  84                 commit_list *temp = list;
  85                 list = temp->next;
  86                 free(temp);
  87         }
  88 }
  89
  90 commit_object *commit_list_pop(commit_list **stack)
  91 {
  92         commit_list *top = *stack;
  93         commit_object *item = top ? top->item : NULL;
  94
  95         if (top) {
  96                 *stack = top->next;
  97                 free(top);
  98         }
  99         return item;
 100 }
 101
 102 static int commit_time_cmp(void *a, void *b)
 103 {
 104         commit_object *commit_a = (commit_object *)a;
 105         commit_object *commit_b = (commit_object *)b;
 106
 107         return (commit_a->time < commit_b->time);
 108 }
 109
 110 static uint32_t object_table_hash(const void *key, int hash_id)
 111 {
 112         uint32_t r;
 113         git_oid *id;
 114
 115         id = (git_oid *)key;
 116         memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
 117         return r;
 118 }
 119
 120 #define COMMITS_PER_CHUNK 128
 121 #define CHUNK_STEP 64
 122 #define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *))
 123
 124 static int alloc_chunk(git_revwalk *walk)
 125 {
 126         void *chunk;
 127
 128         chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP);
 129         if (chunk == NULL)
 130                 return GIT_ENOMEM;
 131
 132         walk->chunk_size = 0;
 133         return git_vector_insert(&walk->memory_alloc, chunk);
 134 }
 135
 136 static commit_object *alloc_commit(git_revwalk *walk)
 137 {
 138         unsigned char *chunk;
 139
 140         if (walk->chunk_size == COMMITS_PER_CHUNK)
 141                 alloc_chunk(walk);
 142
 143         chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1);
 144         chunk += (walk->chunk_size * CHUNK_STEP);
 145         walk->chunk_size++;
 146
 147         return (commit_object *)chunk;
 148 }
 149
 150 static commit_object **alloc_parents(commit_object *commit, size_t n_parents)
 151 {
 152         if (n_parents <= PARENTS_PER_COMMIT)
 153                 return (commit_object **)((unsigned char *)commit + sizeof(commit_object));
 154
 155         return git__malloc(n_parents * sizeof(commit_object *));
 156 }
 157
 158 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 159 {
 160         git_revwalk *walk;
 161
 162         walk = git__malloc(sizeof(git_revwalk));
 163         if (walk == NULL)
 164                 return GIT_ENOMEM;
 165
 166         memset(walk, 0x0, sizeof(git_revwalk));
 167
 168         walk->commits = git_hashtable_alloc(64,
 169                         object_table_hash,
 170                         (git_hash_keyeq_ptr)git_oid_cmp);
 171
 172         if (walk->commits == NULL) {
 173                 free(walk);
 174                 return GIT_ENOMEM;
 175         }
 176
 177         git_vector_init(&walk->pending, 8, NULL);
 178         git_vector_init(&walk->memory_alloc, 8, NULL);
 179         alloc_chunk(walk);
 180
 181         walk->repo = repo;
 182
 183         *revwalk_out = walk;
 184         return GIT_SUCCESS;
 185 }
 186
 187 void git_revwalk_free(git_revwalk *walk)
 188 {
 189         unsigned int i;
 190
 191         if (walk == NULL)
 192                 return;
 193
 194         git_revwalk_reset(walk);
 195         git_hashtable_free(walk->commits);
 196         git_vector_free(&walk->pending);
 197
 198         for (i = 0; i < walk->memory_alloc.length; ++i) {
 199                 free(git_vector_get(&walk->memory_alloc, i));
 200         }
 201
 202         git_vector_free(&walk->memory_alloc);
 203         free(walk);
 204 }
 205
 206 git_repository *git_revwalk_repository(git_revwalk *walk)
 207 {
 208         assert(walk);
 209         return walk->repo;
 210 }
 211
 212 int git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
 213 {
 214         assert(walk);
 215
 216         if (walk->walking)
 217                 return GIT_EBUSY;
 218
 219         walk->sorting = sort_mode;
 220         git_revwalk_reset(walk);
 221         return GIT_SUCCESS;
 222 }
 223
 224 static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 225 {
 226         commit_object *commit;
 227
 228         if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)
 229                 return commit;
 230
 231         commit = alloc_commit(walk);
 232         if (commit == NULL)
 233                 return NULL;
 234
 235         git_oid_cpy(&commit->oid, oid);
 236
 237         if (git_hashtable_insert(walk->commits, &commit->oid, commit) < GIT_SUCCESS) {
 238                 free(commit);
 239                 return NULL;
 240         }
 241
 242         return commit;
 243 }
 244
 245 static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)
 246 {
 247         const int parent_len = STRLEN("parent ") + GIT_OID_HEXSZ + 1;
 248
 249         unsigned char *buffer = raw->data;
 250         unsigned char *buffer_end = buffer + raw->len;
 251         unsigned char *parents_start;
 252
 253         int i, parents = 0;
 254
 255         buffer += STRLEN("tree ") + GIT_OID_HEXSZ + 1;
 256
 257         parents_start = buffer;
 258         while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", STRLEN("parent ")) == 0) {
 259                 parents++;
 260                 buffer += parent_len;
 261         }
 262
 263         commit->parents = alloc_parents(commit, parents);
 264         if (commit->parents == NULL)
 265                 return GIT_ENOMEM;
 266
 267         buffer = parents_start;
 268         for (i = 0; i < parents; ++i) {
 269                 git_oid oid;
 270
 271                 if (git_oid_mkstr(&oid, (char *)buffer + STRLEN("parent ")) < GIT_SUCCESS)
 272                         return GIT_EOBJCORRUPTED;
 273
 274                 commit->parents[i] = commit_lookup(walk, &oid);
 275                 if (commit->parents[i] == NULL)
 276                         return GIT_ENOMEM;
 277
 278                 buffer += parent_len;
 279         }
 280
 281         commit->out_degree = (unsigned short)parents;
 282
 283         if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
 284                 return GIT_EOBJCORRUPTED;
 285
 286         buffer = memchr(buffer, '>', buffer_end - buffer);
 287         if (buffer == NULL)
 288                 return GIT_EOBJCORRUPTED;
 289
 290         commit->time = strtol((char *)buffer + 2, NULL, 10);
 291         if (commit->time == 0)
 292                 return GIT_EOBJCORRUPTED;
 293
 294         commit->parsed = 1;
 295         return GIT_SUCCESS;
 296 }
 297
 298 static int commit_parse(git_revwalk *walk, commit_object *commit)
 299 {
 300         git_rawobj data;
 301         int error;
 302
 303         if (commit->parsed)
 304                 return GIT_SUCCESS;
 305
 306         if ((error = git_odb_read(&data, walk->repo->db, &commit->oid)) < GIT_SUCCESS)
 307                 return error;
 308
 309         if (data.type != GIT_OBJ_COMMIT) {
 310                 git_rawobj_close(&data);
 311                 return GIT_EOBJTYPE;
 312         }
 313
 314         error = commit_quick_parse(walk, commit, &data);
 315         git_rawobj_close(&data);
 316         return error;
 317 }
 318
 319 static void mark_uninteresting(commit_object *commit)
 320 {
 321         unsigned short i;
 322         assert(commit);
 323
 324         commit->uninteresting = 1;
 325
 326         for (i = 0; i < commit->out_degree; ++i)
 327                 if (!commit->parents[i]->uninteresting)
 328                         mark_uninteresting(commit->parents[i]);
 329 }
 330
 331 static int process_commit(git_revwalk *walk, commit_object *commit)
 332 {
 333         int error;
 334
 335         if (commit->seen)
 336                 return GIT_SUCCESS;
 337
 338         commit->seen = 1;
 339
 340         if ((error = commit_parse(walk, commit)) < GIT_SUCCESS)
 341                         return error;
 342
 343         if (commit->uninteresting)
 344                 mark_uninteresting(commit);
 345
 346         return walk->enqueue(walk, commit);
 347 }
 348
 349 static int process_commit_parents(git_revwalk *walk, commit_object *commit)
 350 {
 351         unsigned short i;
 352         int error = GIT_SUCCESS;
 353
 354         for (i = 0; i < commit->out_degree && error == GIT_SUCCESS; ++i) {
 355                 error = process_commit(walk, commit->parents[i]);
 356         }
 357
 358         return error;
 359 }
 360
 361 static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
 362 {
 363         commit_object *commit;
 364
 365         commit = commit_lookup(walk, oid);
 366         if (commit == NULL)
 367                 return GIT_ENOTFOUND;
 368
 369         if (uninteresting)
 370                 mark_uninteresting(commit);
 371
 372         return git_vector_insert(&walk->pending, commit);
 373 }
 374
 375 int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
 376 {
 377         assert(walk && oid);
 378         return push_commit(walk, oid, 0);
 379 }
 380
 381 int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
 382 {
 383         assert(walk && oid);
 384         return push_commit(walk, oid, 1);
 385 }
 386
 387 static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
 388 {
 389         return git_pqueue_insert(&walk->iterator_time, commit);
 390 }
 391
 392 static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
 393 {
 394         return commit_list_insert(commit, &walk->iterator_rand) ? GIT_SUCCESS : GIT_ENOMEM;
 395 }
 396
 397 static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
 398 {
 399         int error;
 400         commit_object *next;
 401
 402         while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
 403                 if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
 404                         return error;
 405
 406                 if (!next->uninteresting) {
 407                         *object_out = next;
 408                         return GIT_SUCCESS;
 409                 }
 410         }
 411
 412         return GIT_EREVWALKOVER;
 413 }
 414
 415 static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
 416 {
 417         int error;
 418         commit_object *next;
 419
 420         while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
 421                 if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
 422                         return error;
 423
 424                 if (!next->uninteresting) {
 425                         *object_out = next;
 426                         return GIT_SUCCESS;
 427                 }
 428         }
 429
 430         return GIT_EREVWALKOVER;
 431 }
 432
 433 static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
 434 {
 435         commit_object *next;
 436         unsigned short i;
 437
 438         for (;;) {
 439                 next = commit_list_pop(&walk->iterator_topo);
 440                 if (next == NULL)
 441                         return GIT_EREVWALKOVER;
 442
 443                 if (next->in_degree > 0) {
 444                         next->topo_delay = 1;
 445                         continue;
 446                 }
 447
 448                 for (i = 0; i < next->out_degree; ++i) {
 449                         commit_object *parent = next->parents[i];
 450
 451                         if (--parent->in_degree == 0 && parent->topo_delay) {
 452                                 parent->topo_delay = 0;
 453                                 commit_list_insert(parent, &walk->iterator_topo);
 454                         }
 455                 }
 456
 457                 *object_out = next;
 458                 return GIT_SUCCESS;
 459         }
 460 }
 461
 462 static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
 463 {
 464         *object_out = commit_list_pop(&walk->iterator_reverse);
 465         return *object_out ? GIT_SUCCESS : GIT_EREVWALKOVER;
 466 }
 467
 468
 469 static int prepare_walk(git_revwalk *walk)
 470 {
 471         unsigned int i;
 472         int error;
 473
 474         if (walk->sorting & GIT_SORT_TIME) {
 475                 if ((error = git_pqueue_init(&walk->iterator_time, 32, commit_time_cmp)) < GIT_SUCCESS)
 476                         return error;
 477
 478                 walk->get_next = &revwalk_next_timesort;
 479                 walk->enqueue = &revwalk_enqueue_timesort;
 480         } else {
 481                 walk->get_next = &revwalk_next_unsorted;
 482                 walk->enqueue = &revwalk_enqueue_unsorted;
 483         }
 484
 485         for (i = 0; i < walk->pending.length; ++i) {
 486                 commit_object *commit = walk->pending.contents[i];
 487                 if ((error = process_commit(walk, commit)) < GIT_SUCCESS) {
 488                         return error;
 489                 }
 490         }
 491
 492         if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
 493                 commit_object *next;
 494                 unsigned short i;
 495                 int error;
 496
 497                 while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) {
 498                         for (i = 0; i < next->out_degree; ++i) {
 499                                 commit_object *parent = next->parents[i];
 500                                 parent->in_degree++;
 501                         }
 502
 503                         commit_list_insert(next, &walk->iterator_topo);
 504                 }
 505
 506                 if (error != GIT_EREVWALKOVER)
 507                         return error;
 508
 509                 walk->get_next = &revwalk_next_toposort;
 510         }
 511
 512         if (walk->sorting & GIT_SORT_REVERSE) {
 513                 commit_object *next;
 514                 int error;
 515
 516                 while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS)
 517                         commit_list_insert(next, &walk->iterator_reverse);
 518
 519                 if (error != GIT_EREVWALKOVER)
 520                         return error;
 521
 522                 walk->get_next = &revwalk_next_reverse;
 523         }
 524
 525         walk->walking = 1;
 526         return GIT_SUCCESS;
 527 }
 528
 529
 530 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 531 {
 532         int error;
 533         commit_object *next;
 534
 535         assert(walk && oid);
 536
 537         if (!walk->walking) {
 538                 if ((error = prepare_walk(walk)) < GIT_SUCCESS)
 539                         return error;
 540         }
 541
 542         error = walk->get_next(&next, walk);
 543         if (error < GIT_SUCCESS)
 544                 return error;
 545
 546         git_oid_cpy(oid, &next->oid);
 547         return GIT_SUCCESS;
 548 }
 549
 550 void git_revwalk_reset(git_revwalk *walk)
 551 {
 552         const void *_unused;
 553         commit_object *commit;
 554
 555         assert(walk);
 556
 557         GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit,
 558                 commit->seen = 0;
 559                 commit->in_degree = 0;
 560                 commit->topo_delay = 0;
 561         );
 562
 563         git_pqueue_free(&walk->iterator_time);
 564         commit_list_free(walk->iterator_topo);
 565         commit_list_free(walk->iterator_rand);
 566         commit_list_free(walk->iterator_reverse);
 567         walk->walking = 0;
 568 }
 569