cache-tree.con commit Merge branch 'jk/doc-diff-options' (6366dd9)
   1#include "cache.h"
   2#include "lockfile.h"
   3#include "tree.h"
   4#include "tree-walk.h"
   5#include "cache-tree.h"
   6
   7#ifndef DEBUG
   8#define DEBUG 0
   9#endif
  10
  11struct cache_tree *cache_tree(void)
  12{
  13        struct cache_tree *it = xcalloc(1, sizeof(struct cache_tree));
  14        it->entry_count = -1;
  15        return it;
  16}
  17
  18void cache_tree_free(struct cache_tree **it_p)
  19{
  20        int i;
  21        struct cache_tree *it = *it_p;
  22
  23        if (!it)
  24                return;
  25        for (i = 0; i < it->subtree_nr; i++)
  26                if (it->down[i]) {
  27                        cache_tree_free(&it->down[i]->cache_tree);
  28                        free(it->down[i]);
  29                }
  30        free(it->down);
  31        free(it);
  32        *it_p = NULL;
  33}
  34
  35static int subtree_name_cmp(const char *one, int onelen,
  36                            const char *two, int twolen)
  37{
  38        if (onelen < twolen)
  39                return -1;
  40        if (twolen < onelen)
  41                return 1;
  42        return memcmp(one, two, onelen);
  43}
  44
  45static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)
  46{
  47        struct cache_tree_sub **down = it->down;
  48        int lo, hi;
  49        lo = 0;
  50        hi = it->subtree_nr;
  51        while (lo < hi) {
  52                int mi = lo + (hi - lo) / 2;
  53                struct cache_tree_sub *mdl = down[mi];
  54                int cmp = subtree_name_cmp(path, pathlen,
  55                                           mdl->name, mdl->namelen);
  56                if (!cmp)
  57                        return mi;
  58                if (cmp < 0)
  59                        hi = mi;
  60                else
  61                        lo = mi + 1;
  62        }
  63        return -lo-1;
  64}
  65
  66static struct cache_tree_sub *find_subtree(struct cache_tree *it,
  67                                           const char *path,
  68                                           int pathlen,
  69                                           int create)
  70{
  71        struct cache_tree_sub *down;
  72        int pos = subtree_pos(it, path, pathlen);
  73        if (0 <= pos)
  74                return it->down[pos];
  75        if (!create)
  76                return NULL;
  77
  78        pos = -pos-1;
  79        ALLOC_GROW(it->down, it->subtree_nr + 1, it->subtree_alloc);
  80        it->subtree_nr++;
  81
  82        FLEX_ALLOC_MEM(down, name, path, pathlen);
  83        down->cache_tree = NULL;
  84        down->namelen = pathlen;
  85
  86        if (pos < it->subtree_nr)
  87                memmove(it->down + pos + 1,
  88                        it->down + pos,
  89                        sizeof(down) * (it->subtree_nr - pos - 1));
  90        it->down[pos] = down;
  91        return down;
  92}
  93
  94struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)
  95{
  96        int pathlen = strlen(path);
  97        return find_subtree(it, path, pathlen, 1);
  98}
  99
 100static int do_invalidate_path(struct cache_tree *it, const char *path)
 101{
 102        /* a/b/c
 103         * ==> invalidate self
 104         * ==> find "a", have it invalidate "b/c"
 105         * a
 106         * ==> invalidate self
 107         * ==> if "a" exists as a subtree, remove it.
 108         */
 109        const char *slash;
 110        int namelen;
 111        struct cache_tree_sub *down;
 112
 113#if DEBUG
 114        fprintf(stderr, "cache-tree invalidate <%s>\n", path);
 115#endif
 116
 117        if (!it)
 118                return 0;
 119        slash = strchrnul(path, '/');
 120        namelen = slash - path;
 121        it->entry_count = -1;
 122        if (!*slash) {
 123                int pos;
 124                pos = subtree_pos(it, path, namelen);
 125                if (0 <= pos) {
 126                        cache_tree_free(&it->down[pos]->cache_tree);
 127                        free(it->down[pos]);
 128                        /* 0 1 2 3 4 5
 129                         *       ^     ^subtree_nr = 6
 130                         *       pos
 131                         * move 4 and 5 up one place (2 entries)
 132                         * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
 133                         */
 134                        MOVE_ARRAY(it->down + pos, it->down + pos + 1,
 135                                   it->subtree_nr - pos - 1);
 136                        it->subtree_nr--;
 137                }
 138                return 1;
 139        }
 140        down = find_subtree(it, path, namelen, 0);
 141        if (down)
 142                do_invalidate_path(down->cache_tree, slash + 1);
 143        return 1;
 144}
 145
 146void cache_tree_invalidate_path(struct index_state *istate, const char *path)
 147{
 148        if (do_invalidate_path(istate->cache_tree, path))
 149                istate->cache_changed |= CACHE_TREE_CHANGED;
 150}
 151
 152static int verify_cache(struct cache_entry **cache,
 153                        int entries, int flags)
 154{
 155        int i, funny;
 156        int silent = flags & WRITE_TREE_SILENT;
 157
 158        /* Verify that the tree is merged */
 159        funny = 0;
 160        for (i = 0; i < entries; i++) {
 161                const struct cache_entry *ce = cache[i];
 162                if (ce_stage(ce)) {
 163                        if (silent)
 164                                return -1;
 165                        if (10 < ++funny) {
 166                                fprintf(stderr, "...\n");
 167                                break;
 168                        }
 169                        fprintf(stderr, "%s: unmerged (%s)\n",
 170                                ce->name, oid_to_hex(&ce->oid));
 171                }
 172        }
 173        if (funny)
 174                return -1;
 175
 176        /* Also verify that the cache does not have path and path/file
 177         * at the same time.  At this point we know the cache has only
 178         * stage 0 entries.
 179         */
 180        funny = 0;
 181        for (i = 0; i < entries - 1; i++) {
 182                /* path/file always comes after path because of the way
 183                 * the cache is sorted.  Also path can appear only once,
 184                 * which means conflicting one would immediately follow.
 185                 */
 186                const char *this_name = cache[i]->name;
 187                const char *next_name = cache[i+1]->name;
 188                int this_len = strlen(this_name);
 189                if (this_len < strlen(next_name) &&
 190                    strncmp(this_name, next_name, this_len) == 0 &&
 191                    next_name[this_len] == '/') {
 192                        if (10 < ++funny) {
 193                                fprintf(stderr, "...\n");
 194                                break;
 195                        }
 196                        fprintf(stderr, "You have both %s and %s\n",
 197                                this_name, next_name);
 198                }
 199        }
 200        if (funny)
 201                return -1;
 202        return 0;
 203}
 204
 205static void discard_unused_subtrees(struct cache_tree *it)
 206{
 207        struct cache_tree_sub **down = it->down;
 208        int nr = it->subtree_nr;
 209        int dst, src;
 210        for (dst = src = 0; src < nr; src++) {
 211                struct cache_tree_sub *s = down[src];
 212                if (s->used)
 213                        down[dst++] = s;
 214                else {
 215                        cache_tree_free(&s->cache_tree);
 216                        free(s);
 217                        it->subtree_nr--;
 218                }
 219        }
 220}
 221
 222int cache_tree_fully_valid(struct cache_tree *it)
 223{
 224        int i;
 225        if (!it)
 226                return 0;
 227        if (it->entry_count < 0 || !has_sha1_file(it->oid.hash))
 228                return 0;
 229        for (i = 0; i < it->subtree_nr; i++) {
 230                if (!cache_tree_fully_valid(it->down[i]->cache_tree))
 231                        return 0;
 232        }
 233        return 1;
 234}
 235
 236static int update_one(struct cache_tree *it,
 237                      struct cache_entry **cache,
 238                      int entries,
 239                      const char *base,
 240                      int baselen,
 241                      int *skip_count,
 242                      int flags)
 243{
 244        struct strbuf buffer;
 245        int missing_ok = flags & WRITE_TREE_MISSING_OK;
 246        int dryrun = flags & WRITE_TREE_DRY_RUN;
 247        int repair = flags & WRITE_TREE_REPAIR;
 248        int to_invalidate = 0;
 249        int i;
 250
 251        assert(!(dryrun && repair));
 252
 253        *skip_count = 0;
 254
 255        if (0 <= it->entry_count && has_sha1_file(it->oid.hash))
 256                return it->entry_count;
 257
 258        /*
 259         * We first scan for subtrees and update them; we start by
 260         * marking existing subtrees -- the ones that are unmarked
 261         * should not be in the result.
 262         */
 263        for (i = 0; i < it->subtree_nr; i++)
 264                it->down[i]->used = 0;
 265
 266        /*
 267         * Find the subtrees and update them.
 268         */
 269        i = 0;
 270        while (i < entries) {
 271                const struct cache_entry *ce = cache[i];
 272                struct cache_tree_sub *sub;
 273                const char *path, *slash;
 274                int pathlen, sublen, subcnt, subskip;
 275
 276                path = ce->name;
 277                pathlen = ce_namelen(ce);
 278                if (pathlen <= baselen || memcmp(base, path, baselen))
 279                        break; /* at the end of this level */
 280
 281                slash = strchr(path + baselen, '/');
 282                if (!slash) {
 283                        i++;
 284                        continue;
 285                }
 286                /*
 287                 * a/bbb/c (base = a/, slash = /c)
 288                 * ==>
 289                 * path+baselen = bbb/c, sublen = 3
 290                 */
 291                sublen = slash - (path + baselen);
 292                sub = find_subtree(it, path + baselen, sublen, 1);
 293                if (!sub->cache_tree)
 294                        sub->cache_tree = cache_tree();
 295                subcnt = update_one(sub->cache_tree,
 296                                    cache + i, entries - i,
 297                                    path,
 298                                    baselen + sublen + 1,
 299                                    &subskip,
 300                                    flags);
 301                if (subcnt < 0)
 302                        return subcnt;
 303                if (!subcnt)
 304                        die("index cache-tree records empty sub-tree");
 305                i += subcnt;
 306                sub->count = subcnt; /* to be used in the next loop */
 307                *skip_count += subskip;
 308                sub->used = 1;
 309        }
 310
 311        discard_unused_subtrees(it);
 312
 313        /*
 314         * Then write out the tree object for this level.
 315         */
 316        strbuf_init(&buffer, 8192);
 317
 318        i = 0;
 319        while (i < entries) {
 320                const struct cache_entry *ce = cache[i];
 321                struct cache_tree_sub *sub = NULL;
 322                const char *path, *slash;
 323                int pathlen, entlen;
 324                const unsigned char *sha1;
 325                unsigned mode;
 326                int expected_missing = 0;
 327                int contains_ita = 0;
 328
 329                path = ce->name;
 330                pathlen = ce_namelen(ce);
 331                if (pathlen <= baselen || memcmp(base, path, baselen))
 332                        break; /* at the end of this level */
 333
 334                slash = strchr(path + baselen, '/');
 335                if (slash) {
 336                        entlen = slash - (path + baselen);
 337                        sub = find_subtree(it, path + baselen, entlen, 0);
 338                        if (!sub)
 339                                die("cache-tree.c: '%.*s' in '%s' not found",
 340                                    entlen, path + baselen, path);
 341                        i += sub->count;
 342                        sha1 = sub->cache_tree->oid.hash;
 343                        mode = S_IFDIR;
 344                        contains_ita = sub->cache_tree->entry_count < 0;
 345                        if (contains_ita) {
 346                                to_invalidate = 1;
 347                                expected_missing = 1;
 348                        }
 349                }
 350                else {
 351                        sha1 = ce->oid.hash;
 352                        mode = ce->ce_mode;
 353                        entlen = pathlen - baselen;
 354                        i++;
 355                }
 356
 357                if (is_null_sha1(sha1) ||
 358                    (mode != S_IFGITLINK && !missing_ok && !has_sha1_file(sha1))) {
 359                        strbuf_release(&buffer);
 360                        if (expected_missing)
 361                                return -1;
 362                        return error("invalid object %06o %s for '%.*s'",
 363                                mode, sha1_to_hex(sha1), entlen+baselen, path);
 364                }
 365
 366                /*
 367                 * CE_REMOVE entries are removed before the index is
 368                 * written to disk. Skip them to remain consistent
 369                 * with the future on-disk index.
 370                 */
 371                if (ce->ce_flags & CE_REMOVE) {
 372                        *skip_count = *skip_count + 1;
 373                        continue;
 374                }
 375
 376                /*
 377                 * CE_INTENT_TO_ADD entries exist on on-disk index but
 378                 * they are not part of generated trees. Invalidate up
 379                 * to root to force cache-tree users to read elsewhere.
 380                 */
 381                if (!sub && ce_intent_to_add(ce)) {
 382                        to_invalidate = 1;
 383                        continue;
 384                }
 385
 386                /*
 387                 * "sub" can be an empty tree if all subentries are i-t-a.
 388                 */
 389                if (contains_ita && !hashcmp(sha1, EMPTY_TREE_SHA1_BIN))
 390                        continue;
 391
 392                strbuf_grow(&buffer, entlen + 100);
 393                strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
 394                strbuf_add(&buffer, sha1, 20);
 395
 396#if DEBUG
 397                fprintf(stderr, "cache-tree update-one %o %.*s\n",
 398                        mode, entlen, path + baselen);
 399#endif
 400        }
 401
 402        if (repair) {
 403                unsigned char sha1[20];
 404                hash_sha1_file(buffer.buf, buffer.len, tree_type, sha1);
 405                if (has_sha1_file(sha1))
 406                        hashcpy(it->oid.hash, sha1);
 407                else
 408                        to_invalidate = 1;
 409        } else if (dryrun)
 410                hash_sha1_file(buffer.buf, buffer.len, tree_type,
 411                               it->oid.hash);
 412        else if (write_sha1_file(buffer.buf, buffer.len, tree_type, it->oid.hash)) {
 413                strbuf_release(&buffer);
 414                return -1;
 415        }
 416
 417        strbuf_release(&buffer);
 418        it->entry_count = to_invalidate ? -1 : i - *skip_count;
 419#if DEBUG
 420        fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
 421                it->entry_count, it->subtree_nr,
 422                oid_to_hex(&it->oid));
 423#endif
 424        return i;
 425}
 426
 427int cache_tree_update(struct index_state *istate, int flags)
 428{
 429        struct cache_tree *it = istate->cache_tree;
 430        struct cache_entry **cache = istate->cache;
 431        int entries = istate->cache_nr;
 432        int skip, i = verify_cache(cache, entries, flags);
 433
 434        if (i)
 435                return i;
 436        i = update_one(it, cache, entries, "", 0, &skip, flags);
 437        if (i < 0)
 438                return i;
 439        istate->cache_changed |= CACHE_TREE_CHANGED;
 440        return 0;
 441}
 442
 443static void write_one(struct strbuf *buffer, struct cache_tree *it,
 444                      const char *path, int pathlen)
 445{
 446        int i;
 447
 448        /* One "cache-tree" entry consists of the following:
 449         * path (NUL terminated)
 450         * entry_count, subtree_nr ("%d %d\n")
 451         * tree-sha1 (missing if invalid)
 452         * subtree_nr "cache-tree" entries for subtrees.
 453         */
 454        strbuf_grow(buffer, pathlen + 100);
 455        strbuf_add(buffer, path, pathlen);
 456        strbuf_addf(buffer, "%c%d %d\n", 0, it->entry_count, it->subtree_nr);
 457
 458#if DEBUG
 459        if (0 <= it->entry_count)
 460                fprintf(stderr, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
 461                        pathlen, path, it->entry_count, it->subtree_nr,
 462                        oid_to_hex(&it->oid));
 463        else
 464                fprintf(stderr, "cache-tree <%.*s> (%d subtree) invalid\n",
 465                        pathlen, path, it->subtree_nr);
 466#endif
 467
 468        if (0 <= it->entry_count) {
 469                strbuf_add(buffer, it->oid.hash, 20);
 470        }
 471        for (i = 0; i < it->subtree_nr; i++) {
 472                struct cache_tree_sub *down = it->down[i];
 473                if (i) {
 474                        struct cache_tree_sub *prev = it->down[i-1];
 475                        if (subtree_name_cmp(down->name, down->namelen,
 476                                             prev->name, prev->namelen) <= 0)
 477                                die("fatal - unsorted cache subtree");
 478                }
 479                write_one(buffer, down->cache_tree, down->name, down->namelen);
 480        }
 481}
 482
 483void cache_tree_write(struct strbuf *sb, struct cache_tree *root)
 484{
 485        write_one(sb, root, "", 0);
 486}
 487
 488static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 489{
 490        const char *buf = *buffer;
 491        unsigned long size = *size_p;
 492        const char *cp;
 493        char *ep;
 494        struct cache_tree *it;
 495        int i, subtree_nr;
 496
 497        it = NULL;
 498        /* skip name, but make sure name exists */
 499        while (size && *buf) {
 500                size--;
 501                buf++;
 502        }
 503        if (!size)
 504                goto free_return;
 505        buf++; size--;
 506        it = cache_tree();
 507
 508        cp = buf;
 509        it->entry_count = strtol(cp, &ep, 10);
 510        if (cp == ep)
 511                goto free_return;
 512        cp = ep;
 513        subtree_nr = strtol(cp, &ep, 10);
 514        if (cp == ep)
 515                goto free_return;
 516        while (size && *buf && *buf != '\n') {
 517                size--;
 518                buf++;
 519        }
 520        if (!size)
 521                goto free_return;
 522        buf++; size--;
 523        if (0 <= it->entry_count) {
 524                if (size < 20)
 525                        goto free_return;
 526                hashcpy(it->oid.hash, (const unsigned char*)buf);
 527                buf += 20;
 528                size -= 20;
 529        }
 530
 531#if DEBUG
 532        if (0 <= it->entry_count)
 533                fprintf(stderr, "cache-tree <%s> (%d ent, %d subtree) %s\n",
 534                        *buffer, it->entry_count, subtree_nr,
 535                        oid_to_hex(&it->oid));
 536        else
 537                fprintf(stderr, "cache-tree <%s> (%d subtrees) invalid\n",
 538                        *buffer, subtree_nr);
 539#endif
 540
 541        /*
 542         * Just a heuristic -- we do not add directories that often but
 543         * we do not want to have to extend it immediately when we do,
 544         * hence +2.
 545         */
 546        it->subtree_alloc = subtree_nr + 2;
 547        it->down = xcalloc(it->subtree_alloc, sizeof(struct cache_tree_sub *));
 548        for (i = 0; i < subtree_nr; i++) {
 549                /* read each subtree */
 550                struct cache_tree *sub;
 551                struct cache_tree_sub *subtree;
 552                const char *name = buf;
 553
 554                sub = read_one(&buf, &size);
 555                if (!sub)
 556                        goto free_return;
 557                subtree = cache_tree_sub(it, name);
 558                subtree->cache_tree = sub;
 559        }
 560        if (subtree_nr != it->subtree_nr)
 561                die("cache-tree: internal error");
 562        *buffer = buf;
 563        *size_p = size;
 564        return it;
 565
 566 free_return:
 567        cache_tree_free(&it);
 568        return NULL;
 569}
 570
 571struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 572{
 573        if (buffer[0])
 574                return NULL; /* not the whole tree */
 575        return read_one(&buffer, &size);
 576}
 577
 578static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)
 579{
 580        if (!it)
 581                return NULL;
 582        while (*path) {
 583                const char *slash;
 584                struct cache_tree_sub *sub;
 585
 586                slash = strchrnul(path, '/');
 587                /*
 588                 * Between path and slash is the name of the subtree
 589                 * to look for.
 590                 */
 591                sub = find_subtree(it, path, slash - path, 0);
 592                if (!sub)
 593                        return NULL;
 594                it = sub->cache_tree;
 595
 596                path = slash;
 597                while (*path == '/')
 598                        path++;
 599        }
 600        return it;
 601}
 602
 603int write_index_as_tree(unsigned char *sha1, struct index_state *index_state, const char *index_path, int flags, const char *prefix)
 604{
 605        int entries, was_valid;
 606        struct lock_file lock_file = LOCK_INIT;
 607        int ret = 0;
 608
 609        hold_lock_file_for_update(&lock_file, index_path, LOCK_DIE_ON_ERROR);
 610
 611        entries = read_index_from(index_state, index_path);
 612        if (entries < 0) {
 613                ret = WRITE_TREE_UNREADABLE_INDEX;
 614                goto out;
 615        }
 616        if (flags & WRITE_TREE_IGNORE_CACHE_TREE)
 617                cache_tree_free(&index_state->cache_tree);
 618
 619        if (!index_state->cache_tree)
 620                index_state->cache_tree = cache_tree();
 621
 622        was_valid = cache_tree_fully_valid(index_state->cache_tree);
 623        if (!was_valid) {
 624                if (cache_tree_update(index_state, flags) < 0) {
 625                        ret = WRITE_TREE_UNMERGED_INDEX;
 626                        goto out;
 627                }
 628                write_locked_index(index_state, &lock_file, COMMIT_LOCK);
 629                /* Not being able to write is fine -- we are only interested
 630                 * in updating the cache-tree part, and if the next caller
 631                 * ends up using the old index with unupdated cache-tree part
 632                 * it misses the work we did here, but that is just a
 633                 * performance penalty and not a big deal.
 634                 */
 635        }
 636
 637        if (prefix) {
 638                struct cache_tree *subtree;
 639                subtree = cache_tree_find(index_state->cache_tree, prefix);
 640                if (!subtree) {
 641                        ret = WRITE_TREE_PREFIX_ERROR;
 642                        goto out;
 643                }
 644                hashcpy(sha1, subtree->oid.hash);
 645        }
 646        else
 647                hashcpy(sha1, index_state->cache_tree->oid.hash);
 648
 649out:
 650        rollback_lock_file(&lock_file);
 651        return ret;
 652}
 653
 654int write_cache_as_tree(unsigned char *sha1, int flags, const char *prefix)
 655{
 656        return write_index_as_tree(sha1, &the_index, get_index_file(), flags, prefix);
 657}
 658
 659static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 660{
 661        struct tree_desc desc;
 662        struct name_entry entry;
 663        int cnt;
 664
 665        oidcpy(&it->oid, &tree->object.oid);
 666        init_tree_desc(&desc, tree->buffer, tree->size);
 667        cnt = 0;
 668        while (tree_entry(&desc, &entry)) {
 669                if (!S_ISDIR(entry.mode))
 670                        cnt++;
 671                else {
 672                        struct cache_tree_sub *sub;
 673                        struct tree *subtree = lookup_tree(entry.oid);
 674                        if (!subtree->object.parsed)
 675                                parse_tree(subtree);
 676                        sub = cache_tree_sub(it, entry.path);
 677                        sub->cache_tree = cache_tree();
 678                        prime_cache_tree_rec(sub->cache_tree, subtree);
 679                        cnt += sub->cache_tree->entry_count;
 680                }
 681        }
 682        it->entry_count = cnt;
 683}
 684
 685void prime_cache_tree(struct index_state *istate, struct tree *tree)
 686{
 687        cache_tree_free(&istate->cache_tree);
 688        istate->cache_tree = cache_tree();
 689        prime_cache_tree_rec(istate->cache_tree, tree);
 690        istate->cache_changed |= CACHE_TREE_CHANGED;
 691}
 692
 693/*
 694 * find the cache_tree that corresponds to the current level without
 695 * exploding the full path into textual form.  The root of the
 696 * cache tree is given as "root", and our current level is "info".
 697 * (1) When at root level, info->prev is NULL, so it is "root" itself.
 698 * (2) Otherwise, find the cache_tree that corresponds to one level
 699 *     above us, and find ourselves in there.
 700 */
 701static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root,
 702                                                         struct traverse_info *info)
 703{
 704        struct cache_tree *our_parent;
 705
 706        if (!info->prev)
 707                return root;
 708        our_parent = find_cache_tree_from_traversal(root, info->prev);
 709        return cache_tree_find(our_parent, info->name.path);
 710}
 711
 712int cache_tree_matches_traversal(struct cache_tree *root,
 713                                 struct name_entry *ent,
 714                                 struct traverse_info *info)
 715{
 716        struct cache_tree *it;
 717
 718        it = find_cache_tree_from_traversal(root, info);
 719        it = cache_tree_find(it, ent->path);
 720        if (it && it->entry_count > 0 && !oidcmp(ent->oid, &it->oid))
 721                return it->entry_count;
 722        return 0;
 723}
 724
 725int update_main_cache_tree(int flags)
 726{
 727        if (!the_index.cache_tree)
 728                the_index.cache_tree = cache_tree();
 729        return cache_tree_update(&the_index, flags);
 730}