diff mbox series

[v5,12/15] strmap: enable allocations to come from a mem_pool

Message ID 34f542d9dd846da5fd81274966ee2ebe0660dcef.1604622299.git.gitgitgadget@gmail.com (mailing list archive)
State Superseded
Headers show
Series Add struct strmap and associated utility functions | expand

Commit Message

Elijah Newren Nov. 6, 2020, 12:24 a.m. UTC 
From: Elijah Newren <newren@gmail.com>

For heavy users of strmaps, allowing the keys and entries to be
allocated from a memory pool can provide significant overhead savings.
Add an option to strmap_init_with_options() to specify a memory pool.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 strmap.c | 31 ++++++++++++++++++++++---------
 strmap.h | 11 ++++++++---
 2 files changed, 30 insertions(+), 12 deletions(-)

Comments

Phillip Wood Nov. 11, 2020, 5:33 p.m. UTC | #1 
Hi Elijah

On 06/11/2020 00:24, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> For heavy users of strmaps, allowing the keys and entries to be
> allocated from a memory pool can provide significant overhead savings.
> Add an option to strmap_init_with_options() to specify a memory pool.
> [...]
> diff --git a/strmap.h b/strmap.h
> index c8c4d7c932..dda928703d 100644
> --- a/strmap.h
> +++ b/strmap.h
> @@ -3,8 +3,10 @@
>   
>   #include "hashmap.h"
>   
> +struct mempool;

I think this is a typo - I assume you wanted to declare `struct 
mem_pool` but it's not strictly necessary as you're only adding a 
pointer to the struct below.

Best Wishes

Phillip

>   struct strmap {
>   	struct hashmap map;
> +	struct mem_pool *pool;
>   	unsigned int strdup_strings:1;
>   };
>   
> @@ -37,9 +39,10 @@ void strmap_init(struct strmap *map);
>   
>   /*
>    * Same as strmap_init, but for those who want to control the memory management
> - * carefully instead of using the default of strdup_strings=1.
> + * carefully instead of using the default of strdup_strings=1 and pool=NULL.
>    */
>   void strmap_init_with_options(struct strmap *map,
> +			      struct mem_pool *pool,
>   			      int strdup_strings);
>   
>   /*
> @@ -137,9 +140,10 @@ static inline void strintmap_init(struct strintmap *map, int default_value)
>   
>   static inline void strintmap_init_with_options(struct strintmap *map,
>   					       int default_value,
> +					       struct mem_pool *pool,
>   					       int strdup_strings)
>   {
> -	strmap_init_with_options(&map->map, strdup_strings);
> +	strmap_init_with_options(&map->map, pool, strdup_strings);
>   	map->default_value = default_value;
>   }
>   
> @@ -221,9 +225,10 @@ static inline void strset_init(struct strset *set)
>   }
>   
>   static inline void strset_init_with_options(struct strset *set,
> +					    struct mem_pool *pool,
>   					    int strdup_strings)
>   {
> -	strmap_init_with_options(&set->map, strdup_strings);
> +	strmap_init_with_options(&set->map, pool, strdup_strings);
>   }
>   
>   static inline void strset_clear(struct strset *set)
>
Elijah Newren Nov. 11, 2020, 6:49 p.m. UTC | #2 
On Wed, Nov 11, 2020 at 9:33 AM Phillip Wood <phillip.wood123@gmail.com> wrote:
>
> Hi Elijah
>
> On 06/11/2020 00:24, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> >
> > For heavy users of strmaps, allowing the keys and entries to be
> > allocated from a memory pool can provide significant overhead savings.
> > Add an option to strmap_init_with_options() to specify a memory pool.
> > [...]
> > diff --git a/strmap.h b/strmap.h
> > index c8c4d7c932..dda928703d 100644
> > --- a/strmap.h
> > +++ b/strmap.h
> > @@ -3,8 +3,10 @@
> >
> >   #include "hashmap.h"
> >
> > +struct mempool;
>
> I think this is a typo - I assume you wanted to declare `struct
> mem_pool` but it's not strictly necessary as you're only adding a
> pointer to the struct below.
>
> Best Wishes
>
> Phillip

Indeed, thanks.

>
> >   struct strmap {
> >       struct hashmap map;
> > +     struct mem_pool *pool;
> >       unsigned int strdup_strings:1;
> >   };
> >
> > @@ -37,9 +39,10 @@ void strmap_init(struct strmap *map);
> >
> >   /*
> >    * Same as strmap_init, but for those who want to control the memory management
> > - * carefully instead of using the default of strdup_strings=1.
> > + * carefully instead of using the default of strdup_strings=1 and pool=NULL.
> >    */
> >   void strmap_init_with_options(struct strmap *map,
> > +                           struct mem_pool *pool,
> >                             int strdup_strings);
> >
> >   /*
> > @@ -137,9 +140,10 @@ static inline void strintmap_init(struct strintmap *map, int default_value)
> >
> >   static inline void strintmap_init_with_options(struct strintmap *map,
> >                                              int default_value,
> > +                                            struct mem_pool *pool,
> >                                              int strdup_strings)
> >   {
> > -     strmap_init_with_options(&map->map, strdup_strings);
> > +     strmap_init_with_options(&map->map, pool, strdup_strings);
> >       map->default_value = default_value;
> >   }
> >
> > @@ -221,9 +225,10 @@ static inline void strset_init(struct strset *set)
> >   }
> >
> >   static inline void strset_init_with_options(struct strset *set,
> > +                                         struct mem_pool *pool,
> >                                           int strdup_strings)
> >   {
> > -     strmap_init_with_options(&set->map, strdup_strings);
> > +     strmap_init_with_options(&set->map, pool, strdup_strings);
> >   }
> >
> >   static inline void strset_clear(struct strset *set)
> >
Jeff King Nov. 11, 2020, 7:01 p.m. UTC | #3 
On Wed, Nov 11, 2020 at 05:33:47PM +0000, Phillip Wood wrote:

> On 06/11/2020 00:24, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> > 
> > For heavy users of strmaps, allowing the keys and entries to be
> > allocated from a memory pool can provide significant overhead savings.
> > Add an option to strmap_init_with_options() to specify a memory pool.
> > [...]
> > diff --git a/strmap.h b/strmap.h
> > index c8c4d7c932..dda928703d 100644
> > --- a/strmap.h
> > +++ b/strmap.h
> > @@ -3,8 +3,10 @@
> >   #include "hashmap.h"
> > +struct mempool;
> 
> I think this is a typo - I assume you wanted to declare `struct mem_pool`
> but it's not strictly necessary as you're only adding a pointer to the
> struct below.

Good catch.

Even if we're only using a pointer to it, we still need a valid forward
declaration (using the pointer only saves us from needing the full
definition). Or so I thought.

It looks like the compiler will treat the use inside the struct:

> >   struct strmap {
> >   	struct hashmap map;
> > +	struct mem_pool *pool;
> >   	unsigned int strdup_strings:1;
> >   };

as an implicit forward declaration, but not the ones inside the function
declarations:

> >   void strmap_init_with_options(struct strmap *map,
> > +			      struct mem_pool *pool,
> >   			      int strdup_strings);

If you replace the pointer in the struct definition with "struct foo",
then "make hdr-check" will complain about mem_pool in the function. And
likewise if you replace the ones in the function with "struct foo", then
we'll complain about those.

I'm not sure whether this is a seldom-seen corner of the C standard, or
a compiler-specific thing (though both clang and gcc seem to allow it).
At any rate, I think it is worth fixing the typo'd forward declaration
(rather than deleting it) to make the intention clear.

-Peff
Chris Torek Nov. 11, 2020, 8:34 p.m. UTC | #4 
On Wed, Nov 11, 2020 at 11:02 AM Jeff King <peff@peff.net> wrote:
> Even if we're only using a pointer to it, we still need a valid forward
> declaration [in a function, but not in a struct definition] ...
> I'm not sure whether this is a seldom-seen corner of the C standard, or
> a compiler-specific thing (though both clang and gcc seem to allow it).

It is standard (and not all *that* seldom-seen, in that many compilers
have warnings when you put these in function prototype scope).  The
forward declaration is implicit, and occurs *in the current scope*.  The
trick is figuring out what the scope is.  At file level, the scope is "level
zero" as it were: file scope.  So it's as global as we get (C separates
"globality" into scope and linkage; *variables* have linkagebut *type
names* do not).  Function prototypes, however, have function-prototype
scope, which ends at the end of the function declaration.

Overall, though, I agree that the nicest style is to have an explicit
forward declaration (in C that is—note that in C++, struct is just a
class with everything public, and class definitions have scope!).

Chris
diff mbox series

Patch

diff --git a/strmap.c b/strmap.c
index 3784865745..139afb9d4b 100644
--- a/strmap.c
+++ b/strmap.c
@@ -1,5 +1,6 @@ 
 #include "git-compat-util.h"
 #include "strmap.h"
+#include "mem-pool.h"
 
 int cmp_strmap_entry(const void *hashmap_cmp_fn_data,
 		     const struct hashmap_entry *entry1,
@@ -24,13 +25,15 @@  static struct strmap_entry *find_strmap_entry(struct strmap *map,
 
 void strmap_init(struct strmap *map)
 {
-	strmap_init_with_options(map, 1);
+	strmap_init_with_options(map, NULL, 1);
 }
 
 void strmap_init_with_options(struct strmap *map,
+			      struct mem_pool *pool,
 			      int strdup_strings)
 {
 	hashmap_init(&map->map, cmp_strmap_entry, NULL, 0);
+	map->pool = pool;
 	map->strdup_strings = strdup_strings;
 }
 
@@ -42,6 +45,10 @@  static void strmap_free_entries_(struct strmap *map, int free_values)
 	if (!map)
 		return;
 
+	if (!free_values && map->pool)
+		/* Memory other than util is owned by and freed with the pool */
+		return;
+
 	/*
 	 * We need to iterate over the hashmap entries and free
 	 * e->key and e->value ourselves; hashmap has no API to
@@ -52,9 +59,11 @@  static void strmap_free_entries_(struct strmap *map, int free_values)
 	hashmap_for_each_entry(&map->map, &iter, e, ent) {
 		if (free_values)
 			free(e->value);
-		if (map->strdup_strings)
-			free((char*)e->key);
-		free(e);
+		if (!map->pool) {
+			if (map->strdup_strings)
+				free((char*)e->key);
+			free(e);
+		}
 	}
 }
 
@@ -77,11 +86,13 @@  static struct strmap_entry *create_entry(struct strmap *map,
 	struct strmap_entry *entry;
 	const char *key = str;
 
-	entry = xmalloc(sizeof(*entry));
+	entry = map->pool ? mem_pool_alloc(map->pool, sizeof(*entry))
+			  : xmalloc(sizeof(*entry));
 	hashmap_entry_init(&entry->ent, strhash(str));
 
 	if (map->strdup_strings)
-		key = xstrdup(str);
+		key = map->pool ? mem_pool_strdup(map->pool, str)
+				: xstrdup(str);
 	entry->key = key;
 	entry->value = data;
 	return entry;
@@ -128,9 +139,11 @@  void strmap_remove(struct strmap *map, const char *str, int free_value)
 		return;
 	if (free_value)
 		free(ret->value);
-	if (map->strdup_strings)
-		free((char*)ret->key);
-	free(ret);
+	if (!map->pool) {
+		if (map->strdup_strings)
+			free((char*)ret->key);
+		free(ret);
+	}
 }
 
 void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt)
diff --git a/strmap.h b/strmap.h
index c8c4d7c932..dda928703d 100644
--- a/strmap.h
+++ b/strmap.h
@@ -3,8 +3,10 @@ 
 
 #include "hashmap.h"
 
+struct mempool;
 struct strmap {
 	struct hashmap map;
+	struct mem_pool *pool;
 	unsigned int strdup_strings:1;
 };
 
@@ -37,9 +39,10 @@  void strmap_init(struct strmap *map);
 
 /*
  * Same as strmap_init, but for those who want to control the memory management
- * carefully instead of using the default of strdup_strings=1.
+ * carefully instead of using the default of strdup_strings=1 and pool=NULL.
  */
 void strmap_init_with_options(struct strmap *map,
+			      struct mem_pool *pool,
 			      int strdup_strings);
 
 /*
@@ -137,9 +140,10 @@  static inline void strintmap_init(struct strintmap *map, int default_value)
 
 static inline void strintmap_init_with_options(struct strintmap *map,
 					       int default_value,
+					       struct mem_pool *pool,
 					       int strdup_strings)
 {
-	strmap_init_with_options(&map->map, strdup_strings);
+	strmap_init_with_options(&map->map, pool, strdup_strings);
 	map->default_value = default_value;
 }
 
@@ -221,9 +225,10 @@  static inline void strset_init(struct strset *set)
 }
 
 static inline void strset_init_with_options(struct strset *set,
+					    struct mem_pool *pool,
 					    int strdup_strings)
 {
-	strmap_init_with_options(&set->map, strdup_strings);
+	strmap_init_with_options(&set->map, pool, strdup_strings);
 }
 
 static inline void strset_clear(struct strset *set)