notes.c

   1 #include "cache.h"
   2 #include "notes.h"
   3 #include "tree.h"
   4 #include "utf8.h"
   5 #include "strbuf.h"
   6 #include "tree-walk.h"
   7
   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  */
  20 struct int_node {
  21         void *a[16];
  22 };
  23
  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).
  27  * As a note entry, the key is the SHA1 of the referenced object, 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 object, 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
  32  * subtree.
  33  */
  34 struct leaf_node {
  35         unsigned char key_sha1[20];
  36         unsigned char val_sha1[20];
  37 };
  38
  39 #define PTR_TYPE_NULL     0
  40 #define PTR_TYPE_INTERNAL 1
  41 #define PTR_TYPE_NOTE     2
  42 #define PTR_TYPE_SUBTREE  3
  43
  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)))
  47
  48 #define GET_NIBBLE(n, sha1) (((sha1[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
  49
  50 #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
  51         (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
  52
  53 struct notes_tree default_notes_tree;
  54
  55 static void load_subtree(struct leaf_node *subtree, struct int_node *node,
  56                 unsigned int n);
  57
  58 /*
  59  * Search the tree until the appropriate location for the given key is found:
  60  * 1. Start at the root node, with n = 0
  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
  65  *    - If a matching subtree entry, unpack that subtree entry (and remove it);
  66  *      restart search at the current level.
  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.
  72  */
  73 static void **note_tree_search(struct int_node **tree,
  74                 unsigned char *n, const unsigned char *key_sha1)
  75 {
  76         struct leaf_node *l;
  77         unsigned char i;
  78         void *p = (*tree)->a[0];
  79
  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];
  93         switch (GET_PTR_TYPE(p)) {
  94         case PTR_TYPE_INTERNAL:
  95                 *tree = CLR_PTR_TYPE(p);
  96                 (*n)++;
  97                 return note_tree_search(tree, n, key_sha1);
  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 */
 102                         (*tree)->a[i] = NULL;
 103                         load_subtree(l, *tree, *n);
 104                         free(l);
 105                         return note_tree_search(tree, n, key_sha1);
 106                 }
 107                 /* fall through */
 108         default:
 109                 return &((*tree)->a[i]);
 110         }
 111 }
 112
 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  */
 118 static 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;
 126         }
 127         return NULL;
 128 }
 129
 130 /* Create a new blob object by concatenating the two given blob objects */
 131 static 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
 173 /*
 174  * To insert a leaf_node:
 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.
 185  */
 186 static void note_tree_insert(struct int_node *tree, unsigned char n,
 187                 struct leaf_node *entry, unsigned char type)
 188 {
 189         struct int_node *new_node;
 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);
 195         switch (GET_PTR_TYPE(*p)) {
 196         case PTR_TYPE_NULL:
 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 "
 211                                             "into note %s for object %s",
 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;
 238                 }
 239                 break;
 240         }
 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);
 249 }
 250
 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  */
 258 static 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  */
 288 static void note_tree_remove(struct notes_tree *t, struct int_node *tree,
 289                 unsigned char n, struct leaf_node *entry)
 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 */
 311         parent_stack[0] = t->root;
 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
 324 /* Free the entire notes data contained in the given tree */
 325 static 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];
 330                 switch (GET_PTR_TYPE(p)) {
 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                 }
 338         }
 339 }
 340
 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
 347  * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
 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  */
 351 static 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;
 367 }
 368
 369 static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 370                 unsigned int n)
 371 {
 372         unsigned char object_sha1[20];
 373         unsigned int prefix_len;
 374         void *buf;
 375         struct tree_desc desc;
 376         struct name_entry entry;
 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);
 385         memcpy(object_sha1, subtree->key_sha1, prefix_len);
 386         while (tree_entry(&desc, &entry)) {
 387                 int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
 388                                 object_sha1 + prefix_len, 20 - prefix_len);
 389                 if (len < 0)
 390                         continue; /* entry.path is not a SHA1 sum. Skip */
 391                 len += prefix_len;
 392
 393                 /*
 394                  * If object SHA1 is complete (len == 20), assume note object
 395                  * If object SHA1 is incomplete (len < 20), assume note subtree
 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);
 401                         hashcpy(l->key_sha1, object_sha1);
 402                         hashcpy(l->val_sha1, entry.sha1);
 403                         if (len < 20) {
 404                                 if (!S_ISDIR(entry.mode))
 405                                         continue; /* entry cannot be subtree */
 406                                 l->key_sha1[19] = (unsigned char) len;
 407                                 type = PTR_TYPE_SUBTREE;
 408                         }
 409                         note_tree_insert(node, n, l, type);
 410                 }
 411         }
 412         free(buf);
 413 }
 414
 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  */
 429 static 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
 455 static 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
 470 static 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++) {
 482 redo:
 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
 542 struct 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
 548 static 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
 556 static 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
 564 static 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
 580 static 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
 601 static 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
 638 struct write_each_note_data {
 639         struct tree_write_stack *root;
 640 };
 641
 642 static 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
 662 void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
 663 {
 664         unsigned char sha1[20], object_sha1[20];
 665         unsigned mode;
 666         struct leaf_node root_tree;
 667
 668         if (!t)
 669                 t = &default_notes_tree;
 670         assert(!t->initialized);
 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
 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
 683         if (flags & NOTES_INIT_EMPTY || !notes_ref ||
 684             read_ref(notes_ref, object_sha1))
 685                 return;
 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);
 689
 690         hashclr(root_tree.key_sha1);
 691         hashcpy(root_tree.val_sha1, sha1);
 692         load_subtree(&root_tree, t->root, 0);
 693 }
 694
 695 void add_note(struct notes_tree *t, const unsigned char *object_sha1,
 696                 const unsigned char *note_sha1)
 697 {
 698         struct leaf_node *l;
 699
 700         if (!t)
 701                 t = &default_notes_tree;
 702         assert(t->initialized);
 703         l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
 704         hashcpy(l->key_sha1, object_sha1);
 705         hashcpy(l->val_sha1, note_sha1);
 706         note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);
 707 }
 708
 709 void remove_note(struct notes_tree *t, const unsigned char *object_sha1)
 710 {
 711         struct leaf_node l;
 712
 713         if (!t)
 714                 t = &default_notes_tree;
 715         assert(t->initialized);
 716         hashcpy(l.key_sha1, object_sha1);
 717         hashclr(l.val_sha1);
 718         return note_tree_remove(t, t->root, 0, &l);
 719 }
 720
 721 const unsigned char *get_note(struct notes_tree *t,
 722                 const unsigned char *object_sha1)
 723 {
 724         struct leaf_node *found;
 725
 726         if (!t)
 727                 t = &default_notes_tree;
 728         assert(t->initialized);
 729         found = note_tree_find(t->root, 0, object_sha1);
 730         return found ? found->val_sha1 : NULL;
 731 }
 732
 733 int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
 734                 void *cb_data)
 735 {
 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);
 740 }
 741
 742 int write_notes_tree(struct notes_tree *t, unsigned char *result)
 743 {
 744         struct tree_write_stack root;
 745         struct write_each_note_data cb_data;
 746         int ret;
 747
 748         if (!t)
 749                 t = &default_notes_tree;
 750         assert(t->initialized);
 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 */
 759         ret = for_each_note(t, FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |
 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
 768 void free_notes(struct notes_tree *t)
 769 {
 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));
 777 }
 778
 779 void format_note(struct notes_tree *t, const unsigned char *object_sha1,
 780                 struct strbuf *sb, const char *output_encoding, int flags)
 781 {
 782         static const char utf8[] = "utf-8";
 783         const unsigned char *sha1;
 784         char *msg, *msg_p;
 785         unsigned long linelen, msglen;
 786         enum object_type type;
 787
 788         if (!t)
 789                 t = &default_notes_tree;
 790         if (!t->initialized)
 791                 init_notes(t, NULL, 0);
 792
 793         sha1 = get_note(t, object_sha1);
 794         if (!sha1)
 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
 817         if (flags & NOTES_SHOW_HEADER)
 818                 strbuf_addstr(sb, "\nNotes:\n");
 819
 820         for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
 821                 linelen = strchrnul(msg_p, '\n') - msg_p;
 822
 823                 if (flags & NOTES_INDENT)
 824                         strbuf_addstr(sb, "    ");
 825                 strbuf_add(sb, msg_p, linelen);
 826                 strbuf_addch(sb, '\n');
 827         }
 828
 829         free(msg);
 830 }