+ return -first-1;
+}
+
+/* Remove entry, return true if there are more entries to go.. */
+int remove_cache_entry_at(int pos)
+{
+ active_cache_changed = 1;
+ active_nr--;
+ if (pos >= active_nr)
+ return 0;
+ memmove(active_cache + pos, active_cache + pos + 1, (active_nr - pos) * sizeof(struct cache_entry *));
+ return 1;
+}
+
+int remove_file_from_cache(const char *path)
+{
+ int pos = cache_name_pos(path, strlen(path));
+ if (pos < 0)
+ pos = -pos-1;
+ while (pos < active_nr && !strcmp(active_cache[pos]->name, path))
+ remove_cache_entry_at(pos);
+ return 0;
+}
+
+int ce_same_name(struct cache_entry *a, struct cache_entry *b)
+{
+ int len = ce_namelen(a);
+ return ce_namelen(b) == len && !memcmp(a->name, b->name, len);
+}
+
+int ce_path_match(const struct cache_entry *ce, const char **pathspec)
+{
+ const char *match, *name;
+ int len;
+
+ if (!pathspec)
+ return 1;
+
+ len = ce_namelen(ce);
+ name = ce->name;
+ while ((match = *pathspec++) != NULL) {
+ int matchlen = strlen(match);
+ if (matchlen > len)
+ continue;
+ if (memcmp(name, match, matchlen))
+ continue;
+ if (matchlen && name[matchlen-1] == '/')
+ return 1;
+ if (name[matchlen] == '/' || !name[matchlen])
+ return 1;
+ if (!matchlen)
+ return 1;
+ }
+ return 0;
+}
+
+/*
+ * Do we have another file that has the beginning components being a
+ * proper superset of the name we're trying to add?
+ */
+static int has_file_name(const struct cache_entry *ce, int pos, int ok_to_replace)
+{
+ int retval = 0;
+ int len = ce_namelen(ce);
+ int stage = ce_stage(ce);
+ const char *name = ce->name;
+
+ while (pos < active_nr) {
+ struct cache_entry *p = active_cache[pos++];
+
+ if (len >= ce_namelen(p))
+ break;
+ if (memcmp(name, p->name, len))
+ break;
+ if (ce_stage(p) != stage)
+ continue;
+ if (p->name[len] != '/')
+ continue;
+ retval = -1;
+ if (!ok_to_replace)
+ break;
+ remove_cache_entry_at(--pos);
+ }
+ return retval;
+}
+
+/*
+ * Do we have another file with a pathname that is a proper
+ * subset of the name we're trying to add?
+ */
+static int has_dir_name(const struct cache_entry *ce, int pos, int ok_to_replace)
+{
+ int retval = 0;
+ int stage = ce_stage(ce);
+ const char *name = ce->name;
+ const char *slash = name + ce_namelen(ce);
+
+ for (;;) {
+ int len;
+
+ for (;;) {
+ if (*--slash == '/')
+ break;
+ if (slash <= ce->name)
+ return retval;
+ }
+ len = slash - name;
+
+ pos = cache_name_pos(name, ntohs(create_ce_flags(len, stage)));
+ if (pos >= 0) {
+ retval = -1;
+ if (ok_to_replace)
+ break;
+ remove_cache_entry_at(pos);
+ continue;
+ }
+
+ /*
+ * Trivial optimization: if we find an entry that
+ * already matches the sub-directory, then we know
+ * we're ok, and we can exit.
+ */
+ pos = -pos-1;
+ while (pos < active_nr) {
+ struct cache_entry *p = active_cache[pos];
+ if ((ce_namelen(p) <= len) ||
+ (p->name[len] != '/') ||
+ memcmp(p->name, name, len))
+ break; /* not our subdirectory */
+ if (ce_stage(p) == stage)
+ /* p is at the same stage as our entry, and
+ * is a subdirectory of what we are looking
+ * at, so we cannot have conflicts at our
+ * level or anything shorter.
+ */
+ return retval;
+ pos++;
+ }
+ }
+ return retval;
+}
+
+/* We may be in a situation where we already have path/file and path
+ * is being added, or we already have path and path/file is being
+ * added. Either one would result in a nonsense tree that has path
+ * twice when git-write-tree tries to write it out. Prevent it.
+ *
+ * If ok-to-replace is specified, we remove the conflicting entries
+ * from the cache so the caller should recompute the insert position.
+ * When this happens, we return non-zero.
+ */
+static int check_file_directory_conflict(const struct cache_entry *ce, int pos, int ok_to_replace)
+{
+ /*
+ * We check if the path is a sub-path of a subsequent pathname
+ * first, since removing those will not change the position
+ * in the array
+ */
+ int retval = has_file_name(ce, pos, ok_to_replace);
+ /*
+ * Then check if the path might have a clashing sub-directory
+ * before it.
+ */
+ return retval + has_dir_name(ce, pos, ok_to_replace);
+}
+
+int add_cache_entry(struct cache_entry *ce, int option)
+{
+ int pos;
+ int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
+ int ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;
+ int skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;
+ pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
+
+ /* existing match? Just replace it. */
+ if (pos >= 0) {
+ active_cache_changed = 1;
+ active_cache[pos] = ce;
+ return 0;
+ }
+ pos = -pos-1;
+
+ /*
+ * Inserting a merged entry ("stage 0") into the index
+ * will always replace all non-merged entries..
+ */
+ if (pos < active_nr && ce_stage(ce) == 0) {
+ while (ce_same_name(active_cache[pos], ce)) {
+ ok_to_add = 1;
+ if (!remove_cache_entry_at(pos))
+ break;
+ }
+ }
+
+ if (!ok_to_add)
+ return -1;
+
+ if (!skip_df_check &&
+ check_file_directory_conflict(ce, pos, ok_to_replace)) {
+ if (!ok_to_replace)
+ return -1;
+ pos = cache_name_pos(ce->name, ntohs(ce->ce_flags));
+ pos = -pos-1;
+ }
+
+ /* Make sure the array is big enough .. */
+ if (active_nr == active_alloc) {
+ active_alloc = alloc_nr(active_alloc);
+ active_cache = xrealloc(active_cache, active_alloc * sizeof(struct cache_entry *));
+ }
+
+ /* Add it in.. */
+ active_nr++;
+ if (active_nr > pos)
+ memmove(active_cache + pos + 1, active_cache + pos, (active_nr - pos - 1) * sizeof(ce));
+ active_cache[pos] = ce;
+ active_cache_changed = 1;
+ return 0;