summaryrefslogtreecommitdiff
path: root/oidset.c
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2017-02-08 20:53:07 (GMT)
committerJunio C Hamano <gitster@pobox.com>2017-02-08 23:39:55 (GMT)
commit29c2bd5fa8cb97eedcd463d49cfc7e753feb3145 (patch)
tree8822280e8073c9af3dccb363d81a881382f6f879 /oidset.c
parent41a078c60b82bad4edf9d1bd8e826aae5f020ee5 (diff)
downloadgit-29c2bd5fa8cb97eedcd463d49cfc7e753feb3145.zip
git-29c2bd5fa8cb97eedcd463d49cfc7e753feb3145.tar.gz
git-29c2bd5fa8cb97eedcd463d49cfc7e753feb3145.tar.bz2
add oidset API
This is similar to many of our uses of sha1-array, but it overcomes one limitation of a sha1-array: when you are de-duplicating a large input with relatively few unique entries, sha1-array uses 20 bytes per non-unique entry. Whereas this set will use memory linear in the number of unique entries (albeit a few more than 20 bytes due to hashmap overhead). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'oidset.c')
-rw-r--r--oidset.c49
1 files changed, 49 insertions, 0 deletions
diff --git a/oidset.c b/oidset.c
new file mode 100644
index 0000000..ac169f0
--- /dev/null
+++ b/oidset.c
@@ -0,0 +1,49 @@
+#include "cache.h"
+#include "oidset.h"
+
+struct oidset_entry {
+ struct hashmap_entry hash;
+ struct object_id oid;
+};
+
+static int oidset_hashcmp(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)
+ return 0;
+
+ hashmap_entry_init(&key, sha1hash(oid->hash));
+ return !!hashmap_get(&set->map, &key, 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, 0);
+
+ 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);
+ return 0;
+}
+
+void oidset_clear(struct oidset *set)
+{
+ hashmap_free(&set->map, 1);
+}