1 /* 2 * Copyright (C) the libgit2 contributors. All rights reserved. 3 * 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. 6 */ 7 8 #ifndef INCLUDE_commit_graph_h__ 9 #define INCLUDE_commit_graph_h__ 10 11 #include "common.h" 12 13 #include "git2/types.h" 14 #include "git2/sys/commit_graph.h" 15 16 #include "map.h" 17 #include "vector.h" 18 19 /** 20 * A commit-graph file. 21 * 22 * This file contains metadata about commits, particularly the generation 23 * number for each one. This can help speed up graph operations without 24 * requiring a full graph traversal. 25 * 26 * Support for this feature was added in git 2.19. 27 */ 28 typedef struct git_commit_graph_file { 29 git_map graph_map; 30 31 /* The OID Fanout table. */ 32 const uint32_t *oid_fanout; 33 /* The total number of commits in the graph. */ 34 uint32_t num_commits; 35 36 /* The OID Lookup table. */ 37 git_oid *oid_lookup; 38 39 /* 40 * The Commit Data table. Each entry contains the OID of the commit followed 41 * by two 8-byte fields in network byte order: 42 * - The indices of the first two parents (32 bits each). 43 * - The generation number (first 30 bits) and commit time in seconds since 44 * UNIX epoch (34 bits). 45 */ 46 const unsigned char *commit_data; 47 48 /* 49 * The Extra Edge List table. Each 4-byte entry is a network byte order index 50 * of one of the i-th (i > 0) parents of commits in the `commit_data` table, 51 * when the commit has more than 2 parents. 52 */ 53 const unsigned char *extra_edge_list; 54 /* The number of entries in the Extra Edge List table. Each entry is 4 bytes wide. */ 55 size_t num_extra_edge_list; 56 57 /* The trailer of the file. Contains the SHA1-checksum of the whole file. */ 58 git_oid checksum; 59 } git_commit_graph_file; 60 61 /** 62 * An entry in the commit-graph file. Provides a subset of the information that 63 * can be obtained from the commit header. 64 */ 65 typedef struct git_commit_graph_entry { 66 /* The generation number of the commit within the graph */ 67 size_t generation; 68 69 /* Time in seconds from UNIX epoch. */ 70 git_time_t commit_time; 71 72 /* The number of parents of the commit. */ 73 size_t parent_count; 74 75 /* 76 * The indices of the parent commits within the Commit Data table. The value 77 * of `GIT_COMMIT_GRAPH_MISSING_PARENT` indicates that no parent is in that 78 * position. 79 */ 80 size_t parent_indices[2]; 81 82 /* The index within the Extra Edge List of any parent after the first two. */ 83 size_t extra_parents_index; 84 85 /* The SHA-1 hash of the root tree of the commit. */ 86 git_oid tree_oid; 87 88 /* The SHA-1 hash of the requested commit. */ 89 git_oid sha1; 90 } git_commit_graph_entry; 91 92 /* A wrapper for git_commit_graph_file to enable lazy loading in the ODB. */ 93 struct git_commit_graph { 94 /* The path to the commit-graph file. Something like ".git/objects/info/commit-graph". */ 95 git_buf filename; 96 97 /* The underlying commit-graph file. */ 98 git_commit_graph_file *file; 99 100 /* Whether the commit-graph file was already checked for validity. */ 101 bool checked; 102 }; 103 104 /** Create a new commit-graph, optionally opening the underlying file. */ 105 int git_commit_graph_new(git_commit_graph **cgraph_out, const char *objects_dir, bool open_file); 106 107 /** Open and validate a commit-graph file. */ 108 int git_commit_graph_file_open(git_commit_graph_file **file_out, const char *path); 109 110 /* 111 * Attempt to get the git_commit_graph's commit-graph file. This object is 112 * still owned by the git_commit_graph. If the repository does not contain a commit graph, 113 * it will return GIT_ENOTFOUND. 114 * 115 * This function is not thread-safe. 116 */ 117 int git_commit_graph_get_file(git_commit_graph_file **file_out, git_commit_graph *cgraph); 118 119 /* Marks the commit-graph file as needing a refresh. */ 120 void git_commit_graph_refresh(git_commit_graph *cgraph); 121 122 /* 123 * A writer for `commit-graph` files. 124 */ 125 struct git_commit_graph_writer { 126 /* 127 * The path of the `objects/info` directory where the `commit-graph` will be 128 * stored. 129 */ 130 git_buf objects_info_dir; 131 132 /* The list of packed commits. */ 133 git_vector commits; 134 }; 135 136 /* 137 * Returns whether the git_commit_graph_file needs to be reloaded since the 138 * contents of the commit-graph file have changed on disk. 139 */ 140 bool git_commit_graph_file_needs_refresh( 141 const git_commit_graph_file *file, const char *path); 142 143 int git_commit_graph_entry_find( 144 git_commit_graph_entry *e, 145 const git_commit_graph_file *file, 146 const git_oid *short_oid, 147 size_t len); 148 int git_commit_graph_entry_parent( 149 git_commit_graph_entry *parent, 150 const git_commit_graph_file *file, 151 const git_commit_graph_entry *entry, 152 size_t n); 153 int git_commit_graph_file_close(git_commit_graph_file *cgraph); 154 void git_commit_graph_file_free(git_commit_graph_file *cgraph); 155 156 /* This is exposed for use in the fuzzers. */ 157 int git_commit_graph_file_parse( 158 git_commit_graph_file *file, 159 const unsigned char *data, 160 size_t size); 161 162 #endif 163