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>

1 files changed, 68 insertions, 0 deletions

diff --git a/oidmap.h b/oidmap.h
new file mode 100644
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