diff mbox series

[v3,12/13] strmap: take advantage of FLEXPTR_ALLOC_STR when relevant

Message ID 7f93cbb525704c0bd254181082e3ed1a2782a2d2.1604343314.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. 2, 2020, 6:55 p.m. UTC 
From: Elijah Newren <newren@gmail.com>

By default, we do not use a mempool and strdup_strings is true; in this
case, we can avoid both an extra allocation and an extra free by just
over-allocating for the strmap_entry leaving enough space at the end to
copy the key.  FLEXPTR_ALLOC_STR exists for exactly this purpose, so
make use of it.

Also, adjust the case when we are using a memory pool and strdup_strings
is true to just do one allocation from the memory pool instead of two so
that the strmap_clear() and strmap_remove() code can just avoid freeing
the key in all cases.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 strmap.c | 35 ++++++++++++++++++-----------------
 strmap.h |  1 +
 2 files changed, 19 insertions(+), 17 deletions(-)

Comments

Jeff King Nov. 4, 2020, 8:43 p.m. UTC | #1 
On Mon, Nov 02, 2020 at 06:55:12PM +0000, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
> 
> By default, we do not use a mempool and strdup_strings is true; in this
> case, we can avoid both an extra allocation and an extra free by just
> over-allocating for the strmap_entry leaving enough space at the end to
> copy the key.  FLEXPTR_ALLOC_STR exists for exactly this purpose, so
> make use of it.
> 
> Also, adjust the case when we are using a memory pool and strdup_strings
> is true to just do one allocation from the memory pool instead of two so
> that the strmap_clear() and strmap_remove() code can just avoid freeing
> the key in all cases.

This turned out to be much less painful than I feared, and I think is
worth doing. Thanks for digging on it.

> +		if (map->strdup_strings) {
> +			if (!map->pool) {
> +				FLEXPTR_ALLOC_STR(entry, key, str);
> +			} else {
> +				/* Remember +1 for nul byte twice below */
> +				size_t len = strlen(str);
> +				entry = mem_pool_alloc(map->pool,
> +					       st_add3(sizeof(*entry), len, 1));
> +				memcpy(entry->keydata, str, len+1);
> +			}

Perhaps:

  size_t len = st_add(strlen(str), 1); /* include NUL */
  entry = mem_pool_alloc(map->pool, st_add(sizeof(*entry), len));
  memcpy(entry->keydata, str, len);

would be more obvious than the "remember to do it twice" comment?

With a FLEXPTR, I don't think you need keydata at all (since we would
never use that name; note that we don't even pass it in at all to
FLEXPTR_ALLOC_STR). Without that, I think your memcpy becomes:

  memcpy(entry + 1, str, len);

Remember that "entry" is a typed pointer, so "1" is really moving
sizeof(*entry) bytes.

> +		} else if (!map->pool) {
> +			entry = xmalloc(sizeof(*entry));
> +		} else {
> +			entry = mem_pool_alloc(map->pool, sizeof(*entry));
> +		}

OK, so if we're not strdup-ing then we either get a mempool or a fresh
entry. Makes sense.

>  		hashmap_entry_init(&entry->ent, strhash(str));
> -
> -		if (map->strdup_strings)
> -			key = map->pool ? mem_pool_strdup(map->pool, str)
> -					: xstrdup(str);
> -		entry->key = key;
> +		entry->key = map->strdup_strings ? entry->keydata : str;

I think this is subtly wrong in the FLEXPTR case. The data isn't in
keydata; it's directly after the struct. That's _usually_ the same
thing, but:

  - the compiler can put struct padding at the end if it wants

  - FLEX_ARRAY is usually zero, but for compatibility on some platforms
    it must be 1

The call to FLEXPTR_ALLOC_STR() will have already set it up properly
(and this is at best writing the same value, and at worst messing it
up).

I think you probably want to leave the FLEXPTR_ALLOC_STR() part alone,
put a:

  entry->key = (void *)(entry + 1);

line in the mem_pool code path, and then here do:

  if (!strdup_strings)
	entry->key = str;

-Peff
diff mbox series

Patch

diff --git a/strmap.c b/strmap.c
index 34bca92522..9abd47fd4b 100644
--- a/strmap.c
+++ b/strmap.c
@@ -59,11 +59,8 @@  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->pool) {
-			if (map->strdup_strings)
-				free((char*)e->key);
+		if (!map->pool)
 			free(e);
-		}
 	}
 }
 
@@ -88,16 +85,23 @@  void *strmap_put(struct strmap *map, const char *str, void *data)
 		old = entry->value;
 		entry->value = data;
 	} else {
-		const char *key = str;
-
-		entry = map->pool ? mem_pool_alloc(map->pool, sizeof(*entry))
-				  : xmalloc(sizeof(*entry));
+		if (map->strdup_strings) {
+			if (!map->pool) {
+				FLEXPTR_ALLOC_STR(entry, key, str);
+			} else {
+				/* Remember +1 for nul byte twice below */
+				size_t len = strlen(str);
+				entry = mem_pool_alloc(map->pool,
+					       st_add3(sizeof(*entry), len, 1));
+				memcpy(entry->keydata, str, len+1);
+			}
+		} else if (!map->pool) {
+			entry = xmalloc(sizeof(*entry));
+		} else {
+			entry = mem_pool_alloc(map->pool, sizeof(*entry));
+		}
 		hashmap_entry_init(&entry->ent, strhash(str));
-
-		if (map->strdup_strings)
-			key = map->pool ? mem_pool_strdup(map->pool, str)
-					: xstrdup(str);
-		entry->key = key;
+		entry->key = map->strdup_strings ? entry->keydata : str;
 		entry->value = data;
 		hashmap_add(&map->map, &entry->ent);
 	}
@@ -130,11 +134,8 @@  void strmap_remove(struct strmap *map, const char *str, int free_value)
 		return;
 	if (free_value)
 		free(ret->value);
-	if (!map->pool) {
-		if (map->strdup_strings)
-			free((char*)ret->key);
+	if (!map->pool)
 		free(ret);
-	}
 }
 
 void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt)
diff --git a/strmap.h b/strmap.h
index 6ffa6afb6a..0dd80b276e 100644
--- a/strmap.h
+++ b/strmap.h
@@ -14,6 +14,7 @@  struct strmap_entry {
 	struct hashmap_entry ent;
 	const char *key;
 	void *value;
+	char keydata[FLEX_ARRAY]; /* if strdup_strings=1, key == &keydata[0] */
 };
 
 int cmp_strmap_entry(const void *hashmap_cmp_fn_data,