8 * Use a non-balancing simple 16-tree structure with struct int_node as
9 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
10 * 16-array of pointers to its children.
11 * The bottom 2 bits of each pointer is used to identify the pointer type
12 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
13 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
14 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
15 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
17 * The root node is a statically allocated struct int_node.
24 * Leaf nodes come in two variants, note entries and subtree entries,
25 * distinguished by the LSb of the leaf node pointer (see above).
26 * As a note entry, the key is the SHA1 of the referenced object, and the
27 * value is the SHA1 of the note object.
28 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
29 * referenced object, using the last byte of the key to store the length of
30 * the prefix. The value is the SHA1 of the tree object containing the notes
34 unsigned char key_sha1
[20];
35 unsigned char val_sha1
[20];
38 #define PTR_TYPE_NULL 0
39 #define PTR_TYPE_INTERNAL 1
40 #define PTR_TYPE_NOTE 2
41 #define PTR_TYPE_SUBTREE 3
43 #define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)
44 #define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))
45 #define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
47 #define GET_NIBBLE(n, sha1) (((sha1[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
49 #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
50 (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
52 static struct int_node root_node
;
54 static int initialized
;
56 static void load_subtree(struct leaf_node
*subtree
, struct int_node
*node
,
60 * Search the tree until the appropriate location for the given key is found:
61 * 1. Start at the root node, with n = 0
62 * 2. If a[0] at the current level is a matching subtree entry, unpack that
63 * subtree entry and remove it; restart search at the current level.
64 * 3. Use the nth nibble of the key as an index into a:
65 * - If a[n] is an int_node, recurse from #2 into that node and increment n
66 * - If a matching subtree entry, unpack that subtree entry (and remove it);
67 * restart search at the current level.
68 * - Otherwise, we have found one of the following:
69 * - a subtree entry which does not match the key
70 * - a note entry which may or may not match the key
71 * - an unused leaf node (NULL)
72 * In any case, set *tree and *n, and return pointer to the tree location.
74 static void **note_tree_search(struct int_node
**tree
,
75 unsigned char *n
, const unsigned char *key_sha1
)
79 void *p
= (*tree
)->a
[0];
81 if (GET_PTR_TYPE(p
) == PTR_TYPE_SUBTREE
) {
82 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
83 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_sha1
)) {
84 /* unpack tree and resume search */
86 load_subtree(l
, *tree
, *n
);
88 return note_tree_search(tree
, n
, key_sha1
);
92 i
= GET_NIBBLE(*n
, key_sha1
);
94 switch (GET_PTR_TYPE(p
)) {
95 case PTR_TYPE_INTERNAL
:
96 *tree
= CLR_PTR_TYPE(p
);
98 return note_tree_search(tree
, n
, key_sha1
);
99 case PTR_TYPE_SUBTREE
:
100 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
101 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_sha1
)) {
102 /* unpack tree and resume search */
103 (*tree
)->a
[i
] = NULL
;
104 load_subtree(l
, *tree
, *n
);
106 return note_tree_search(tree
, n
, key_sha1
);
110 return &((*tree
)->a
[i
]);
115 * To find a leaf_node:
116 * Search to the tree location appropriate for the given key:
117 * If a note entry with matching key, return the note entry, else return NULL.
119 static struct leaf_node
*note_tree_find(struct int_node
*tree
, unsigned char n
,
120 const unsigned char *key_sha1
)
122 void **p
= note_tree_search(&tree
, &n
, key_sha1
);
123 if (GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
) {
124 struct leaf_node
*l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
125 if (!hashcmp(key_sha1
, l
->key_sha1
))
131 /* Create a new blob object by concatenating the two given blob objects */
132 static int concatenate_notes(unsigned char *cur_sha1
,
133 const unsigned char *new_sha1
)
135 char *cur_msg
, *new_msg
, *buf
;
136 unsigned long cur_len
, new_len
, buf_len
;
137 enum object_type cur_type
, new_type
;
140 /* read in both note blob objects */
141 new_msg
= read_sha1_file(new_sha1
, &new_type
, &new_len
);
142 if (!new_msg
|| !new_len
|| new_type
!= OBJ_BLOB
) {
146 cur_msg
= read_sha1_file(cur_sha1
, &cur_type
, &cur_len
);
147 if (!cur_msg
|| !cur_len
|| cur_type
!= OBJ_BLOB
) {
150 hashcpy(cur_sha1
, new_sha1
);
154 /* we will separate the notes by a newline anyway */
155 if (cur_msg
[cur_len
- 1] == '\n')
158 /* concatenate cur_msg and new_msg into buf */
159 buf_len
= cur_len
+ 1 + new_len
;
160 buf
= (char *) xmalloc(buf_len
);
161 memcpy(buf
, cur_msg
, cur_len
);
163 memcpy(buf
+ cur_len
+ 1, new_msg
, new_len
);
168 /* create a new blob object from buf */
169 ret
= write_sha1_file(buf
, buf_len
, "blob", cur_sha1
);
175 * To insert a leaf_node:
176 * Search to the tree location appropriate for the given leaf_node's key:
177 * - If location is unused (NULL), store the tweaked pointer directly there
178 * - If location holds a note entry that matches the note-to-be-inserted, then
179 * concatenate the two notes.
180 * - If location holds a note entry that matches the subtree-to-be-inserted,
181 * then unpack the subtree-to-be-inserted into the location.
182 * - If location holds a matching subtree entry, unpack the subtree at that
183 * location, and restart the insert operation from that level.
184 * - Else, create a new int_node, holding both the node-at-location and the
185 * node-to-be-inserted, and store the new int_node into the location.
187 static void note_tree_insert(struct int_node
*tree
, unsigned char n
,
188 struct leaf_node
*entry
, unsigned char type
)
190 struct int_node
*new_node
;
192 void **p
= note_tree_search(&tree
, &n
, entry
->key_sha1
);
194 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
195 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
196 switch (GET_PTR_TYPE(*p
)) {
199 *p
= SET_PTR_TYPE(entry
, type
);
204 if (!hashcmp(l
->key_sha1
, entry
->key_sha1
)) {
205 /* skip concatenation if l == entry */
206 if (!hashcmp(l
->val_sha1
, entry
->val_sha1
))
209 if (concatenate_notes(l
->val_sha1
,
211 die("failed to concatenate note %s "
212 "into note %s for object %s",
213 sha1_to_hex(entry
->val_sha1
),
214 sha1_to_hex(l
->val_sha1
),
215 sha1_to_hex(l
->key_sha1
));
220 case PTR_TYPE_SUBTREE
:
221 if (!SUBTREE_SHA1_PREFIXCMP(l
->key_sha1
,
224 load_subtree(entry
, tree
, n
);
231 case PTR_TYPE_SUBTREE
:
232 if (!SUBTREE_SHA1_PREFIXCMP(entry
->key_sha1
, l
->key_sha1
)) {
233 /* unpack 'l' and restart insert */
235 load_subtree(l
, tree
, n
);
237 note_tree_insert(tree
, n
, entry
, type
);
243 /* non-matching leaf_node */
244 assert(GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
||
245 GET_PTR_TYPE(*p
) == PTR_TYPE_SUBTREE
);
246 new_node
= (struct int_node
*) xcalloc(sizeof(struct int_node
), 1);
247 note_tree_insert(new_node
, n
+ 1, l
, GET_PTR_TYPE(*p
));
248 *p
= SET_PTR_TYPE(new_node
, PTR_TYPE_INTERNAL
);
249 note_tree_insert(new_node
, n
+ 1, entry
, type
);
253 * How to consolidate an int_node:
254 * If there are > 1 non-NULL entries, give up and return non-zero.
255 * Otherwise replace the int_node at the given index in the given parent node
256 * with the only entry (or a NULL entry if no entries) from the given tree,
259 static int note_tree_consolidate(struct int_node
*tree
,
260 struct int_node
*parent
, unsigned char index
)
265 assert(tree
&& parent
);
266 assert(CLR_PTR_TYPE(parent
->a
[index
]) == tree
);
268 for (i
= 0; i
< 16; i
++) {
269 if (GET_PTR_TYPE(tree
->a
[i
]) != PTR_TYPE_NULL
) {
270 if (p
) /* more than one entry */
276 /* replace tree with p in parent[index] */
277 parent
->a
[index
] = p
;
283 * To remove a leaf_node:
284 * Search to the tree location appropriate for the given leaf_node's key:
285 * - If location does not hold a matching entry, abort and do nothing.
286 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
287 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
289 static void note_tree_remove(struct int_node
*tree
, unsigned char n
,
290 struct leaf_node
*entry
)
293 struct int_node
*parent_stack
[20];
295 void **p
= note_tree_search(&tree
, &n
, entry
->key_sha1
);
297 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
298 if (GET_PTR_TYPE(*p
) != PTR_TYPE_NOTE
)
299 return; /* type mismatch, nothing to remove */
300 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
301 if (hashcmp(l
->key_sha1
, entry
->key_sha1
))
302 return; /* key mismatch, nothing to remove */
304 /* we have found a matching entry */
306 *p
= SET_PTR_TYPE(NULL
, PTR_TYPE_NULL
);
308 /* consolidate this tree level, and parent levels, if possible */
310 return; /* cannot consolidate top level */
311 /* first, build stack of ancestors between root and current node */
312 parent_stack
[0] = &root_node
;
313 for (i
= 0; i
< n
; i
++) {
314 j
= GET_NIBBLE(i
, entry
->key_sha1
);
315 parent_stack
[i
+ 1] = CLR_PTR_TYPE(parent_stack
[i
]->a
[j
]);
317 assert(i
== n
&& parent_stack
[i
] == tree
);
318 /* next, unwind stack until note_tree_consolidate() is done */
320 !note_tree_consolidate(parent_stack
[i
], parent_stack
[i
- 1],
321 GET_NIBBLE(i
- 1, entry
->key_sha1
)))
325 /* Free the entire notes data contained in the given tree */
326 static void note_tree_free(struct int_node
*tree
)
329 for (i
= 0; i
< 16; i
++) {
330 void *p
= tree
->a
[i
];
331 switch (GET_PTR_TYPE(p
)) {
332 case PTR_TYPE_INTERNAL
:
333 note_tree_free(CLR_PTR_TYPE(p
));
336 case PTR_TYPE_SUBTREE
:
337 free(CLR_PTR_TYPE(p
));
343 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
344 * - hex - Partial SHA1 segment in ASCII hex format
345 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
346 * - sha1 - Partial SHA1 value is written here
347 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
348 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
349 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
350 * Pads sha1 with NULs up to sha1_len (not included in returned length).
352 static int get_sha1_hex_segment(const char *hex
, unsigned int hex_len
,
353 unsigned char *sha1
, unsigned int sha1_len
)
355 unsigned int i
, len
= hex_len
>> 1;
356 if (hex_len
% 2 != 0 || len
> sha1_len
)
358 for (i
= 0; i
< len
; i
++) {
359 unsigned int val
= (hexval(hex
[0]) << 4) | hexval(hex
[1]);
365 for (; i
< sha1_len
; i
++)
370 static void load_subtree(struct leaf_node
*subtree
, struct int_node
*node
,
373 unsigned char object_sha1
[20];
374 unsigned int prefix_len
;
376 struct tree_desc desc
;
377 struct name_entry entry
;
379 buf
= fill_tree_descriptor(&desc
, subtree
->val_sha1
);
381 die("Could not read %s for notes-index",
382 sha1_to_hex(subtree
->val_sha1
));
384 prefix_len
= subtree
->key_sha1
[19];
385 assert(prefix_len
* 2 >= n
);
386 memcpy(object_sha1
, subtree
->key_sha1
, prefix_len
);
387 while (tree_entry(&desc
, &entry
)) {
388 int len
= get_sha1_hex_segment(entry
.path
, strlen(entry
.path
),
389 object_sha1
+ prefix_len
, 20 - prefix_len
);
391 continue; /* entry.path is not a SHA1 sum. Skip */
395 * If object SHA1 is complete (len == 20), assume note object
396 * If object SHA1 is incomplete (len < 20), assume note subtree
399 unsigned char type
= PTR_TYPE_NOTE
;
400 struct leaf_node
*l
= (struct leaf_node
*)
401 xcalloc(sizeof(struct leaf_node
), 1);
402 hashcpy(l
->key_sha1
, object_sha1
);
403 hashcpy(l
->val_sha1
, entry
.sha1
);
405 if (!S_ISDIR(entry
.mode
))
406 continue; /* entry cannot be subtree */
407 l
->key_sha1
[19] = (unsigned char) len
;
408 type
= PTR_TYPE_SUBTREE
;
410 note_tree_insert(node
, n
, l
, type
);
416 void init_notes(const char *notes_ref
, int flags
)
418 unsigned char sha1
[20], object_sha1
[20];
420 struct leaf_node root_tree
;
422 assert(!initialized
);
426 notes_ref
= getenv(GIT_NOTES_REF_ENVIRONMENT
);
428 notes_ref
= notes_ref_name
; /* value of core.notesRef config */
430 notes_ref
= GIT_NOTES_DEFAULT_REF
;
432 if (flags
& NOTES_INIT_EMPTY
|| !notes_ref
||
433 read_ref(notes_ref
, object_sha1
))
435 if (get_tree_entry(object_sha1
, "", sha1
, &mode
))
436 die("Failed to read notes tree referenced by %s (%s)",
437 notes_ref
, object_sha1
);
439 hashclr(root_tree
.key_sha1
);
440 hashcpy(root_tree
.val_sha1
, sha1
);
441 load_subtree(&root_tree
, &root_node
, 0);
444 void add_note(const unsigned char *object_sha1
, const unsigned char *note_sha1
)
449 l
= (struct leaf_node
*) xmalloc(sizeof(struct leaf_node
));
450 hashcpy(l
->key_sha1
, object_sha1
);
451 hashcpy(l
->val_sha1
, note_sha1
);
452 note_tree_insert(&root_node
, 0, l
, PTR_TYPE_NOTE
);
455 void remove_note(const unsigned char *object_sha1
)
460 hashcpy(l
.key_sha1
, object_sha1
);
462 return note_tree_remove(&root_node
, 0, &l
);
465 const unsigned char *get_note(const unsigned char *object_sha1
)
467 struct leaf_node
*found
;
470 found
= note_tree_find(&root_node
, 0, object_sha1
);
471 return found
? found
->val_sha1
: NULL
;
474 void free_notes(void)
476 note_tree_free(&root_node
);
477 memset(&root_node
, 0, sizeof(struct int_node
));
481 void format_note(const unsigned char *object_sha1
, struct strbuf
*sb
,
482 const char *output_encoding
, int flags
)
484 static const char utf8
[] = "utf-8";
485 const unsigned char *sha1
;
487 unsigned long linelen
, msglen
;
488 enum object_type type
;
493 sha1
= get_note(object_sha1
);
497 if (!(msg
= read_sha1_file(sha1
, &type
, &msglen
)) || !msglen
||
503 if (output_encoding
&& *output_encoding
&&
504 strcmp(utf8
, output_encoding
)) {
505 char *reencoded
= reencode_string(msg
, output_encoding
, utf8
);
509 msglen
= strlen(msg
);
513 /* we will end the annotation by a newline anyway */
514 if (msglen
&& msg
[msglen
- 1] == '\n')
517 if (flags
& NOTES_SHOW_HEADER
)
518 strbuf_addstr(sb
, "\nNotes:\n");
520 for (msg_p
= msg
; msg_p
< msg
+ msglen
; msg_p
+= linelen
+ 1) {
521 linelen
= strchrnul(msg_p
, '\n') - msg_p
;
523 if (flags
& NOTES_INDENT
)
524 strbuf_addstr(sb
, " ");
525 strbuf_add(sb
, msg_p
, linelen
);
526 strbuf_addch(sb
, '\n');