From 9e6fabde82e91366a7fea5a81e795d26bbe7e10d Mon Sep 17 00:00:00 2001 From: Jonathan Tan Date: Fri, 29 Sep 2017 15:54:22 -0700 Subject: 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 Signed-off-by: Junio C Hamano diff --git a/Makefile b/Makefile index ed4ca43..64136dd 100644 --- 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 105506e..008b25d 100644 --- 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 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 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 a6a08ba..f1f874a 100644 --- 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 b7eaab5..f4c9e0f 100644 --- 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`. -- cgit v0.10.2-6-g49f6