diff options
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | fetch-pack.c | 2 | ||||
| -rw-r--r-- | oidmap.c | 51 | ||||
| -rw-r--r-- | oidmap.h | 68 | ||||
| -rw-r--r-- | oidset.c | 36 | ||||
| -rw-r--r-- | oidset.h | 6 |
6 files changed, 133 insertions, 31 deletions
@@ -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 105506e9aa..008b25d3db 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 0000000000..6db4fffcdb --- /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 0000000000..18f54cde14 --- /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 @@ -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); } @@ -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`. |