hashmap: factor out getting a hash code from a SHA1

Copying the first bytes of a SHA1 is duplicated in six places,
however, the implications (the actual value would depend on the
endianness of the platform) is documented only once.

Add a properly documented API for this.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt
index b977ae8bbb1f46ebb40d1d315e79262fe344f1c2..37727cd2c02fe22ce401f180e03782002f9615d9 100644 (file)
--- a/Documentation/technical/api-hashmap.txt
+++ b/Documentation/technical/api-hashmap.txt
@@ -58,6 +58,15 @@ Functions
 +
 `strihash` and `memihash` are case insensitive versions.
 
 +
 `strihash` and `memihash` are case insensitive versions.
 

+`unsigned int sha1hash(const unsigned char *sha1)`::
+
+       Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code
+       for use in hash tables. Cryptographic hashes are supposed to have
+       uniform distribution, so in contrast to `memhash()`, this just copies
+       the first `sizeof(int)` bytes without shuffling any bits. Note that
+       the results will be different on big-endian and little-endian
+       platforms, so they should not be stored or transferred over the net.
+

 `void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`::
 
        Initializes a hashmap structure.
 `void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`::
 
        Initializes a hashmap structure.

diff --git a/builtin/describe.c b/builtin/describe.c
index 24d740c8b1705f9c8993bd808c9a618acecc300c..57e84c8ae68c8172b3cbc4136f40c459743427da 100644 (file)
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -56,17 +56,10 @@ static int commit_name_cmp(const struct commit_name *cn1,
        return hashcmp(cn1->peeled, peeled ? peeled : cn2->peeled);
 }
 
        return hashcmp(cn1->peeled, peeled ? peeled : cn2->peeled);
 }
 

-static inline unsigned int hash_sha1(const unsigned char *sha1)
-{
-       unsigned int hash;
-       memcpy(&hash, sha1, sizeof(hash));
-       return hash;
-}
-

 static inline struct commit_name *find_commit_name(const unsigned char *peeled)
 {
        struct commit_name key;
 static inline struct commit_name *find_commit_name(const unsigned char *peeled)
 {
        struct commit_name key;

-       hashmap_entry_init(&key, hash_sha1(peeled));
+       hashmap_entry_init(&key, sha1hash(peeled));

        return hashmap_get(&names, &key, peeled);
 }
 
        return hashmap_get(&names, &key, peeled);
 }
 


@@ -114,7 +107,7 @@ static void add_to_known_names(const char *path,
                if (!e) {
                        e = xmalloc(sizeof(struct commit_name));
                        hashcpy(e->peeled, peeled);
                if (!e) {
                        e = xmalloc(sizeof(struct commit_name));
                        hashcpy(e->peeled, peeled);

-                       hashmap_entry_init(e, hash_sha1(peeled));
+                       hashmap_entry_init(e, sha1hash(peeled));

                        hashmap_add(&names, e);
                        e->path = NULL;
                }
                        hashmap_add(&names, e);
                        e->path = NULL;
                }

diff --git a/decorate.c b/decorate.c
index 7cb5d29a89a43ecf7e433db513b66184df3accb8..b2aac90c26296eacdd6c2cdb68a15f3744c595e9 100644 (file)
--- a/decorate.c
+++ b/decorate.c
@@ -8,10 +8,7 @@
 
 static unsigned int hash_obj(const struct object *obj, unsigned int n)
 {
 
 static unsigned int hash_obj(const struct object *obj, unsigned int n)
 {

-       unsigned int hash;
-
-       memcpy(&hash, obj->sha1, sizeof(unsigned int));
-       return hash % n;
+       return sha1hash(obj->sha1) % n;

 }
 
 static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
 }
 
 static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 749a35d2c2ab3271c6503a19271a5be6a6e97b4d..6fa97d44336d4f6250b94e5c20de56b9c51bb66e 100644 (file)
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -242,14 +242,12 @@ struct file_similarity {
 
 static unsigned int hash_filespec(struct diff_filespec *filespec)
 {
 
 static unsigned int hash_filespec(struct diff_filespec *filespec)
 {

-       unsigned int hash;

        if (!filespec->sha1_valid) {
                if (diff_populate_filespec(filespec, 0))
                        return 0;
                hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
        }
        if (!filespec->sha1_valid) {
                if (diff_populate_filespec(filespec, 0))
                        return 0;
                hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
        }

-       memcpy(&hash, filespec->sha1, sizeof(hash));
-       return hash;
+       return sha1hash(filespec->sha1);

 }
 
 static int find_identical_files(struct hashmap *srcs,
 }
 
 static int find_identical_files(struct hashmap *srcs,

diff --git a/hashmap.h b/hashmap.h
index a816ad47b14d2d377ba0e03a3f401ed36a56efa8..c51fd0abf78c98a7b74b719ba2d18ec77507d41e 100644 (file)
--- a/hashmap.h
+++ b/hashmap.h
@@ -13,6 +13,17 @@ extern unsigned int strihash(const char *buf);
 extern unsigned int memhash(const void *buf, size_t len);
 extern unsigned int memihash(const void *buf, size_t len);
 
 extern unsigned int memhash(const void *buf, size_t len);
 extern unsigned int memihash(const void *buf, size_t len);
 

+static inline unsigned int sha1hash(const unsigned char *sha1)
+{
+       /*
+        * Equivalent to 'return *(unsigned int *)sha1;', but safe on
+        * platforms that don't support unaligned reads.
+        */
+       unsigned int hash;
+       memcpy(&hash, sha1, sizeof(hash));
+       return hash;
+}
+

 /* data structures */
 
 struct hashmap_entry {
 /* data structures */
 
 struct hashmap_entry {

diff --git a/khash.h b/khash.h
index 57ff6038c5be0fb5aa28f1b297bf6972bebab350..06c79065490f152ceed2732ba1b93c309eb4d574 100644 (file)
--- a/khash.h
+++ b/khash.h
@@ -320,19 +320,12 @@ static const double __ac_HASH_UPPER = 0.77;
                code;                                                                                           \
        } }
 
                code;                                                                                           \
        } }
 

-static inline khint_t __kh_oid_hash(const unsigned char *oid)
-{
-       khint_t hash;
-       memcpy(&hash, oid, sizeof(hash));
-       return hash;
-}
-

 #define __kh_oid_cmp(a, b) (hashcmp(a, b) == 0)
 
 #define __kh_oid_cmp(a, b) (hashcmp(a, b) == 0)
 

-KHASH_INIT(sha1, const unsigned char *, void *, 1, __kh_oid_hash, __kh_oid_cmp)
+KHASH_INIT(sha1, const unsigned char *, void *, 1, sha1hash, __kh_oid_cmp)

 typedef kh_sha1_t khash_sha1;
 
 typedef kh_sha1_t khash_sha1;
 

-KHASH_INIT(sha1_pos, const unsigned char *, int, 1, __kh_oid_hash, __kh_oid_cmp)
+KHASH_INIT(sha1_pos, const unsigned char *, int, 1, sha1hash, __kh_oid_cmp)

 typedef kh_sha1_pos_t khash_sha1_pos;
 
 #endif /* __AC_KHASH_H */
 typedef kh_sha1_pos_t khash_sha1_pos;
 
 #endif /* __AC_KHASH_H */

diff --git a/object.c b/object.c
index 9c31e9a5e0e0d913044501089e09037e47894f03..91c7c867b9943f6e1b5b7fef560d50450c8adc5a 100644 (file)
--- a/object.c
+++ b/object.c
@@ -50,18 +50,7 @@ int type_from_string(const char *str)
  */
 static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)
 {
  */
 static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)
 {

-       unsigned int hash;
-
-       /*
-        * Since the sha1 is essentially random, we just take the
-        * required number of bits directly from the first
-        * sizeof(unsigned int) bytes of sha1.  First we have to copy
-        * the bytes into a properly aligned integer.  If we cared
-        * about getting consistent results across architectures, we
-        * would have to call ntohl() here, too.
-        */
-       memcpy(&hash, sha1, sizeof(unsigned int));
-       return hash & (n - 1);
+       return sha1hash(sha1) & (n - 1);

 }
 
 /*
 }
 
 /*

diff --git a/pack-objects.c b/pack-objects.c
index 4f36c3204544c40ada8e6ce584deb6063b055518..9992f3ecf249c32e5be31dc047bad46a4c4ac367 100644 (file)
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -7,10 +7,9 @@ static uint32_t locate_object_entry_hash(struct packing_data *pdata,
                                         const unsigned char *sha1,
                                         int *found)
 {
                                         const unsigned char *sha1,
                                         int *found)
 {

-       uint32_t i, hash, mask = (pdata->index_size - 1);
+       uint32_t i, mask = (pdata->index_size - 1);

 
 

-       memcpy(&hash, sha1, sizeof(uint32_t));
-       i = hash & mask;
+       i = sha1hash(sha1) & mask;

 
        while (pdata->index[i] > 0) {
                uint32_t pos = pdata->index[i] - 1;
 
        while (pdata->index[i] > 0) {
                uint32_t pos = pdata->index[i] - 1;