oidmap: map with OID as key

This is similar to using the hashmap in hashmap.c, but with an
easier-to-use API. In particular, custom entry comparisons no longer
need to be written, and lookups can be done without constructing a
temporary entry structure.

This is implemented as a thin wrapper over the hashmap API. In
particular, this means that there is an additional 4-byte overhead due
to the fact that the first 4 bytes of the hash is redundantly stored.
For now, I'm taking the simpler approach, but if need be, we can
reimplement oidmap without affecting the callers significantly.

oidset has been updated to use oidmap.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/Makefile b/Makefile
index ed4ca438bd9c6ddab51f78cb4b620f02a7e12eed..64136dde488cacb317167b3363f6c2c9997fdc64 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -821,6 +821,7 @@ LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
 LIB_OBJS += notes-utils.o
 LIB_OBJS += object.o
+LIB_OBJS += oidmap.o
 LIB_OBJS += oidset.o
 LIB_OBJS += packfile.o
 LIB_OBJS += pack-bitmap.o

diff --git a/fetch-pack.c b/fetch-pack.c
index 105506e9aa5e5ae52dff30866d681331323f1679..008b25d3db08726b0fc1569f88fba76694bbcc12 100644 (file)
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -611,7 +611,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
         * add to "newlist" between calls, the additions will always be for
         * oids that are already in the set.
         */
-       if (!tip_oids->map.tablesize) {
+       if (!tip_oids->map.map.tablesize) {
                add_refs_to_oidset(tip_oids, unmatched);
                add_refs_to_oidset(tip_oids, newlist);
        }

diff --git a/oidmap.c b/oidmap.c
new file mode 100644 (file)
index 0000000..6db4fff
--- /dev/null
+++ b/oidmap.c
@@ -0,0 +1,51 @@
+#include "cache.h"
+#include "oidmap.h"
+
+static int cmpfn(const void *hashmap_cmp_fn_data,
+                const void *entry, const void *entry_or_key,
+                const void *keydata)
+{
+       const struct oidmap_entry *entry_ = entry;
+       if (keydata)
+               return oidcmp(&entry_->oid, (const struct object_id *) keydata);
+       return oidcmp(&entry_->oid,
+                     &((const struct oidmap_entry *) entry_or_key)->oid);
+}
+
+static int hash(const struct object_id *oid)
+{
+       int hash;
+       memcpy(&hash, oid->hash, sizeof(hash));
+       return hash;
+}
+
+void oidmap_init(struct oidmap *map, size_t initial_size)
+{
+       hashmap_init(&map->map, cmpfn, NULL, initial_size);
+}
+
+void oidmap_free(struct oidmap *map, int free_entries)
+{
+       if (!map)
+               return;
+       hashmap_free(&map->map, free_entries);
+}
+
+void *oidmap_get(const struct oidmap *map, const struct object_id *key)
+{
+       return hashmap_get_from_hash(&map->map, hash(key), key);
+}
+
+void *oidmap_remove(struct oidmap *map, const struct object_id *key)
+{
+       struct hashmap_entry entry;
+       hashmap_entry_init(&entry, hash(key));
+       return hashmap_remove(&map->map, &entry, key);
+}
+
+void *oidmap_put(struct oidmap *map, void *entry)
+{
+       struct oidmap_entry *to_put = entry;
+       hashmap_entry_init(&to_put->internal_entry, hash(&to_put->oid));
+       return hashmap_put(&map->map, to_put);
+}

diff --git a/oidmap.h b/oidmap.h
new file mode 100644 (file)
index 0000000..18f54cd
--- /dev/null
+++ b/oidmap.h
@@ -0,0 +1,68 @@
+#ifndef OIDMAP_H
+#define OIDMAP_H
+
+#include "hashmap.h"
+
+/*
+ * struct oidmap_entry is a structure representing an entry in the hash table,
+ * which must be used as first member of user data structures.
+ *
+ * Users should set the oid field. oidmap_put() will populate the
+ * internal_entry field.
+ */
+struct oidmap_entry {
+       /* For internal use only */
+       struct hashmap_entry internal_entry;
+
+       struct object_id oid;
+};
+
+struct oidmap {
+       struct hashmap map;
+};
+
+#define OIDMAP_INIT { { NULL } }
+
+/*
+ * Initializes an oidmap structure.
+ *
+ * `map` is the oidmap to initialize.
+ *
+ * If the total number of entries is known in advance, the `initial_size`
+ * parameter may be used to preallocate a sufficiently large table and thus
+ * prevent expensive resizing. If 0, the table is dynamically resized.
+ */
+extern void oidmap_init(struct oidmap *map, size_t initial_size);
+
+/*
+ * Frees an oidmap structure and allocated memory.
+ *
+ * If `free_entries` is true, each oidmap_entry in the map is freed as well
+ * using stdlibs free().
+ */
+extern void oidmap_free(struct oidmap *map, int free_entries);
+
+/*
+ * Returns the oidmap entry for the specified oid, or NULL if not found.
+ */
+extern void *oidmap_get(const struct oidmap *map,
+                       const struct object_id *key);
+
+/*
+ * Adds or replaces an oidmap entry.
+ *
+ * ((struct oidmap_entry *) entry)->internal_entry will be populated by this
+ * function.
+ *
+ * Returns the replaced entry, or NULL if not found (i.e. the entry was added).
+ */
+extern void *oidmap_put(struct oidmap *map, void *entry);
+
+/*
+ * Removes an oidmap entry matching the specified oid.
+ *
+ * Returns the removed entry, or NULL if not found.
+ */
+extern void *oidmap_remove(struct oidmap *map, const struct object_id *key);
+
+#endif

diff --git a/oidset.c b/oidset.c
index a6a08ba52abdcda75b0bd5cc28349cd3c4be871c..f1f874aaad2c0375eb80d3b714ae6ad460c75ddc 100644 (file)
--- a/oidset.c
+++ b/oidset.c
@@ -1,50 +1,30 @@
 #include "cache.h"
 #include "oidset.h"
 
-struct oidset_entry {
-       struct hashmap_entry hash;
-       struct object_id oid;
-};
-
-static int oidset_hashcmp(const void *unused_cmp_data,
-                         const void *va, const void *vb,
-                         const void *vkey)
-{
-       const struct oidset_entry *a = va, *b = vb;
-       const struct object_id *key = vkey;
-       return oidcmp(&a->oid, key ? key : &b->oid);
-}
-
 int oidset_contains(const struct oidset *set, const struct object_id *oid)
 {
-       struct hashmap_entry key;
-
-       if (!set->map.cmpfn)
+       if (!set->map.map.tablesize)
                return 0;
-
-       hashmap_entry_init(&key, sha1hash(oid->hash));
-       return !!hashmap_get(&set->map, &key, oid);
+       return !!oidmap_get(&set->map, oid);
 }
 
 int oidset_insert(struct oidset *set, const struct object_id *oid)
 {
-       struct oidset_entry *entry;
-
-       if (!set->map.cmpfn)
-               hashmap_init(&set->map, oidset_hashcmp, NULL, 0);
+       struct oidmap_entry *entry;
 
-       if (oidset_contains(set, oid))
+       if (!set->map.map.tablesize)
+               oidmap_init(&set->map, 0);
+       else if (oidset_contains(set, oid))
                return 1;
 
        entry = xmalloc(sizeof(*entry));
-       hashmap_entry_init(&entry->hash, sha1hash(oid->hash));
        oidcpy(&entry->oid, oid);
 
-       hashmap_add(&set->map, entry);
+       oidmap_put(&set->map, entry);
        return 0;
 }
 
 void oidset_clear(struct oidset *set)
 {
-       hashmap_free(&set->map, 1);
+       oidmap_free(&set->map, 1);
 }

diff --git a/oidset.h b/oidset.h
index b7eaab5b88f3e6e287384eceb76757e6be9fe015..f4c9e0f9c04e71440aee3c1382297cbf8b1c7827 100644 (file)
--- a/oidset.h
+++ b/oidset.h
@@ -1,6 +1,8 @@
 #ifndef OIDSET_H
 #define OIDSET_H
 
+#include "oidmap.h"
+
 /**
  * This API is similar to sha1-array, in that it maintains a set of object ids
  * in a memory-efficient way. The major differences are:
@@ -17,10 +19,10 @@
  * A single oidset; should be zero-initialized (or use OIDSET_INIT).
  */
 struct oidset {
-       struct hashmap map;
+       struct oidmap map;
 };
 
-#define OIDSET_INIT { { NULL } }
+#define OIDSET_INIT { OIDMAP_INIT }
 
 /**
  * Returns true iff `set` contains `oid`.