X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=refs.c;h=e7843eb6b70b7de6c1ed1992db7adee1d99b27bc;hb=57cf4ad6e82af6aaa38bb215ea35ea9c465c6045;hp=448f0271f830ca1b38f4d077b667e7aa122657d3;hpb=55956350024f0706294001cb50d513cf0fa038a1;p=git.git diff --git a/refs.c b/refs.c index 448f0271f..e7843eb6b 100644 --- a/refs.c +++ b/refs.c @@ -7,14 +7,18 @@ /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */ #define REF_KNOWS_PEELED 0x10 -struct ref_list { - struct ref_list *next; +struct ref_entry { unsigned char flag; /* ISSYMREF? ISPACKED? */ unsigned char sha1[20]; unsigned char peeled[20]; char name[FLEX_ARRAY]; }; +struct ref_array { + int nr, alloc; + struct ref_entry **refs; +}; + static const char *parse_ref_line(char *line, unsigned char *sha1) { /* @@ -43,151 +47,176 @@ static const char *parse_ref_line(char *line, unsigned char *sha1) return line; } -static struct ref_list *add_ref(const char *name, const unsigned char *sha1, - int flag, struct ref_list *list, - struct ref_list **new_entry) +static void add_ref(const char *name, const unsigned char *sha1, + int flag, int check_name, struct ref_array *refs, + struct ref_entry **new_entry) { int len; - struct ref_list *entry; + struct ref_entry *entry; /* Allocate it and add it in.. */ len = strlen(name) + 1; - entry = xmalloc(sizeof(struct ref_list) + len); + entry = xmalloc(sizeof(struct ref_entry) + len); hashcpy(entry->sha1, sha1); hashclr(entry->peeled); - if (check_refname_format(name, REFNAME_ALLOW_ONELEVEL|REFNAME_DOT_COMPONENT)) + if (check_name && + check_refname_format(name, REFNAME_ALLOW_ONELEVEL|REFNAME_DOT_COMPONENT)) die("Reference has invalid format: '%s'", name); memcpy(entry->name, name, len); entry->flag = flag; - entry->next = list; if (new_entry) *new_entry = entry; - return entry; + ALLOC_GROW(refs->refs, refs->nr + 1, refs->alloc); + refs->refs[refs->nr++] = entry; +} + +static int ref_entry_cmp(const void *a, const void *b) +{ + struct ref_entry *one = *(struct ref_entry **)a; + struct ref_entry *two = *(struct ref_entry **)b; + return strcmp(one->name, two->name); } -/* merge sort the ref list */ -static struct ref_list *sort_ref_list(struct ref_list *list) +static void sort_ref_array(struct ref_array *array) { - int psize, qsize, last_merge_count, cmp; - struct ref_list *p, *q, *l, *e; - struct ref_list *new_list = list; - int k = 1; - int merge_count = 0; + int i = 0, j = 1; - if (!list) - return list; + /* Nothing to sort unless there are at least two entries */ + if (array->nr < 2) + return; - do { - last_merge_count = merge_count; - merge_count = 0; + qsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp); - psize = 0; + /* Remove any duplicates from the ref_array */ + for (; j < array->nr; j++) { + struct ref_entry *a = array->refs[i]; + struct ref_entry *b = array->refs[j]; + if (!strcmp(a->name, b->name)) { + if (hashcmp(a->sha1, b->sha1)) + die("Duplicated ref, and SHA1s don't match: %s", + a->name); + warning("Duplicated ref: %s", a->name); + free(b); + continue; + } + i++; + array->refs[i] = array->refs[j]; + } + array->nr = i + 1; +} - p = new_list; - q = new_list; - new_list = NULL; - l = NULL; +static struct ref_entry *search_ref_array(struct ref_array *array, const char *name) +{ + struct ref_entry *e, **r; + int len; - while (p) { - merge_count++; + if (name == NULL) + return NULL; - while (psize < k && q->next) { - q = q->next; - psize++; - } - qsize = k; - - while ((psize > 0) || (qsize > 0 && q)) { - if (qsize == 0 || !q) { - e = p; - p = p->next; - psize--; - } else if (psize == 0) { - e = q; - q = q->next; - qsize--; - } else { - cmp = strcmp(q->name, p->name); - if (cmp < 0) { - e = q; - q = q->next; - qsize--; - } else if (cmp > 0) { - e = p; - p = p->next; - psize--; - } else { - if (hashcmp(q->sha1, p->sha1)) - die("Duplicated ref, and SHA1s don't match: %s", - q->name); - warning("Duplicated ref: %s", q->name); - e = q; - q = q->next; - qsize--; - free(e); - e = p; - p = p->next; - psize--; - } - } + if (!array->nr) + return NULL; - e->next = NULL; + len = strlen(name) + 1; + e = xmalloc(sizeof(struct ref_entry) + len); + memcpy(e->name, name, len); - if (l) - l->next = e; - if (!new_list) - new_list = e; - l = e; - } + r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp); - p = q; - }; + free(e); - k = k * 2; - } while ((last_merge_count != merge_count) || (last_merge_count != 1)); + if (r == NULL) + return NULL; - return new_list; + return *r; } /* * Future: need to be in "struct repository" * when doing a full libification. */ -static struct cached_refs { +static struct ref_cache { + struct ref_cache *next; char did_loose; char did_packed; - struct ref_list *loose; - struct ref_list *packed; -} cached_refs, submodule_refs; -static struct ref_list *current_ref; + struct ref_array loose; + struct ref_array packed; + /* The submodule name, or "" for the main repo. */ + char name[FLEX_ARRAY]; +} *ref_cache; + +static struct ref_entry *current_ref; -static struct ref_list *extra_refs; +static struct ref_array extra_refs; -static void free_ref_list(struct ref_list *list) +static void free_ref_array(struct ref_array *array) { - struct ref_list *next; - for ( ; list; list = next) { - next = list->next; - free(list); - } + int i; + for (i = 0; i < array->nr; i++) + free(array->refs[i]); + free(array->refs); + array->nr = array->alloc = 0; + array->refs = NULL; +} + +static void clear_packed_ref_cache(struct ref_cache *refs) +{ + if (refs->did_packed) + free_ref_array(&refs->packed); + refs->did_packed = 0; +} + +static void clear_loose_ref_cache(struct ref_cache *refs) +{ + if (refs->did_loose) + free_ref_array(&refs->loose); + refs->did_loose = 0; } -static void invalidate_cached_refs(void) +static struct ref_cache *create_ref_cache(const char *submodule) { - struct cached_refs *ca = &cached_refs; + int len; + struct ref_cache *refs; + if (!submodule) + submodule = ""; + len = strlen(submodule) + 1; + refs = xcalloc(1, sizeof(struct ref_cache) + len); + memcpy(refs->name, submodule, len); + return refs; +} - if (ca->did_loose && ca->loose) - free_ref_list(ca->loose); - if (ca->did_packed && ca->packed) - free_ref_list(ca->packed); - ca->loose = ca->packed = NULL; - ca->did_loose = ca->did_packed = 0; +/* + * Return a pointer to a ref_cache for the specified submodule. For + * the main repository, use submodule==NULL. The returned structure + * will be allocated and initialized but not necessarily populated; it + * should not be freed. + */ +static struct ref_cache *get_ref_cache(const char *submodule) +{ + struct ref_cache *refs = ref_cache; + if (!submodule) + submodule = ""; + while (refs) { + if (!strcmp(submodule, refs->name)) + return refs; + refs = refs->next; + } + + refs = create_ref_cache(submodule); + refs->next = ref_cache; + ref_cache = refs; + return refs; } -static void read_packed_refs(FILE *f, struct cached_refs *cached_refs) +void invalidate_ref_cache(const char *submodule) { - struct ref_list *list = NULL; - struct ref_list *last = NULL; + struct ref_cache *refs = get_ref_cache(submodule); + clear_packed_ref_cache(refs); + clear_loose_ref_cache(refs); +} + +static void read_packed_refs(FILE *f, struct ref_array *array) +{ + struct ref_entry *last = NULL; char refline[PATH_MAX]; int flag = REF_ISPACKED; @@ -206,7 +235,7 @@ static void read_packed_refs(FILE *f, struct cached_refs *cached_refs) name = parse_ref_line(refline, sha1); if (name) { - list = add_ref(name, sha1, flag, list, &last); + add_ref(name, sha1, flag, 1, array, &last); continue; } if (last && @@ -216,48 +245,43 @@ static void read_packed_refs(FILE *f, struct cached_refs *cached_refs) !get_sha1_hex(refline + 1, sha1)) hashcpy(last->peeled, sha1); } - cached_refs->packed = sort_ref_list(list); + sort_ref_array(array); } void add_extra_ref(const char *name, const unsigned char *sha1, int flag) { - extra_refs = add_ref(name, sha1, flag, extra_refs, NULL); + add_ref(name, sha1, flag, 0, &extra_refs, NULL); } void clear_extra_refs(void) { - free_ref_list(extra_refs); - extra_refs = NULL; + free_ref_array(&extra_refs); } -static struct ref_list *get_packed_refs(const char *submodule) +static struct ref_array *get_packed_refs(const char *submodule) { - const char *packed_refs_file; - struct cached_refs *refs; + struct ref_cache *refs = get_ref_cache(submodule); - if (submodule) { - packed_refs_file = git_path_submodule(submodule, "packed-refs"); - refs = &submodule_refs; - free_ref_list(refs->packed); - } else { - packed_refs_file = git_path("packed-refs"); - refs = &cached_refs; - } + if (!refs->did_packed) { + const char *packed_refs_file; + FILE *f; - if (!refs->did_packed || submodule) { - FILE *f = fopen(packed_refs_file, "r"); - refs->packed = NULL; + if (submodule) + packed_refs_file = git_path_submodule(submodule, "packed-refs"); + else + packed_refs_file = git_path("packed-refs"); + f = fopen(packed_refs_file, "r"); if (f) { - read_packed_refs(f, refs); + read_packed_refs(f, &refs->packed); fclose(f); } refs->did_packed = 1; } - return refs->packed; + return &refs->packed; } -static struct ref_list *get_ref_dir(const char *submodule, const char *base, - struct ref_list *list) +static void get_ref_dir(const char *submodule, const char *base, + struct ref_array *array) { DIR *dir; const char *path; @@ -300,7 +324,7 @@ static struct ref_list *get_ref_dir(const char *submodule, const char *base, if (stat(refdir, &st) < 0) continue; if (S_ISDIR(st.st_mode)) { - list = get_ref_dir(submodule, ref, list); + get_ref_dir(submodule, ref, array); continue; } if (submodule) { @@ -310,17 +334,15 @@ static struct ref_list *get_ref_dir(const char *submodule, const char *base, hashclr(sha1); flag |= REF_ISBROKEN; } - } else - if (!resolve_ref(ref, sha1, 1, &flag)) { - hashclr(sha1); - flag |= REF_ISBROKEN; - } - list = add_ref(ref, sha1, flag, list, NULL); + } else if (!resolve_ref(ref, sha1, 1, &flag)) { + hashclr(sha1); + flag |= REF_ISBROKEN; + } + add_ref(ref, sha1, flag, 1, array, NULL); } free(ref); closedir(dir); } - return sort_ref_list(list); } struct warn_if_dangling_data { @@ -357,49 +379,43 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname) for_each_rawref(warn_if_dangling_symref, &data); } -static struct ref_list *get_loose_refs(const char *submodule) +static struct ref_array *get_loose_refs(const char *submodule) { - if (submodule) { - free_ref_list(submodule_refs.loose); - submodule_refs.loose = get_ref_dir(submodule, "refs", NULL); - return submodule_refs.loose; - } + struct ref_cache *refs = get_ref_cache(submodule); - if (!cached_refs.did_loose) { - cached_refs.loose = get_ref_dir(NULL, "refs", NULL); - cached_refs.did_loose = 1; + if (!refs->did_loose) { + get_ref_dir(submodule, "refs", &refs->loose); + sort_ref_array(&refs->loose); + refs->did_loose = 1; } - return cached_refs.loose; + return &refs->loose; } /* We allow "recursive" symbolic refs. Only within reason, though */ #define MAXDEPTH 5 #define MAXREFLEN (1024) +/* + * Called by resolve_gitlink_ref_recursive() after it failed to read + * from "name", which is "module/.git/". Find in + * the packed-refs file for the submodule. + */ static int resolve_gitlink_packed_ref(char *name, int pathlen, const char *refname, unsigned char *result) { - FILE *f; - struct cached_refs refs; - struct ref_list *ref; - int retval; + int retval = -1; + struct ref_entry *ref; + struct ref_array *array; - strcpy(name + pathlen, "packed-refs"); - f = fopen(name, "r"); - if (!f) - return -1; - read_packed_refs(f, &refs); - fclose(f); - ref = refs.packed; - retval = -1; - while (ref) { - if (!strcmp(ref->name, refname)) { - retval = 0; - memcpy(result, ref->sha1, 20); - break; - } - ref = ref->next; + /* being defensive: resolve_gitlink_ref() did this for us */ + if (pathlen < 6 || memcmp(name + pathlen - 6, "/.git/", 6)) + die("Oops"); + name[pathlen - 6] = '\0'; /* make it path to the submodule */ + array = get_packed_refs(name); + ref = search_ref_array(array, refname); + if (ref != NULL) { + memcpy(result, ref->sha1, 20); + retval = 0; } - free_ref_list(refs.packed); return retval; } @@ -472,13 +488,11 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *re */ static int get_packed_ref(const char *ref, unsigned char *sha1) { - struct ref_list *list = get_packed_refs(NULL); - while (list) { - if (!strcmp(ref, list->name)) { - hashcpy(sha1, list->sha1); - return 0; - } - list = list->next; + struct ref_array *packed = get_packed_refs(NULL); + struct ref_entry *entry = search_ref_array(packed, ref); + if (entry) { + hashcpy(sha1, entry->sha1); + return 0; } return -1; } @@ -607,7 +621,7 @@ int read_ref(const char *ref, unsigned char *sha1) #define DO_FOR_EACH_INCLUDE_BROKEN 01 static int do_one_ref(const char *base, each_ref_fn fn, int trim, - int flags, void *cb_data, struct ref_list *entry) + int flags, void *cb_data, struct ref_entry *entry) { if (prefixcmp(entry->name, base)) return 0; @@ -653,18 +667,12 @@ int peel_ref(const char *ref, unsigned char *sha1) return -1; if ((flag & REF_ISPACKED)) { - struct ref_list *list = get_packed_refs(NULL); + struct ref_array *array = get_packed_refs(NULL); + struct ref_entry *r = search_ref_array(array, ref); - while (list) { - if (!strcmp(list->name, ref)) { - if (list->flag & REF_KNOWS_PEELED) { - hashcpy(sha1, list->peeled); - return 0; - } - /* older pack-refs did not leave peeled ones */ - break; - } - list = list->next; + if (r != NULL && r->flag & REF_KNOWS_PEELED) { + hashcpy(sha1, r->peeled); + return 0; } } @@ -683,36 +691,39 @@ fallback: static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn, int trim, int flags, void *cb_data) { - int retval = 0; - struct ref_list *packed = get_packed_refs(submodule); - struct ref_list *loose = get_loose_refs(submodule); + int retval = 0, i, p = 0, l = 0; + struct ref_array *packed = get_packed_refs(submodule); + struct ref_array *loose = get_loose_refs(submodule); - struct ref_list *extra; + struct ref_array *extra = &extra_refs; - for (extra = extra_refs; extra; extra = extra->next) - retval = do_one_ref(base, fn, trim, flags, cb_data, extra); + for (i = 0; i < extra->nr; i++) + retval = do_one_ref(base, fn, trim, flags, cb_data, extra->refs[i]); - while (packed && loose) { - struct ref_list *entry; - int cmp = strcmp(packed->name, loose->name); + while (p < packed->nr && l < loose->nr) { + struct ref_entry *entry; + int cmp = strcmp(packed->refs[p]->name, loose->refs[l]->name); if (!cmp) { - packed = packed->next; + p++; continue; } if (cmp > 0) { - entry = loose; - loose = loose->next; + entry = loose->refs[l++]; } else { - entry = packed; - packed = packed->next; + entry = packed->refs[p++]; } retval = do_one_ref(base, fn, trim, flags, cb_data, entry); if (retval) goto end_each; } - for (packed = packed ? packed : loose; packed; packed = packed->next) { - retval = do_one_ref(base, fn, trim, flags, cb_data, packed); + if (l < loose->nr) { + p = l; + packed = loose; + } + + for (; p < packed->nr; p++) { + retval = do_one_ref(base, fn, trim, flags, cb_data, packed->refs[p]); if (retval) goto end_each; } @@ -1045,24 +1056,24 @@ static int remove_empty_directories(const char *file) } static int is_refname_available(const char *ref, const char *oldref, - struct ref_list *list, int quiet) -{ - int namlen = strlen(ref); /* e.g. 'foo/bar' */ - while (list) { - /* list->name could be 'foo' or 'foo/bar/baz' */ - if (!oldref || strcmp(oldref, list->name)) { - int len = strlen(list->name); + struct ref_array *array, int quiet) +{ + int i, namlen = strlen(ref); /* e.g. 'foo/bar' */ + for (i = 0; i < array->nr; i++ ) { + struct ref_entry *entry = array->refs[i]; + /* entry->name could be 'foo' or 'foo/bar/baz' */ + if (!oldref || strcmp(oldref, entry->name)) { + int len = strlen(entry->name); int cmplen = (namlen < len) ? namlen : len; - const char *lead = (namlen < len) ? list->name : ref; - if (!strncmp(ref, list->name, cmplen) && + const char *lead = (namlen < len) ? entry->name : ref; + if (!strncmp(ref, entry->name, cmplen) && lead[cmplen] == '/') { if (!quiet) error("'%s' exists; cannot create '%s'", - list->name, ref); + entry->name, ref); return 0; } } - list = list->next; } return 1; } @@ -1253,18 +1264,13 @@ static struct lock_file packlock; static int repack_without_ref(const char *refname) { - struct ref_list *list, *packed_ref_list; - int fd; - int found = 0; + struct ref_array *packed; + struct ref_entry *ref; + int fd, i; - packed_ref_list = get_packed_refs(NULL); - for (list = packed_ref_list; list; list = list->next) { - if (!strcmp(refname, list->name)) { - found = 1; - break; - } - } - if (!found) + packed = get_packed_refs(NULL); + ref = search_ref_array(packed, refname); + if (ref == NULL) return 0; fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0); if (fd < 0) { @@ -1272,17 +1278,19 @@ static int repack_without_ref(const char *refname) return error("cannot delete '%s' from packed refs", refname); } - for (list = packed_ref_list; list; list = list->next) { + for (i = 0; i < packed->nr; i++) { char line[PATH_MAX + 100]; int len; - if (!strcmp(refname, list->name)) + ref = packed->refs[i]; + + if (!strcmp(refname, ref->name)) continue; len = snprintf(line, sizeof(line), "%s %s\n", - sha1_to_hex(list->sha1), list->name); + sha1_to_hex(ref->sha1), ref->name); /* this should not happen but just being defensive */ if (len > sizeof(line)) - die("too long a refname '%s'", list->name); + die("too long a refname '%s'", ref->name); write_or_die(fd, line, len); } return commit_lock_file(&packlock); @@ -1321,7 +1329,7 @@ int delete_ref(const char *refname, const unsigned char *sha1, int delopt) ret |= repack_without_ref(refname); unlink_or_warn(git_path("logs/%s", lock->ref_name)); - invalidate_cached_refs(); + invalidate_ref_cache(NULL); unlock_ref(lock); return ret; } @@ -1337,7 +1345,6 @@ int delete_ref(const char *refname, const unsigned char *sha1, int delopt) int rename_ref(const char *oldref, const char *newref, const char *logmsg) { - static const char renamed_ref[] = "RENAMED-REF"; unsigned char sha1[20], orig_sha1[20]; int flag = 0, logmoved = 0; struct ref_lock *lock; @@ -1361,13 +1368,6 @@ int rename_ref(const char *oldref, const char *newref, const char *logmsg) if (!is_refname_available(newref, oldref, get_loose_refs(NULL), 0)) return 1; - lock = lock_ref_sha1_basic(renamed_ref, NULL, 0, NULL); - if (!lock) - return error("unable to lock %s", renamed_ref); - lock->force_write = 1; - if (write_ref_sha1(lock, orig_sha1, logmsg)) - return error("unable to save current sha1 in %s", renamed_ref); - if (log && rename(git_path("logs/%s", oldref), git_path(TMP_RENAMED_LOG))) return error("unable to move logfile logs/%s to "TMP_RENAMED_LOG": %s", oldref, strerror(errno)); @@ -1620,7 +1620,7 @@ int write_ref_sha1(struct ref_lock *lock, unlock_ref(lock); return -1; } - invalidate_cached_refs(); + clear_loose_ref_cache(get_ref_cache(NULL)); if (log_ref_write(lock->ref_name, lock->old_sha1, sha1, logmsg) < 0 || (strcmp(lock->ref_name, lock->orig_ref_name) && log_ref_write(lock->orig_ref_name, lock->old_sha1, sha1, logmsg) < 0)) { @@ -1977,7 +1977,7 @@ int update_ref(const char *action, const char *refname, return 0; } -int ref_exists(char *refname) +int ref_exists(const char *refname) { unsigned char sha1[20]; return !!resolve_ref(refname, sha1, 1, NULL);