Notes API: Allow multiple concurrent notes trees with new struct notes_tree
[git/git.git] / notes.c
CommitLineData
a97a7468 1#include "cache.h"
a97a7468 2#include "notes.h"
61a7cca0 3#include "tree.h"
a97a7468
JS
4#include "utf8.h"
5#include "strbuf.h"
fd53c9eb
JS
6#include "tree-walk.h"
7
23123aec
JH
8/*
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 *
17 *
18 * The root node is a statically allocated struct int_node.
19 */
20struct int_node {
21 void *a[16];
fd53c9eb
JS
22};
23
23123aec
JH
24/*
25 * Leaf nodes come in two variants, note entries and subtree entries,
26 * distinguished by the LSb of the leaf node pointer (see above).
a7e7eff6 27 * As a note entry, the key is the SHA1 of the referenced object, and the
23123aec
JH
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
a7e7eff6 30 * referenced object, using the last byte of the key to store the length of
23123aec
JH
31 * the prefix. The value is the SHA1 of the tree object containing the notes
32 * subtree.
33 */
34struct leaf_node {
35 unsigned char key_sha1[20];
36 unsigned char val_sha1[20];
fd53c9eb 37};
a97a7468 38
23123aec
JH
39#define PTR_TYPE_NULL 0
40#define PTR_TYPE_INTERNAL 1
41#define PTR_TYPE_NOTE 2
42#define PTR_TYPE_SUBTREE 3
fd53c9eb 43
23123aec
JH
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)))
fd53c9eb 47
1ec666b0 48#define GET_NIBBLE(n, sha1) (((sha1[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
fd53c9eb 49
23123aec
JH
50#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
51 (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
fd53c9eb 52
cd305392 53struct notes_tree default_notes_tree;
23123aec
JH
54
55static void load_subtree(struct leaf_node *subtree, struct int_node *node,
56 unsigned int n);
57
58/*
ef8db638 59 * Search the tree until the appropriate location for the given key is found:
23123aec 60 * 1. Start at the root node, with n = 0
ef8db638
JH
61 * 2. If a[0] at the current level is a matching subtree entry, unpack that
62 * subtree entry and remove it; restart search at the current level.
63 * 3. Use the nth nibble of the key as an index into a:
64 * - If a[n] is an int_node, recurse from #2 into that node and increment n
23123aec
JH
65 * - If a matching subtree entry, unpack that subtree entry (and remove it);
66 * restart search at the current level.
ef8db638
JH
67 * - Otherwise, we have found one of the following:
68 * - a subtree entry which does not match the key
69 * - a note entry which may or may not match the key
70 * - an unused leaf node (NULL)
71 * In any case, set *tree and *n, and return pointer to the tree location.
23123aec 72 */
ef8db638
JH
73static void **note_tree_search(struct int_node **tree,
74 unsigned char *n, const unsigned char *key_sha1)
23123aec
JH
75{
76 struct leaf_node *l;
ef8db638
JH
77 unsigned char i;
78 void *p = (*tree)->a[0];
23123aec 79
ef8db638
JH
80 if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
81 l = (struct leaf_node *) CLR_PTR_TYPE(p);
82 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
83 /* unpack tree and resume search */
84 (*tree)->a[0] = NULL;
85 load_subtree(l, *tree, *n);
86 free(l);
87 return note_tree_search(tree, n, key_sha1);
88 }
89 }
90
91 i = GET_NIBBLE(*n, key_sha1);
92 p = (*tree)->a[i];
0ab1faae 93 switch (GET_PTR_TYPE(p)) {
23123aec 94 case PTR_TYPE_INTERNAL:
ef8db638
JH
95 *tree = CLR_PTR_TYPE(p);
96 (*n)++;
97 return note_tree_search(tree, n, key_sha1);
23123aec
JH
98 case PTR_TYPE_SUBTREE:
99 l = (struct leaf_node *) CLR_PTR_TYPE(p);
100 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
101 /* unpack tree and resume search */
ef8db638
JH
102 (*tree)->a[i] = NULL;
103 load_subtree(l, *tree, *n);
23123aec 104 free(l);
ef8db638 105 return note_tree_search(tree, n, key_sha1);
23123aec 106 }
ef8db638 107 /* fall through */
23123aec 108 default:
ef8db638 109 return &((*tree)->a[i]);
fd53c9eb 110 }
ef8db638 111}
23123aec 112
ef8db638
JH
113/*
114 * To find a leaf_node:
115 * Search to the tree location appropriate for the given key:
116 * If a note entry with matching key, return the note entry, else return NULL.
117 */
118static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
119 const unsigned char *key_sha1)
120{
121 void **p = note_tree_search(&tree, &n, key_sha1);
122 if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
123 struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
124 if (!hashcmp(key_sha1, l->key_sha1))
125 return l;
23123aec
JH
126 }
127 return NULL;
fd53c9eb
JS
128}
129
ef8db638
JH
130/* Create a new blob object by concatenating the two given blob objects */
131static int concatenate_notes(unsigned char *cur_sha1,
132 const unsigned char *new_sha1)
133{
134 char *cur_msg, *new_msg, *buf;
135 unsigned long cur_len, new_len, buf_len;
136 enum object_type cur_type, new_type;
137 int ret;
138
139 /* read in both note blob objects */
140 new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
141 if (!new_msg || !new_len || new_type != OBJ_BLOB) {
142 free(new_msg);
143 return 0;
144 }
145 cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
146 if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
147 free(cur_msg);
148 free(new_msg);
149 hashcpy(cur_sha1, new_sha1);
150 return 0;
151 }
152
153 /* we will separate the notes by a newline anyway */
154 if (cur_msg[cur_len - 1] == '\n')
155 cur_len--;
156
157 /* concatenate cur_msg and new_msg into buf */
158 buf_len = cur_len + 1 + new_len;
159 buf = (char *) xmalloc(buf_len);
160 memcpy(buf, cur_msg, cur_len);
161 buf[cur_len] = '\n';
162 memcpy(buf + cur_len + 1, new_msg, new_len);
163
164 free(cur_msg);
165 free(new_msg);
166
167 /* create a new blob object from buf */
168 ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
169 free(buf);
170 return ret;
171}
172
23123aec
JH
173/*
174 * To insert a leaf_node:
ef8db638
JH
175 * Search to the tree location appropriate for the given leaf_node's key:
176 * - If location is unused (NULL), store the tweaked pointer directly there
177 * - If location holds a note entry that matches the note-to-be-inserted, then
178 * concatenate the two notes.
179 * - If location holds a note entry that matches the subtree-to-be-inserted,
180 * then unpack the subtree-to-be-inserted into the location.
181 * - If location holds a matching subtree entry, unpack the subtree at that
182 * location, and restart the insert operation from that level.
183 * - Else, create a new int_node, holding both the node-at-location and the
184 * node-to-be-inserted, and store the new int_node into the location.
23123aec 185 */
ef8db638
JH
186static void note_tree_insert(struct int_node *tree, unsigned char n,
187 struct leaf_node *entry, unsigned char type)
fd53c9eb 188{
23123aec 189 struct int_node *new_node;
ef8db638
JH
190 struct leaf_node *l;
191 void **p = note_tree_search(&tree, &n, entry->key_sha1);
192
193 assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
194 l = (struct leaf_node *) CLR_PTR_TYPE(*p);
0ab1faae 195 switch (GET_PTR_TYPE(*p)) {
23123aec 196 case PTR_TYPE_NULL:
ef8db638
JH
197 assert(!*p);
198 *p = SET_PTR_TYPE(entry, type);
199 return;
200 case PTR_TYPE_NOTE:
201 switch (type) {
202 case PTR_TYPE_NOTE:
203 if (!hashcmp(l->key_sha1, entry->key_sha1)) {
204 /* skip concatenation if l == entry */
205 if (!hashcmp(l->val_sha1, entry->val_sha1))
206 return;
207
208 if (concatenate_notes(l->val_sha1,
209 entry->val_sha1))
210 die("failed to concatenate note %s "
a7e7eff6 211 "into note %s for object %s",
ef8db638
JH
212 sha1_to_hex(entry->val_sha1),
213 sha1_to_hex(l->val_sha1),
214 sha1_to_hex(l->key_sha1));
215 free(entry);
216 return;
217 }
218 break;
219 case PTR_TYPE_SUBTREE:
220 if (!SUBTREE_SHA1_PREFIXCMP(l->key_sha1,
221 entry->key_sha1)) {
222 /* unpack 'entry' */
223 load_subtree(entry, tree, n);
224 free(entry);
225 return;
226 }
227 break;
228 }
229 break;
230 case PTR_TYPE_SUBTREE:
231 if (!SUBTREE_SHA1_PREFIXCMP(entry->key_sha1, l->key_sha1)) {
232 /* unpack 'l' and restart insert */
233 *p = NULL;
234 load_subtree(l, tree, n);
235 free(l);
236 note_tree_insert(tree, n, entry, type);
237 return;
23123aec 238 }
ef8db638 239 break;
fd53c9eb 240 }
ef8db638
JH
241
242 /* non-matching leaf_node */
243 assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
244 GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
245 new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
246 note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p));
247 *p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
248 note_tree_insert(new_node, n + 1, entry, type);
23123aec 249}
fd53c9eb 250
1ec666b0
JH
251/*
252 * How to consolidate an int_node:
253 * If there are > 1 non-NULL entries, give up and return non-zero.
254 * Otherwise replace the int_node at the given index in the given parent node
255 * with the only entry (or a NULL entry if no entries) from the given tree,
256 * and return 0.
257 */
258static int note_tree_consolidate(struct int_node *tree,
259 struct int_node *parent, unsigned char index)
260{
261 unsigned int i;
262 void *p = NULL;
263
264 assert(tree && parent);
265 assert(CLR_PTR_TYPE(parent->a[index]) == tree);
266
267 for (i = 0; i < 16; i++) {
268 if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
269 if (p) /* more than one entry */
270 return -2;
271 p = tree->a[i];
272 }
273 }
274
275 /* replace tree with p in parent[index] */
276 parent->a[index] = p;
277 free(tree);
278 return 0;
279}
280
281/*
282 * To remove a leaf_node:
283 * Search to the tree location appropriate for the given leaf_node's key:
284 * - If location does not hold a matching entry, abort and do nothing.
285 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
286 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
287 */
cd305392
JH
288static void note_tree_remove(struct notes_tree *t, struct int_node *tree,
289 unsigned char n, struct leaf_node *entry)
1ec666b0
JH
290{
291 struct leaf_node *l;
292 struct int_node *parent_stack[20];
293 unsigned char i, j;
294 void **p = note_tree_search(&tree, &n, entry->key_sha1);
295
296 assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
297 if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE)
298 return; /* type mismatch, nothing to remove */
299 l = (struct leaf_node *) CLR_PTR_TYPE(*p);
300 if (hashcmp(l->key_sha1, entry->key_sha1))
301 return; /* key mismatch, nothing to remove */
302
303 /* we have found a matching entry */
304 free(l);
305 *p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL);
306
307 /* consolidate this tree level, and parent levels, if possible */
308 if (!n)
309 return; /* cannot consolidate top level */
310 /* first, build stack of ancestors between root and current node */
cd305392 311 parent_stack[0] = t->root;
1ec666b0
JH
312 for (i = 0; i < n; i++) {
313 j = GET_NIBBLE(i, entry->key_sha1);
314 parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]);
315 }
316 assert(i == n && parent_stack[i] == tree);
317 /* next, unwind stack until note_tree_consolidate() is done */
318 while (i > 0 &&
319 !note_tree_consolidate(parent_stack[i], parent_stack[i - 1],
320 GET_NIBBLE(i - 1, entry->key_sha1)))
321 i--;
322}
323
23123aec
JH
324/* Free the entire notes data contained in the given tree */
325static void note_tree_free(struct int_node *tree)
326{
327 unsigned int i;
328 for (i = 0; i < 16; i++) {
329 void *p = tree->a[i];
0ab1faae 330 switch (GET_PTR_TYPE(p)) {
23123aec
JH
331 case PTR_TYPE_INTERNAL:
332 note_tree_free(CLR_PTR_TYPE(p));
333 /* fall through */
334 case PTR_TYPE_NOTE:
335 case PTR_TYPE_SUBTREE:
336 free(CLR_PTR_TYPE(p));
337 }
fd53c9eb 338 }
23123aec 339}
fd53c9eb 340
23123aec
JH
341/*
342 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
343 * - hex - Partial SHA1 segment in ASCII hex format
344 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
345 * - sha1 - Partial SHA1 value is written here
346 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
0ab1faae 347 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
23123aec
JH
348 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
349 * Pads sha1 with NULs up to sha1_len (not included in returned length).
350 */
351static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
352 unsigned char *sha1, unsigned int sha1_len)
353{
354 unsigned int i, len = hex_len >> 1;
355 if (hex_len % 2 != 0 || len > sha1_len)
356 return -1;
357 for (i = 0; i < len; i++) {
358 unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
359 if (val & ~0xff)
360 return -1;
361 *sha1++ = val;
362 hex += 2;
363 }
364 for (; i < sha1_len; i++)
365 *sha1++ = 0;
366 return len;
fd53c9eb
JS
367}
368
23123aec
JH
369static void load_subtree(struct leaf_node *subtree, struct int_node *node,
370 unsigned int n)
fd53c9eb 371{
a7e7eff6 372 unsigned char object_sha1[20];
23123aec 373 unsigned int prefix_len;
23123aec 374 void *buf;
fd53c9eb
JS
375 struct tree_desc desc;
376 struct name_entry entry;
23123aec
JH
377
378 buf = fill_tree_descriptor(&desc, subtree->val_sha1);
379 if (!buf)
380 die("Could not read %s for notes-index",
381 sha1_to_hex(subtree->val_sha1));
382
383 prefix_len = subtree->key_sha1[19];
384 assert(prefix_len * 2 >= n);
a7e7eff6 385 memcpy(object_sha1, subtree->key_sha1, prefix_len);
23123aec
JH
386 while (tree_entry(&desc, &entry)) {
387 int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
a7e7eff6 388 object_sha1 + prefix_len, 20 - prefix_len);
23123aec
JH
389 if (len < 0)
390 continue; /* entry.path is not a SHA1 sum. Skip */
391 len += prefix_len;
392
393 /*
a7e7eff6
JH
394 * If object SHA1 is complete (len == 20), assume note object
395 * If object SHA1 is incomplete (len < 20), assume note subtree
23123aec
JH
396 */
397 if (len <= 20) {
398 unsigned char type = PTR_TYPE_NOTE;
399 struct leaf_node *l = (struct leaf_node *)
400 xcalloc(sizeof(struct leaf_node), 1);
a7e7eff6 401 hashcpy(l->key_sha1, object_sha1);
23123aec
JH
402 hashcpy(l->val_sha1, entry.sha1);
403 if (len < 20) {
488bdf2e
JH
404 if (!S_ISDIR(entry.mode))
405 continue; /* entry cannot be subtree */
23123aec
JH
406 l->key_sha1[19] = (unsigned char) len;
407 type = PTR_TYPE_SUBTREE;
408 }
ef8db638 409 note_tree_insert(node, n, l, type);
23123aec
JH
410 }
411 }
412 free(buf);
413}
414
73f77b90
JH
415/*
416 * Determine optimal on-disk fanout for this part of the notes tree
417 *
418 * Given a (sub)tree and the level in the internal tree structure, determine
419 * whether or not the given existing fanout should be expanded for this
420 * (sub)tree.
421 *
422 * Values of the 'fanout' variable:
423 * - 0: No fanout (all notes are stored directly in the root notes tree)
424 * - 1: 2/38 fanout
425 * - 2: 2/2/36 fanout
426 * - 3: 2/2/2/34 fanout
427 * etc.
428 */
429static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
430 unsigned char fanout)
431{
432 /*
433 * The following is a simple heuristic that works well in practice:
434 * For each even-numbered 16-tree level (remember that each on-disk
435 * fanout level corresponds to _two_ 16-tree levels), peek at all 16
436 * entries at that tree level. If all of them are either int_nodes or
437 * subtree entries, then there are likely plenty of notes below this
438 * level, so we return an incremented fanout.
439 */
440 unsigned int i;
441 if ((n % 2) || (n > 2 * fanout))
442 return fanout;
443 for (i = 0; i < 16; i++) {
444 switch (GET_PTR_TYPE(tree->a[i])) {
445 case PTR_TYPE_SUBTREE:
446 case PTR_TYPE_INTERNAL:
447 continue;
448 default:
449 return fanout;
450 }
451 }
452 return fanout + 1;
453}
454
455static void construct_path_with_fanout(const unsigned char *sha1,
456 unsigned char fanout, char *path)
457{
458 unsigned int i = 0, j = 0;
459 const char *hex_sha1 = sha1_to_hex(sha1);
460 assert(fanout < 20);
461 while (fanout) {
462 path[i++] = hex_sha1[j++];
463 path[i++] = hex_sha1[j++];
464 path[i++] = '/';
465 fanout--;
466 }
467 strcpy(path + i, hex_sha1 + j);
468}
469
470static int for_each_note_helper(struct int_node *tree, unsigned char n,
471 unsigned char fanout, int flags, each_note_fn fn,
472 void *cb_data)
473{
474 unsigned int i;
475 void *p;
476 int ret = 0;
477 struct leaf_node *l;
478 static char path[40 + 19 + 1]; /* hex SHA1 + 19 * '/' + NUL */
479
480 fanout = determine_fanout(tree, n, fanout);
481 for (i = 0; i < 16; i++) {
482redo:
483 p = tree->a[i];
484 switch (GET_PTR_TYPE(p)) {
485 case PTR_TYPE_INTERNAL:
486 /* recurse into int_node */
487 ret = for_each_note_helper(CLR_PTR_TYPE(p), n + 1,
488 fanout, flags, fn, cb_data);
489 break;
490 case PTR_TYPE_SUBTREE:
491 l = (struct leaf_node *) CLR_PTR_TYPE(p);
492 /*
493 * Subtree entries in the note tree represent parts of
494 * the note tree that have not yet been explored. There
495 * is a direct relationship between subtree entries at
496 * level 'n' in the tree, and the 'fanout' variable:
497 * Subtree entries at level 'n <= 2 * fanout' should be
498 * preserved, since they correspond exactly to a fanout
499 * directory in the on-disk structure. However, subtree
500 * entries at level 'n > 2 * fanout' should NOT be
501 * preserved, but rather consolidated into the above
502 * notes tree level. We achieve this by unconditionally
503 * unpacking subtree entries that exist below the
504 * threshold level at 'n = 2 * fanout'.
505 */
506 if (n <= 2 * fanout &&
507 flags & FOR_EACH_NOTE_YIELD_SUBTREES) {
508 /* invoke callback with subtree */
509 unsigned int path_len =
510 l->key_sha1[19] * 2 + fanout;
511 assert(path_len < 40 + 19);
512 construct_path_with_fanout(l->key_sha1, fanout,
513 path);
514 /* Create trailing slash, if needed */
515 if (path[path_len - 1] != '/')
516 path[path_len++] = '/';
517 path[path_len] = '\0';
518 ret = fn(l->key_sha1, l->val_sha1, path,
519 cb_data);
520 }
521 if (n > fanout * 2 ||
522 !(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) {
523 /* unpack subtree and resume traversal */
524 tree->a[i] = NULL;
525 load_subtree(l, tree, n);
526 free(l);
527 goto redo;
528 }
529 break;
530 case PTR_TYPE_NOTE:
531 l = (struct leaf_node *) CLR_PTR_TYPE(p);
532 construct_path_with_fanout(l->key_sha1, fanout, path);
533 ret = fn(l->key_sha1, l->val_sha1, path, cb_data);
534 break;
535 }
536 if (ret)
537 return ret;
538 }
539 return 0;
540}
541
61a7cca0
JH
542struct tree_write_stack {
543 struct tree_write_stack *next;
544 struct strbuf buf;
545 char path[2]; /* path to subtree in next, if any */
546};
547
548static inline int matches_tree_write_stack(struct tree_write_stack *tws,
549 const char *full_path)
550{
551 return full_path[0] == tws->path[0] &&
552 full_path[1] == tws->path[1] &&
553 full_path[2] == '/';
554}
555
556static void write_tree_entry(struct strbuf *buf, unsigned int mode,
557 const char *path, unsigned int path_len, const
558 unsigned char *sha1)
559{
560 strbuf_addf(buf, "%06o %.*s%c", mode, path_len, path, '\0');
561 strbuf_add(buf, sha1, 20);
562}
563
564static void tree_write_stack_init_subtree(struct tree_write_stack *tws,
565 const char *path)
566{
567 struct tree_write_stack *n;
568 assert(!tws->next);
569 assert(tws->path[0] == '\0' && tws->path[1] == '\0');
570 n = (struct tree_write_stack *)
571 xmalloc(sizeof(struct tree_write_stack));
572 n->next = NULL;
573 strbuf_init(&n->buf, 256 * (32 + 40)); /* assume 256 entries per tree */
574 n->path[0] = n->path[1] = '\0';
575 tws->next = n;
576 tws->path[0] = path[0];
577 tws->path[1] = path[1];
578}
579
580static int tree_write_stack_finish_subtree(struct tree_write_stack *tws)
581{
582 int ret;
583 struct tree_write_stack *n = tws->next;
584 unsigned char s[20];
585 if (n) {
586 ret = tree_write_stack_finish_subtree(n);
587 if (ret)
588 return ret;
589 ret = write_sha1_file(n->buf.buf, n->buf.len, tree_type, s);
590 if (ret)
591 return ret;
592 strbuf_release(&n->buf);
593 free(n);
594 tws->next = NULL;
595 write_tree_entry(&tws->buf, 040000, tws->path, 2, s);
596 tws->path[0] = tws->path[1] = '\0';
597 }
598 return 0;
599}
600
601static int write_each_note_helper(struct tree_write_stack *tws,
602 const char *path, unsigned int mode,
603 const unsigned char *sha1)
604{
605 size_t path_len = strlen(path);
606 unsigned int n = 0;
607 int ret;
608
609 /* Determine common part of tree write stack */
610 while (tws && 3 * n < path_len &&
611 matches_tree_write_stack(tws, path + 3 * n)) {
612 n++;
613 tws = tws->next;
614 }
615
616 /* tws point to last matching tree_write_stack entry */
617 ret = tree_write_stack_finish_subtree(tws);
618 if (ret)
619 return ret;
620
621 /* Start subtrees needed to satisfy path */
622 while (3 * n + 2 < path_len && path[3 * n + 2] == '/') {
623 tree_write_stack_init_subtree(tws, path + 3 * n);
624 n++;
625 tws = tws->next;
626 }
627
628 /* There should be no more directory components in the given path */
629 assert(memchr(path + 3 * n, '/', path_len - (3 * n)) == NULL);
630
631 /* Finally add given entry to the current tree object */
632 write_tree_entry(&tws->buf, mode, path + 3 * n, path_len - (3 * n),
633 sha1);
634
635 return 0;
636}
637
638struct write_each_note_data {
639 struct tree_write_stack *root;
640};
641
642static int write_each_note(const unsigned char *object_sha1,
643 const unsigned char *note_sha1, char *note_path,
644 void *cb_data)
645{
646 struct write_each_note_data *d =
647 (struct write_each_note_data *) cb_data;
648 size_t note_path_len = strlen(note_path);
649 unsigned int mode = 0100644;
650
651 if (note_path[note_path_len - 1] == '/') {
652 /* subtree entry */
653 note_path_len--;
654 note_path[note_path_len] = '\0';
655 mode = 040000;
656 }
657 assert(note_path_len <= 40 + 19);
658
659 return write_each_note_helper(d->root, note_path, mode, note_sha1);
660}
661
cd305392 662void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
23123aec 663{
a7e7eff6 664 unsigned char sha1[20], object_sha1[20];
23123aec
JH
665 unsigned mode;
666 struct leaf_node root_tree;
fd53c9eb 667
cd305392
JH
668 if (!t)
669 t = &default_notes_tree;
670 assert(!t->initialized);
709f79b0
JH
671
672 if (!notes_ref)
673 notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
674 if (!notes_ref)
675 notes_ref = notes_ref_name; /* value of core.notesRef config */
676 if (!notes_ref)
677 notes_ref = GIT_NOTES_DEFAULT_REF;
678
cd305392
JH
679 t->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
680 t->ref = notes_ref ? xstrdup(notes_ref) : NULL;
681 t->initialized = 1;
682
709f79b0
JH
683 if (flags & NOTES_INIT_EMPTY || !notes_ref ||
684 read_ref(notes_ref, object_sha1))
fd53c9eb 685 return;
709f79b0
JH
686 if (get_tree_entry(object_sha1, "", sha1, &mode))
687 die("Failed to read notes tree referenced by %s (%s)",
688 notes_ref, object_sha1);
fd53c9eb 689
23123aec
JH
690 hashclr(root_tree.key_sha1);
691 hashcpy(root_tree.val_sha1, sha1);
cd305392 692 load_subtree(&root_tree, t->root, 0);
fd53c9eb
JS
693}
694
cd305392
JH
695void add_note(struct notes_tree *t, const unsigned char *object_sha1,
696 const unsigned char *note_sha1)
2626b536
JH
697{
698 struct leaf_node *l;
699
cd305392
JH
700 if (!t)
701 t = &default_notes_tree;
702 assert(t->initialized);
2626b536
JH
703 l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
704 hashcpy(l->key_sha1, object_sha1);
705 hashcpy(l->val_sha1, note_sha1);
cd305392 706 note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);
2626b536
JH
707}
708
cd305392 709void remove_note(struct notes_tree *t, const unsigned char *object_sha1)
1ec666b0
JH
710{
711 struct leaf_node l;
712
cd305392
JH
713 if (!t)
714 t = &default_notes_tree;
715 assert(t->initialized);
1ec666b0
JH
716 hashcpy(l.key_sha1, object_sha1);
717 hashclr(l.val_sha1);
cd305392 718 return note_tree_remove(t, t->root, 0, &l);
1ec666b0
JH
719}
720
cd305392
JH
721const unsigned char *get_note(struct notes_tree *t,
722 const unsigned char *object_sha1)
fd53c9eb 723{
9b391f21
JH
724 struct leaf_node *found;
725
cd305392
JH
726 if (!t)
727 t = &default_notes_tree;
728 assert(t->initialized);
729 found = note_tree_find(t->root, 0, object_sha1);
9b391f21 730 return found ? found->val_sha1 : NULL;
fd53c9eb 731}
a97a7468 732
cd305392
JH
733int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
734 void *cb_data)
73f77b90 735{
cd305392
JH
736 if (!t)
737 t = &default_notes_tree;
738 assert(t->initialized);
739 return for_each_note_helper(t->root, 0, 0, flags, fn, cb_data);
73f77b90
JH
740}
741
cd305392 742int write_notes_tree(struct notes_tree *t, unsigned char *result)
61a7cca0
JH
743{
744 struct tree_write_stack root;
745 struct write_each_note_data cb_data;
746 int ret;
747
cd305392
JH
748 if (!t)
749 t = &default_notes_tree;
750 assert(t->initialized);
61a7cca0
JH
751
752 /* Prepare for traversal of current notes tree */
753 root.next = NULL; /* last forward entry in list is grounded */
754 strbuf_init(&root.buf, 256 * (32 + 40)); /* assume 256 entries */
755 root.path[0] = root.path[1] = '\0';
756 cb_data.root = &root;
757
758 /* Write tree objects representing current notes tree */
cd305392 759 ret = for_each_note(t, FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |
61a7cca0
JH
760 FOR_EACH_NOTE_YIELD_SUBTREES,
761 write_each_note, &cb_data) ||
762 tree_write_stack_finish_subtree(&root) ||
763 write_sha1_file(root.buf.buf, root.buf.len, tree_type, result);
764 strbuf_release(&root.buf);
765 return ret;
766}
767
cd305392 768void free_notes(struct notes_tree *t)
27d57564 769{
cd305392
JH
770 if (!t)
771 t = &default_notes_tree;
772 if (t->root)
773 note_tree_free(t->root);
774 free(t->root);
775 free(t->ref);
776 memset(t, 0, sizeof(struct notes_tree));
27d57564
JH
777}
778
cd305392
JH
779void format_note(struct notes_tree *t, const unsigned char *object_sha1,
780 struct strbuf *sb, const char *output_encoding, int flags)
a97a7468
JS
781{
782 static const char utf8[] = "utf-8";
9b391f21 783 const unsigned char *sha1;
a97a7468
JS
784 char *msg, *msg_p;
785 unsigned long linelen, msglen;
786 enum object_type type;
787
cd305392
JH
788 if (!t)
789 t = &default_notes_tree;
790 if (!t->initialized)
791 init_notes(t, NULL, 0);
a97a7468 792
cd305392 793 sha1 = get_note(t, object_sha1);
fd53c9eb 794 if (!sha1)
a97a7468
JS
795 return;
796
797 if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||
798 type != OBJ_BLOB) {
799 free(msg);
800 return;
801 }
802
803 if (output_encoding && *output_encoding &&
804 strcmp(utf8, output_encoding)) {
805 char *reencoded = reencode_string(msg, output_encoding, utf8);
806 if (reencoded) {
807 free(msg);
808 msg = reencoded;
809 msglen = strlen(msg);
810 }
811 }
812
813 /* we will end the annotation by a newline anyway */
814 if (msglen && msg[msglen - 1] == '\n')
815 msglen--;
816
c56fcc89
JH
817 if (flags & NOTES_SHOW_HEADER)
818 strbuf_addstr(sb, "\nNotes:\n");
a97a7468
JS
819
820 for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
821 linelen = strchrnul(msg_p, '\n') - msg_p;
822
c56fcc89
JH
823 if (flags & NOTES_INDENT)
824 strbuf_addstr(sb, " ");
a97a7468
JS
825 strbuf_add(sb, msg_p, linelen);
826 strbuf_addch(sb, '\n');
827 }
828
829 free(msg);
830}