patchoidmap: 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.
> 
> oidset has been updated to use oidmap.

> On 09/27, Jonathan Tan wrote:
> > 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.
> > 
> > oidset has been updated to use oidmap.
> 
> After a quick glance at the code, I think it looks good.  I do have one
> suggestion though.  This map is structured much like our internal
> hashmap where if you want to include any data you have to implement your
> own struct with the internal 'entry' struct as the first member in your
> custom struct.  I personal dislike this method, despite the potential
> memory savings, because it makes the data structure much more difficult
> to use.
> 
> If all i wanted was a map from 'OID -> const char *' then I would need
> to write all the boilerplate code to make a struct which contains the
> map 'entry' struct + the 'const char *' entry.
>
> You are also making the
> caller responsible for allocating the individual entries instead of
> letting the data structure take care of that internally.

> > To me it seems like a much simpler API for a map would be to just allow
> > callers to store a 'void *' as the value.
> 
> I agree that the API would be simpler.
> 
> My main motivation with this design is indeed to save memory, and not
> inconvenience the user too much (in the case where you're storing things
> larger than one pointer, you just need to remember to put the special
> struct at the beginning of your struct), but if memory is not so
> important, I agree that we can switch to the "util" design.

> When I saw that you were implementing "oidset" in terms of "oidmap", I
> was all ready to be crabby about this extra memory. But then I saw that
> the implementation tries hard not to waste any memory. :)
> 
> All of which is to say I gave this some thought when I was in the "ready
> to be crabby" phase, and came to the conclusion that it probably isn't
> that painful. An unused pointer is 8 bytes per entry. We're already
> spending 20 for the oid itself (which is likely to grow to 32
> eventually), plus 8 for the chained "next" pointer. Plus potentially 8
> for a padded version of the hash, if we just use a straight hashmap that
> duplicates the hash field.
> 
> So depending how you count it, we're wasting between 28% (sha1 and no
> extra hash) and 16% (sha256 plus reusing hashmap). That's not great, but
> it's probably not breaking the bank.

> Another way of thinking about it. Large-ish (but not insane) repos have
> on the order of 5-10 million objects. If we had an oidset that mentioned
> every single object in the repository, that's 40-80MB wasted in the
> worst case. For current uses of oidset, that's probably fine. It's
> generally used only to collect ref tips (so probably two orders of
> magnitude less).
> 
> If you're planning on using an oidset to mark every object in a
> 100-million-object monorepo, we'd probably care more. But I'd venture to
> say that any scheme which involves generating that hash table on the fly
> is doing it wrong. At at that scale we'd want to look at compact
> mmap-able on-disk representations.

> > So depending how you count it, we're wasting between 28% (sha1 and no
> > extra hash) and 16% (sha256 plus reusing hashmap). That's not great, but
> > it's probably not breaking the bank.
> 
> Hmm...how did you get the 16% figure? The values, as I see it, are:
>  - 32 for the sha256 hash itself
>  - 8 for the "next" chain pointer
>  - 8 for the padded hash
>  - 8 for the "util" pointer
> 
> For an oidset, the padded hash and the "util" pointer are wasted, which is
> 16/56=0.286. (If you assume, say, 8 bytes of malloc bookkeeping overhead, then
> 16/64=0.25.)

> > So I think we may be better off going with the solution here that's
> > simpler and requires introducing less code. If it does turn out to be a
> > memory problem in the future, this is a _really_ easy thing to optimize
> > after the fact, because we have these nice abstractions.
> 
> Optimizing away the padded hash should be straightforward. Optimizing away the
> "util" pointer after we have code that uses it is (slightly?) less
> straightforward, but still doable.

> I still lean towards saving memory by eliminating the padded hash and
> not using the "util" pointer, because the complication is contained
> within only two files (oidmap.{c,h}), and because the constant factors
> in memory savings might end up mattering. But I don't feel strongly
> about that - I think any of the oidmaps that we have discussed is an
> improvement over what we have now.

> If you're planning on using an oidset to mark every object in a
> 100-million-object monorepo, we'd probably care more. But I'd venture to
> say that any scheme which involves generating that hash table on the fly
> is doing it wrong. At at that scale we'd want to look at compact
> mmap-able on-disk representations.

> On Thu, 28 Sep 2017, Jeff King wrote:
> 
> > If you're planning on using an oidset to mark every object in a
> > 100-million-object monorepo, we'd probably care more. But I'd venture to
> > say that any scheme which involves generating that hash table on the fly
> > is doing it wrong. At at that scale we'd want to look at compact
> > mmap-able on-disk representations.
> 
> Or maybe you would look at a *not-so-compact* mmap()able on-disk
> representation, to allow for painless updates.
> 
> You really will want to avoid having to write out large files just because
> a small part of them changed. We learn that lesson the hard way, from
> having to write 350MB worth of .git/index for every single, painful `git
> add` operation.

>  Makefile |   1 +
>  oidmap.c | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  oidmap.h |  98 ++++++++++++++++++++++++++++++++++++++++
>  oidset.c |  38 ++++------------
>  oidset.h |   4 +-
>  5 files changed, 263 insertions(+), 30 deletions(-)
>  create mode 100644 oidmap.c
>  create mode 100644 oidmap.h
>
> diff --git a/Makefile b/Makefile
> index ed4ca438b..64136dde4 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/oidmap.c b/oidmap.c
> new file mode 100644
> index 000000000..40e696cee
> --- /dev/null
> +++ b/oidmap.c
> @@ -0,0 +1,152 @@
> +#include "cache.h"
> +#include "oidmap.h"
> +
> +#define OIDMAP_INITIAL_SIZE 64
> +/* grow / shrink by 2^2 */
> +#define OIDMAP_RESIZE_BITS 2
> +/* load factor in percent */
> +#define OIDMAP_LOAD_FACTOR 80
> +
> +static void alloc_table(struct oidmap *map, unsigned int size)
> +{
> +	map->tablesize = size;
> +	map->table = xcalloc(size, sizeof(struct oidmap_entry *));
> +
> +	/* calculate resize thresholds for new size */
> +	map->grow_at = (unsigned int) ((uint64_t) size * OIDMAP_LOAD_FACTOR / 100);
> +	if (size <= OIDMAP_INITIAL_SIZE)
> +		map->shrink_at = 0;
> +	else
> +		/*
> +		 * The shrink-threshold must be slightly smaller than
> +		 * (grow-threshold / resize-factor) to prevent erratic resizing,
> +		 * thus we divide by (resize-factor + 1).
> +		 */
> +		map->shrink_at = map->grow_at / ((1 << OIDMAP_RESIZE_BITS) + 1);
> +}
> +
> +static inline unsigned int bucket(const struct oidmap *map,
> +				  const struct object_id *key)
> +{
> +	unsigned int hash;
> +	memcpy(&hash, key->hash, sizeof(hash));
> +	return hash & (map->tablesize - 1);
> +}
> +
> +static void rehash(struct oidmap *map, unsigned int newsize)
> +{
> +	unsigned int i, oldsize = map->tablesize;
> +	struct oidmap_entry **oldtable = map->table;
> +
> +	alloc_table(map, newsize);
> +	for (i = 0; i < oldsize; i++) {
> +		struct oidmap_entry *e = oldtable[i];
> +		while (e) {
> +			struct oidmap_entry *next = e->next;
> +			unsigned int b = bucket(map, &e->oid);
> +			e->next = map->table[b];
> +			map->table[b] = e;
> +			e = next;
> +		}
> +	}
> +	free(oldtable);
> +}
> +
> +static inline struct oidmap_entry **find_entry_ptr(const struct oidmap *map,
> +						   const struct object_id *key)
> +{
> +	struct oidmap_entry **e = &map->table[bucket(map, key)];
> +	while (*e && oidcmp(&(*e)->oid, key))
> +		e = &(*e)->next;
> +	return e;
> +}
> +
> +void oidmap_init(struct oidmap *map, size_t initial_size)
> +{
> +	unsigned int size = OIDMAP_INITIAL_SIZE;
> +
> +	memset(map, 0, sizeof(*map));
> +
> +	/* calculate initial table size and allocate the table */
> +	initial_size = (unsigned int) ((uint64_t) initial_size * 100
> +			/ OIDMAP_LOAD_FACTOR);
> +	while (initial_size > size)
> +		size <<= OIDMAP_RESIZE_BITS;
> +	alloc_table(map, size);
> +
> +	/*
> +	 * Keep track of the number of items in the map and
> +	 * allow the map to automatically grow as necessary.
> +	 */
> +	map->do_count_items = 1;
> +}
> +
> +void oidmap_free(struct oidmap *map, int free_entries)
> +{
> +	if (!map || !map->table)
> +		return;
> +	if (free_entries) {
> +		int i;
> +		for (i = 0; i < map->tablesize; i++) {
> +			struct oidmap_entry *e = map->table[i];
> +			while (e) {
> +				struct oidmap_entry *next = e->next;
> +				free(e);
> +				e = next;
> +			}
> +		}
> +	}
> +	free(map->table);
> +	memset(map, 0, sizeof(*map));
> +}
> +
> +void *oidmap_get(const struct oidmap *map, const struct object_id *key)
> +{
> +	return *find_entry_ptr(map, key);
> +}
> +
> +static void oidmap_add(struct oidmap *map, struct oidmap_entry *entry)
> +{
> +	unsigned int b = bucket(map, &entry->oid);
> +
> +	/* add entry */
> +	entry->next = map->table[b];
> +	map->table[b] = entry;
> +
> +	/* fix size and rehash if appropriate */
> +	if (map->do_count_items) {
> +		map->private_size++;
> +		if (map->private_size > map->grow_at)
> +			rehash(map, map->tablesize << OIDMAP_RESIZE_BITS);
> +	}
> +}
> +
> +void *oidmap_remove(struct oidmap *map, const struct object_id *key)
> +{
> +	struct oidmap_entry *old;
> +	struct oidmap_entry **e = find_entry_ptr(map, key);
> +	if (!*e)
> +		return NULL;
> +
> +	/* remove existing entry */
> +	old = *e;
> +	*e = old->next;
> +	old->next = NULL;
> +
> +	/* fix size and rehash if appropriate */
> +	if (map->do_count_items) {
> +		map->private_size--;
> +		if (map->private_size < map->shrink_at)
> +			rehash(map, map->tablesize >> OIDMAP_RESIZE_BITS);
> +	}
> +
> +	return old;
> +}
> +
> +void *oidmap_put(struct oidmap *map, void *entry)
> +{
> +	struct oidmap_entry *to_put = entry;
> +	struct oidmap_entry *old = oidmap_remove(map, &to_put->oid);
> +	oidmap_add(map, to_put);
> +	return old;
> +}
> diff --git a/oidmap.h b/oidmap.h
> new file mode 100644
> index 000000000..a543ed828
> --- /dev/null
> +++ b/oidmap.h
> @@ -0,0 +1,98 @@
> +#ifndef OIDMAP_H
> +#define OIDMAP_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. It must be
> + * zero-initialized (or use OIDMAP_ENTRY_INIT).
> + */
> +struct oidmap_entry {
> +	/*
> +	 * next points to the next entry in case of collisions (i.e. if
> +	 * multiple entries map to the same bucket). For oidmap's internal use
> +	 * only.
> +	 */
> +	struct oidmap_entry *next;
> +
> +	struct object_id oid;
> +};
> +#define OIDMAP_ENTRY_INIT { NULL }
> +
> +/*
> + * struct oidmap is the hash table structure. Members can be used as follows,
> + * but should not be modified directly.
> + */
> +struct oidmap {
> +	struct oidmap_entry **table;
> +
> +	/* total number of entries (0 means the hashmap is empty) */
> +	unsigned int private_size; /* use oidmap_get_size() */
> +
> +	/*
> +	 * tablesize is the allocated size of the hash table. A non-0 value
> +	 * indicates that the hashmap is initialized. It may also be useful
> +	 * for statistical purposes (i.e. `size / tablesize` is the current
> +	 * load factor).
> +	 */
> +	unsigned int tablesize;
> +
> +	unsigned int grow_at;
> +	unsigned int shrink_at;
> +
> +	unsigned int do_count_items : 1;
> +};
> +
> +/* oidmap functions */
> +
> +/*
> + * 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);
> +
> +/*
> + * Return the number of items in the map.
> + */
> +static inline unsigned int oidmap_get_size(struct oidmap *map)
> +{
> +	if (map->do_count_items)
> +		return map->private_size;
> +
> +	BUG("oidmap_get_size: size not set");
> +	return 0;
> +}
> +
> +/*
> + * 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.
> + *
> + * 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 a6a08ba52..6fe7036c4 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.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.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));
> +	entry = xcalloc(1, sizeof(*entry));
>  	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 b7eaab5b8..b1ec82bfc 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,7 +19,7 @@
>   * A single oidset; should be zero-initialized (or use OIDSET_INIT).
>   */
>  struct oidset {
> -	struct hashmap map;
> +	struct oidmap map;
>  };
>  
>  #define OIDSET_INIT { { NULL } }

> Jonathan Tan <jonathantanmy@google.com> writes:
> 
> > 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.
> 
> A naïve question is why this needs to duplicate so much code, just
> to build something similar in spirit to hashmap but unlike hashmap
> that can take caller-defined keys, limited to using oid as the keys,
> instead of just being a thin API wrapper that uses hashmap as its
> internal implementation detail.  
> 
> Is the way hashmap API is structured so hard to use it in such a
> way, or something?

> 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>
> ---
> Some replies to v1 [1] [2] seem to indicate that simpler non-duplicated
> code should be preferred over optimizing away the storage of the 4-byte
> hash code, and I have no objection to that, so I have updated this code
> to be a thin wrapper over hashmap with the 4-byte overhead.
> 
> After this patch, if the 4-byte overhead is found to be too much, we can
> migrate to something similar to v1 relatively easily.
> 
> I decided not to go with the util pointer method because we will not be
> able to migrate away from it so easily if need be.

> 
> [1] https://public-inbox.org/git/xmqqr2ur348z.fsf@gitster.mtv.corp.google.com/
> [2] https://public-inbox.org/git/20170929192624.4ukvpjujgiyzgibb@sigill.intra.peff.net/
> ---
>  Makefile     |  1 +
>  fetch-pack.c |  2 +-
>  oidmap.c     | 51 +++++++++++++++++++++++++++++++++++++++++++++
>  oidmap.h     | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  oidset.c     | 36 +++++++-------------------------
>  oidset.h     |  6 ++++--
>  6 files changed, 133 insertions(+), 31 deletions(-)
>  create mode 100644 oidmap.c
>  create mode 100644 oidmap.h
> 
> diff --git a/Makefile b/Makefile
> index ed4ca438b..64136dde4 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 105506e9a..008b25d3d 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 000000000..6db4fffcd
> --- /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 000000000..18f54cde1
> --- /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 a6a08ba52..f1f874aaa 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 b7eaab5b8..f4c9e0f9c 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`.
> -- 
> 2.14.2.822.g60be5d43e6-goog
> 

> > Some replies to v1 [1] [2] seem to indicate that simpler non-duplicated
> > code should be preferred over optimizing away the storage of the 4-byte
> > hash code, and I have no objection to that, so I have updated this code
> > to be a thin wrapper over hashmap with the 4-byte overhead.
> > 
> > After this patch, if the 4-byte overhead is found to be too much, we can
> > migrate to something similar to v1 relatively easily.
> > 
> > I decided not to go with the util pointer method because we will not be
> > able to migrate away from it so easily if need be.
> 
> This makes me a bit sad because I tend to lean more towards making
> things simpler.  I'm still a supporter of the 'util' pointer but I
> understand why we would choose otherwise.

> Right, I kind of wonder if this has fallen into an uncanny value where
> we have this almost-hashmap infrastructure, but the end result is not
> significantly easier to use than a plain-old hashmap.
>
> I.e., it looks like you still have to declare something like:
>
>   struct my_data {
>         struct oidmap_entry oid;
>         int value; /* mapping to an int */
>   };
>
> and handle the allocation of the entry yourself. If we instead just
> adding an oidhash() and oidcmpfn(), then callers could those directly.

> On Tue, Oct 03, 2017 at 05:29:01PM -0700, Jonathan Tan wrote:
>
>> At this point I decided that I prefer the thin wrapper, but the "light
>> touch" (struct oidmap_entry, oidcmpfn(), oidmap_get() only) still
>> better than the status quo.
>
> OK. I can certainly live with that. And worst case, I suppose, is that a
> caller wants some underlying hashmap function and we just have to extend
> the oidmap API to include it. It's not like we're adding new hashmap
> functions willy-nilly.