Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 1 | #include <ctype.h> |
Linus Torvalds | 961784e | 2005-05-18 16:14:22 -0700 | [diff] [blame] | 2 | #include "tag.h" |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 3 | #include "commit.h" |
| 4 | #include "cache.h" |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 5 | |
Jon Seymour | ab580ac | 2005-07-07 02:39:34 +1000 | [diff] [blame] | 6 | struct sort_node |
| 7 | { |
| 8 | /* |
| 9 | * the number of children of the associated commit |
| 10 | * that also occur in the list being sorted. |
| 11 | */ |
| 12 | unsigned int indegree; |
| 13 | |
| 14 | /* |
| 15 | * reference to original list item that we will re-use |
| 16 | * on output. |
| 17 | */ |
| 18 | struct commit_list * list_item; |
| 19 | |
| 20 | }; |
| 21 | |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 22 | const char *commit_type = "commit"; |
| 23 | |
Linus Torvalds | 9b66ec0 | 2005-06-26 17:50:46 -0700 | [diff] [blame] | 24 | enum cmit_fmt get_commit_format(const char *arg) |
| 25 | { |
| 26 | if (!*arg) |
| 27 | return CMIT_FMT_DEFAULT; |
| 28 | if (!strcmp(arg, "=raw")) |
| 29 | return CMIT_FMT_RAW; |
| 30 | if (!strcmp(arg, "=medium")) |
| 31 | return CMIT_FMT_MEDIUM; |
| 32 | if (!strcmp(arg, "=short")) |
| 33 | return CMIT_FMT_SHORT; |
| 34 | if (!strcmp(arg, "=full")) |
| 35 | return CMIT_FMT_FULL; |
| 36 | die("invalid --pretty format"); |
| 37 | } |
| 38 | |
Jason McMullan | 5d6ccf5 | 2005-06-03 11:05:39 -0400 | [diff] [blame] | 39 | static struct commit *check_commit(struct object *obj, const unsigned char *sha1) |
Linus Torvalds | 961784e | 2005-05-18 16:14:22 -0700 | [diff] [blame] | 40 | { |
| 41 | if (obj->type != commit_type) { |
| 42 | error("Object %s is a %s, not a commit", |
| 43 | sha1_to_hex(sha1), obj->type); |
| 44 | return NULL; |
| 45 | } |
| 46 | return (struct commit *) obj; |
| 47 | } |
| 48 | |
Jason McMullan | 5d6ccf5 | 2005-06-03 11:05:39 -0400 | [diff] [blame] | 49 | struct commit *lookup_commit_reference(const unsigned char *sha1) |
Linus Torvalds | 961784e | 2005-05-18 16:14:22 -0700 | [diff] [blame] | 50 | { |
| 51 | struct object *obj = parse_object(sha1); |
| 52 | |
| 53 | if (!obj) |
| 54 | return NULL; |
| 55 | if (obj->type == tag_type) |
| 56 | obj = ((struct tag *)obj)->tagged; |
| 57 | return check_commit(obj, sha1); |
| 58 | } |
| 59 | |
Jason McMullan | 5d6ccf5 | 2005-06-03 11:05:39 -0400 | [diff] [blame] | 60 | struct commit *lookup_commit(const unsigned char *sha1) |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 61 | { |
| 62 | struct object *obj = lookup_object(sha1); |
| 63 | if (!obj) { |
Christopher Li | 812666c | 2005-04-26 12:00:58 -0700 | [diff] [blame] | 64 | struct commit *ret = xmalloc(sizeof(struct commit)); |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 65 | memset(ret, 0, sizeof(struct commit)); |
| 66 | created_object(sha1, &ret->object); |
Linus Torvalds | d32987b | 2005-04-24 14:17:13 -0700 | [diff] [blame] | 67 | ret->object.type = commit_type; |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 68 | return ret; |
| 69 | } |
Nicolas Pitre | d1af002 | 2005-05-20 16:59:17 -0400 | [diff] [blame] | 70 | if (!obj->type) |
| 71 | obj->type = commit_type; |
Linus Torvalds | 961784e | 2005-05-18 16:14:22 -0700 | [diff] [blame] | 72 | return check_commit(obj, sha1); |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 73 | } |
| 74 | |
| 75 | static unsigned long parse_commit_date(const char *buf) |
| 76 | { |
| 77 | unsigned long date; |
| 78 | |
| 79 | if (memcmp(buf, "author", 6)) |
| 80 | return 0; |
| 81 | while (*buf++ != '\n') |
| 82 | /* nada */; |
| 83 | if (memcmp(buf, "committer", 9)) |
| 84 | return 0; |
| 85 | while (*buf++ != '>') |
| 86 | /* nada */; |
| 87 | date = strtoul(buf, NULL, 10); |
| 88 | if (date == ULONG_MAX) |
| 89 | date = 0; |
| 90 | return date; |
| 91 | } |
| 92 | |
Nicolas Pitre | bd2c39f | 2005-05-06 13:48:34 -0400 | [diff] [blame] | 93 | int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size) |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 94 | { |
Nicolas Pitre | bd2c39f | 2005-05-06 13:48:34 -0400 | [diff] [blame] | 95 | void *bufptr = buffer; |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 96 | unsigned char parent[20]; |
Linus Torvalds | 6c88be1 | 2005-06-20 20:26:03 -0700 | [diff] [blame] | 97 | struct commit_list **pptr; |
Nicolas Pitre | bd2c39f | 2005-05-06 13:48:34 -0400 | [diff] [blame] | 98 | |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 99 | if (item->object.parsed) |
| 100 | return 0; |
| 101 | item->object.parsed = 1; |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 102 | get_sha1_hex(bufptr + 5, parent); |
| 103 | item->tree = lookup_tree(parent); |
Linus Torvalds | 235ac40 | 2005-04-24 14:31:57 -0700 | [diff] [blame] | 104 | if (item->tree) |
| 105 | add_ref(&item->object, &item->tree->object); |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 106 | bufptr += 46; /* "tree " + "hex sha1" + "\n" */ |
Linus Torvalds | 6c88be1 | 2005-06-20 20:26:03 -0700 | [diff] [blame] | 107 | pptr = &item->parents; |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 108 | while (!memcmp(bufptr, "parent ", 7) && |
| 109 | !get_sha1_hex(bufptr + 7, parent)) { |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 110 | struct commit *new_parent = lookup_commit(parent); |
Linus Torvalds | 235ac40 | 2005-04-24 14:31:57 -0700 | [diff] [blame] | 111 | if (new_parent) { |
Linus Torvalds | 6c88be1 | 2005-06-20 20:26:03 -0700 | [diff] [blame] | 112 | pptr = &commit_list_insert(new_parent, pptr)->next; |
Linus Torvalds | 235ac40 | 2005-04-24 14:31:57 -0700 | [diff] [blame] | 113 | add_ref(&item->object, &new_parent->object); |
| 114 | } |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 115 | bufptr += 48; |
| 116 | } |
| 117 | item->date = parse_commit_date(bufptr); |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 118 | return 0; |
| 119 | } |
| 120 | |
Nicolas Pitre | bd2c39f | 2005-05-06 13:48:34 -0400 | [diff] [blame] | 121 | int parse_commit(struct commit *item) |
| 122 | { |
| 123 | char type[20]; |
| 124 | void *buffer; |
| 125 | unsigned long size; |
| 126 | int ret; |
| 127 | |
| 128 | if (item->object.parsed) |
| 129 | return 0; |
| 130 | buffer = read_sha1_file(item->object.sha1, type, &size); |
| 131 | if (!buffer) |
| 132 | return error("Could not read %s", |
| 133 | sha1_to_hex(item->object.sha1)); |
| 134 | if (strcmp(type, commit_type)) { |
| 135 | free(buffer); |
| 136 | return error("Object %s not a commit", |
| 137 | sha1_to_hex(item->object.sha1)); |
| 138 | } |
| 139 | ret = parse_commit_buffer(item, buffer, size); |
Linus Torvalds | 3ff1fbb | 2005-05-25 18:27:14 -0700 | [diff] [blame] | 140 | if (!ret) { |
| 141 | item->buffer = buffer; |
| 142 | return 0; |
| 143 | } |
Nicolas Pitre | bd2c39f | 2005-05-06 13:48:34 -0400 | [diff] [blame] | 144 | free(buffer); |
| 145 | return ret; |
| 146 | } |
| 147 | |
Linus Torvalds | ac5155e | 2005-05-30 18:44:02 -0700 | [diff] [blame] | 148 | struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p) |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 149 | { |
Christopher Li | 812666c | 2005-04-26 12:00:58 -0700 | [diff] [blame] | 150 | struct commit_list *new_list = xmalloc(sizeof(struct commit_list)); |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 151 | new_list->item = item; |
| 152 | new_list->next = *list_p; |
| 153 | *list_p = new_list; |
Linus Torvalds | ac5155e | 2005-05-30 18:44:02 -0700 | [diff] [blame] | 154 | return new_list; |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 155 | } |
| 156 | |
Daniel Barkalow | 175785e | 2005-04-18 11:39:48 -0700 | [diff] [blame] | 157 | void free_commit_list(struct commit_list *list) |
| 158 | { |
| 159 | while (list) { |
| 160 | struct commit_list *temp = list; |
| 161 | list = temp->next; |
| 162 | free(temp); |
| 163 | } |
| 164 | } |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 165 | |
Linus Torvalds | f755494 | 2005-07-06 09:31:17 -0700 | [diff] [blame] | 166 | struct commit_list * insert_by_date(struct commit *item, struct commit_list **list) |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 167 | { |
| 168 | struct commit_list **pp = list; |
| 169 | struct commit_list *p; |
| 170 | while ((p = *pp) != NULL) { |
| 171 | if (p->item->date < item->date) { |
| 172 | break; |
| 173 | } |
| 174 | pp = &p->next; |
| 175 | } |
Linus Torvalds | f755494 | 2005-07-06 09:31:17 -0700 | [diff] [blame] | 176 | return commit_list_insert(item, pp); |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 177 | } |
| 178 | |
| 179 | |
| 180 | void sort_by_date(struct commit_list **list) |
| 181 | { |
| 182 | struct commit_list *ret = NULL; |
| 183 | while (*list) { |
Linus Torvalds | f755494 | 2005-07-06 09:31:17 -0700 | [diff] [blame] | 184 | insert_by_date((*list)->item, &ret); |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 185 | *list = (*list)->next; |
| 186 | } |
| 187 | *list = ret; |
| 188 | } |
| 189 | |
Daniel Barkalow | 58e28af | 2005-04-23 20:29:22 -0700 | [diff] [blame] | 190 | struct commit *pop_most_recent_commit(struct commit_list **list, |
| 191 | unsigned int mark) |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 192 | { |
| 193 | struct commit *ret = (*list)->item; |
| 194 | struct commit_list *parents = ret->parents; |
| 195 | struct commit_list *old = *list; |
| 196 | |
| 197 | *list = (*list)->next; |
| 198 | free(old); |
| 199 | |
| 200 | while (parents) { |
Linus Torvalds | 4056c09 | 2005-04-23 19:21:28 -0700 | [diff] [blame] | 201 | struct commit *commit = parents->item; |
Daniel Barkalow | 58e28af | 2005-04-23 20:29:22 -0700 | [diff] [blame] | 202 | parse_commit(commit); |
| 203 | if (!(commit->object.flags & mark)) { |
| 204 | commit->object.flags |= mark; |
Linus Torvalds | f755494 | 2005-07-06 09:31:17 -0700 | [diff] [blame] | 205 | insert_by_date(commit, list); |
Linus Torvalds | 4056c09 | 2005-04-23 19:21:28 -0700 | [diff] [blame] | 206 | } |
Daniel Barkalow | dd97f85 | 2005-04-23 18:47:23 -0700 | [diff] [blame] | 207 | parents = parents->next; |
| 208 | } |
| 209 | return ret; |
| 210 | } |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 211 | |
| 212 | /* |
| 213 | * Generic support for pretty-printing the header |
| 214 | */ |
| 215 | static int get_one_line(const char *msg, unsigned long len) |
| 216 | { |
| 217 | int ret = 0; |
| 218 | |
| 219 | while (len--) { |
| 220 | char c = *msg++; |
| 221 | ret++; |
| 222 | if (c == '\n') |
| 223 | break; |
| 224 | if (!c) |
| 225 | return 0; |
| 226 | } |
| 227 | return ret; |
| 228 | } |
| 229 | |
Linus Torvalds | 9b66ec0 | 2005-06-26 17:50:46 -0700 | [diff] [blame] | 230 | static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const char *line) |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 231 | { |
| 232 | char *date; |
| 233 | unsigned int namelen; |
| 234 | unsigned long time; |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 235 | int tz, ret; |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 236 | |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 237 | date = strchr(line, '>'); |
| 238 | if (!date) |
| 239 | return 0; |
| 240 | namelen = ++date - line; |
| 241 | time = strtoul(date, &date, 10); |
| 242 | tz = strtol(date, NULL, 10); |
| 243 | |
Linus Torvalds | 9b66ec0 | 2005-06-26 17:50:46 -0700 | [diff] [blame] | 244 | ret = sprintf(buf, "%s: %.*s\n", what, namelen, line); |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 245 | if (fmt == CMIT_FMT_MEDIUM) |
| 246 | ret += sprintf(buf + ret, "Date: %s\n", show_date(time, tz)); |
| 247 | return ret; |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 248 | } |
| 249 | |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 250 | static int is_empty_line(const char *line, int len) |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 251 | { |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 252 | while (len && isspace(line[len-1])) |
| 253 | len--; |
| 254 | return !len; |
| 255 | } |
| 256 | |
Linus Torvalds | 28342a5 | 2005-06-18 13:52:05 -0700 | [diff] [blame] | 257 | static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents) |
| 258 | { |
| 259 | int offset = 0; |
| 260 | switch (parents) { |
| 261 | case 1: |
| 262 | break; |
| 263 | case 2: |
| 264 | /* Go back to the previous line: 40 characters of previous parent, and one '\n' */ |
| 265 | offset = sprintf(buf, "Merge: %.40s\n", line-41); |
| 266 | /* Fallthrough */ |
| 267 | default: |
| 268 | /* Replace the previous '\n' with a space */ |
| 269 | buf[offset-1] = ' '; |
| 270 | offset += sprintf(buf + offset, "%.40s\n", line+7); |
| 271 | } |
| 272 | return offset; |
| 273 | } |
| 274 | |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 275 | unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space) |
| 276 | { |
| 277 | int hdr = 1, body = 0; |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 278 | unsigned long offset = 0; |
Linus Torvalds | 28342a5 | 2005-06-18 13:52:05 -0700 | [diff] [blame] | 279 | int parents = 0; |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 280 | |
| 281 | for (;;) { |
| 282 | const char *line = msg; |
| 283 | int linelen = get_one_line(msg, len); |
| 284 | |
| 285 | if (!linelen) |
| 286 | break; |
| 287 | |
| 288 | /* |
| 289 | * We want some slop for indentation and a possible |
| 290 | * final "...". Thus the "+ 20". |
| 291 | */ |
| 292 | if (offset + linelen + 20 > space) { |
| 293 | memcpy(buf + offset, " ...\n", 8); |
| 294 | offset += 8; |
| 295 | break; |
| 296 | } |
| 297 | |
| 298 | msg += linelen; |
| 299 | len -= linelen; |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 300 | if (hdr) { |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 301 | if (linelen == 1) { |
| 302 | hdr = 0; |
| 303 | buf[offset++] = '\n'; |
| 304 | continue; |
| 305 | } |
| 306 | if (fmt == CMIT_FMT_RAW) { |
| 307 | memcpy(buf + offset, line, linelen); |
| 308 | offset += linelen; |
| 309 | continue; |
| 310 | } |
Linus Torvalds | 28342a5 | 2005-06-18 13:52:05 -0700 | [diff] [blame] | 311 | if (!memcmp(line, "parent ", 7)) { |
| 312 | if (linelen != 48) |
| 313 | die("bad parent line in commit"); |
| 314 | offset += add_parent_info(fmt, buf + offset, line, ++parents); |
| 315 | } |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 316 | if (!memcmp(line, "author ", 7)) |
Linus Torvalds | 9b66ec0 | 2005-06-26 17:50:46 -0700 | [diff] [blame] | 317 | offset += add_user_info("Author", fmt, buf + offset, line + 7); |
| 318 | if (fmt == CMIT_FMT_FULL) { |
| 319 | if (!memcmp(line, "committer ", 10)) |
| 320 | offset += add_user_info("Commit", fmt, buf + offset, line + 10); |
| 321 | } |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 322 | continue; |
| 323 | } |
Linus Torvalds | 000182e | 2005-06-05 09:02:03 -0700 | [diff] [blame] | 324 | |
| 325 | if (is_empty_line(line, linelen)) { |
| 326 | if (!body) |
| 327 | continue; |
| 328 | if (fmt == CMIT_FMT_SHORT) |
| 329 | break; |
| 330 | } else { |
| 331 | body = 1; |
| 332 | } |
Linus Torvalds | e3bc7a3 | 2005-06-01 08:34:23 -0700 | [diff] [blame] | 333 | memset(buf + offset, ' ', 4); |
| 334 | memcpy(buf + offset + 4, line, linelen); |
| 335 | offset += linelen + 4; |
| 336 | } |
| 337 | /* Make sure there is an EOLN */ |
| 338 | if (buf[offset - 1] != '\n') |
| 339 | buf[offset++] = '\n'; |
| 340 | buf[offset] = '\0'; |
| 341 | return offset; |
| 342 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 343 | |
| 344 | struct commit *pop_commit(struct commit_list **stack) |
| 345 | { |
| 346 | struct commit_list *top = *stack; |
| 347 | struct commit *item = top ? top->item : NULL; |
| 348 | |
| 349 | if (top) { |
| 350 | *stack = top->next; |
| 351 | free(top); |
| 352 | } |
| 353 | return item; |
| 354 | } |
| 355 | |
| 356 | int count_parents(struct commit * commit) |
| 357 | { |
| 358 | int count = 0; |
| 359 | struct commit_list * parents = commit->parents; |
| 360 | for (count=0;parents; parents=parents->next,count++) |
| 361 | ; |
| 362 | return count; |
| 363 | } |
| 364 | |
Jon Seymour | ab580ac | 2005-07-07 02:39:34 +1000 | [diff] [blame] | 365 | /* |
| 366 | * Performs an in-place topological sort on the list supplied. |
| 367 | */ |
| 368 | void sort_in_topological_order(struct commit_list ** list) |
| 369 | { |
| 370 | struct commit_list * next = *list; |
| 371 | struct commit_list * work = NULL; |
| 372 | struct commit_list ** pptr = list; |
| 373 | struct sort_node * nodes; |
| 374 | struct sort_node * next_nodes; |
| 375 | int count = 0; |
| 376 | |
| 377 | /* determine the size of the list */ |
| 378 | while (next) { |
| 379 | next = next->next; |
| 380 | count++; |
| 381 | } |
| 382 | /* allocate an array to help sort the list */ |
| 383 | nodes = xcalloc(count, sizeof(*nodes)); |
| 384 | /* link the list to the array */ |
| 385 | next_nodes = nodes; |
| 386 | next=*list; |
| 387 | while (next) { |
| 388 | next_nodes->list_item = next; |
| 389 | next->item->object.util = next_nodes; |
| 390 | next_nodes++; |
| 391 | next = next->next; |
| 392 | } |
| 393 | /* update the indegree */ |
| 394 | next=*list; |
| 395 | while (next) { |
| 396 | struct commit_list * parents = next->item->parents; |
| 397 | while (parents) { |
| 398 | struct commit * parent=parents->item; |
| 399 | struct sort_node * pn = (struct sort_node *)parent->object.util; |
| 400 | |
| 401 | if (pn) |
| 402 | pn->indegree++; |
| 403 | parents=parents->next; |
| 404 | } |
| 405 | next=next->next; |
| 406 | } |
| 407 | /* |
| 408 | * find the tips |
| 409 | * |
| 410 | * tips are nodes not reachable from any other node in the list |
| 411 | * |
| 412 | * the tips serve as a starting set for the work queue. |
| 413 | */ |
| 414 | next=*list; |
| 415 | while (next) { |
| 416 | struct sort_node * node = (struct sort_node *)next->item->object.util; |
| 417 | |
| 418 | if (node->indegree == 0) { |
| 419 | commit_list_insert(next->item, &work); |
| 420 | } |
| 421 | next=next->next; |
| 422 | } |
| 423 | /* process the list in topological order */ |
| 424 | while (work) { |
| 425 | struct commit * work_item = pop_commit(&work); |
| 426 | struct sort_node * work_node = (struct sort_node *)work_item->object.util; |
| 427 | struct commit_list * parents = work_item->parents; |
| 428 | |
| 429 | while (parents) { |
| 430 | struct commit * parent=parents->item; |
| 431 | struct sort_node * pn = (struct sort_node *)parent->object.util; |
| 432 | |
| 433 | if (pn) { |
| 434 | /* |
| 435 | * parents are only enqueued for emission |
| 436 | * when all their children have been emitted thereby |
| 437 | * guaranteeing topological order. |
| 438 | */ |
| 439 | pn->indegree--; |
| 440 | if (!pn->indegree) |
| 441 | commit_list_insert(parent, &work); |
| 442 | } |
| 443 | parents=parents->next; |
| 444 | } |
| 445 | /* |
| 446 | * work_item is a commit all of whose children |
| 447 | * have already been emitted. we can emit it now. |
| 448 | */ |
| 449 | *pptr = work_node->list_item; |
| 450 | pptr = &(*pptr)->next; |
| 451 | *pptr = NULL; |
| 452 | work_item->object.util = NULL; |
| 453 | } |
| 454 | free(nodes); |
| 455 | } |