From: Brandon Williams <bmwill@google.com>
To: Jonathan Tan <jonathantanmy@google.com>
Cc: git@vger.kernel.org, gitster@pobox.com, peff@peff.net
Subject: Re: [PATCH v2] oidmap: map with OID as key
Date: Mon, 2 Oct 2017 16:48:48 -0700 [thread overview]
Message-ID: <20171002234848.GG5189@google.com> (raw)
In-Reply-To: <20170929225422.81467-1-jonathantanmy@google.com>
On 09/29, 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.
>
> 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.
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.
>
> [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
>
--
Brandon Williams
next prev parent reply other threads:[~2017-10-02 23:48 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-09-27 22:19 [PATCH] oidmap: map with OID as key Jonathan Tan
2017-09-28 0:41 ` Brandon Williams
2017-09-28 17:46 ` Jonathan Tan
2017-09-28 20:05 ` Jeff King
2017-09-29 19:04 ` Jonathan Tan
2017-09-29 19:26 ` Jeff King
2017-09-29 21:43 ` Johannes Schindelin
2017-09-29 23:24 ` Jeff King
2017-09-28 3:13 ` Junio C Hamano
2017-09-28 17:38 ` Jonathan Tan
2017-09-29 22:54 ` [PATCH v2] " Jonathan Tan
2017-10-02 23:48 ` Brandon Williams [this message]
2017-10-03 6:31 ` Jeff King
2017-10-04 0:29 ` Jonathan Tan
2017-10-04 7:45 ` Jeff King
2017-10-04 8:48 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171002234848.GG5189@google.com \
--to=bmwill@google.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jonathantanmy@google.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).