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