]> rtime.felk.cvut.cz Git - git.git/commitdiff
Merge branch 'kb/fast-hashmap'
authorJunio C Hamano <gitster@pobox.com>
Thu, 27 Feb 2014 22:01:09 +0000 (14:01 -0800)
committerJunio C Hamano <gitster@pobox.com>
Thu, 27 Feb 2014 22:01:09 +0000 (14:01 -0800)
Improvements to our hash table to get it to meet the needs of the
msysgit fscache project, with some nice performance improvements.

* kb/fast-hashmap:
  name-hash: retire unused index_name_exists()
  hashmap.h: use 'unsigned int' for hash-codes everywhere
  test-hashmap.c: drop unnecessary #includes
  .gitignore: test-hashmap is a generated file
  read-cache.c: fix memory leaks caused by removed cache entries
  builtin/update-index.c: cleanup update_one
  fix 'git update-index --verbose --again' output
  remove old hash.[ch] implementation
  name-hash.c: remove cache entries instead of marking them CE_UNHASHED
  name-hash.c: use new hash map implementation for cache entries
  name-hash.c: remove unreferenced directory entries
  name-hash.c: use new hash map implementation for directories
  diffcore-rename.c: use new hash map implementation
  diffcore-rename.c: simplify finding exact renames
  diffcore-rename.c: move code around to prepare for the next patch
  buitin/describe.c: use new hash map implementation
  add a hashtable implementation that supports O(1) removal
  submodule: don't access the .gitmodules cache entry after removing it

1  2 
.gitignore
Makefile
builtin/describe.c
cache.h
submodule.c
unpack-trees.c

diff --combined .gitignore
index b5f9defed37c43b2c6075d7065c8cbae2b1797e1,cb1db5492c2f23f43b28d56dbc46a59eae083af0..dc600f9b36d09f0668064e044520c7ce633f09d8
@@@ -2,7 -2,6 +2,7 @@@
  /GIT-CFLAGS
  /GIT-LDFLAGS
  /GIT-PREFIX
 +/GIT-PERL-DEFINES
  /GIT-PYTHON-VARS
  /GIT-SCRIPT-DEFINES
  /GIT-USER-AGENT
@@@ -76,6 -75,7 +76,6 @@@
  /git-init-db
  /git-instaweb
  /git-log
 -/git-lost-found
  /git-ls-files
  /git-ls-remote
  /git-ls-tree
  /git-pack-refs
  /git-parse-remote
  /git-patch-id
 -/git-peek-remote
  /git-prune
  /git-prune-packed
  /git-pull
  /git-remote-testsvn
  /git-repack
  /git-replace
 -/git-repo-config
  /git-request-pull
  /git-rerere
  /git-reset
  /git-svn
  /git-symbolic-ref
  /git-tag
 -/git-tar-tree
  /git-unpack-file
  /git-unpack-objects
  /git-update-index
  /test-dump-cache-tree
  /test-scrap-cache-tree
  /test-genrandom
+ /test-hashmap
  /test-index-version
  /test-line-buffer
  /test-match-trees
diff --combined Makefile
index dddaf4f287cf5cd5e99ad2587d53ba7582c51e29,f495dd4c13b9ea9e66b70e0fa25737f8f39e35fe..c3213bd54b453ff5b96bc4bec184e4d878312185
+++ b/Makefile
@@@ -452,6 -452,7 +452,6 @@@ SCRIPT_SH += git-am.s
  SCRIPT_SH += git-bisect.sh
  SCRIPT_SH += git-difftool--helper.sh
  SCRIPT_SH += git-filter-branch.sh
 -SCRIPT_SH += git-lost-found.sh
  SCRIPT_SH += git-merge-octopus.sh
  SCRIPT_SH += git-merge-one-file.sh
  SCRIPT_SH += git-merge-resolve.sh
@@@ -460,6 -461,7 +460,6 @@@ SCRIPT_SH += git-pull.s
  SCRIPT_SH += git-quiltimport.sh
  SCRIPT_SH += git-rebase.sh
  SCRIPT_SH += git-remote-testgit.sh
 -SCRIPT_SH += git-repack.sh
  SCRIPT_SH += git-request-pull.sh
  SCRIPT_SH += git-stash.sh
  SCRIPT_SH += git-submodule.sh
@@@ -555,6 -557,7 +555,7 @@@ TEST_PROGRAMS_NEED_X += test-dat
  TEST_PROGRAMS_NEED_X += test-delta
  TEST_PROGRAMS_NEED_X += test-dump-cache-tree
  TEST_PROGRAMS_NEED_X += test-genrandom
+ TEST_PROGRAMS_NEED_X += test-hashmap
  TEST_PROGRAMS_NEED_X += test-index-version
  TEST_PROGRAMS_NEED_X += test-line-buffer
  TEST_PROGRAMS_NEED_X += test-match-trees
@@@ -586,8 -589,11 +587,8 @@@ BUILT_INS += git-cherry$
  BUILT_INS += git-cherry-pick$X
  BUILT_INS += git-format-patch$X
  BUILT_INS += git-fsck-objects$X
 -BUILT_INS += git-get-tar-commit-id$X
  BUILT_INS += git-init$X
  BUILT_INS += git-merge-subtree$X
 -BUILT_INS += git-peek-remote$X
 -BUILT_INS += git-repo-config$X
  BUILT_INS += git-show$X
  BUILT_INS += git-stage$X
  BUILT_INS += git-status$X
@@@ -671,7 -677,7 +672,7 @@@ LIB_H += git-compat-util.
  LIB_H += gpg-interface.h
  LIB_H += graph.h
  LIB_H += grep.h
- LIB_H += hash.h
+ LIB_H += hashmap.h
  LIB_H += help.h
  LIB_H += http.h
  LIB_H += kwset.h
@@@ -802,7 -808,7 +803,7 @@@ LIB_OBJS += gettext.
  LIB_OBJS += gpg-interface.o
  LIB_OBJS += graph.o
  LIB_OBJS += grep.o
- LIB_OBJS += hash.o
+ LIB_OBJS += hashmap.o
  LIB_OBJS += help.o
  LIB_OBJS += hex.o
  LIB_OBJS += ident.o
@@@ -928,7 -934,6 +929,7 @@@ BUILTIN_OBJS += builtin/fmt-merge-msg.
  BUILTIN_OBJS += builtin/for-each-ref.o
  BUILTIN_OBJS += builtin/fsck.o
  BUILTIN_OBJS += builtin/gc.o
 +BUILTIN_OBJS += builtin/get-tar-commit-id.o
  BUILTIN_OBJS += builtin/grep.o
  BUILTIN_OBJS += builtin/hash-object.o
  BUILTIN_OBJS += builtin/help.o
@@@ -965,7 -970,6 +966,7 @@@ BUILTIN_OBJS += builtin/reflog.
  BUILTIN_OBJS += builtin/remote.o
  BUILTIN_OBJS += builtin/remote-ext.o
  BUILTIN_OBJS += builtin/remote-fd.o
 +BUILTIN_OBJS += builtin/repack.o
  BUILTIN_OBJS += builtin/replace.o
  BUILTIN_OBJS += builtin/rerere.o
  BUILTIN_OBJS += builtin/reset.o
@@@ -980,6 -984,7 +981,6 @@@ BUILTIN_OBJS += builtin/show-ref.
  BUILTIN_OBJS += builtin/stripspace.o
  BUILTIN_OBJS += builtin/symbolic-ref.o
  BUILTIN_OBJS += builtin/tag.o
 -BUILTIN_OBJS += builtin/tar-tree.o
  BUILTIN_OBJS += builtin/unpack-file.o
  BUILTIN_OBJS += builtin/unpack-objects.o
  BUILTIN_OBJS += builtin/update-index.o
@@@ -1584,7 -1589,6 +1585,7 @@@ PERL_PATH_SQ = $(subst ','\'',$(PERL_PA
  PYTHON_PATH_SQ = $(subst ','\'',$(PYTHON_PATH))
  TCLTK_PATH_SQ = $(subst ','\'',$(TCLTK_PATH))
  DIFF_SQ = $(subst ','\'',$(DIFF))
 +PERLLIB_EXTRA_SQ = $(subst ','\'',$(PERLLIB_EXTRA))
  
  LIBS = $(GITLIBS) $(EXTLIBS)
  
@@@ -1773,7 -1777,7 +1774,7 @@@ $(SCRIPT_LIB) : % : %.sh GIT-SCRIPT-DEF
  
  git.res: git.rc GIT-VERSION-FILE
        $(QUIET_RC)$(RC) \
 -        $(join -DMAJOR= -DMINOR= -DPATCH=, $(wordlist 1,3,$(subst -, ,$(subst ., ,$(GIT_VERSION))))) \
 +        $(join -DMAJOR= -DMINOR=, $(wordlist 1,2,$(subst -, ,$(subst ., ,$(GIT_VERSION))))) \
          -DGIT_VERSION="\\\"$(GIT_VERSION)\\\"" $< -o $@
  
  ifndef NO_PERL
@@@ -1789,12 -1793,9 +1790,12 @@@ perl/PM.stamp: FORC
  perl/perl.mak: GIT-CFLAGS GIT-PREFIX perl/Makefile perl/Makefile.PL
        $(QUIET_SUBDIR0)perl $(QUIET_SUBDIR1) PERL_PATH='$(PERL_PATH_SQ)' prefix='$(prefix_SQ)' $(@F)
  
 -$(patsubst %.perl,%,$(SCRIPT_PERL)): % : %.perl GIT-VERSION-FILE
 +PERL_DEFINES = $(PERL_PATH_SQ):$(PERLLIB_EXTRA_SQ)
 +$(patsubst %.perl,%,$(SCRIPT_PERL)): % : %.perl perl/perl.mak GIT-PERL-DEFINES GIT-VERSION-FILE
        $(QUIET_GEN)$(RM) $@ $@+ && \
        INSTLIBDIR=`MAKEFLAGS= $(MAKE) -C perl -s --no-print-directory instlibdir` && \
 +      INSTLIBDIR_EXTRA='$(PERLLIB_EXTRA_SQ)' && \
 +      INSTLIBDIR="$$INSTLIBDIR$${INSTLIBDIR_EXTRA:+:$$INSTLIBDIR_EXTRA}" && \
        sed -e '1{' \
            -e '        s|#!.*perl|#!$(PERL_PATH_SQ)|' \
            -e '        h' \
        chmod +x $@+ && \
        mv $@+ $@
  
 +GIT-PERL-DEFINES: FORCE
 +      @FLAGS='$(PERL_DEFINES)'; \
 +          if test x"$$FLAGS" != x"`cat $@ 2>/dev/null`" ; then \
 +              echo >&2 "    * new perl-specific parameters"; \
 +              echo "$$FLAGS" >$@; \
 +          fi
 +
  
  .PHONY: gitweb
  gitweb:
@@@ -2050,10 -2044,10 +2051,10 @@@ git-imap-send$X: imap-send.o GIT-LDFLAG
        $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
                $(LIBS) $(OPENSSL_LINK) $(OPENSSL_LIBSSL) $(LIB_4_CRYPTO)
  
 -git-http-fetch$X: revision.o http.o http-walker.o http-fetch.o GIT-LDFLAGS $(GITLIBS)
 +git-http-fetch$X: http.o http-walker.o http-fetch.o GIT-LDFLAGS $(GITLIBS)
        $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
                $(LIBS) $(CURL_LIBCURL)
 -git-http-push$X: revision.o http.o http-push.o GIT-LDFLAGS $(GITLIBS)
 +git-http-push$X: http.o http-push.o GIT-LDFLAGS $(GITLIBS)
        $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
                $(LIBS) $(CURL_LIBCURL) $(EXPAT_LIBEXPAT)
  
@@@ -2501,8 -2495,7 +2502,8 @@@ ifndef NO_TCLT
        $(MAKE) -C git-gui clean
  endif
        $(RM) GIT-VERSION-FILE GIT-CFLAGS GIT-LDFLAGS GIT-BUILD-OPTIONS
 -      $(RM) GIT-USER-AGENT GIT-PREFIX GIT-SCRIPT-DEFINES GIT-PYTHON-VARS
 +      $(RM) GIT-USER-AGENT GIT-PREFIX
 +      $(RM) GIT-SCRIPT-DEFINES GIT-PERL-DEFINES GIT-PYTHON-VARS
  
  .PHONY: all install profile-clean clean strip
  .PHONY: shell_compatibility_test please_set_SHELL_PATH_to_a_more_modern_shell
diff --combined builtin/describe.c
index 7db43dae1be95e86c21249d9150fc8553c367527,104202898e42f8c59cdd15a6433c4bef187d8493..dadd999c41f6aebe488d057e94e239dfb7dffaec
@@@ -6,10 -6,10 +6,10 @@@
  #include "exec_cmd.h"
  #include "parse-options.h"
  #include "diff.h"
- #include "hash.h"
+ #include "hashmap.h"
  #include "argv-array.h"
  
 -#define SEEN          (1u<<0)
 +#define SEEN          (1u << 0)
  #define MAX_TAGS      (FLAG_BITS - 1)
  
  static const char * const describe_usage[] = {
@@@ -25,7 -25,7 +25,7 @@@ static int longformat
  static int first_parent;
  static int abbrev = -1; /* unspecified */
  static int max_candidates = 10;
- static struct hash_table names;
+ static struct hashmap names;
  static int have_util;
  static const char *pattern;
  static int always;
@@@ -36,8 -36,9 +36,8 @@@ static const char *diff_index_args[] = 
        "diff-index", "--quiet", "HEAD", "--", NULL
  };
  
 -
  struct commit_name {
-       struct commit_name *next;
+       struct hashmap_entry entry;
        unsigned char peeled[20];
        struct tag *tag;
        unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */
        unsigned char sha1[20];
        char *path;
  };
 +
  static const char *prio_names[] = {
        "head", "lightweight", "annotated",
  };
  
+ static int commit_name_cmp(const struct commit_name *cn1,
+               const struct commit_name *cn2, const void *peeled)
+ {
+       return hashcmp(cn1->peeled, peeled ? peeled : cn2->peeled);
+ }
  static inline unsigned int hash_sha1(const unsigned char *sha1)
  {
        unsigned int hash;
  
  static inline struct commit_name *find_commit_name(const unsigned char *peeled)
  {
-       struct commit_name *n = lookup_hash(hash_sha1(peeled), &names);
-       while (n && !!hashcmp(peeled, n->peeled))
-               n = n->next;
-       return n;
- }
- static int set_util(void *chain, void *data)
- {
-       struct commit_name *n;
-       for (n = chain; n; n = n->next) {
-               struct commit *c = lookup_commit_reference_gently(n->peeled, 1);
-               if (c)
-                       c->util = n;
-       }
-       return 0;
+       struct commit_name key;
+       hashmap_entry_init(&key, hash_sha1(peeled));
+       return hashmap_get(&names, &key, peeled);
  }
  
  static int replace_name(struct commit_name *e,
@@@ -118,16 -112,10 +112,10 @@@ static void add_to_known_names(const ch
        struct tag *tag = NULL;
        if (replace_name(e, prio, sha1, &tag)) {
                if (!e) {
-                       void **pos;
                        e = xmalloc(sizeof(struct commit_name));
                        hashcpy(e->peeled, peeled);
-                       pos = insert_hash(hash_sha1(peeled), e, &names);
-                       if (pos) {
-                               e->next = *pos;
-                               *pos = e;
-                       } else {
-                               e->next = NULL;
-                       }
+                       hashmap_entry_init(e, hash_sha1(peeled));
+                       hashmap_add(&names, e);
                        e->path = NULL;
                }
                e->tag = tag;
  
  static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)
  {
 -      int is_tag = !prefixcmp(path, "refs/tags/");
 +      int is_tag = starts_with(path, "refs/tags/");
        unsigned char peeled[20];
        int is_annotated, prio;
  
@@@ -292,7 -280,14 +280,14 @@@ static void describe(const char *arg, i
                fprintf(stderr, _("searching to describe %s\n"), arg);
  
        if (!have_util) {
-               for_each_hash(&names, set_util, NULL);
+               struct hashmap_iter iter;
+               struct commit *c;
+               struct commit_name *n = hashmap_iter_first(&names, &iter);
+               for (; n; n = hashmap_iter_next(&iter)) {
+                       c = lookup_commit_reference_gently(n->peeled, 1);
+                       if (c)
+                               c->util = n;
+               }
                have_util = 1;
        }
  
@@@ -463,9 -458,9 +458,9 @@@ int cmd_describe(int argc, const char *
                return cmd_name_rev(args.argc, args.argv, prefix);
        }
  
-       init_hash(&names);
+       hashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);
        for_each_rawref(get_name, NULL);
-       if (!names.nr && !always)
+       if (!names.size && !always)
                die(_("No names found, cannot describe anything."));
  
        if (argc == 0) {
        } else if (dirty) {
                die(_("--dirty is incompatible with commit-ishes"));
        } else {
 -              while (argc-- > 0) {
 +              while (argc-- > 0)
                        describe(*argv++, argc == 0);
 -              }
        }
        return 0;
  }
diff --combined cache.h
index dc040fb1aa99b7970e85e5b175e60f862ff6a74a,353c687c19413589a95484bf7458500dc43968a5..21251598d017aa36e69d9c570216bc19cb980b51
+++ b/cache.h
@@@ -3,7 -3,7 +3,7 @@@
  
  #include "git-compat-util.h"
  #include "strbuf.h"
- #include "hash.h"
+ #include "hashmap.h"
  #include "advice.h"
  #include "gettext.h"
  #include "convert.h"
@@@ -130,12 -130,12 +130,12 @@@ struct stat_data 
  };
  
  struct cache_entry {
+       struct hashmap_entry ent;
        struct stat_data ce_stat_data;
        unsigned int ce_mode;
        unsigned int ce_flags;
        unsigned int ce_namelen;
        unsigned char sha1[20];
-       struct cache_entry *next;
        char name[FLEX_ARRAY]; /* more */
  };
  
  #define CE_ADDED             (1 << 19)
  
  #define CE_HASHED            (1 << 20)
- #define CE_UNHASHED          (1 << 21)
  #define CE_WT_REMOVE         (1 << 22) /* remove in work directory */
  #define CE_CONFLICTED        (1 << 23)
  
@@@ -195,17 -194,18 +194,18 @@@ struct pathspec
   * Copy the sha1 and stat state of a cache entry from one to
   * another. But we never change the name, or the hash state!
   */
- #define CE_STATE_MASK (CE_HASHED | CE_UNHASHED)
  static inline void copy_cache_entry(struct cache_entry *dst,
                                    const struct cache_entry *src)
  {
-       unsigned int state = dst->ce_flags & CE_STATE_MASK;
+       unsigned int state = dst->ce_flags & CE_HASHED;
  
        /* Don't copy hash chain and name */
-       memcpy(dst, src, offsetof(struct cache_entry, next));
+       memcpy(&dst->ce_stat_data, &src->ce_stat_data,
+                       offsetof(struct cache_entry, name) -
+                       offsetof(struct cache_entry, ce_stat_data));
  
        /* Restore the hash state */
-       dst->ce_flags = (dst->ce_flags & ~CE_STATE_MASK) | state;
+       dst->ce_flags = (dst->ce_flags & ~CE_HASHED) | state;
  }
  
  static inline unsigned create_ce_flags(unsigned stage)
@@@ -277,8 -277,8 +277,8 @@@ struct index_state 
        struct cache_time timestamp;
        unsigned name_hash_initialized : 1,
                 initialized : 1;
-       struct hash_table name_hash;
-       struct hash_table dir_hash;
+       struct hashmap name_hash;
+       struct hashmap dir_hash;
  };
  
  extern struct index_state the_index;
@@@ -316,7 -316,6 +316,6 @@@ extern void free_name_hash(struct index
  #define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options))
  #define cache_dir_exists(name, namelen) index_dir_exists(&the_index, (name), (namelen))
  #define cache_file_exists(name, namelen, igncase) index_file_exists(&the_index, (name), (namelen), (igncase))
- #define cache_name_exists(name, namelen, igncase) index_name_exists(&the_index, (name), (namelen), (igncase))
  #define cache_name_is_other(name, namelen) index_name_is_other(&the_index, (name), (namelen))
  #define resolve_undo_clear() resolve_undo_clear_index(&the_index)
  #define unmerge_cache_entry_at(at) unmerge_index_entry_at(&the_index, at)
@@@ -354,7 -353,6 +353,7 @@@ static inline enum object_type object_t
  #define DB_ENVIRONMENT "GIT_OBJECT_DIRECTORY"
  #define INDEX_ENVIRONMENT "GIT_INDEX_FILE"
  #define GRAFT_ENVIRONMENT "GIT_GRAFT_FILE"
 +#define GIT_SHALLOW_FILE_ENVIRONMENT "GIT_SHALLOW_FILE"
  #define TEMPLATE_DIR_ENVIRONMENT "GIT_TEMPLATE_DIR"
  #define CONFIG_ENVIRONMENT "GIT_CONFIG"
  #define CONFIG_DATA_ENVIRONMENT "GIT_CONFIG_PARAMETERS"
@@@ -399,6 -397,7 +398,6 @@@ extern int is_bare_repository(void)
  extern int is_inside_git_dir(void);
  extern char *git_work_tree_cfg;
  extern int is_inside_work_tree(void);
 -extern int have_git_dir(void);
  extern const char *get_git_dir(void);
  extern int is_git_directory(const char *path);
  extern char *get_object_directory(void);
@@@ -467,7 -466,6 +466,6 @@@ extern int unmerged_index(const struct 
  extern int verify_path(const char *path);
  extern struct cache_entry *index_dir_exists(struct index_state *istate, const char *name, int namelen);
  extern struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int igncase);
- extern struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int igncase);
  extern int index_name_pos(const struct index_state *, const char *name, int namelen);
  #define ADD_CACHE_OK_TO_ADD 1         /* Ok to add */
  #define ADD_CACHE_OK_TO_REPLACE 2     /* Ok to replace file/directory */
@@@ -737,29 -735,8 +735,29 @@@ enum sharedrepo 
  };
  int git_config_perm(const char *var, const char *value);
  int adjust_shared_perm(const char *path);
 -int safe_create_leading_directories(char *path);
 -int safe_create_leading_directories_const(const char *path);
 +
 +/*
 + * Create the directory containing the named path, using care to be
 + * somewhat safe against races.  Return one of the scld_error values
 + * to indicate success/failure.
 + *
 + * SCLD_VANISHED indicates that one of the ancestor directories of the
 + * path existed at one point during the function call and then
 + * suddenly vanished, probably because another process pruned the
 + * directory while we were working.  To be robust against this kind of
 + * race, callers might want to try invoking the function again when it
 + * returns SCLD_VANISHED.
 + */
 +enum scld_error {
 +      SCLD_OK = 0,
 +      SCLD_FAILED = -1,
 +      SCLD_PERMS = -2,
 +      SCLD_EXISTS = -3,
 +      SCLD_VANISHED = -4
 +};
 +enum scld_error safe_create_leading_directories(char *path);
 +enum scld_error safe_create_leading_directories_const(const char *path);
 +
  int mkdir_in_gitdir(const char *path);
  extern void home_config_paths(char **global, char **xdg, char *file);
  extern char *expand_user_path(const char *path);
@@@ -772,7 -749,6 +770,7 @@@ int is_directory(const char *)
  const char *real_path(const char *path);
  const char *real_path_if_valid(const char *path);
  const char *absolute_path(const char *path);
 +const char *remove_leading_path(const char *in, const char *prefix);
  const char *relative_path(const char *in, const char *prefix, struct strbuf *sb);
  int normalize_path_copy_len(char *dst, const char *src, int *prefix_len);
  int normalize_path_copy(char *dst, const char *src);
@@@ -782,11 -758,11 +780,11 @@@ int daemon_avoid_alias(const char *path
  int offset_1st_component(const char *path);
  
  /* object replacement */
 -#define READ_SHA1_FILE_REPLACE 1
 +#define LOOKUP_REPLACE_OBJECT 1
  extern void *read_sha1_file_extended(const unsigned char *sha1, enum object_type *type, unsigned long *size, unsigned flag);
  static inline void *read_sha1_file(const unsigned char *sha1, enum object_type *type, unsigned long *size)
  {
 -      return read_sha1_file_extended(sha1, type, size, READ_SHA1_FILE_REPLACE);
 +      return read_sha1_file_extended(sha1, type, size, LOOKUP_REPLACE_OBJECT);
  }
  extern const unsigned char *do_lookup_replace_object(const unsigned char *sha1);
  static inline const unsigned char *lookup_replace_object(const unsigned char *sha1)
                return sha1;
        return do_lookup_replace_object(sha1);
  }
 +static inline const unsigned char *lookup_replace_object_extended(const unsigned char *sha1, unsigned flag)
 +{
 +      if (!(flag & LOOKUP_REPLACE_OBJECT))
 +              return sha1;
 +      return lookup_replace_object(sha1);
 +}
  
  /* Read and unpack a sha1 file into memory, write memory to a sha1 file */
  extern int sha1_object_info(const unsigned char *, unsigned long *);
@@@ -915,12 -885,9 +913,12 @@@ extern int dwim_log(const char *str, in
  extern int interpret_branch_name(const char *str, int len, struct strbuf *);
  extern int get_sha1_mb(const char *str, unsigned char *sha1);
  
 -extern int refname_match(const char *abbrev_name, const char *full_name, const char **rules);
 -extern const char *ref_rev_parse_rules[];
 -#define ref_fetch_rules ref_rev_parse_rules
 +/*
 + * Return true iff abbrev_name is a possible abbreviation for
 + * full_name according to the rules defined by ref_rev_parse_rules in
 + * refs.c.
 + */
 +extern int refname_match(const char *abbrev_name, const char *full_name);
  
  extern int create_symref(const char *ref, const char *refs_heads_master, const char *logmsg);
  extern int validate_headref(const char *ref);
@@@ -1006,7 -973,6 +1004,7 @@@ struct checkout 
                 refresh_cache:1;
  };
  
 +#define TEMPORARY_FILENAME_LENGTH 25
  extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);
  
  struct cache_def {
@@@ -1105,7 -1071,6 +1103,7 @@@ struct object_info 
        enum object_type *typep;
        unsigned long *sizep;
        unsigned long *disk_sizep;
 +      unsigned char *delta_base_sha1;
  
        /* Response */
        enum {
                } packed;
        } u;
  };
 -extern int sha1_object_info_extended(const unsigned char *, struct object_info *);
 +extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);
  
  /* Dumb servers support */
  extern int update_server_info(int);
@@@ -1268,8 -1233,6 +1266,8 @@@ __attribute__((format (printf, 2, 3))
  extern void trace_argv_printf(const char **argv, const char *format, ...);
  extern void trace_repo_setup(const char *prefix);
  extern int trace_want(const char *key);
 +__attribute__((format (printf, 2, 3)))
 +extern void trace_printf_key(const char *key, const char *fmt, ...);
  extern void trace_strbuf(const char *key, const struct strbuf *buf);
  
  void packet_trace_identity(const char *prog);
diff --combined submodule.c
index 613857e400f826f3d4ea28c87025b2c2df42408a,e3884877f20129a94e664492d25e6f9dd7291b56..b80ecacf60dc87025336b6b6d6a51acc9321f429
@@@ -116,30 -116,7 +116,7 @@@ int remove_path_from_gitmodules(const c
  
  void stage_updated_gitmodules(void)
  {
-       struct strbuf buf = STRBUF_INIT;
-       struct stat st;
-       int pos;
-       struct cache_entry *ce;
-       int namelen = strlen(".gitmodules");
-       pos = cache_name_pos(".gitmodules", namelen);
-       if (pos < 0) {
-               warning(_("could not find .gitmodules in index"));
-               return;
-       }
-       ce = active_cache[pos];
-       ce->ce_flags = namelen;
-       if (strbuf_read_file(&buf, ".gitmodules", 0) < 0)
-               die(_("reading updated .gitmodules failed"));
-       if (lstat(".gitmodules", &st) < 0)
-               die_errno(_("unable to stat updated .gitmodules"));
-       fill_stat_cache_info(ce, &st);
-       ce->ce_mode = ce_mode_from_stat(ce, st.st_mode);
-       if (remove_cache_entry_at(pos) < 0)
-               die(_("unable to remove .gitmodules from index"));
-       if (write_sha1_file(buf.buf, buf.len, blob_type, ce->sha1))
-               die(_("adding updated .gitmodules failed"));
-       if (add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE))
+       if (add_file_to_cache(".gitmodules", 0))
                die(_("staging updated .gitmodules failed"));
  }
  
@@@ -201,7 -178,7 +178,7 @@@ void set_diffopt_flags_from_submodule_c
  
  int submodule_config(const char *var, const char *value, void *cb)
  {
 -      if (!prefixcmp(var, "submodule."))
 +      if (starts_with(var, "submodule."))
                return parse_submodule_config_option(var, value);
        else if (!strcmp(var, "fetch.recursesubmodules")) {
                config_fetch_recurse_submodules = parse_fetch_recurse_submodules_arg(var, value);
diff --combined unpack-trees.c
index 164354dad7cbbaa7100f73256807680a75188021,36f3a7d06c73ecee27f4a5c0058b428023c086ad..0692ebe16e62fa4b31a20ec9c28cabb041236709
@@@ -105,12 -105,11 +105,11 @@@ void setup_unpack_trees_porcelain(struc
  static void do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
                         unsigned int set, unsigned int clear)
  {
-       clear |= CE_HASHED | CE_UNHASHED;
+       clear |= CE_HASHED;
  
        if (set & CE_REMOVE)
                set |= CE_WT_REMOVE;
  
-       ce->next = NULL;
        ce->ce_flags = (ce->ce_flags & ~clear) | set;
        add_index_entry(&o->result, ce,
                        ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
@@@ -830,24 -829,23 +829,24 @@@ static int unpack_callback(int n, unsig
  }
  
  static int clear_ce_flags_1(struct cache_entry **cache, int nr,
 -                          char *prefix, int prefix_len,
 +                          struct strbuf *prefix,
                            int select_mask, int clear_mask,
                            struct exclude_list *el, int defval);
  
  /* Whole directory matching */
  static int clear_ce_flags_dir(struct cache_entry **cache, int nr,
 -                            char *prefix, int prefix_len,
 +                            struct strbuf *prefix,
                              char *basename,
                              int select_mask, int clear_mask,
                              struct exclude_list *el, int defval)
  {
        struct cache_entry **cache_end;
        int dtype = DT_DIR;
 -      int ret = is_excluded_from_list(prefix, prefix_len,
 +      int ret = is_excluded_from_list(prefix->buf, prefix->len,
                                        basename, &dtype, el);
 +      int rc;
  
 -      prefix[prefix_len++] = '/';
 +      strbuf_addch(prefix, '/');
  
        /* If undecided, use matching result of parent dir in defval */
        if (ret < 0)
  
        for (cache_end = cache; cache_end != cache + nr; cache_end++) {
                struct cache_entry *ce = *cache_end;
 -              if (strncmp(ce->name, prefix, prefix_len))
 +              if (strncmp(ce->name, prefix->buf, prefix->len))
                        break;
        }
  
         * calling clear_ce_flags_1(). That function will call
         * the expensive is_excluded_from_list() on every entry.
         */
 -      return clear_ce_flags_1(cache, cache_end - cache,
 -                              prefix, prefix_len,
 -                              select_mask, clear_mask,
 -                              el, ret);
 +      rc = clear_ce_flags_1(cache, cache_end - cache,
 +                            prefix,
 +                            select_mask, clear_mask,
 +                            el, ret);
 +      strbuf_setlen(prefix, prefix->len - 1);
 +      return rc;
  }
  
  /*
   * Top level path has prefix_len zero.
   */
  static int clear_ce_flags_1(struct cache_entry **cache, int nr,
 -                          char *prefix, int prefix_len,
 +                          struct strbuf *prefix,
                            int select_mask, int clear_mask,
                            struct exclude_list *el, int defval)
  {
                        continue;
                }
  
 -              if (prefix_len && strncmp(ce->name, prefix, prefix_len))
 +              if (prefix->len && strncmp(ce->name, prefix->buf, prefix->len))
                        break;
  
 -              name = ce->name + prefix_len;
 +              name = ce->name + prefix->len;
                slash = strchr(name, '/');
  
                /* If it's a directory, try whole directory match first */
                        int processed;
  
                        len = slash - name;
 -                      memcpy(prefix + prefix_len, name, len);
 +                      strbuf_add(prefix, name, len);
  
 -                      /*
 -                       * terminate the string (no trailing slash),
 -                       * clear_c_f_dir needs it
 -                       */
 -                      prefix[prefix_len + len] = '\0';
                        processed = clear_ce_flags_dir(cache, cache_end - cache,
 -                                                     prefix, prefix_len + len,
 -                                                     prefix + prefix_len,
 +                                                     prefix,
 +                                                     prefix->buf + prefix->len - len,
                                                       select_mask, clear_mask,
                                                       el, defval);
  
                        /* clear_c_f_dir eats a whole dir already? */
                        if (processed) {
                                cache += processed;
 +                              strbuf_setlen(prefix, prefix->len - len);
                                continue;
                        }
  
 -                      prefix[prefix_len + len++] = '/';
 +                      strbuf_addch(prefix, '/');
                        cache += clear_ce_flags_1(cache, cache_end - cache,
 -                                                prefix, prefix_len + len,
 +                                                prefix,
                                                  select_mask, clear_mask, el, defval);
 +                      strbuf_setlen(prefix, prefix->len - len - 1);
                        continue;
                }
  
@@@ -961,12 -960,9 +960,12 @@@ static int clear_ce_flags(struct cache_
                            int select_mask, int clear_mask,
                            struct exclude_list *el)
  {
 -      char prefix[PATH_MAX];
 +      static struct strbuf prefix = STRBUF_INIT;
 +
 +      strbuf_reset(&prefix);
 +
        return clear_ce_flags_1(cache, nr,
 -                              prefix, 0,
 +                              &prefix,
                                select_mask, clear_mask,
                                el, 0);
  }
@@@ -1766,23 -1762,14 +1765,23 @@@ int twoway_merge(const struct cache_ent
                newtree = NULL;
  
        if (current) {
 -              if ((!oldtree && !newtree) || /* 4 and 5 */
 -                  (!oldtree && newtree &&
 -                   same(current, newtree)) || /* 6 and 7 */
 -                  (oldtree && newtree &&
 -                   same(oldtree, newtree)) || /* 14 and 15 */
 -                  (oldtree && newtree &&
 -                   !same(oldtree, newtree) && /* 18 and 19 */
 -                   same(current, newtree))) {
 +              if (current->ce_flags & CE_CONFLICTED) {
 +                      if (same(oldtree, newtree) || o->reset) {
 +                              if (!newtree)
 +                                      return deleted_entry(current, current, o);
 +                              else
 +                                      return merged_entry(newtree, current, o);
 +                      }
 +                      return o->gently ? -1 : reject_merge(current, o);
 +              }
 +              else if ((!oldtree && !newtree) || /* 4 and 5 */
 +                       (!oldtree && newtree &&
 +                        same(current, newtree)) || /* 6 and 7 */
 +                       (oldtree && newtree &&
 +                        same(oldtree, newtree)) || /* 14 and 15 */
 +                       (oldtree && newtree &&
 +                        !same(oldtree, newtree) && /* 18 and 19 */
 +                        same(current, newtree))) {
                        return keep_entry(current, o);
                }
                else if (oldtree && !newtree && same(current, oldtree)) {