commit: add generation number to struct commit

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one
more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this
information to revision walks. We use three special values to signal
the generation number is invalid:

GENERATION_NUMBER_INFINITY 0xFFFFFFFF
GENERATION_NUMBER_MAX 0x3FFFFFFF
GENERATION_NUMBER_ZERO 0

The first (_INFINITY) means the generation number has not been loaded or
computed. The second (_MAX) means the generation number is too large to
store in the commit-graph file. The third (_ZERO) means the generation
number was loaded from a commit graph file that was written by a version
of git that did not support generation numbers.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/alloc.c b/alloc.c
index cf4f8b61e126c0e9992dc34c6cb52b6f896a565d..e8ab14f4a12bc65eb32152192af1faf719e3423c 100644 (file)
--- a/alloc.c
+++ b/alloc.c
@@ -94,6 +94,7 @@ void *alloc_commit_node(void)
        c->object.type = OBJ_COMMIT;
        c->index = alloc_commit_index();
        c->graph_pos = COMMIT_NOT_FROM_GRAPH;
+       c->generation = GENERATION_NUMBER_INFINITY;
        return c;
 }
 

diff --git a/commit-graph.c b/commit-graph.c
index 70fa1b25fd3d07a935cc0e7ba4cf70bc24ca3d21..9ad21c3ffb6fb0104deba7e8fed12972351ce51b 100644 (file)
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -262,6 +262,8 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin
        date_low = get_be32(commit_data + g->hash_len + 12);
        item->date = (timestamp_t)((date_high << 32) | date_low);
 
+       item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
+
        pptr = &item->parents;
 
        edge_value = get_be32(commit_data + g->hash_len);

diff --git a/commit.h b/commit.h
index 23a3f364edec6b609a39f15518cfda06af69e487..aac3b8c56faf4b82199fb7d7763aad06f2e4e32f 100644 (file)
--- a/commit.h
+++ b/commit.h
@@ -10,6 +10,9 @@
 #include "pretty.h"
 
 #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
+#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF
+#define GENERATION_NUMBER_MAX 0x3FFFFFFF
+#define GENERATION_NUMBER_ZERO 0
 
 struct commit_list {
        struct commit *item;
@@ -30,6 +33,7 @@ struct commit {
         */
        struct tree *maybe_tree;
        uint32_t graph_pos;
+       uint32_t generation;
 };
 
 extern int save_commit_buffer;