git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 2/7] Move name hashing functions into a file of its own

From
Linus Torvalds <torvalds@linux-foundation.org>
Date
Mar 22, 2008, 17:25 UTC
Message-ID
<alpine.LFD.1.00.0803221022480.3020@woody.linux-foundation.org>
In-Reply-To
<alpine.LFD.1.00.0803221021220.3020@woody.linux-foundation.org>
From: Linus Torvalds <torvalds@woody.linux-foundation.org>
Date: Fri, 21 Mar 2008 13:16:24 -0700

It's really totally separate functionality, and if we want to start doing case-insensitive hash lookups, I'd rather do it when it's separated out.

It also renames "remove_index_entry()" to "remove_name_hash()", because that really describes the thing better. It doesn't actually remove the index entry, that's done by "remove_index_entry_at()", which is something very different, despite the similarity in names.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This makes no code changes what-so-ever apart from the movement/renaming, just moves things around a bit, and makes a function that used to be static (add_name_hash()) be exported because it's now in a different file.

 Makefile            |    1 +
 builtin-read-tree.c |    2 +-
 cache.h             |   31 ++++++++++++----------
 name-hash.c         |   73 +++++++++++++++++++++++++++++++++++++++++++++++++++
 read-cache.c        |   65 ++-------------------------------------------
 5 files changed, 95 insertions(+), 77 deletions(-)
 create mode 100644 name-hash.c
diff --git a/Makefile b/Makefile
index 7c70b00..6d35662 100644
--- a/Makefile
+++ b/Makefile
@@ -421,6 +421,7 @@ LIB_OBJS += log-tree.o
 LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
+LIB_OBJS += name-hash.o
 LIB_OBJS += object.o
 LIB_OBJS += pack-check.o
 LIB_OBJS += pack-revindex.o
diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index e9cfd2b..7ac3088 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -40,7 +40,7 @@ static int read_cache_unmerged(void)
 	for (i = 0; i < active_nr; i++) {
 		struct cache_entry *ce = active_cache[i];
 		if (ce_stage(ce)) {
-			remove_index_entry(ce);
+			remove_name_hash(ce);
 			if (last && !strcmp(ce->name, last->name))
 				continue;
 			cache_tree_invalidate_path(active_cache_tree, ce->name);
diff --git a/cache.h b/cache.h
index 2a1e7ec..2afc788 100644
--- a/cache.h
+++ b/cache.h
@@ -153,20 +153,6 @@ static inline void copy_cache_entry(struct cache_entry *dst, struct cache_entry
 	dst->ce_flags = (dst->ce_flags & ~CE_STATE_MASK) | state;
 }
 
-/*
- * We don't actually *remove* it, we can just mark it invalid so that
- * we won't find it in lookups.
- *
- * Not only would we have to search the lists (simple enough), but
- * we'd also have to rehash other hash buckets in case this makes the
- * hash bucket empty (common). So it's much better to just mark
- * it.
- */
-static inline void remove_index_entry(struct cache_entry *ce)
-{
-	ce->ce_flags |= CE_UNHASHED;
-}
-
 static inline unsigned create_ce_flags(size_t len, unsigned stage)
 {
 	if (len >= CE_NAMEMASK)
@@ -241,6 +227,23 @@ struct index_state {
 
 extern struct index_state the_index;
 
+/* Name hashing */
+extern void add_name_hash(struct index_state *istate, struct cache_entry *ce);
+/*
+ * We don't actually *remove* it, we can just mark it invalid so that
+ * we won't find it in lookups.
+ *
+ * Not only would we have to search the lists (simple enough), but
+ * we'd also have to rehash other hash buckets in case this makes the
+ * hash bucket empty (common). So it's much better to just mark
+ * it.
+ */
+static inline void remove_name_hash(struct cache_entry *ce)
+{
+	ce->ce_flags |= CE_UNHASHED;
+}
+
+
 #ifndef NO_THE_INDEX_COMPATIBILITY_MACROS
 #define active_cache (the_index.cache)
 #define active_nr (the_index.cache_nr)
diff --git a/name-hash.c b/name-hash.c
new file mode 100644
index 0000000..e56eb16
--- /dev/null
+++ b/name-hash.c
@@ -0,0 +1,73 @@
+/*
+ * name-hash.c
+ *
+ * Hashing names in the index state
+ *
+ * Copyright (C) 2008 Linus Torvalds
+ */
+#define NO_THE_INDEX_COMPATIBILITY_MACROS
+#include "cache.h"
+
+static unsigned int hash_name(const char *name, int namelen)
+{
+	unsigned int hash = 0x123;
+
+	do {
+		unsigned char c = *name++;
+		hash = hash*101 + c;
+	} while (--namelen);
+	return hash;
+}
+
+static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
+{
+	void **pos;
+	unsigned int hash;
+
+	if (ce->ce_flags & CE_HASHED)
+		return;
+	ce->ce_flags |= CE_HASHED;
+	ce->next = NULL;
+	hash = hash_name(ce->name, ce_namelen(ce));
+	pos = insert_hash(hash, ce, &istate->name_hash);
+	if (pos) {
+		ce->next = *pos;
+		*pos = ce;
+	}
+}
+
+static void lazy_init_name_hash(struct index_state *istate)
+{
+	int nr;
+
+	if (istate->name_hash_initialized)
+		return;
+	for (nr = 0; nr < istate->cache_nr; nr++)
+		hash_index_entry(istate, istate->cache[nr]);
+	istate->name_hash_initialized = 1;
+}
+
+void add_name_hash(struct index_state *istate, struct cache_entry *ce)
+{
+	ce->ce_flags &= ~CE_UNHASHED;
+	if (istate->name_hash_initialized)
+		hash_index_entry(istate, ce);
+}
+
+int index_name_exists(struct index_state *istate, const char *name, int namelen)
+{
+	unsigned int hash = hash_name(name, namelen);
+	struct cache_entry *ce;
+
+	lazy_init_name_hash(istate);
+	ce = lookup_hash(hash, &istate->name_hash);
+
+	while (ce) {
+		if (!(ce->ce_flags & CE_UNHASHED)) {
+			if (!cache_name_compare(name, namelen, ce->name, ce->ce_flags))
+				return 1;
+		}
+		ce = ce->next;
+	}
+	return 0;
+}
diff --git a/read-cache.c b/read-cache.c
index a92b25b..5dc998d 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -23,80 +23,21 @@
 
 struct index_state the_index;
 
-static unsigned int hash_name(const char *name, int namelen)
-{
-	unsigned int hash = 0x123;
-
-	do {
-		unsigned char c = *name++;
-		hash = hash*101 + c;
-	} while (--namelen);
-	return hash;
-}
-
-static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
-{
-	void **pos;
-	unsigned int hash;
-
-	if (ce->ce_flags & CE_HASHED)
-		return;
-	ce->ce_flags |= CE_HASHED;
-	ce->next = NULL;
-	hash = hash_name(ce->name, ce_namelen(ce));
-	pos = insert_hash(hash, ce, &istate->name_hash);
-	if (pos) {
-		ce->next = *pos;
-		*pos = ce;
-	}
-}
-
-static void lazy_init_name_hash(struct index_state *istate)
-{
-	int nr;
-
-	if (istate->name_hash_initialized)
-		return;
-	for (nr = 0; nr < istate->cache_nr; nr++)
-		hash_index_entry(istate, istate->cache[nr]);
-	istate->name_hash_initialized = 1;
-}
-
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
-	ce->ce_flags &= ~CE_UNHASHED;
 	istate->cache[nr] = ce;
-	if (istate->name_hash_initialized)
-		hash_index_entry(istate, ce);
+	add_name_hash(istate, ce);
 }
 
 static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
 	struct cache_entry *old = istate->cache[nr];
 
-	remove_index_entry(old);
+	remove_name_hash(old);
 	set_index_entry(istate, nr, ce);
 	istate->cache_changed = 1;
 }
 
-int index_name_exists(struct index_state *istate, const char *name, int namelen)
-{
-	unsigned int hash = hash_name(name, namelen);
-	struct cache_entry *ce;
-
-	lazy_init_name_hash(istate);
-	ce = lookup_hash(hash, &istate->name_hash);
-
-	while (ce) {
-		if (!(ce->ce_flags & CE_UNHASHED)) {
-			if (!cache_name_compare(name, namelen, ce->name, ce->ce_flags))
-				return 1;
-		}
-		ce = ce->next;
-	}
-	return 0;
-}
-
 /*
  * This only updates the "non-critical" parts of the directory
  * cache, ie the parts that aren't tracked by GIT, and only used
@@ -438,7 +379,7 @@ int remove_index_entry_at(struct index_state *istate, int pos)
 {
 	struct cache_entry *ce = istate->cache[pos];
 
-	remove_index_entry(ce);
+	remove_name_hash(ce);
 	istate->cache_changed = 1;
 	istate->cache_nr--;
 	if (pos >= istate->cache_nr)

-- 
1.5.5.rc0.28.g61a0.dirty
Previous: Linus TorvaldsNext: Linus Torvalds
Message 3 of 29 in “Case-insensitive filesystem support, take 1”
  1. 0/7 Case-insensitive filesystem support, take 1Linus Torvalds, Mar 22, 2008
  2. 1/7 Make unpack_trees_options bit flags actual bitfieldsLinus Torvalds, Mar 22, 2008
  3. 2/7 Move name hashing functions into a file of its ownLinus Torvalds, Mar 22, 2008
  4. 3/7 Make "index_name_exists()" return the cache_entry it foundLinus Torvalds, Mar 22, 2008
  5. 4/7 Make hash_name_lookup able to do case-independent lookupsLinus Torvalds, Mar 22, 2008
  6. 5/7 Add 'core.ignorecase' optionLinus Torvalds, Mar 22, 2008
  7. 6/7 Make branch merging aware of underlying case-insensitive filsystemsLinus Torvalds, Mar 22, 2008
  8. 7/7 Make unpack-tree update removed files before any updated filesLinus Torvalds, Mar 22, 2008
  9. 0/7 Final wordsLinus Torvalds, Mar 22, 2008
  10. Linus TorvaldsMar 22, 2008
  11. 8/7 When adding files to the index, add support for case-independent matchesLinus Torvalds, Mar 22, 2008
  12. 9/7 Make git-add behave more sensibly in a case-insensitive environmentLinus Torvalds, Mar 22, 2008
  13. Junio C HamanoMar 23, 2008
  14. Junio C HamanoMar 23, 2008
  15. Linus TorvaldsMar 23, 2008
  16. Johannes SchindelinMar 22, 2008
  17. Linus TorvaldsMar 22, 2008
  18. Johannes SchindelinMar 22, 2008
  19. t0050: Set core.ignorecase case to activate case insensitivitySteffen Prohaska, Mar 22, 2008
  20. git-init: autodetect core.ignorecaseDmitry Potapov, Mar 25, 2008
  21. Johannes SchindelinMar 25, 2008
  22. git-init: autodetect core.ignorecaseDmitry Potapov, Mar 25, 2008
  23. Dmitry PotapovMar 25, 2008
  24. Dmitry PotapovMar 25, 2008
  25. Linus TorvaldsMar 25, 2008
  26. Dmitry PotapovMar 26, 2008
  27. Linus TorvaldsMar 26, 2008
  28. Derek FawcusMar 25, 2008
  29. Jan HudecMar 25, 2008

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.