notes.c

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