summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2018-10-19 04:34:06 (GMT)
committerJunio C Hamano <gitster@pobox.com>2018-10-19 04:34:06 (GMT)
commit82d0a8c05af8d1f7df0c308d23d078e0bac9c594 (patch)
treef61c5b42ba05367508c7f349e970ed679cac5913
parent9822b8f10d2c255c3bda81aa800fa056549f034a (diff)
parent8c84ae659e0e17d55f5ddc58bc79855ed7650e00 (diff)
downloadgit-82d0a8c05af8d1f7df0c308d23d078e0bac9c594.zip
git-82d0a8c05af8d1f7df0c308d23d078e0bac9c594.tar.gz
git-82d0a8c05af8d1f7df0c308d23d078e0bac9c594.tar.bz2
Merge branch 'rs/oidset-on-khash'
The oidset API was built on top of the oidmap API which in turn is on the hashmap API. Replace the implementation to build on top of the khash API and gain performance. * rs/oidset-on-khash: oidset: uninline oidset_init() oidset: use khash khash: factor out kh_release_* fetch-pack: load tip_oids eagerly iff needed fetch-pack: factor out is_unmatched_ref()
-rw-r--r--fetch-pack.c49
-rw-r--r--khash.h9
-rw-r--r--oidset.c41
-rw-r--r--oidset.h43
4 files changed, 81 insertions, 61 deletions
diff --git a/fetch-pack.c b/fetch-pack.c
index 75047a4..5391456 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -526,21 +526,14 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)
oidset_insert(oids, &refs->old_oid);
}
-static int tip_oids_contain(struct oidset *tip_oids,
- struct ref *unmatched, struct ref *newlist,
- const struct object_id *id)
+static int is_unmatched_ref(const struct ref *ref)
{
- /*
- * Note that this only looks at the ref lists the first time it's
- * called. This works out in filter_refs() because even though it may
- * add to "newlist" between calls, the additions will always be for
- * oids that are already in the set.
- */
- if (!tip_oids->map.map.tablesize) {
- add_refs_to_oidset(tip_oids, unmatched);
- add_refs_to_oidset(tip_oids, newlist);
- }
- return oidset_contains(tip_oids, id);
+ struct object_id oid;
+ const char *p;
+ return ref->match_status == REF_NOT_MATCHED &&
+ !parse_oid_hex(ref->name, &oid, &p) &&
+ *p == '\0' &&
+ oideq(&oid, &ref->old_oid);
}
static void filter_refs(struct fetch_pack_args *args,
@@ -553,6 +546,8 @@ static void filter_refs(struct fetch_pack_args *args,
struct ref *ref, *next;
struct oidset tip_oids = OIDSET_INIT;
int i;
+ int strict = !(allow_unadvertised_object_request &
+ (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
i = 0;
for (ref = *refs; ref; ref = next) {
@@ -589,23 +584,25 @@ static void filter_refs(struct fetch_pack_args *args,
}
}
+ if (strict) {
+ for (i = 0; i < nr_sought; i++) {
+ ref = sought[i];
+ if (!is_unmatched_ref(ref))
+ continue;
+
+ add_refs_to_oidset(&tip_oids, unmatched);
+ add_refs_to_oidset(&tip_oids, newlist);
+ break;
+ }
+ }
+
/* Append unmatched requests to the list */
for (i = 0; i < nr_sought; i++) {
- struct object_id oid;
- const char *p;
-
ref = sought[i];
- if (ref->match_status != REF_NOT_MATCHED)
- continue;
- if (parse_oid_hex(ref->name, &oid, &p) ||
- *p != '\0' ||
- !oideq(&oid, &ref->old_oid))
+ if (!is_unmatched_ref(ref))
continue;
- if ((allow_unadvertised_object_request &
- (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||
- tip_oids_contain(&tip_oids, unmatched, newlist,
- &ref->old_oid)) {
+ if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) {
ref->match_status = REF_MATCHED;
*newtail = copy_ref(ref);
newtail = &(*newtail)->next;
diff --git a/khash.h b/khash.h
index 07b4cc2..d10caa0 100644
--- a/khash.h
+++ b/khash.h
@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;
SCOPE kh_##name##_t *kh_init_##name(void) { \
return (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t)); \
} \
+ SCOPE void kh_release_##name(kh_##name##_t *h) \
+ { \
+ free(h->flags); \
+ free((void *)h->keys); \
+ free((void *)h->vals); \
+ } \
SCOPE void kh_destroy_##name(kh_##name##_t *h) \
{ \
if (h) { \
- free((void *)h->keys); free(h->flags); \
- free((void *)h->vals); \
+ kh_release_##name(h); \
free(h); \
} \
} \
diff --git a/oidset.c b/oidset.c
index 454c54f..fe4eb92 100644
--- a/oidset.c
+++ b/oidset.c
@@ -1,40 +1,37 @@
#include "cache.h"
#include "oidset.h"
+void oidset_init(struct oidset *set, size_t initial_size)
+{
+ memset(&set->set, 0, sizeof(set->set));
+ if (initial_size)
+ kh_resize_oid(&set->set, initial_size);
+}
+
int oidset_contains(const struct oidset *set, const struct object_id *oid)
{
- if (!set->map.map.tablesize)
- return 0;
- return !!oidmap_get(&set->map, oid);
+ khiter_t pos = kh_get_oid(&set->set, *oid);
+ return pos != kh_end(&set->set);
}
int oidset_insert(struct oidset *set, const struct object_id *oid)
{
- struct oidmap_entry *entry;
-
- if (!set->map.map.tablesize)
- oidmap_init(&set->map, 0);
- else if (oidset_contains(set, oid))
- return 1;
-
- entry = xmalloc(sizeof(*entry));
- oidcpy(&entry->oid, oid);
-
- oidmap_put(&set->map, entry);
- return 0;
+ int added;
+ kh_put_oid(&set->set, *oid, &added);
+ return !added;
}
int oidset_remove(struct oidset *set, const struct object_id *oid)
{
- struct oidmap_entry *entry;
-
- entry = oidmap_remove(&set->map, oid);
- free(entry);
-
- return (entry != NULL);
+ khiter_t pos = kh_get_oid(&set->set, *oid);
+ if (pos == kh_end(&set->set))
+ return 0;
+ kh_del_oid(&set->set, pos);
+ return 1;
}
void oidset_clear(struct oidset *set)
{
- oidmap_free(&set->map, 1);
+ kh_release_oid(&set->set);
+ oidset_init(set, 0);
}
diff --git a/oidset.h b/oidset.h
index 40ec5f8..c9d0f6d 100644
--- a/oidset.h
+++ b/oidset.h
@@ -1,7 +1,8 @@
#ifndef OIDSET_H
#define OIDSET_H
-#include "oidmap.h"
+#include "hashmap.h"
+#include "khash.h"
/**
* This API is similar to sha1-array, in that it maintains a set of object ids
@@ -15,20 +16,35 @@
* table overhead.
*/
+static inline unsigned int oid_hash(struct object_id oid)
+{
+ return sha1hash(oid.hash);
+}
+
+static inline int oid_equal(struct object_id a, struct object_id b)
+{
+ return oideq(&a, &b);
+}
+
+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)
+
/**
* A single oidset; should be zero-initialized (or use OIDSET_INIT).
*/
struct oidset {
- struct oidmap map;
+ kh_oid_t set;
};
-#define OIDSET_INIT { OIDMAP_INIT }
+#define OIDSET_INIT { { 0 } }
-static inline void oidset_init(struct oidset *set, size_t initial_size)
-{
- oidmap_init(&set->map, initial_size);
-}
+/**
+ * Initialize the oidset structure `set`.
+ *
+ * If `initial_size` is bigger than 0 then preallocate to allow inserting
+ * the specified number of elements without further allocations.
+ */
+void oidset_init(struct oidset *set, size_t initial_size);
/**
* Returns true iff `set` contains `oid`.
@@ -58,19 +74,24 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);
void oidset_clear(struct oidset *set);
struct oidset_iter {
- struct oidmap_iter m_iter;
+ kh_oid_t *set;
+ khiter_t iter;
};
static inline void oidset_iter_init(struct oidset *set,
struct oidset_iter *iter)
{
- oidmap_iter_init(&set->map, &iter->m_iter);
+ iter->set = &set->set;
+ iter->iter = kh_begin(iter->set);
}
static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)
{
- struct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);
- return e ? &e->oid : NULL;
+ for (; iter->iter != kh_end(iter->set); iter->iter++) {
+ if (kh_exist(iter->set, iter->iter))
+ return &kh_key(iter->set, iter->iter++);
+ }
+ return NULL;
}
static inline struct object_id *oidset_iter_first(struct oidset *set,