[v2,06/10] strmap: add more utility functions

Commit Message

Elijah Newren Oct. 13, 2020, 12:40 a.m. UTC

From: Elijah Newren <[e-mail]>

This adds a number of additional convienence functions I want/need:
  * strmap_empty()
  * strmap_get_size()
  * strmap_remove()
  * strmap_for_each_entry()
  * strmap_get_entry()

I suspect the first four are self-explanatory.

strmap_get_entry() is similar to strmap_get() except that instead of just
returning the void* value that the string maps to, it returns the
strmap_entry that contains both the string and the void* value (or
NULL if the string isn't in the map).  This is helpful because it avoids
multiple lookups, e.g. in some cases a caller would need to call:
  * strmap_contains() to check that the map has an entry for the string
  * strmap_get() to get the void* value
  * <do some work to update the value>
  * strmap_put() to update/overwrite the value
If the void* pointer returned really is a pointer, then the last step is
unnecessary, but if the void* pointer is just cast to an integer then
strmap_put() will be needed.  In contrast, one can call strmap_get_entry()
and then:
  * check if the string was in the map by whether the pointer is NULL
  * access the value via entry->value
  * directly update entry->value
meaning that we can replace two or three hash table lookups with one.

Signed-off-by: Elijah Newren <[e-mail]>
---
 strmap.c | 20 ++++++++++++++++++++
 strmap.h | 38 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+)

Comments

Jeff King Oct. 30, 2020, 2:23 p.m. UTC | #1

On Tue, Oct 13, 2020 at 12:40:46AM +0000, Elijah Newren via GitGitGadget wrote:

> strmap_get_entry() is similar to strmap_get() except that instead of just
> returning the void* value that the string maps to, it returns the
> strmap_entry that contains both the string and the void* value (or
> NULL if the string isn't in the map).  This is helpful because it avoids
> multiple lookups, e.g. in some cases a caller would need to call:
>   * strmap_contains() to check that the map has an entry for the string
>   * strmap_get() to get the void* value
>   * <do some work to update the value>
>   * strmap_put() to update/overwrite the value

Oh, I guess I should have read ahead when responding to the last patch. :)

Yes, this function makes perfect sense to have (along with the simpler
alternatives for the callers that don't need this complexity).

>  strmap.c | 20 ++++++++++++++++++++
>  strmap.h | 38 ++++++++++++++++++++++++++++++++++++++

The implementation all looks pretty straight-forward.

> +void strmap_remove(struct strmap *map, const char *str, int free_util)
> +{
> +	struct strmap_entry entry, *ret;
> +	hashmap_entry_init(&entry.ent, strhash(str));
> +	entry.key = str;
> +	ret = hashmap_remove_entry(&map->map, &entry, ent, NULL);
> +	if (!ret)
> +		return;
> +	if (free_util)
> +		free(ret->value);
> +	if (map->strdup_strings)
> +		free((char*)ret->key);
> +	free(ret);
> +}

Another spot that would be simplified by using FLEXPTRs. :)

> +/*
> + * Return whether the strmap is empty.
> + */
> +static inline int strmap_empty(struct strmap *map)
> +{
> +	return hashmap_get_size(&map->map) == 0;
> +}

Maybe:

  return strmap_get_size(&map) == 0;

would be slightly simpler (and more importantly, show callers the
equivalence between the two).

> +/*
> + * iterate through @map using @iter, @var is a pointer to a type strmap_entry
> + */
> +#define strmap_for_each_entry(mystrmap, iter, var)	\
> +	for (var = hashmap_iter_first_entry_offset(&(mystrmap)->map, iter, \
> +						   OFFSETOF_VAR(var, ent)); \
> +		var; \
> +		var = hashmap_iter_next_entry_offset(iter, \
> +						     OFFSETOF_VAR(var, ent)))

Makes sense. This is like hashmap_for_each_entry, but we don't need
anyone to tell us the offset of "ent" within the struct.

I suspect we need the same "var = NULL" that hashmap recently got in
0ad621f61e (hashmap_for_each_entry(): workaround MSVC's runtime check
failure #3, 2020-09-30). Alternatively, I think you could drop
OFFSETOF_VAR completely in favor offsetof(struct strmap_entry, ent).

In fact, since we know the correct type for "var", we _could_ declare it
ourselves in a new block enclosing the loop. But that is probably making
the code too magic; people reading the code would say "huh? where is
entry declared?".

-Peff

Elijah Newren Oct. 30, 2020, 4:43 p.m. UTC | #2

On Fri, Oct 30, 2020 at 7:23 AM Jeff King <[e-mail]> wrote:
>
> On Tue, Oct 13, 2020 at 12:40:46AM +0000, Elijah Newren via GitGitGadget wrote:
>
> > strmap_get_entry() is similar to strmap_get() except that instead of just
> > returning the void* value that the string maps to, it returns the
> > strmap_entry that contains both the string and the void* value (or
> > NULL if the string isn't in the map).  This is helpful because it avoids
> > multiple lookups, e.g. in some cases a caller would need to call:
> >   * strmap_contains() to check that the map has an entry for the string
> >   * strmap_get() to get the void* value
> >   * <do some work to update the value>
> >   * strmap_put() to update/overwrite the value
>
> Oh, I guess I should have read ahead when responding to the last patch. :)
>
> Yes, this function makes perfect sense to have (along with the simpler
> alternatives for the callers that don't need this complexity).
>
> >  strmap.c | 20 ++++++++++++++++++++
> >  strmap.h | 38 ++++++++++++++++++++++++++++++++++++++
>
> The implementation all looks pretty straight-forward.
>
> > +void strmap_remove(struct strmap *map, const char *str, int free_util)
> > +{
> > +     struct strmap_entry entry, *ret;
> > +     hashmap_entry_init(&entry.ent, strhash(str));
> > +     entry.key = str;
> > +     ret = hashmap_remove_entry(&map->map, &entry, ent, NULL);
> > +     if (!ret)
> > +             return;
> > +     if (free_util)
> > +             free(ret->value);
> > +     if (map->strdup_strings)
> > +             free((char*)ret->key);
> > +     free(ret);
> > +}
>
> Another spot that would be simplified by using FLEXPTRs. :)
>
> > +/*
> > + * Return whether the strmap is empty.
> > + */
> > +static inline int strmap_empty(struct strmap *map)
> > +{
> > +     return hashmap_get_size(&map->map) == 0;
> > +}
>
> Maybe:
>
>   return strmap_get_size(&map) == 0;
>
> would be slightly simpler (and more importantly, show callers the
> equivalence between the two).

Makes sense; will change it.

> > +/*
> > + * iterate through @map using @iter, @var is a pointer to a type strmap_entry
> > + */
> > +#define strmap_for_each_entry(mystrmap, iter, var)   \
> > +     for (var = hashmap_iter_first_entry_offset(&(mystrmap)->map, iter, \
> > +                                                OFFSETOF_VAR(var, ent)); \
> > +             var; \
> > +             var = hashmap_iter_next_entry_offset(iter, \
> > +                                                  OFFSETOF_VAR(var, ent)))
>
> Makes sense. This is like hashmap_for_each_entry, but we don't need
> anyone to tell us the offset of "ent" within the struct.
>
> I suspect we need the same "var = NULL" that hashmap recently got in
> 0ad621f61e (hashmap_for_each_entry(): workaround MSVC's runtime check
> failure #3, 2020-09-30). Alternatively, I think you could drop
> OFFSETOF_VAR completely in favor offsetof(struct strmap_entry, ent).
>
> In fact, since we know the correct type for "var", we _could_ declare it
> ourselves in a new block enclosing the loop. But that is probably making
> the code too magic; people reading the code would say "huh? where is
> entry declared?".

Actually, since we know ent is the first entry in strmap, the offset
is always 0.  So can't we just avoid OFFSETOF_VAR() and offsetof()
entirely, by just using hashmap_iter_first() and hashmap_iter_next()?
I'm going to try that.

Jeff King Nov. 3, 2020, 4:12 p.m. UTC | #3

On Fri, Oct 30, 2020 at 09:43:33AM -0700, Elijah Newren wrote:

> > I suspect we need the same "var = NULL" that hashmap recently got in
> > 0ad621f61e (hashmap_for_each_entry(): workaround MSVC's runtime check
> > failure #3, 2020-09-30). Alternatively, I think you could drop
> > OFFSETOF_VAR completely in favor offsetof(struct strmap_entry, ent).
> >
> > In fact, since we know the correct type for "var", we _could_ declare it
> > ourselves in a new block enclosing the loop. But that is probably making
> > the code too magic; people reading the code would say "huh? where is
> > entry declared?".
> 
> Actually, since we know ent is the first entry in strmap, the offset
> is always 0.  So can't we just avoid OFFSETOF_VAR() and offsetof()
> entirely, by just using hashmap_iter_first() and hashmap_iter_next()?
> I'm going to try that.

Yes, I think that would work fine. You may want to add a comment to the
struct indicating that it's important for the hashmap_entry to be at the
front of the struct. Using offsetof() means that it's impossible to get
it wrong, though.

-Peff

Patch

diff --git a/strmap.c b/strmap.c
index 4b48d64274..909b9fbedf 100644
--- a/strmap.c
+++ b/strmap.c
@@ -90,6 +90,11 @@  void *strmap_put(struct strmap *map, const char *str, void *data)
 	return old;
 }
 
+struct strmap_entry *strmap_get_entry(struct strmap *map, const char *str)
+{
+	return find_strmap_entry(map, str);
+}
+
 void *strmap_get(struct strmap *map, const char *str)
 {
 	struct strmap_entry *entry = find_strmap_entry(map, str);
@@ -100,3 +105,18 @@  int strmap_contains(struct strmap *map, const char *str)
 {
 	return find_strmap_entry(map, str) != NULL;
 }
+
+void strmap_remove(struct strmap *map, const char *str, int free_util)
+{
+	struct strmap_entry entry, *ret;
+	hashmap_entry_init(&entry.ent, strhash(str));
+	entry.key = str;
+	ret = hashmap_remove_entry(&map->map, &entry, ent, NULL);
+	if (!ret)
+		return;
+	if (free_util)
+		free(ret->value);
+	if (map->strdup_strings)
+		free((char*)ret->key);
+	free(ret);
+}
diff --git a/strmap.h b/strmap.h
index 493d19cbc0..e49d020970 100644
--- a/strmap.h
+++ b/strmap.h
@@ -42,6 +42,12 @@  void strmap_clear(struct strmap *map, int free_values);
  */
 void *strmap_put(struct strmap *map, const char *str, void *data);
 
+/*
+ * Return the strmap_entry mapped by "str", or NULL if there is not such
+ * an item in map.
+ */
+struct strmap_entry *strmap_get_entry(struct strmap *map, const char *str);
+
 /*
  * Return the data pointer mapped by "str", or NULL if the entry does not
  * exist.
@@ -54,4 +60,36 @@  void *strmap_get(struct strmap *map, const char *str);
  */
 int strmap_contains(struct strmap *map, const char *str);
 
+/*
+ * Remove the given entry from the strmap.  If the string isn't in the
+ * strmap, the map is not altered.
+ */
+void strmap_remove(struct strmap *map, const char *str, int free_value);
+
+/*
+ * Return whether the strmap is empty.
+ */
+static inline int strmap_empty(struct strmap *map)
+{
+	return hashmap_get_size(&map->map) == 0;
+}
+
+/*
+ * Return how many entries the strmap has.
+ */
+static inline unsigned int strmap_get_size(struct strmap *map)
+{
+	return hashmap_get_size(&map->map);
+}
+
+/*
+ * iterate through @map using @iter, @var is a pointer to a type strmap_entry
+ */
+#define strmap_for_each_entry(mystrmap, iter, var)	\
+	for (var = hashmap_iter_first_entry_offset(&(mystrmap)->map, iter, \
+						   OFFSETOF_VAR(var, ent)); \
+		var; \
+		var = hashmap_iter_next_entry_offset(iter, \
+						     OFFSETOF_VAR(var, ent)))
+
 #endif /* STRMAP_H */