]>
Commit | Line | Data |
---|---|---|
06160502 | 1 | /* |
5e0de328 | 2 | * Copyright (C) 2009-2012 the libgit2 contributors |
06160502 | 3 | * |
bb742ede VM |
4 | * This file is part of libgit2, distributed under the GNU GPL v2 with |
5 | * a Linking Exception. For full terms see the included COPYING file. | |
06160502 SP |
6 | */ |
7 | ||
64a47c01 | 8 | #include "common.h" |
08d5d000 | 9 | #include "commit.h" |
72a3fe42 | 10 | #include "odb.h" |
3315782c | 11 | #include "hashtable.h" |
71db842f | 12 | #include "pqueue.h" |
06160502 | 13 | |
b5c5f0f8 VM |
14 | #include "git2/revwalk.h" |
15 | ||
155aca2d CMN |
16 | #include <regex.h> |
17 | ||
de7ab85d CMN |
18 | #define PARENT1 (1 << 0) |
19 | #define PARENT2 (1 << 1) | |
20 | #define RESULT (1 << 2) | |
21 | #define STALE (1 << 3) | |
22 | ||
71db842f VM |
23 | typedef struct commit_object { |
24 | git_oid oid; | |
25 | uint32_t time; | |
26 | unsigned int seen:1, | |
27 | uninteresting:1, | |
28 | topo_delay:1, | |
de7ab85d CMN |
29 | parsed:1, |
30 | flags : 4; | |
71db842f VM |
31 | |
32 | unsigned short in_degree; | |
33 | unsigned short out_degree; | |
34 | ||
35 | struct commit_object **parents; | |
36 | } commit_object; | |
37 | ||
38 | typedef struct commit_list { | |
39 | commit_object *item; | |
40 | struct commit_list *next; | |
41 | } commit_list; | |
42 | ||
43 | struct git_revwalk { | |
44 | git_repository *repo; | |
9462c471 | 45 | git_odb *odb; |
71db842f VM |
46 | |
47 | git_hashtable *commits; | |
71db842f VM |
48 | |
49 | commit_list *iterator_topo; | |
50 | commit_list *iterator_rand; | |
51 | commit_list *iterator_reverse; | |
52 | git_pqueue iterator_time; | |
53 | ||
54 | int (*get_next)(commit_object **, git_revwalk *); | |
55 | int (*enqueue)(git_revwalk *, commit_object *); | |
56 | ||
57 | git_vector memory_alloc; | |
58 | size_t chunk_size; | |
59 | ||
60 | unsigned walking:1; | |
61 | unsigned int sorting; | |
62 | }; | |
63 | ||
de7ab85d CMN |
64 | static int commit_time_cmp(void *a, void *b) |
65 | { | |
66 | commit_object *commit_a = (commit_object *)a; | |
67 | commit_object *commit_b = (commit_object *)b; | |
68 | ||
69 | return (commit_a->time < commit_b->time); | |
70 | } | |
71 | ||
d568d585 | 72 | static commit_list *commit_list_insert(commit_object *item, commit_list **list_p) |
71db842f VM |
73 | { |
74 | commit_list *new_list = git__malloc(sizeof(commit_list)); | |
081d2291 CMN |
75 | if (new_list == NULL) |
76 | return NULL; | |
77 | ||
71db842f VM |
78 | new_list->item = item; |
79 | new_list->next = *list_p; | |
80 | *list_p = new_list; | |
81 | return new_list; | |
82 | } | |
83 | ||
de7ab85d CMN |
84 | static commit_list *commit_list_insert_by_date(commit_object *item, commit_list **list_p) |
85 | { | |
86 | commit_list **pp = list_p; | |
87 | commit_list *p; | |
88 | ||
89 | while ((p = *pp) != NULL) { | |
90 | if (commit_time_cmp(p->item, item) < 0) | |
91 | break; | |
92 | ||
93 | pp = &p->next; | |
94 | } | |
95 | ||
96 | return commit_list_insert(item, pp); | |
97 | } | |
d568d585 | 98 | static void commit_list_free(commit_list **list_p) |
71db842f | 99 | { |
36b31329 VM |
100 | commit_list *list = *list_p; |
101 | ||
71db842f VM |
102 | while (list) { |
103 | commit_list *temp = list; | |
104 | list = temp->next; | |
3286c408 | 105 | git__free(temp); |
71db842f | 106 | } |
36b31329 VM |
107 | |
108 | *list_p = NULL; | |
71db842f VM |
109 | } |
110 | ||
d568d585 | 111 | static commit_object *commit_list_pop(commit_list **stack) |
71db842f VM |
112 | { |
113 | commit_list *top = *stack; | |
114 | commit_object *item = top ? top->item : NULL; | |
115 | ||
116 | if (top) { | |
117 | *stack = top->next; | |
3286c408 | 118 | git__free(top); |
71db842f VM |
119 | } |
120 | return item; | |
121 | } | |
122 | ||
71db842f | 123 | static uint32_t object_table_hash(const void *key, int hash_id) |
3315782c VM |
124 | { |
125 | uint32_t r; | |
803ca5cb | 126 | const git_oid *id = key; |
5e15176d | 127 | |
71db842f | 128 | memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r)); |
3315782c VM |
129 | return r; |
130 | } | |
131 | ||
71db842f VM |
132 | #define COMMITS_PER_CHUNK 128 |
133 | #define CHUNK_STEP 64 | |
134 | #define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *)) | |
135 | ||
136 | static int alloc_chunk(git_revwalk *walk) | |
06160502 | 137 | { |
71db842f VM |
138 | void *chunk; |
139 | ||
140 | chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP); | |
141 | if (chunk == NULL) | |
142 | return GIT_ENOMEM; | |
143 | ||
144 | walk->chunk_size = 0; | |
145 | return git_vector_insert(&walk->memory_alloc, chunk); | |
146 | } | |
147 | ||
148 | static commit_object *alloc_commit(git_revwalk *walk) | |
149 | { | |
150 | unsigned char *chunk; | |
151 | ||
152 | if (walk->chunk_size == COMMITS_PER_CHUNK) | |
153 | alloc_chunk(walk); | |
154 | ||
155 | chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1); | |
156 | chunk += (walk->chunk_size * CHUNK_STEP); | |
157 | walk->chunk_size++; | |
158 | ||
159 | return (commit_object *)chunk; | |
160 | } | |
161 | ||
162 | static commit_object **alloc_parents(commit_object *commit, size_t n_parents) | |
163 | { | |
164 | if (n_parents <= PARENTS_PER_COMMIT) | |
165 | return (commit_object **)((unsigned char *)commit + sizeof(commit_object)); | |
166 | ||
167 | return git__malloc(n_parents * sizeof(commit_object *)); | |
3315782c VM |
168 | } |
169 | ||
40721f6b | 170 | |
71db842f | 171 | static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid) |
3315782c | 172 | { |
71db842f | 173 | commit_object *commit; |
58b0cbea | 174 | |
71db842f | 175 | if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL) |
3315782c | 176 | return commit; |
40721f6b | 177 | |
71db842f | 178 | commit = alloc_commit(walk); |
3315782c VM |
179 | if (commit == NULL) |
180 | return NULL; | |
5e15176d | 181 | |
71db842f | 182 | git_oid_cpy(&commit->oid, oid); |
3315782c | 183 | |
71db842f | 184 | if (git_hashtable_insert(walk->commits, &commit->oid, commit) < GIT_SUCCESS) { |
3286c408 | 185 | git__free(commit); |
71db842f VM |
186 | return NULL; |
187 | } | |
3315782c VM |
188 | |
189 | return commit; | |
06160502 | 190 | } |
08d5d000 | 191 | |
71db842f | 192 | static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw) |
e5d1faef | 193 | { |
932669b8 | 194 | const int parent_len = strlen("parent ") + GIT_OID_HEXSZ + 1; |
3315782c | 195 | |
71db842f VM |
196 | unsigned char *buffer = raw->data; |
197 | unsigned char *buffer_end = buffer + raw->len; | |
198 | unsigned char *parents_start; | |
3315782c | 199 | |
71db842f | 200 | int i, parents = 0; |
ad196c6a | 201 | int commit_time; |
3315782c | 202 | |
932669b8 | 203 | buffer += strlen("tree ") + GIT_OID_HEXSZ + 1; |
e5d1faef | 204 | |
71db842f | 205 | parents_start = buffer; |
932669b8 | 206 | while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", strlen("parent ")) == 0) { |
71db842f VM |
207 | parents++; |
208 | buffer += parent_len; | |
209 | } | |
3315782c | 210 | |
71db842f VM |
211 | commit->parents = alloc_parents(commit, parents); |
212 | if (commit->parents == NULL) | |
213 | return GIT_ENOMEM; | |
3315782c | 214 | |
71db842f VM |
215 | buffer = parents_start; |
216 | for (i = 0; i < parents; ++i) { | |
217 | git_oid oid; | |
3315782c | 218 | |
932669b8 | 219 | if (git_oid_fromstr(&oid, (char *)buffer + strlen("parent ")) < GIT_SUCCESS) |
b51c9269 | 220 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Parent object is corrupted"); |
eec95235 | 221 | |
71db842f VM |
222 | commit->parents[i] = commit_lookup(walk, &oid); |
223 | if (commit->parents[i] == NULL) | |
224 | return GIT_ENOMEM; | |
3315782c | 225 | |
71db842f VM |
226 | buffer += parent_len; |
227 | } | |
3315782c | 228 | |
71db842f | 229 | commit->out_degree = (unsigned short)parents; |
3315782c | 230 | |
71db842f | 231 | if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL) |
b51c9269 | 232 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Object is corrupted"); |
3315782c | 233 | |
71db842f VM |
234 | buffer = memchr(buffer, '>', buffer_end - buffer); |
235 | if (buffer == NULL) | |
b51c9269 | 236 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Can't find author"); |
3315782c | 237 | |
c6e65aca | 238 | if (git__strtol32(&commit_time, (char *)buffer + 2, NULL, 10) < GIT_SUCCESS) |
b51c9269 | 239 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Can't parse commit time"); |
e5d1faef | 240 | |
c6e65aca | 241 | commit->time = (time_t)commit_time; |
71db842f VM |
242 | commit->parsed = 1; |
243 | return GIT_SUCCESS; | |
3315782c | 244 | } |
8add0153 | 245 | |
71db842f | 246 | static int commit_parse(git_revwalk *walk, commit_object *commit) |
3315782c | 247 | { |
72a3fe42 | 248 | git_odb_object *obj; |
71db842f | 249 | int error; |
3315782c | 250 | |
71db842f VM |
251 | if (commit->parsed) |
252 | return GIT_SUCCESS; | |
08d5d000 | 253 | |
9462c471 | 254 | if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < GIT_SUCCESS) |
b51c9269 | 255 | return git__rethrow(error, "Failed to parse commit. Can't read object"); |
52f2390b | 256 | |
72a3fe42 | 257 | if (obj->raw.type != GIT_OBJ_COMMIT) { |
45e79e37 | 258 | git_odb_object_free(obj); |
b51c9269 | 259 | return git__throw(GIT_EOBJTYPE, "Failed to parse commit. Object is no commit object"); |
9b3577ed | 260 | } |
71db842f | 261 | |
72a3fe42 | 262 | error = commit_quick_parse(walk, commit, &obj->raw); |
45e79e37 | 263 | git_odb_object_free(obj); |
c0cd9d50 | 264 | return error == GIT_SUCCESS ? GIT_SUCCESS : git__rethrow(error, "Failed to parse commit"); |
3315782c VM |
265 | } |
266 | ||
de7ab85d CMN |
267 | static commit_object *interesting(commit_list *list) |
268 | { | |
269 | while (list) { | |
270 | commit_object *commit = list->item; | |
271 | list = list->next; | |
272 | if (commit->flags & STALE) | |
273 | continue; | |
274 | ||
275 | return commit; | |
276 | } | |
277 | ||
278 | return NULL; | |
279 | } | |
280 | ||
281 | static int merge_bases_many(commit_list **out, git_revwalk *walk, commit_object *one, git_vector *twos) | |
282 | { | |
283 | int error; | |
284 | unsigned int i; | |
285 | commit_object *two; | |
286 | commit_list *list = NULL, *result = NULL; | |
287 | ||
288 | /* if the commit is repeated, we have a our merge base already */ | |
289 | git_vector_foreach(twos, i, two) { | |
290 | if (one == two) | |
291 | return commit_list_insert(one, out) ? GIT_SUCCESS : GIT_ENOMEM; | |
292 | } | |
293 | ||
294 | if ((error = commit_parse(walk, one)) < GIT_SUCCESS) | |
295 | return error; | |
296 | ||
297 | one->flags |= PARENT1; | |
298 | if (commit_list_insert(one, &list) == NULL) | |
299 | return GIT_ENOMEM; | |
300 | ||
301 | git_vector_foreach(twos, i, two) { | |
302 | commit_parse(walk, two); | |
303 | two->flags |= PARENT2; | |
304 | if (commit_list_insert_by_date(two, &list) == NULL) | |
305 | return GIT_ENOMEM; | |
306 | } | |
307 | ||
308 | /* as long as there are non-STALE commits */ | |
309 | while (interesting(list)) { | |
310 | commit_object *commit = list->item; | |
311 | commit_list *next; | |
312 | int flags; | |
313 | ||
314 | next = list->next; | |
315 | git__free(list); | |
316 | list = next; | |
317 | ||
318 | flags = commit->flags & (PARENT1 | PARENT2 | STALE); | |
319 | if (flags == (PARENT1 | PARENT2)) { | |
320 | if (!(commit->flags & RESULT)) { | |
321 | commit->flags |= RESULT; | |
322 | if (commit_list_insert_by_date(commit, &result) == NULL) | |
323 | return GIT_ENOMEM; | |
324 | } | |
325 | /* we mark the parents of a merge stale */ | |
326 | flags |= STALE; | |
327 | } | |
328 | ||
329 | for (i = 0; i < commit->out_degree; i++) { | |
330 | commit_object *p = commit->parents[i]; | |
331 | if ((p->flags & flags) == flags) | |
332 | continue; | |
333 | ||
334 | if ((error = commit_parse(walk, p)) < GIT_SUCCESS) | |
335 | return error; | |
336 | ||
337 | p->flags |= flags; | |
338 | if (commit_list_insert_by_date(p, &list) == NULL) | |
339 | return GIT_ENOMEM; | |
340 | } | |
341 | } | |
342 | ||
343 | commit_list_free(&list); | |
344 | /* filter out any stale commits in the results */ | |
345 | list = result; | |
346 | result = NULL; | |
347 | ||
348 | while (list) { | |
349 | struct commit_list *next = list->next; | |
350 | if (!(list->item->flags & STALE)) | |
351 | if (commit_list_insert_by_date(list->item, &result) == NULL) | |
352 | return GIT_ENOMEM; | |
353 | ||
354 | free(list); | |
355 | list = next; | |
356 | } | |
357 | ||
358 | *out = result; | |
359 | return GIT_SUCCESS; | |
360 | } | |
361 | ||
362 | int git_merge_base(git_oid *out, git_repository *repo, git_oid *one, git_oid *two) | |
363 | { | |
364 | git_revwalk *walk; | |
365 | git_vector list; | |
366 | commit_list *result; | |
367 | commit_object *commit; | |
368 | void *contents[1]; | |
369 | int error; | |
370 | ||
371 | error = git_revwalk_new(&walk, repo); | |
372 | if (error < GIT_SUCCESS) | |
373 | return error; | |
374 | ||
375 | commit = commit_lookup(walk, two); | |
376 | if (commit == NULL) | |
377 | goto cleanup; | |
378 | ||
379 | /* This is just one value, so we can do it on the stack */ | |
380 | memset(&list, 0x0, sizeof(git_vector)); | |
381 | contents[0] = commit; | |
382 | list.length = 1; | |
383 | list.contents = contents; | |
384 | ||
385 | commit = commit_lookup(walk, one); | |
386 | if (commit == NULL) | |
387 | goto cleanup; | |
388 | ||
389 | error = merge_bases_many(&result, walk, commit, &list); | |
390 | if (error < GIT_SUCCESS) | |
391 | return error; | |
392 | ||
393 | if (result == NULL) | |
394 | return GIT_ENOTFOUND; | |
395 | ||
396 | git_oid_cpy(out, &result->item->oid); | |
397 | commit_list_free(&result); | |
398 | ||
399 | cleanup: | |
400 | git_revwalk_free(walk); | |
401 | ||
402 | return GIT_SUCCESS; | |
403 | } | |
404 | ||
71db842f | 405 | static void mark_uninteresting(commit_object *commit) |
3315782c | 406 | { |
71db842f VM |
407 | unsigned short i; |
408 | assert(commit); | |
1f080e2d | 409 | |
71db842f | 410 | commit->uninteresting = 1; |
08d5d000 | 411 | |
71db842f VM |
412 | for (i = 0; i < commit->out_degree; ++i) |
413 | if (!commit->parents[i]->uninteresting) | |
414 | mark_uninteresting(commit->parents[i]); | |
3315782c | 415 | } |
1a895dd7 | 416 | |
c68dee2a | 417 | static int process_commit(git_revwalk *walk, commit_object *commit, int hide) |
3315782c | 418 | { |
71db842f | 419 | int error; |
3315782c | 420 | |
c68dee2a VM |
421 | if (hide) |
422 | mark_uninteresting(commit); | |
423 | ||
71db842f VM |
424 | if (commit->seen) |
425 | return GIT_SUCCESS; | |
3315782c | 426 | |
71db842f | 427 | commit->seen = 1; |
1a895dd7 | 428 | |
71db842f | 429 | if ((error = commit_parse(walk, commit)) < GIT_SUCCESS) |
c0cd9d50 | 430 | return git__rethrow(error, "Failed to process commit"); |
e5d1faef | 431 | |
71db842f VM |
432 | return walk->enqueue(walk, commit); |
433 | } | |
3315782c | 434 | |
71db842f VM |
435 | static int process_commit_parents(git_revwalk *walk, commit_object *commit) |
436 | { | |
437 | unsigned short i; | |
438 | int error = GIT_SUCCESS; | |
c836c332 | 439 | |
71db842f | 440 | for (i = 0; i < commit->out_degree && error == GIT_SUCCESS; ++i) { |
c68dee2a | 441 | error = process_commit(walk, commit->parents[i], commit->uninteresting); |
3315782c VM |
442 | } |
443 | ||
c0cd9d50 | 444 | return error == GIT_SUCCESS ? GIT_SUCCESS : git__rethrow(error, "Failed to process commit parents"); |
08d5d000 VM |
445 | } |
446 | ||
71db842f | 447 | static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting) |
08d5d000 | 448 | { |
71db842f | 449 | commit_object *commit; |
1a895dd7 | 450 | |
71db842f VM |
451 | commit = commit_lookup(walk, oid); |
452 | if (commit == NULL) | |
b51c9269 | 453 | return git__throw(GIT_ENOTFOUND, "Failed to push commit. Object not found"); |
1f080e2d | 454 | |
c68dee2a | 455 | return process_commit(walk, commit, uninteresting); |
3315782c VM |
456 | } |
457 | ||
71db842f VM |
458 | int git_revwalk_push(git_revwalk *walk, const git_oid *oid) |
459 | { | |
460 | assert(walk && oid); | |
461 | return push_commit(walk, oid, 0); | |
462 | } | |
3315782c | 463 | |
155aca2d | 464 | |
71db842f VM |
465 | int git_revwalk_hide(git_revwalk *walk, const git_oid *oid) |
466 | { | |
467 | assert(walk && oid); | |
468 | return push_commit(walk, oid, 1); | |
469 | } | |
3315782c | 470 | |
06b9d915 CMN |
471 | static int push_ref(git_revwalk *walk, const char *refname, int hide) |
472 | { | |
473 | git_reference *ref, *resolved; | |
474 | int error; | |
475 | ||
476 | error = git_reference_lookup(&ref, walk->repo, refname); | |
477 | if (error < GIT_SUCCESS) | |
478 | return error; | |
479 | error = git_reference_resolve(&resolved, ref); | |
480 | git_reference_free(ref); | |
481 | if (error < GIT_SUCCESS) | |
482 | return error; | |
483 | error = push_commit(walk, git_reference_oid(resolved), hide); | |
484 | git_reference_free(resolved); | |
485 | return error; | |
486 | } | |
487 | ||
155aca2d CMN |
488 | struct push_cb_data { |
489 | git_revwalk *walk; | |
490 | const char *glob; | |
491 | int hide; | |
492 | }; | |
493 | ||
494 | static int push_glob_cb(const char *refname, void *data_) | |
495 | { | |
496 | struct push_cb_data *data = (struct push_cb_data *)data_; | |
497 | ||
06b9d915 CMN |
498 | if (!git__fnmatch(data->glob, refname, 0)) |
499 | return push_ref(data->walk, refname, data->hide); | |
155aca2d CMN |
500 | |
501 | return GIT_SUCCESS; | |
502 | } | |
503 | ||
504 | static int push_glob(git_revwalk *walk, const char *glob, int hide) | |
505 | { | |
506 | git_buf buf = GIT_BUF_INIT; | |
507 | struct push_cb_data data; | |
508 | int error; | |
509 | regex_t preg; | |
510 | ||
511 | assert(walk && glob); | |
512 | ||
513 | /* refs/ is implied if not given in the glob */ | |
514 | if (strncmp(glob, GIT_REFS_DIR, strlen(GIT_REFS_DIR))) { | |
515 | git_buf_printf(&buf, GIT_REFS_DIR "%s", glob); | |
516 | } else { | |
517 | git_buf_puts(&buf, glob); | |
518 | } | |
519 | ||
520 | /* If no '?', '*' or '[' exist, we append '/ *' to the glob */ | |
521 | memset(&preg, 0x0, sizeof(regex_t)); | |
522 | if (regcomp(&preg, "[?*[]", REG_EXTENDED)) { | |
523 | error = git__throw(GIT_EOSERR, "Regex failed to compile"); | |
524 | goto cleanup; | |
525 | } | |
526 | ||
527 | if (regexec(&preg, glob, 0, NULL, 0)) | |
528 | git_buf_puts(&buf, "/*"); | |
529 | ||
530 | if (git_buf_oom(&buf)) { | |
531 | error = GIT_ENOMEM; | |
532 | goto cleanup; | |
533 | } | |
534 | ||
535 | data.walk = walk; | |
536 | data.glob = git_buf_cstr(&buf); | |
537 | data.hide = hide; | |
538 | ||
539 | error = git_reference_foreach(walk->repo, GIT_REF_LISTALL, push_glob_cb, &data); | |
540 | ||
541 | cleanup: | |
542 | regfree(&preg); | |
543 | git_buf_free(&buf); | |
544 | return error; | |
545 | } | |
546 | ||
547 | int git_revwalk_push_glob(git_revwalk *walk, const char *glob) | |
548 | { | |
549 | assert(walk && glob); | |
550 | return push_glob(walk, glob, 0); | |
551 | } | |
552 | ||
553 | int git_revwalk_hide_glob(git_revwalk *walk, const char *glob) | |
554 | { | |
555 | assert(walk && glob); | |
556 | return push_glob(walk, glob, 1); | |
557 | } | |
558 | ||
f7367993 CMN |
559 | int git_revwalk_push_head(git_revwalk *walk) |
560 | { | |
561 | assert(walk); | |
06b9d915 | 562 | return push_ref(walk, GIT_HEAD_FILE, 0); |
f7367993 CMN |
563 | } |
564 | ||
565 | int git_revwalk_hide_head(git_revwalk *walk) | |
566 | { | |
567 | assert(walk); | |
06b9d915 CMN |
568 | return push_ref(walk, GIT_HEAD_FILE, 1); |
569 | } | |
570 | ||
571 | int git_revwalk_push_ref(git_revwalk *walk, const char *refname) | |
572 | { | |
573 | assert(walk && refname); | |
574 | return push_ref(walk, refname, 0); | |
575 | } | |
576 | ||
577 | int git_revwalk_hide_ref(git_revwalk *walk, const char *refname) | |
578 | { | |
579 | assert(walk && refname); | |
580 | return push_ref(walk, refname, 1); | |
f7367993 CMN |
581 | } |
582 | ||
71db842f | 583 | static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit) |
3315782c | 584 | { |
71db842f VM |
585 | return git_pqueue_insert(&walk->iterator_time, commit); |
586 | } | |
3315782c | 587 | |
71db842f VM |
588 | static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit) |
589 | { | |
590 | return commit_list_insert(commit, &walk->iterator_rand) ? GIT_SUCCESS : GIT_ENOMEM; | |
591 | } | |
3315782c | 592 | |
71db842f VM |
593 | static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk) |
594 | { | |
595 | int error; | |
596 | commit_object *next; | |
5e15176d | 597 | |
71db842f VM |
598 | while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) { |
599 | if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS) | |
c0cd9d50 | 600 | return git__rethrow(error, "Failed to load next revision"); |
6bb7aa13 | 601 | |
71db842f VM |
602 | if (!next->uninteresting) { |
603 | *object_out = next; | |
604 | return GIT_SUCCESS; | |
605 | } | |
9b3577ed | 606 | } |
08d5d000 | 607 | |
c0cd9d50 | 608 | return git__throw(GIT_EREVWALKOVER, "Failed to load next revision"); |
3315782c VM |
609 | } |
610 | ||
71db842f | 611 | static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk) |
3315782c | 612 | { |
71db842f VM |
613 | int error; |
614 | commit_object *next; | |
3315782c | 615 | |
71db842f VM |
616 | while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) { |
617 | if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS) | |
c0cd9d50 | 618 | return git__rethrow(error, "Failed to load next revision"); |
6bb7aa13 | 619 | |
71db842f VM |
620 | if (!next->uninteresting) { |
621 | *object_out = next; | |
622 | return GIT_SUCCESS; | |
623 | } | |
3315782c VM |
624 | } |
625 | ||
c0cd9d50 | 626 | return git__throw(GIT_EREVWALKOVER, "Failed to load next revision"); |
a7c182c5 | 627 | } |
1a895dd7 | 628 | |
71db842f | 629 | static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk) |
a7c182c5 | 630 | { |
71db842f VM |
631 | commit_object *next; |
632 | unsigned short i; | |
1a895dd7 | 633 | |
71db842f VM |
634 | for (;;) { |
635 | next = commit_list_pop(&walk->iterator_topo); | |
636 | if (next == NULL) | |
c0cd9d50 | 637 | return git__throw(GIT_EREVWALKOVER, "Failed to load next revision"); |
5e15176d | 638 | |
71db842f VM |
639 | if (next->in_degree > 0) { |
640 | next->topo_delay = 1; | |
641 | continue; | |
642 | } | |
655d381a | 643 | |
71db842f VM |
644 | for (i = 0; i < next->out_degree; ++i) { |
645 | commit_object *parent = next->parents[i]; | |
5e15176d | 646 | |
71db842f VM |
647 | if (--parent->in_degree == 0 && parent->topo_delay) { |
648 | parent->topo_delay = 0; | |
081d2291 CMN |
649 | if (commit_list_insert(parent, &walk->iterator_topo) == NULL) |
650 | return GIT_ENOMEM; | |
71db842f VM |
651 | } |
652 | } | |
5e15176d | 653 | |
71db842f VM |
654 | *object_out = next; |
655 | return GIT_SUCCESS; | |
656 | } | |
5e15176d VM |
657 | } |
658 | ||
71db842f | 659 | static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk) |
5e15176d | 660 | { |
71db842f VM |
661 | *object_out = commit_list_pop(&walk->iterator_reverse); |
662 | return *object_out ? GIT_SUCCESS : GIT_EREVWALKOVER; | |
663 | } | |
5e15176d | 664 | |
3315782c | 665 | |
71db842f VM |
666 | static int prepare_walk(git_revwalk *walk) |
667 | { | |
71db842f | 668 | int error; |
36aaf1ff | 669 | commit_object *next; |
08d5d000 | 670 | |
71db842f | 671 | if (walk->sorting & GIT_SORT_TOPOLOGICAL) { |
71db842f | 672 | unsigned short i; |
08d5d000 | 673 | |
71db842f VM |
674 | while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) { |
675 | for (i = 0; i < next->out_degree; ++i) { | |
676 | commit_object *parent = next->parents[i]; | |
677 | parent->in_degree++; | |
678 | } | |
3315782c | 679 | |
081d2291 CMN |
680 | if (commit_list_insert(next, &walk->iterator_topo) == NULL) |
681 | return GIT_ENOMEM; | |
71db842f | 682 | } |
3315782c | 683 | |
71db842f | 684 | if (error != GIT_EREVWALKOVER) |
c0cd9d50 | 685 | return git__rethrow(error, "Failed to prepare revision walk"); |
3315782c | 686 | |
71db842f VM |
687 | walk->get_next = &revwalk_next_toposort; |
688 | } | |
3315782c | 689 | |
71db842f | 690 | if (walk->sorting & GIT_SORT_REVERSE) { |
3315782c | 691 | |
71db842f | 692 | while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) |
081d2291 CMN |
693 | if (commit_list_insert(next, &walk->iterator_reverse) == NULL) |
694 | return GIT_ENOMEM; | |
3315782c | 695 | |
71db842f | 696 | if (error != GIT_EREVWALKOVER) |
c0cd9d50 | 697 | return git__rethrow(error, "Failed to prepare revision walk"); |
9bdb7594 | 698 | |
71db842f VM |
699 | walk->get_next = &revwalk_next_reverse; |
700 | } | |
40721f6b | 701 | |
71db842f VM |
702 | walk->walking = 1; |
703 | return GIT_SUCCESS; | |
704 | } | |
3315782c | 705 | |
3315782c | 706 | |
36aaf1ff VM |
707 | |
708 | ||
709 | ||
710 | int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) | |
711 | { | |
9462c471 | 712 | int error; |
36aaf1ff VM |
713 | git_revwalk *walk; |
714 | ||
715 | walk = git__malloc(sizeof(git_revwalk)); | |
716 | if (walk == NULL) | |
717 | return GIT_ENOMEM; | |
718 | ||
719 | memset(walk, 0x0, sizeof(git_revwalk)); | |
720 | ||
721 | walk->commits = git_hashtable_alloc(64, | |
722 | object_table_hash, | |
723 | (git_hash_keyeq_ptr)git_oid_cmp); | |
724 | ||
725 | if (walk->commits == NULL) { | |
3286c408 | 726 | git__free(walk); |
36aaf1ff VM |
727 | return GIT_ENOMEM; |
728 | } | |
729 | ||
730 | git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp); | |
731 | git_vector_init(&walk->memory_alloc, 8, NULL); | |
732 | alloc_chunk(walk); | |
733 | ||
734 | walk->get_next = &revwalk_next_unsorted; | |
735 | walk->enqueue = &revwalk_enqueue_unsorted; | |
736 | ||
737 | walk->repo = repo; | |
738 | ||
9462c471 VM |
739 | error = git_repository_odb(&walk->odb, repo); |
740 | if (error < GIT_SUCCESS) { | |
741 | git_revwalk_free(walk); | |
742 | return error; | |
743 | } | |
744 | ||
36aaf1ff VM |
745 | *revwalk_out = walk; |
746 | return GIT_SUCCESS; | |
747 | } | |
748 | ||
749 | void git_revwalk_free(git_revwalk *walk) | |
750 | { | |
751 | unsigned int i; | |
21d73e71 | 752 | commit_object *commit; |
36aaf1ff VM |
753 | |
754 | if (walk == NULL) | |
755 | return; | |
756 | ||
757 | git_revwalk_reset(walk); | |
9462c471 | 758 | git_odb_free(walk->odb); |
21d73e71 VM |
759 | |
760 | /* if the parent has more than PARENTS_PER_COMMIT parents, | |
761 | * we had to allocate a separate array for those parents. | |
762 | * make sure it's being free'd */ | |
854eccbb | 763 | GIT_HASHTABLE_FOREACH_VALUE(walk->commits, commit, { |
21d73e71 | 764 | if (commit->out_degree > PARENTS_PER_COMMIT) |
3286c408 | 765 | git__free(commit->parents); |
21d73e71 VM |
766 | }); |
767 | ||
36aaf1ff VM |
768 | git_hashtable_free(walk->commits); |
769 | git_pqueue_free(&walk->iterator_time); | |
770 | ||
771 | for (i = 0; i < walk->memory_alloc.length; ++i) | |
3286c408 | 772 | git__free(git_vector_get(&walk->memory_alloc, i)); |
36aaf1ff VM |
773 | |
774 | git_vector_free(&walk->memory_alloc); | |
3286c408 | 775 | git__free(walk); |
36aaf1ff VM |
776 | } |
777 | ||
778 | git_repository *git_revwalk_repository(git_revwalk *walk) | |
779 | { | |
780 | assert(walk); | |
781 | return walk->repo; | |
782 | } | |
783 | ||
784 | void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode) | |
785 | { | |
786 | assert(walk); | |
787 | ||
788 | if (walk->walking) | |
789 | git_revwalk_reset(walk); | |
790 | ||
791 | walk->sorting = sort_mode; | |
792 | ||
793 | if (walk->sorting & GIT_SORT_TIME) { | |
794 | walk->get_next = &revwalk_next_timesort; | |
795 | walk->enqueue = &revwalk_enqueue_timesort; | |
796 | } else { | |
797 | walk->get_next = &revwalk_next_unsorted; | |
798 | walk->enqueue = &revwalk_enqueue_unsorted; | |
799 | } | |
800 | } | |
801 | ||
71db842f VM |
802 | int git_revwalk_next(git_oid *oid, git_revwalk *walk) |
803 | { | |
804 | int error; | |
805 | commit_object *next; | |
3315782c | 806 | |
71db842f | 807 | assert(walk && oid); |
3315782c | 808 | |
71db842f VM |
809 | if (!walk->walking) { |
810 | if ((error = prepare_walk(walk)) < GIT_SUCCESS) | |
c0cd9d50 | 811 | return git__rethrow(error, "Failed to load next revision"); |
71db842f | 812 | } |
3315782c | 813 | |
71db842f | 814 | error = walk->get_next(&next, walk); |
ce90d81f VM |
815 | |
816 | if (error == GIT_EREVWALKOVER) { | |
817 | git_revwalk_reset(walk); | |
818 | return GIT_EREVWALKOVER; | |
36aaf1ff | 819 | } |
3315782c | 820 | |
ce90d81f VM |
821 | if (error < GIT_SUCCESS) |
822 | return git__rethrow(error, "Failed to load next revision"); | |
823 | ||
71db842f VM |
824 | git_oid_cpy(oid, &next->oid); |
825 | return GIT_SUCCESS; | |
3315782c VM |
826 | } |
827 | ||
71db842f | 828 | void git_revwalk_reset(git_revwalk *walk) |
3315782c | 829 | { |
71db842f | 830 | commit_object *commit; |
3315782c | 831 | |
71db842f | 832 | assert(walk); |
9bdb7594 | 833 | |
854eccbb | 834 | GIT_HASHTABLE_FOREACH_VALUE(walk->commits, commit, |
71db842f VM |
835 | commit->seen = 0; |
836 | commit->in_degree = 0; | |
837 | commit->topo_delay = 0; | |
97313ce2 | 838 | commit->uninteresting = 0; |
71db842f | 839 | ); |
9bdb7594 | 840 | |
36aaf1ff | 841 | git_pqueue_clear(&walk->iterator_time); |
36b31329 VM |
842 | commit_list_free(&walk->iterator_topo); |
843 | commit_list_free(&walk->iterator_rand); | |
844 | commit_list_free(&walk->iterator_reverse); | |
71db842f | 845 | walk->walking = 0; |
08d5d000 | 846 | } |
36b7cdb6 | 847 |