#include "../config.h"
#include "../refs.h"
#include "refs-internal.h"
-#include "ref-cache.h"
#include "packed-backend.h"
#include "../iterator.h"
#include "../lockfile.h"
*/
struct packed_ref_store *refs;
- struct ref_cache *cache;
-
/* Is the `packed-refs` file currently mmapped? */
int mmapped;
static int release_packed_ref_cache(struct packed_ref_cache *packed_refs)
{
if (!--packed_refs->referrers) {
- free_ref_cache(packed_refs->cache);
stat_validity_clear(&packed_refs->validity);
release_packed_ref_buffer(packed_refs);
free(packed_refs);
}
+/*
+ * This value is set in `base.flags` if the peeled value of the
+ * current reference is known. In that case, `peeled` contains the
+ * correct peeled value for the reference, which might be `null_sha1`
+ * if the reference is not a tag or if it is broken.
+ */
+#define REF_KNOWS_PEELED 0x40
+
/*
* An iterator over a packed-refs file that is currently mmapped.
*/
}
}
+/*
+ * Compare a packed-refs record pointed to by `rec` to the specified
+ * NUL-terminated refname.
+ */
+static int cmp_entry_to_refname(const char *rec, const char *refname)
+{
+ const char *r1 = rec + GIT_SHA1_HEXSZ + 1;
+ const char *r2 = refname;
+
+ while (1) {
+ if (*r1 == '\n')
+ return *r2 ? -1 : 0;
+ if (!*r2)
+ return 1;
+ if (*r1 != *r2)
+ return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1;
+ r1++;
+ r2++;
+ }
+}
+
/*
* `packed_refs->buf` is not known to be sorted. Check whether it is,
* and if not, sort it into new memory and munmap/free the old
return p;
}
+/*
+ * Return a pointer to the start of the record following the record
+ * that contains `*p`. If none is found before `end`, return `end`.
+ */
+static const char *find_end_of_record(const char *p, const char *end)
+{
+ while (++p < end && (p[-1] != '\n' || p[0] == '^'))
+ ;
+ return p;
+}
+
/*
* We want to be able to compare mmapped reference records quickly,
* without totally parsing them. We can do so because the records are
return 1;
}
+/*
+ * Find the place in `cache->buf` where the start of the record for
+ * `refname` starts. If `mustexist` is true and the reference doesn't
+ * exist, then return NULL. If `mustexist` is false and the reference
+ * doesn't exist, then return the point where that reference would be
+ * inserted. In the latter mode, `refname` doesn't have to be a proper
+ * reference name; for example, one could search for "refs/replace/"
+ * to find the start of any replace references.
+ *
+ * The record is sought using a binary search, so `cache->buf` must be
+ * sorted.
+ */
+static const char *find_reference_location(struct packed_ref_cache *cache,
+ const char *refname, int mustexist)
+{
+ /*
+ * This is not *quite* a garden-variety binary search, because
+ * the data we're searching is made up of records, and we
+ * always need to find the beginning of a record to do a
+ * comparison. A "record" here is one line for the reference
+ * itself and zero or one peel lines that start with '^'. Our
+ * loop invariant is described in the next two comments.
+ */
+
+ /*
+ * A pointer to the character at the start of a record whose
+ * preceding records all have reference names that come
+ * *before* `refname`.
+ */
+ const char *lo = cache->buf + cache->header_len;
+
+ /*
+ * A pointer to a the first character of a record whose
+ * reference name comes *after* `refname`.
+ */
+ const char *hi = cache->eof;
+
+ while (lo < hi) {
+ const char *mid, *rec;
+ int cmp;
+
+ mid = lo + (hi - lo) / 2;
+ rec = find_start_of_record(lo, mid);
+ cmp = cmp_entry_to_refname(rec, refname);
+ if (cmp < 0) {
+ lo = find_end_of_record(mid, hi);
+ } else if (cmp > 0) {
+ hi = rec;
+ } else {
+ return rec;
+ }
+ }
+
+ if (mustexist)
+ return NULL;
+ else
+ return lo;
+}
+
/*
* Read from the `packed-refs` file into a newly-allocated
* `packed_ref_cache` and return it. The return value will already
static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)
{
struct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));
- struct ref_dir *dir;
- struct ref_iterator *iter;
int sorted = 0;
- int ok;
packed_refs->refs = refs;
acquire_packed_ref_cache(packed_refs);
- packed_refs->cache = create_ref_cache(NULL, NULL);
- packed_refs->cache->root->flag &= ~REF_INCOMPLETE;
packed_refs->peeled = PEELED_NONE;
if (!load_contents(packed_refs))
packed_refs->eof = buf_copy + size;
}
- dir = get_ref_dir(packed_refs->cache->root);
- iter = mmapped_ref_iterator_begin(
- packed_refs,
- packed_refs->buf + packed_refs->header_len,
- packed_refs->eof);
- while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
- struct ref_entry *entry =
- create_ref_entry(iter->refname, iter->oid, iter->flags);
-
- if ((iter->flags & REF_KNOWS_PEELED))
- ref_iterator_peel(iter, &entry->u.value.peeled);
- add_ref_entry(dir, entry);
- }
-
- if (ok != ITER_DONE)
- die("error reading packed-refs file %s", refs->path);
-
return packed_refs;
}
return refs->cache;
}
-static struct ref_dir *get_packed_ref_dir(struct packed_ref_cache *packed_ref_cache)
-{
- return get_ref_dir(packed_ref_cache->cache->root);
-}
-
-static struct ref_dir *get_packed_refs(struct packed_ref_store *refs)
-{
- return get_packed_ref_dir(get_packed_ref_cache(refs));
-}
-
-/*
- * Return the ref_entry for the given refname from the packed
- * references. If it does not exist, return NULL.
- */
-static struct ref_entry *get_packed_ref(struct packed_ref_store *refs,
- const char *refname)
-{
- return find_ref_entry(get_packed_refs(refs), refname);
-}
-
static int packed_read_raw_ref(struct ref_store *ref_store,
const char *refname, unsigned char *sha1,
struct strbuf *referent, unsigned int *type)
{
struct packed_ref_store *refs =
packed_downcast(ref_store, REF_STORE_READ, "read_raw_ref");
-
- struct ref_entry *entry;
+ struct packed_ref_cache *packed_refs = get_packed_ref_cache(refs);
+ const char *rec;
*type = 0;
- entry = get_packed_ref(refs, refname);
- if (!entry) {
+ rec = find_reference_location(packed_refs, refname, 1);
+
+ if (!rec) {
+ /* refname is not a packed reference. */
errno = ENOENT;
return -1;
}
- hashcpy(sha1, entry->u.value.oid.hash);
- *type = REF_ISPACKED;
- return 0;
-}
-
-static int packed_peel_ref(struct ref_store *ref_store,
- const char *refname, unsigned char *sha1)
-{
- struct packed_ref_store *refs =
- packed_downcast(ref_store, REF_STORE_READ | REF_STORE_ODB,
- "peel_ref");
- struct ref_entry *r = get_packed_ref(refs, refname);
+ if (get_sha1_hex(rec, sha1))
+ die_invalid_line(refs->path, rec, packed_refs->eof - rec);
- if (!r || peel_entry(r, 0))
- return -1;
-
- hashcpy(sha1, r->u.value.peeled.hash);
+ *type = REF_ISPACKED;
return 0;
}
const char *prefix, unsigned int flags)
{
struct packed_ref_store *refs;
+ struct packed_ref_cache *packed_refs;
+ const char *start;
struct packed_ref_iterator *iter;
struct ref_iterator *ref_iterator;
unsigned int required_flags = REF_STORE_READ;
* the packed-ref cache is up to date with what is on disk,
* and re-reads it if not.
*/
+ iter->cache = packed_refs = get_packed_ref_cache(refs);
+ acquire_packed_ref_cache(packed_refs);
+
+ if (prefix && *prefix)
+ start = find_reference_location(packed_refs, prefix, 0);
+ else
+ start = packed_refs->buf + packed_refs->header_len;
- iter->cache = get_packed_ref_cache(refs);
- acquire_packed_ref_cache(iter->cache);
- iter->iter0 = cache_ref_iterator_begin(iter->cache->cache, prefix, 0);
+ iter->iter0 = mmapped_ref_iterator_begin(packed_refs,
+ start, packed_refs->eof);
iter->flags = flags;
+ if (prefix && *prefix)
+ /* Stop iteration after we've gone *past* prefix: */
+ ref_iterator = prefix_ref_iterator_begin(ref_iterator, prefix, 0);
+
return ref_iterator;
}
packed_initial_transaction_commit,
packed_pack_refs,
- packed_peel_ref,
packed_create_symref,
packed_delete_refs,
packed_rename_ref,