[3/5] strmap: add more utility functions

Commit Message

Linus Arver via GitGitGadget Aug. 21, 2020, 6:52 p.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_free()
  * strmap_get_item()

I suspect the first four are self-explanatory.

strmap_free() differs from strmap_clear() in that the data structure is
not reusable after it is called; strmap_clear() is not sufficient for
the API because without strmap_free() we will leak memory.

strmap_get_item() is similar to strmap_get() except that instead of just
returning the void* value that the string maps to, it returns the
string_list_item 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_item()
and then:
  * check if the string was in the map by whether the pointer is NULL
  * access the value via item->util
  * directly update item->util
meaning that we can replace two or three hash table lookups with one.

Signed-off-by: Elijah Newren <[e-mail]>
---
 strmap.c | 35 ++++++++++++++++++++++++++++++-----
 strmap.h | 43 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 73 insertions(+), 5 deletions(-)

Comments

Jeff King Aug. 21, 2020, 7:58 p.m. UTC | #1

On Fri, Aug 21, 2020 at 06:52:27PM +0000, Elijah Newren via GitGitGadget wrote:

> 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_free()
>   * strmap_get_item()
> 
> I suspect the first four are self-explanatory.

Yup, all make sense. We might also want real iterators rather than
strmap_for_each_entry(), which can be a bit more convenient given the
lack of lambdas in C. But I'd be happy to wait until a caller arises.

> strmap_free() differs from strmap_clear() in that the data structure is
> not reusable after it is called; strmap_clear() is not sufficient for
> the API because without strmap_free() we will leak memory.

Hmm, I missed in the previous function that strmap_clear() is actually
leaving allocated memory. I think this is bad, because it's unlike most
of our other data structure clear() functions.

We could work around it with the lazy-init stuff I mentioned in my last
email (i.e., _don't_ strmap_init() at the end of strmap_clear(), and
just let strmap_put() take care of initializing if somebody actually
adds something again).

But IMHO this is a sign that we should be fixing hashmap() to work like
that, too.

> strmap_get_item() is similar to strmap_get() except that instead of just
> returning the void* value that the string maps to, it returns the
> string_list_item 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

That makes sense. If you follow my suggestion to drop string_list_item,
then it would be OK to return the whole str_entry. (I forgot to mention
in the last patch, but perhaps strmap_entry would be a more distinctive
name).

> diff --git a/strmap.h b/strmap.h
> index eb5807f6fa..45d0a4f714 100644
> --- a/strmap.h
> +++ b/strmap.h
> @@ -21,6 +21,11 @@ void strmap_init(struct strmap *map);
>  /*
>   * Remove all entries from the map, releasing any allocated resources.
>   */
> +void strmap_free(struct strmap *map, int free_values);
> +
> +/*
> + * Same as calling strmap_free() followed by strmap_init().
> + */
>  void strmap_clear(struct strmap *map, int free_values);

I guess the docstring was a bit inaccurate in the previous patch, then. :)

-Peff

Patch

diff --git a/strmap.c b/strmap.c
index 1c9fdb3b1e..a4bfffcd8b 100644
--- a/strmap.c
+++ b/strmap.c
@@ -27,7 +27,7 @@  void strmap_init(struct strmap *map)
 	hashmap_init(&map->map, cmp_str_entry, NULL, 0);
 }
 
-void strmap_clear(struct strmap *map, int free_util)
+void strmap_free(struct strmap *map, int free_util)
 {
 	struct hashmap_iter iter;
 	struct str_entry *e;
@@ -35,12 +35,19 @@  void strmap_clear(struct strmap *map, int free_util)
 	if (!map)
 		return;
 
-	hashmap_for_each_entry(&map->map, &iter, e, ent /* member name */) {
-		free(e->item.string);
-		if (free_util)
-			free(e->item.util);
+	if (free_util) {
+		hashmap_for_each_entry(&map->map, &iter, e, ent) {
+			free(e->item.string);
+			if (free_util)
+				free(e->item.util);
+		}
 	}
 	hashmap_free_entries(&map->map, struct str_entry, ent);
+}
+
+void strmap_clear(struct strmap *map, int free_util)
+{
+	strmap_free(map, free_util);
 	strmap_init(map);
 }
 
@@ -69,6 +76,13 @@  void *strmap_put(struct strmap *map, const char *str, void *data)
 	return old;
 }
 
+struct string_list_item *strmap_get_item(struct strmap *map,
+					 const char *str)
+{
+	struct str_entry *entry = find_str_entry(map, str);
+	return entry ? &entry->item : NULL;
+}
+
 void *strmap_get(struct strmap *map, const char *str)
 {
 	struct str_entry *entry = find_str_entry(map, str);
@@ -79,3 +93,14 @@  int strmap_contains(struct strmap *map, const char *str)
 {
 	return find_str_entry(map, str) != NULL;
 }
+
+void strmap_remove(struct strmap *map, const char *str, int free_util)
+{
+	struct str_entry entry, *ret;
+	hashmap_entry_init(&entry.ent, strhash(str));
+	entry.item.string = (char *)str;
+	ret = hashmap_remove_entry(&map->map, &entry, ent, NULL);
+	if (ret && free_util)
+		free(ret->item.util);
+	free(ret);
+}
diff --git a/strmap.h b/strmap.h
index eb5807f6fa..45d0a4f714 100644
--- a/strmap.h
+++ b/strmap.h
@@ -21,6 +21,11 @@  void strmap_init(struct strmap *map);
 /*
  * Remove all entries from the map, releasing any allocated resources.
  */
+void strmap_free(struct strmap *map, int free_values);
+
+/*
+ * Same as calling strmap_free() followed by strmap_init().
+ */
 void strmap_clear(struct strmap *map, int free_values);
 
 /*
@@ -32,6 +37,12 @@  void strmap_clear(struct strmap *map, int free_values);
  */
 void *strmap_put(struct strmap *map, const char *str, void *data);
 
+/*
+ * Return the string_list_item mapped by "str", or NULL if there is not such
+ * an item in map.
+ */
+struct string_list_item *strmap_get_item(struct strmap *map, const char *str);
+
 /*
  * Return the data pointer mapped by "str", or NULL if the entry does not
  * exist.
@@ -44,4 +55,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 str_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 */