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