9 * Use a non-balancing simple 16-tree structure with struct int_node as
10 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
11 * 16-array of pointers to its children.
12 * The bottom 2 bits of each pointer is used to identify the pointer type
13 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
14 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
15 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
16 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
18 * The root node is a statically allocated struct int_node.
25 * Leaf nodes come in two variants, note entries and subtree entries,
26 * distinguished by the LSb of the leaf node pointer (see above).
27 * As a note entry, the key is the SHA1 of the referenced commit, and the
28 * value is the SHA1 of the note object.
29 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
30 * referenced commit, using the last byte of the key to store the length of
31 * the prefix. The value is the SHA1 of the tree object containing the notes
35 unsigned char key_sha1
[20];
36 unsigned char val_sha1
[20];
39 #define PTR_TYPE_NULL 0
40 #define PTR_TYPE_INTERNAL 1
41 #define PTR_TYPE_NOTE 2
42 #define PTR_TYPE_SUBTREE 3
44 #define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)
45 #define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))
46 #define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
48 #define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((~n & 0x01) << 2)) & 0x0f)
50 #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
51 (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
53 static struct int_node root_node
;
55 static int initialized
;
57 static void load_subtree(struct leaf_node
*subtree
, struct int_node
*node
,
61 * Search the tree until the appropriate location for the given key is found:
62 * 1. Start at the root node, with n = 0
63 * 2. If a[0] at the current level is a matching subtree entry, unpack that
64 * subtree entry and remove it; restart search at the current level.
65 * 3. Use the nth nibble of the key as an index into a:
66 * - If a[n] is an int_node, recurse from #2 into that node and increment n
67 * - If a matching subtree entry, unpack that subtree entry (and remove it);
68 * restart search at the current level.
69 * - Otherwise, we have found one of the following:
70 * - a subtree entry which does not match the key
71 * - a note entry which may or may not match the key
72 * - an unused leaf node (NULL)
73 * In any case, set *tree and *n, and return pointer to the tree location.
75 static void **note_tree_search(struct int_node
**tree
,
76 unsigned char *n
, const unsigned char *key_sha1
)
80 void *p
= (*tree
)->a
[0];
82 if (GET_PTR_TYPE(p
) == PTR_TYPE_SUBTREE
) {
83 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
84 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_sha1
)) {
85 /* unpack tree and resume search */
87 load_subtree(l
, *tree
, *n
);
89 return note_tree_search(tree
, n
, key_sha1
);
93 i
= GET_NIBBLE(*n
, key_sha1
);
95 switch (GET_PTR_TYPE(p
)) {
96 case PTR_TYPE_INTERNAL
:
97 *tree
= CLR_PTR_TYPE(p
);
99 return note_tree_search(tree
, n
, key_sha1
);
100 case PTR_TYPE_SUBTREE
:
101 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
102 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_sha1
)) {
103 /* unpack tree and resume search */
104 (*tree
)->a
[i
] = NULL
;
105 load_subtree(l
, *tree
, *n
);
107 return note_tree_search(tree
, n
, key_sha1
);
111 return &((*tree
)->a
[i
]);
116 * To find a leaf_node:
117 * Search to the tree location appropriate for the given key:
118 * If a note entry with matching key, return the note entry, else return NULL.
120 static struct leaf_node
*note_tree_find(struct int_node
*tree
, unsigned char n
,
121 const unsigned char *key_sha1
)
123 void **p
= note_tree_search(&tree
, &n
, key_sha1
);
124 if (GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
) {
125 struct leaf_node
*l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
126 if (!hashcmp(key_sha1
, l
->key_sha1
))
132 /* Create a new blob object by concatenating the two given blob objects */
133 static int concatenate_notes(unsigned char *cur_sha1
,
134 const unsigned char *new_sha1
)
136 char *cur_msg
, *new_msg
, *buf
;
137 unsigned long cur_len
, new_len
, buf_len
;
138 enum object_type cur_type
, new_type
;
141 /* read in both note blob objects */
142 new_msg
= read_sha1_file(new_sha1
, &new_type
, &new_len
);
143 if (!new_msg
|| !new_len
|| new_type
!= OBJ_BLOB
) {
147 cur_msg
= read_sha1_file(cur_sha1
, &cur_type
, &cur_len
);
148 if (!cur_msg
|| !cur_len
|| cur_type
!= OBJ_BLOB
) {
151 hashcpy(cur_sha1
, new_sha1
);
155 /* we will separate the notes by a newline anyway */
156 if (cur_msg
[cur_len
- 1] == '\n')
159 /* concatenate cur_msg and new_msg into buf */
160 buf_len
= cur_len
+ 1 + new_len
;
161 buf
= (char *) xmalloc(buf_len
);
162 memcpy(buf
, cur_msg
, cur_len
);
164 memcpy(buf
+ cur_len
+ 1, new_msg
, new_len
);
169 /* create a new blob object from buf */
170 ret
= write_sha1_file(buf
, buf_len
, "blob", cur_sha1
);
176 * To insert a leaf_node:
177 * Search to the tree location appropriate for the given leaf_node's key:
178 * - If location is unused (NULL), store the tweaked pointer directly there
179 * - If location holds a note entry that matches the note-to-be-inserted, then
180 * concatenate the two notes.
181 * - If location holds a note entry that matches the subtree-to-be-inserted,
182 * then unpack the subtree-to-be-inserted into the location.
183 * - If location holds a matching subtree entry, unpack the subtree at that
184 * location, and restart the insert operation from that level.
185 * - Else, create a new int_node, holding both the node-at-location and the
186 * node-to-be-inserted, and store the new int_node into the location.
188 static void note_tree_insert(struct int_node
*tree
, unsigned char n
,
189 struct leaf_node
*entry
, unsigned char type
)
191 struct int_node
*new_node
;
193 void **p
= note_tree_search(&tree
, &n
, entry
->key_sha1
);
195 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
196 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
197 switch (GET_PTR_TYPE(*p
)) {
200 *p
= SET_PTR_TYPE(entry
, type
);
205 if (!hashcmp(l
->key_sha1
, entry
->key_sha1
)) {
206 /* skip concatenation if l == entry */
207 if (!hashcmp(l
->val_sha1
, entry
->val_sha1
))
210 if (concatenate_notes(l
->val_sha1
,
212 die("failed to concatenate note %s "
213 "into note %s for commit %s",
214 sha1_to_hex(entry
->val_sha1
),
215 sha1_to_hex(l
->val_sha1
),
216 sha1_to_hex(l
->key_sha1
));
221 case PTR_TYPE_SUBTREE
:
222 if (!SUBTREE_SHA1_PREFIXCMP(l
->key_sha1
,
225 load_subtree(entry
, tree
, n
);
232 case PTR_TYPE_SUBTREE
:
233 if (!SUBTREE_SHA1_PREFIXCMP(entry
->key_sha1
, l
->key_sha1
)) {
234 /* unpack 'l' and restart insert */
236 load_subtree(l
, tree
, n
);
238 note_tree_insert(tree
, n
, entry
, type
);
244 /* non-matching leaf_node */
245 assert(GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
||
246 GET_PTR_TYPE(*p
) == PTR_TYPE_SUBTREE
);
247 new_node
= (struct int_node
*) xcalloc(sizeof(struct int_node
), 1);
248 note_tree_insert(new_node
, n
+ 1, l
, GET_PTR_TYPE(*p
));
249 *p
= SET_PTR_TYPE(new_node
, PTR_TYPE_INTERNAL
);
250 note_tree_insert(new_node
, n
+ 1, entry
, type
);
253 /* Free the entire notes data contained in the given tree */
254 static void note_tree_free(struct int_node
*tree
)
257 for (i
= 0; i
< 16; i
++) {
258 void *p
= tree
->a
[i
];
259 switch (GET_PTR_TYPE(p
)) {
260 case PTR_TYPE_INTERNAL
:
261 note_tree_free(CLR_PTR_TYPE(p
));
264 case PTR_TYPE_SUBTREE
:
265 free(CLR_PTR_TYPE(p
));
271 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
272 * - hex - Partial SHA1 segment in ASCII hex format
273 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
274 * - sha1 - Partial SHA1 value is written here
275 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
276 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
277 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
278 * Pads sha1 with NULs up to sha1_len (not included in returned length).
280 static int get_sha1_hex_segment(const char *hex
, unsigned int hex_len
,
281 unsigned char *sha1
, unsigned int sha1_len
)
283 unsigned int i
, len
= hex_len
>> 1;
284 if (hex_len
% 2 != 0 || len
> sha1_len
)
286 for (i
= 0; i
< len
; i
++) {
287 unsigned int val
= (hexval(hex
[0]) << 4) | hexval(hex
[1]);
293 for (; i
< sha1_len
; i
++)
298 static void load_subtree(struct leaf_node
*subtree
, struct int_node
*node
,
301 unsigned char commit_sha1
[20];
302 unsigned int prefix_len
;
304 struct tree_desc desc
;
305 struct name_entry entry
;
307 buf
= fill_tree_descriptor(&desc
, subtree
->val_sha1
);
309 die("Could not read %s for notes-index",
310 sha1_to_hex(subtree
->val_sha1
));
312 prefix_len
= subtree
->key_sha1
[19];
313 assert(prefix_len
* 2 >= n
);
314 memcpy(commit_sha1
, subtree
->key_sha1
, prefix_len
);
315 while (tree_entry(&desc
, &entry
)) {
316 int len
= get_sha1_hex_segment(entry
.path
, strlen(entry
.path
),
317 commit_sha1
+ prefix_len
, 20 - prefix_len
);
319 continue; /* entry.path is not a SHA1 sum. Skip */
323 * If commit SHA1 is complete (len == 20), assume note object
324 * If commit SHA1 is incomplete (len < 20), assume note subtree
327 unsigned char type
= PTR_TYPE_NOTE
;
328 struct leaf_node
*l
= (struct leaf_node
*)
329 xcalloc(sizeof(struct leaf_node
), 1);
330 hashcpy(l
->key_sha1
, commit_sha1
);
331 hashcpy(l
->val_sha1
, entry
.sha1
);
333 if (!S_ISDIR(entry
.mode
))
334 continue; /* entry cannot be subtree */
335 l
->key_sha1
[19] = (unsigned char) len
;
336 type
= PTR_TYPE_SUBTREE
;
338 note_tree_insert(node
, n
, l
, type
);
344 static void initialize_notes(const char *notes_ref_name
)
346 unsigned char sha1
[20], commit_sha1
[20];
348 struct leaf_node root_tree
;
350 if (!notes_ref_name
|| read_ref(notes_ref_name
, commit_sha1
) ||
351 get_tree_entry(commit_sha1
, "", sha1
, &mode
))
354 hashclr(root_tree
.key_sha1
);
355 hashcpy(root_tree
.val_sha1
, sha1
);
356 load_subtree(&root_tree
, &root_node
, 0);
359 static unsigned char *lookup_notes(const unsigned char *commit_sha1
)
361 struct leaf_node
*found
= note_tree_find(&root_node
, 0, commit_sha1
);
363 return found
->val_sha1
;
367 void free_notes(void)
369 note_tree_free(&root_node
);
370 memset(&root_node
, 0, sizeof(struct int_node
));
374 void get_commit_notes(const struct commit
*commit
, struct strbuf
*sb
,
375 const char *output_encoding
, int flags
)
377 static const char utf8
[] = "utf-8";
380 unsigned long linelen
, msglen
;
381 enum object_type type
;
384 const char *env
= getenv(GIT_NOTES_REF_ENVIRONMENT
);
386 notes_ref_name
= getenv(GIT_NOTES_REF_ENVIRONMENT
);
387 else if (!notes_ref_name
)
388 notes_ref_name
= GIT_NOTES_DEFAULT_REF
;
389 initialize_notes(notes_ref_name
);
393 sha1
= lookup_notes(commit
->object
.sha1
);
397 if (!(msg
= read_sha1_file(sha1
, &type
, &msglen
)) || !msglen
||
403 if (output_encoding
&& *output_encoding
&&
404 strcmp(utf8
, output_encoding
)) {
405 char *reencoded
= reencode_string(msg
, output_encoding
, utf8
);
409 msglen
= strlen(msg
);
413 /* we will end the annotation by a newline anyway */
414 if (msglen
&& msg
[msglen
- 1] == '\n')
417 if (flags
& NOTES_SHOW_HEADER
)
418 strbuf_addstr(sb
, "\nNotes:\n");
420 for (msg_p
= msg
; msg_p
< msg
+ msglen
; msg_p
+= linelen
+ 1) {
421 linelen
= strchrnul(msg_p
, '\n') - msg_p
;
423 if (flags
& NOTES_INDENT
)
424 strbuf_addstr(sb
, " ");
425 strbuf_add(sb
, msg_p
, linelen
);
426 strbuf_addch(sb
, '\n');