refs/ref-cache.c

   1 #include "../cache.h"
   2 #include "../refs.h"
   3 #include "refs-internal.h"
   4 #include "ref-cache.h"
   5 #include "../iterator.h"
   6
   7 void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
   8 {
   9         ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
  10         dir->entries[dir->nr++] = entry;
  11         /* optimize for the case that entries are added in order */
  12         if (dir->nr == 1 ||
  13             (dir->nr == dir->sorted + 1 &&
  14              strcmp(dir->entries[dir->nr - 2]->name,
  15                     dir->entries[dir->nr - 1]->name) < 0))
  16                 dir->sorted = dir->nr;
  17 }
  18
  19 struct ref_dir *get_ref_dir(struct ref_entry *entry)
  20 {
  21         struct ref_dir *dir;
  22         assert(entry->flag & REF_DIR);
  23         dir = &entry->u.subdir;
  24         if (entry->flag & REF_INCOMPLETE) {
  25                 if (!dir->cache->fill_ref_dir)
  26                         die("BUG: incomplete ref_store without fill_ref_dir function");
  27
  28                 dir->cache->fill_ref_dir(dir->cache->ref_store, dir, entry->name);
  29                 entry->flag &= ~REF_INCOMPLETE;
  30         }
  31         return dir;
  32 }
  33
  34 struct ref_entry *create_ref_entry(const char *refname,
  35                                    const unsigned char *sha1, int flag,
  36                                    int check_name)
  37 {
  38         struct ref_entry *ref;
  39
  40         if (check_name &&
  41             check_refname_format(refname, REFNAME_ALLOW_ONELEVEL))
  42                 die("Reference has invalid format: '%s'", refname);
  43         FLEX_ALLOC_STR(ref, name, refname);
  44         hashcpy(ref->u.value.oid.hash, sha1);
  45         oidclr(&ref->u.value.peeled);
  46         ref->flag = flag;
  47         return ref;
  48 }
  49
  50 struct ref_cache *create_ref_cache(struct ref_store *refs,
  51                                    fill_ref_dir_fn *fill_ref_dir)
  52 {
  53         struct ref_cache *ret = xcalloc(1, sizeof(*ret));
  54
  55         ret->ref_store = refs;
  56         ret->fill_ref_dir = fill_ref_dir;
  57         ret->root = create_dir_entry(ret, "", 0, 1);
  58         return ret;
  59 }
  60
  61 static void clear_ref_dir(struct ref_dir *dir);
  62
  63 static void free_ref_entry(struct ref_entry *entry)
  64 {
  65         if (entry->flag & REF_DIR) {
  66                 /*
  67                  * Do not use get_ref_dir() here, as that might
  68                  * trigger the reading of loose refs.
  69                  */
  70                 clear_ref_dir(&entry->u.subdir);
  71         }
  72         free(entry);
  73 }
  74
  75 void free_ref_cache(struct ref_cache *cache)
  76 {
  77         free_ref_entry(cache->root);
  78         free(cache);
  79 }
  80
  81 /*
  82  * Clear and free all entries in dir, recursively.
  83  */
  84 static void clear_ref_dir(struct ref_dir *dir)
  85 {
  86         int i;
  87         for (i = 0; i < dir->nr; i++)
  88                 free_ref_entry(dir->entries[i]);
  89         free(dir->entries);
  90         dir->sorted = dir->nr = dir->alloc = 0;
  91         dir->entries = NULL;
  92 }
  93
  94 struct ref_entry *create_dir_entry(struct ref_cache *cache,
  95                                    const char *dirname, size_t len,
  96                                    int incomplete)
  97 {
  98         struct ref_entry *direntry;
  99
 100         FLEX_ALLOC_MEM(direntry, name, dirname, len);
 101         direntry->u.subdir.cache = cache;
 102         direntry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0);
 103         return direntry;
 104 }
 105
 106 static int ref_entry_cmp(const void *a, const void *b)
 107 {
 108         struct ref_entry *one = *(struct ref_entry **)a;
 109         struct ref_entry *two = *(struct ref_entry **)b;
 110         return strcmp(one->name, two->name);
 111 }
 112
 113 static void sort_ref_dir(struct ref_dir *dir);
 114
 115 struct string_slice {
 116         size_t len;
 117         const char *str;
 118 };
 119
 120 static int ref_entry_cmp_sslice(const void *key_, const void *ent_)
 121 {
 122         const struct string_slice *key = key_;
 123         const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;
 124         int cmp = strncmp(key->str, ent->name, key->len);
 125         if (cmp)
 126                 return cmp;
 127         return '\0' - (unsigned char)ent->name[key->len];
 128 }
 129
 130 int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)
 131 {
 132         struct ref_entry **r;
 133         struct string_slice key;
 134
 135         if (refname == NULL || !dir->nr)
 136                 return -1;
 137
 138         sort_ref_dir(dir);
 139         key.len = len;
 140         key.str = refname;
 141         r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),
 142                     ref_entry_cmp_sslice);
 143
 144         if (r == NULL)
 145                 return -1;
 146
 147         return r - dir->entries;
 148 }
 149
 150 /*
 151  * Search for a directory entry directly within dir (without
 152  * recursing).  Sort dir if necessary.  subdirname must be a directory
 153  * name (i.e., end in '/').  If mkdir is set, then create the
 154  * directory if it is missing; otherwise, return NULL if the desired
 155  * directory cannot be found.  dir must already be complete.
 156  */
 157 static struct ref_dir *search_for_subdir(struct ref_dir *dir,
 158                                          const char *subdirname, size_t len,
 159                                          int mkdir)
 160 {
 161         int entry_index = search_ref_dir(dir, subdirname, len);
 162         struct ref_entry *entry;
 163         if (entry_index == -1) {
 164                 if (!mkdir)
 165                         return NULL;
 166                 /*
 167                  * Since dir is complete, the absence of a subdir
 168                  * means that the subdir really doesn't exist;
 169                  * therefore, create an empty record for it but mark
 170                  * the record complete.
 171                  */
 172                 entry = create_dir_entry(dir->cache, subdirname, len, 0);
 173                 add_entry_to_dir(dir, entry);
 174         } else {
 175                 entry = dir->entries[entry_index];
 176         }
 177         return get_ref_dir(entry);
 178 }
 179
 180 /*
 181  * If refname is a reference name, find the ref_dir within the dir
 182  * tree that should hold refname. If refname is a directory name
 183  * (i.e., it ends in '/'), then return that ref_dir itself. dir must
 184  * represent the top-level directory and must already be complete.
 185  * Sort ref_dirs and recurse into subdirectories as necessary. If
 186  * mkdir is set, then create any missing directories; otherwise,
 187  * return NULL if the desired directory cannot be found.
 188  */
 189 static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 190                                            const char *refname, int mkdir)
 191 {
 192         const char *slash;
 193         for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
 194                 size_t dirnamelen = slash - refname + 1;
 195                 struct ref_dir *subdir;
 196                 subdir = search_for_subdir(dir, refname, dirnamelen, mkdir);
 197                 if (!subdir) {
 198                         dir = NULL;
 199                         break;
 200                 }
 201                 dir = subdir;
 202         }
 203
 204         return dir;
 205 }
 206
 207 struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
 208 {
 209         int entry_index;
 210         struct ref_entry *entry;
 211         dir = find_containing_dir(dir, refname, 0);
 212         if (!dir)
 213                 return NULL;
 214         entry_index = search_ref_dir(dir, refname, strlen(refname));
 215         if (entry_index == -1)
 216                 return NULL;
 217         entry = dir->entries[entry_index];
 218         return (entry->flag & REF_DIR) ? NULL : entry;
 219 }
 220
 221 int remove_entry_from_dir(struct ref_dir *dir, const char *refname)
 222 {
 223         int refname_len = strlen(refname);
 224         int entry_index;
 225         struct ref_entry *entry;
 226         int is_dir = refname[refname_len - 1] == '/';
 227         if (is_dir) {
 228                 /*
 229                  * refname represents a reference directory.  Remove
 230                  * the trailing slash; otherwise we will get the
 231                  * directory *representing* refname rather than the
 232                  * one *containing* it.
 233                  */
 234                 char *dirname = xmemdupz(refname, refname_len - 1);
 235                 dir = find_containing_dir(dir, dirname, 0);
 236                 free(dirname);
 237         } else {
 238                 dir = find_containing_dir(dir, refname, 0);
 239         }
 240         if (!dir)
 241                 return -1;
 242         entry_index = search_ref_dir(dir, refname, refname_len);
 243         if (entry_index == -1)
 244                 return -1;
 245         entry = dir->entries[entry_index];
 246
 247         memmove(&dir->entries[entry_index],
 248                 &dir->entries[entry_index + 1],
 249                 (dir->nr - entry_index - 1) * sizeof(*dir->entries)
 250                 );
 251         dir->nr--;
 252         if (dir->sorted > entry_index)
 253                 dir->sorted--;
 254         free_ref_entry(entry);
 255         return dir->nr;
 256 }
 257
 258 int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref)
 259 {
 260         dir = find_containing_dir(dir, ref->name, 1);
 261         if (!dir)
 262                 return -1;
 263         add_entry_to_dir(dir, ref);
 264         return 0;
 265 }
 266
 267 /*
 268  * Emit a warning and return true iff ref1 and ref2 have the same name
 269  * and the same sha1.  Die if they have the same name but different
 270  * sha1s.
 271  */
 272 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
 273 {
 274         if (strcmp(ref1->name, ref2->name))
 275                 return 0;
 276
 277         /* Duplicate name; make sure that they don't conflict: */
 278
 279         if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
 280                 /* This is impossible by construction */
 281                 die("Reference directory conflict: %s", ref1->name);
 282
 283         if (oidcmp(&ref1->u.value.oid, &ref2->u.value.oid))
 284                 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
 285
 286         warning("Duplicated ref: %s", ref1->name);
 287         return 1;
 288 }
 289
 290 /*
 291  * Sort the entries in dir non-recursively (if they are not already
 292  * sorted) and remove any duplicate entries.
 293  */
 294 static void sort_ref_dir(struct ref_dir *dir)
 295 {
 296         int i, j;
 297         struct ref_entry *last = NULL;
 298
 299         /*
 300          * This check also prevents passing a zero-length array to qsort(),
 301          * which is a problem on some platforms.
 302          */
 303         if (dir->sorted == dir->nr)
 304                 return;
 305
 306         QSORT(dir->entries, dir->nr, ref_entry_cmp);
 307
 308         /* Remove any duplicates: */
 309         for (i = 0, j = 0; j < dir->nr; j++) {
 310                 struct ref_entry *entry = dir->entries[j];
 311                 if (last && is_dup_ref(last, entry))
 312                         free_ref_entry(entry);
 313                 else
 314                         last = dir->entries[i++] = entry;
 315         }
 316         dir->sorted = dir->nr = i;
 317 }
 318
 319 /*
 320  * Load all of the refs from `dir` (recursively) into our in-memory
 321  * cache.
 322  */
 323 static void prime_ref_dir(struct ref_dir *dir)
 324 {
 325         /*
 326          * The hard work of loading loose refs is done by get_ref_dir(), so we
 327          * just need to recurse through all of the sub-directories. We do not
 328          * even need to care about sorting, as traversal order does not matter
 329          * to us.
 330          */
 331         int i;
 332         for (i = 0; i < dir->nr; i++) {
 333                 struct ref_entry *entry = dir->entries[i];
 334                 if (entry->flag & REF_DIR)
 335                         prime_ref_dir(get_ref_dir(entry));
 336         }
 337 }
 338
 339 /*
 340  * A level in the reference hierarchy that is currently being iterated
 341  * through.
 342  */
 343 struct cache_ref_iterator_level {
 344         /*
 345          * The ref_dir being iterated over at this level. The ref_dir
 346          * is sorted before being stored here.
 347          */
 348         struct ref_dir *dir;
 349
 350         /*
 351          * The index of the current entry within dir (which might
 352          * itself be a directory). If index == -1, then the iteration
 353          * hasn't yet begun. If index == dir->nr, then the iteration
 354          * through this level is over.
 355          */
 356         int index;
 357 };
 358
 359 /*
 360  * Represent an iteration through a ref_dir in the memory cache. The
 361  * iteration recurses through subdirectories.
 362  */
 363 struct cache_ref_iterator {
 364         struct ref_iterator base;
 365
 366         /*
 367          * The number of levels currently on the stack. This is always
 368          * at least 1, because when it becomes zero the iteration is
 369          * ended and this struct is freed.
 370          */
 371         size_t levels_nr;
 372
 373         /* The number of levels that have been allocated on the stack */
 374         size_t levels_alloc;
 375
 376         /*
 377          * A stack of levels. levels[0] is the uppermost level that is
 378          * being iterated over in this iteration. (This is not
 379          * necessary the top level in the references hierarchy. If we
 380          * are iterating through a subtree, then levels[0] will hold
 381          * the ref_dir for that subtree, and subsequent levels will go
 382          * on from there.)
 383          */
 384         struct cache_ref_iterator_level *levels;
 385 };
 386
 387 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
 388 {
 389         struct cache_ref_iterator *iter =
 390                 (struct cache_ref_iterator *)ref_iterator;
 391
 392         while (1) {
 393                 struct cache_ref_iterator_level *level =
 394                         &iter->levels[iter->levels_nr - 1];
 395                 struct ref_dir *dir = level->dir;
 396                 struct ref_entry *entry;
 397
 398                 if (level->index == -1)
 399                         sort_ref_dir(dir);
 400
 401                 if (++level->index == level->dir->nr) {
 402                         /* This level is exhausted; pop up a level */
 403                         if (--iter->levels_nr == 0)
 404                                 return ref_iterator_abort(ref_iterator);
 405
 406                         continue;
 407                 }
 408
 409                 entry = dir->entries[level->index];
 410
 411                 if (entry->flag & REF_DIR) {
 412                         /* push down a level */
 413                         ALLOC_GROW(iter->levels, iter->levels_nr + 1,
 414                                    iter->levels_alloc);
 415
 416                         level = &iter->levels[iter->levels_nr++];
 417                         level->dir = get_ref_dir(entry);
 418                         level->index = -1;
 419                 } else {
 420                         iter->base.refname = entry->name;
 421                         iter->base.oid = &entry->u.value.oid;
 422                         iter->base.flags = entry->flag;
 423                         return ITER_OK;
 424                 }
 425         }
 426 }
 427
 428 enum peel_status peel_entry(struct ref_entry *entry, int repeel)
 429 {
 430         enum peel_status status;
 431
 432         if (entry->flag & REF_KNOWS_PEELED) {
 433                 if (repeel) {
 434                         entry->flag &= ~REF_KNOWS_PEELED;
 435                         oidclr(&entry->u.value.peeled);
 436                 } else {
 437                         return is_null_oid(&entry->u.value.peeled) ?
 438                                 PEEL_NON_TAG : PEEL_PEELED;
 439                 }
 440         }
 441         if (entry->flag & REF_ISBROKEN)
 442                 return PEEL_BROKEN;
 443         if (entry->flag & REF_ISSYMREF)
 444                 return PEEL_IS_SYMREF;
 445
 446         status = peel_object(entry->u.value.oid.hash, entry->u.value.peeled.hash);
 447         if (status == PEEL_PEELED || status == PEEL_NON_TAG)
 448                 entry->flag |= REF_KNOWS_PEELED;
 449         return status;
 450 }
 451
 452 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
 453                                    struct object_id *peeled)
 454 {
 455         struct cache_ref_iterator *iter =
 456                 (struct cache_ref_iterator *)ref_iterator;
 457         struct cache_ref_iterator_level *level;
 458         struct ref_entry *entry;
 459
 460         level = &iter->levels[iter->levels_nr - 1];
 461
 462         if (level->index == -1)
 463                 die("BUG: peel called before advance for cache iterator");
 464
 465         entry = level->dir->entries[level->index];
 466
 467         if (peel_entry(entry, 0))
 468                 return -1;
 469         oidcpy(peeled, &entry->u.value.peeled);
 470         return 0;
 471 }
 472
 473 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
 474 {
 475         struct cache_ref_iterator *iter =
 476                 (struct cache_ref_iterator *)ref_iterator;
 477
 478         free(iter->levels);
 479         base_ref_iterator_free(ref_iterator);
 480         return ITER_DONE;
 481 }
 482
 483 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
 484         cache_ref_iterator_advance,
 485         cache_ref_iterator_peel,
 486         cache_ref_iterator_abort
 487 };
 488
 489 struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
 490                                               const char *prefix,
 491                                               int prime_dir)
 492 {
 493         struct ref_dir *dir;
 494         struct cache_ref_iterator *iter;
 495         struct ref_iterator *ref_iterator;
 496         struct cache_ref_iterator_level *level;
 497
 498         dir = get_ref_dir(cache->root);
 499         if (prefix && *prefix)
 500                 dir = find_containing_dir(dir, prefix, 0);
 501         if (!dir)
 502                 /* There's nothing to iterate over. */
 503                 return  empty_ref_iterator_begin();
 504
 505         if (prime_dir)
 506                 prime_ref_dir(dir);
 507
 508         iter = xcalloc(1, sizeof(*iter));
 509         ref_iterator = &iter->base;
 510         base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);
 511         ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
 512
 513         iter->levels_nr = 1;
 514         level = &iter->levels[0];
 515         level->index = -1;
 516         level->dir = dir;
 517
 518         if (prefix && *prefix)
 519                 ref_iterator = prefix_ref_iterator_begin(ref_iterator,
 520                                                          prefix, 0);
 521
 522         return ref_iterator;
 523 }