Skip to contentSkip to conversation

Add struct strmap and associated utility functions

PATCH Superseded Elijah Newren via GitGitGadget 6 participants 144 messages Aug 21, 2020 – Nov 11, 2020 Kbuild Page 2 of 2

lore
Share & tools
lore
#139 lore raw

PATCH v6 12/15 strmap: enable allocations to come from a mem_pool

In reply to Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

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.

---
 strmap.c | 31 ++++++++++++++++++++++---------
 strmap.h | 11 ++++++++---
 2 files changed, 30 insertions(+), 12 deletions(-)
strmap.c +22 -9
index 3784865745..139afb9d4b 100644
@@ -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)
strmap.h +8 -3
index c8c4d7c932..8745b7ceb1 100644
@@ -3,8 +3,10 @@
 
 #include "hashmap.h"
 
+struct mem_pool;
 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)
Signature · 1 line
gitgitgadget
#131 lore raw

PATCH v6 4/15 hashmap: introduce a new hashmap_partial_clear()

In reply to Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

merge-ort is a heavy user of strmaps, which are built on hashmap.[ch]. clear_or_reinit_internal_opts() in merge-ort was taking about 12% of overall runtime in my testcase involving rebasing 35 patches of linux.git across a big rename. clear_or_reinit_internal_opts() was calling hashmap_free() followed by hashmap_init(), meaning that not only was it freeing all the memory associated with each of the strmaps just to immediately allocate a new array again, it was allocating a new array that was likely smaller than needed (thus resulting in later need to rehash things). The ending size of the map table on the previous commit was likely almost perfectly sized for the next commit we wanted to pick, and not dropping and reallocating the table immediately is a win.

Add some new API to hashmap to clear a hashmap of entries without freeing map->table (and instead only zeroing it out like alloc_table() would do, along with zeroing the count of items in the table and the shrink_at field).

---
 hashmap.c | 39 +++++++++++++++++++++++++++------------
 hashmap.h | 13 ++++++++++++-
 2 files changed, 39 insertions(+), 13 deletions(-)
hashmap.c +27 -12
index bb7c9979b8..922ed07954 100644
@@ -174,22 +174,37 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
 	map->do_count_items = 1;
 }
 
+static void free_individual_entries(struct hashmap *map, ssize_t entry_offset)
+{
+	struct hashmap_iter iter;
+	struct hashmap_entry *e;
+
+	hashmap_iter_init(map, &iter);
+	while ((e = hashmap_iter_next(&iter)))
+		/*
+		 * like container_of, but using caller-calculated
+		 * offset (caller being hashmap_free_entries)
+		 */
+		free((char *)e - entry_offset);
+}
+
+void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset)
+{
+	if (!map || !map->table)
+		return;
+	if (entry_offset >= 0)  /* called by hashmap_clear_entries */
+		free_individual_entries(map, entry_offset);
+	memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *));
+	map->shrink_at = 0;
+	map->private_size = 0;
+}
+
 void hashmap_free_(struct hashmap *map, ssize_t entry_offset)
 {
 	if (!map || !map->table)
 		return;
-	if (entry_offset >= 0) { /* called by hashmap_free_entries */
-		struct hashmap_iter iter;
-		struct hashmap_entry *e;
-
-		hashmap_iter_init(map, &iter);
-		while ((e = hashmap_iter_next(&iter)))
-			/*
-			 * like container_of, but using caller-calculated
-			 * offset (caller being hashmap_free_entries)
-			 */
-			free((char *)e - entry_offset);
-	}
+	if (entry_offset >= 0)  /* called by hashmap_free_entries */
+		free_individual_entries(map, entry_offset);
 	free(map->table);
 	memset(map, 0, sizeof(*map));
 }
hashmap.h +12 -1
index 3b0f2bcade..e9430d582a 100644
@@ -235,7 +235,8 @@ void hashmap_init(struct hashmap *map,
 		  const void *equals_function_data,
 		  size_t initial_size);
 
-/* internal function for freeing hashmap */
+/* internal functions for clearing or freeing hashmap */
+void hashmap_partial_clear_(struct hashmap *map, ssize_t offset);
 void hashmap_free_(struct hashmap *map, ssize_t offset);
 
 /*
@@ -268,6 +269,16 @@ void hashmap_free_(struct hashmap *map, ssize_t offset);
  */
 #define hashmap_free(map) hashmap_free_(map, -1)
 
+/*
+ * Basically the same as calling hashmap_free() followed by hashmap_init(),
+ * but doesn't incur the overhead of deallocating and reallocating
+ * map->table; it leaves map->table allocated and the same size but zeroes
+ * it out so it's ready for use again as an empty map.  As with
+ * hashmap_free(), you may need to free the entries yourself before calling
+ * this function.
+ */
+#define hashmap_partial_clear(map) hashmap_partial_clear_(map, -1)
+
 /*
  * Frees @map and all entries.  @type is the struct type of the entry
  * where @member is the hashmap_entry struct used to associate with @map.
Signature · 1 line
gitgitgadget
#141 lore raw

PATCH v6 14/15 Use new HASHMAP_INIT macro to simplify hashmap initialization

In reply to Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

Now that hashamp has lazy initialization and a HASHMAP_INIT macro, hashmaps allocated on the stack can be initialized without a call to hashmap_init() and in some cases makes the code a bit shorter. Convert some callsites over to take advantage of this.

---
 attr.c                  | 26 ++++++++------------------
 bloom.c                 |  3 +--
 builtin/difftool.c      |  9 ++++-----
 range-diff.c            |  4 +---
 revision.c              |  9 +--------
 t/helper/test-hashmap.c |  3 +--
 6 files changed, 16 insertions(+), 38 deletions(-)
attr.c +8 -18
index a826b2ef1f..4ef85d668b 100644
@@ -52,13 +52,6 @@ static inline void hashmap_unlock(struct attr_hashmap *map)
 	pthread_mutex_unlock(&map->mutex);
 }
 
-/*
- * The global dictionary of all interned attributes.  This
- * is a singleton object which is shared between threads.
- * Access to this dictionary must be surrounded with a mutex.
- */
-static struct attr_hashmap g_attr_hashmap;
-
 /* The container for objects stored in "struct attr_hashmap" */
 struct attr_hash_entry {
 	struct hashmap_entry ent;
@@ -80,11 +73,14 @@ static int attr_hash_entry_cmp(const void *unused_cmp_data,
 	return (a->keylen != b->keylen) || strncmp(a->key, b->key, a->keylen);
 }
 
-/* Initialize an 'attr_hashmap' object */
-static void attr_hashmap_init(struct attr_hashmap *map)
-{
-	hashmap_init(&map->map, attr_hash_entry_cmp, NULL, 0);
-}
+/*
+ * The global dictionary of all interned attributes.  This
+ * is a singleton object which is shared between threads.
+ * Access to this dictionary must be surrounded with a mutex.
+ */
+static struct attr_hashmap g_attr_hashmap = {
+	HASHMAP_INIT(attr_hash_entry_cmp, NULL)
+};
 
 /*
  * Retrieve the 'value' stored in a hashmap given the provided 'key'.
@@ -96,9 +92,6 @@ static void *attr_hashmap_get(struct attr_hashmap *map,
 	struct attr_hash_entry k;
 	struct attr_hash_entry *e;
 
-	if (!map->map.tablesize)
-		attr_hashmap_init(map);
-
 	hashmap_entry_init(&k.ent, memhash(key, keylen));
 	k.key = key;
 	k.keylen = keylen;
@@ -114,9 +107,6 @@ static void attr_hashmap_add(struct attr_hashmap *map,
 {
 	struct attr_hash_entry *e;
 
-	if (!map->map.tablesize)
-		attr_hashmap_init(map);
-
 	e = xmalloc(sizeof(struct attr_hash_entry));
 	hashmap_entry_init(&e->ent, memhash(key, keylen));
 	e->key = key;
bloom.c +1 -2
index 719c313a1c..b176f28f53 100644
@@ -229,10 +229,9 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 	diffcore_std(&diffopt);
 
 	if (diff_queued_diff.nr <= settings->max_changed_paths) {
-		struct hashmap pathmap;
+		struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL);
 		struct pathmap_hash_entry *e;
 		struct hashmap_iter iter;
-		hashmap_init(&pathmap, pathmap_cmp, NULL, 0);
 
 		for (i = 0; i < diff_queued_diff.nr; i++) {
 			const char *path = diff_queued_diff.queue[i]->two->path;
builtin/difftool.c +4 -5
index 7ac432b881..6e18e623fd 100644
@@ -342,7 +342,10 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,
 	const char *workdir, *tmp;
 	int ret = 0, i;
 	FILE *fp;
-	struct hashmap working_tree_dups, submodules, symlinks2;
+	struct hashmap working_tree_dups = HASHMAP_INIT(working_tree_entry_cmp,
+							NULL);
+	struct hashmap submodules = HASHMAP_INIT(pair_cmp, NULL);
+	struct hashmap symlinks2 = HASHMAP_INIT(pair_cmp, NULL);
 	struct hashmap_iter iter;
 	struct pair_entry *entry;
 	struct index_state wtindex;
@@ -383,10 +386,6 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,
 	rdir_len = rdir.len;
 	wtdir_len = wtdir.len;
 
-	hashmap_init(&working_tree_dups, working_tree_entry_cmp, NULL, 0);
-	hashmap_init(&submodules, pair_cmp, NULL, 0);
-	hashmap_init(&symlinks2, pair_cmp, NULL, 0);
-
 	child.no_stdin = 1;
 	child.git_cmd = 1;
 	child.use_shell = 0;
range-diff.c +1 -3
index befeecae44..b9950f10c8 100644
@@ -232,11 +232,9 @@ static int patch_util_cmp(const void *dummy, const struct patch_util *a,
 
 static void find_exact_matches(struct string_list *a, struct string_list *b)
 {
-	struct hashmap map;
+	struct hashmap map = HASHMAP_INIT((hashmap_cmp_fn)patch_util_cmp, NULL);
 	int i;
 
-	hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0);
-
 	/* First, add the patches of a to a hash map */
 	for (i = 0; i < a->nr; i++) {
 		struct patch_util *util = a->items[i].util;
revision.c +1 -8
index f27649d45d..c6e169e3eb 100644
@@ -124,11 +124,6 @@ static int path_and_oids_cmp(const void *hashmap_cmp_fn_data,
 	return strcmp(e1->path, e2->path);
 }
 
-static void paths_and_oids_init(struct hashmap *map)
-{
-	hashmap_init(map, path_and_oids_cmp, NULL, 0);
-}
-
 static void paths_and_oids_clear(struct hashmap *map)
 {
 	struct hashmap_iter iter;
@@ -213,7 +208,7 @@ void mark_trees_uninteresting_sparse(struct repository *r,
 				     struct oidset *trees)
 {
 	unsigned has_interesting = 0, has_uninteresting = 0;
-	struct hashmap map;
+	struct hashmap map = HASHMAP_INIT(path_and_oids_cmp, NULL);
 	struct hashmap_iter map_iter;
 	struct path_and_oids_entry *entry;
 	struct object_id *oid;
@@ -237,8 +232,6 @@ void mark_trees_uninteresting_sparse(struct repository *r,
 	if (!has_uninteresting || !has_interesting)
 		return;
 
-	paths_and_oids_init(&map);
-
 	oidset_iter_init(trees, &iter);
 	while ((oid = oidset_iter_next(&iter))) {
 		struct tree *tree = lookup_tree(r, oid);
t/helper/test-hashmap.c +1 -2
index 2475663b49..36ff07bd4b 100644
@@ -151,12 +151,11 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 int cmd__hashmap(int argc, const char **argv)
 {
 	struct strbuf line = STRBUF_INIT;
-	struct hashmap map;
 	int icase;
+	struct hashmap map = HASHMAP_INIT(test_entry_cmp, &icase);
 
 	/* init hash map */
 	icase = argc > 1 && !strcmp("ignorecase", argv[1]);
-	hashmap_init(&map, test_entry_cmp, &icase, 0);
 
 	/* process commands from stdin */
 	while (strbuf_getline(&line, stdin) != EOF) {
Signature · 1 line
gitgitgadget
#142 lore raw

PATCH v6 15/15 shortlog: use strset from strmap.h

In reply to Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

---
 builtin/shortlog.c | 61 +++-------------------------------------------
 1 file changed, 4 insertions(+), 57 deletions(-)
builtin/shortlog.c +4 -57
index 83f0a739b4..c52e4ccd19 100644
@@ -10,6 +10,7 @@
 #include "shortlog.h"
 #include "parse-options.h"
 #include "trailer.h"
+#include "strmap.h"
 
 static char const * const shortlog_usage[] = {
 	N_("git shortlog [<options>] [<revision-range>] [[--] <path>...]"),
@@ -169,60 +170,6 @@ static void read_from_stdin(struct shortlog *log)
 	strbuf_release(&oneline);
 }
 
-struct strset_item {
-	struct hashmap_entry ent;
-	char value[FLEX_ARRAY];
-};
-
-struct strset {
-	struct hashmap map;
-};
-
-#define STRSET_INIT { { NULL } }
-
-static int strset_item_hashcmp(const void *hash_data,
-			       const struct hashmap_entry *entry,
-			       const struct hashmap_entry *entry_or_key,
-			       const void *keydata)
-{
-	const struct strset_item *a, *b;
-
-	a = container_of(entry, const struct strset_item, ent);
-	if (keydata)
-		return strcmp(a->value, keydata);
-
-	b = container_of(entry_or_key, const struct strset_item, ent);
-	return strcmp(a->value, b->value);
-}
-
-/*
- * Adds "str" to the set if it was not already present; returns true if it was
- * already there.
- */
-static int strset_check_and_add(struct strset *ss, const char *str)
-{
-	unsigned int hash = strhash(str);
-	struct strset_item *item;
-
-	if (!ss->map.table)
-		hashmap_init(&ss->map, strset_item_hashcmp, NULL, 0);
-
-	if (hashmap_get_from_hash(&ss->map, hash, str))
-		return 1;
-
-	FLEX_ALLOC_STR(item, value, str);
-	hashmap_entry_init(&item->ent, hash);
-	hashmap_add(&ss->map, &item->ent);
-	return 0;
-}
-
-static void strset_clear(struct strset *ss)
-{
-	if (!ss->map.table)
-		return;
-	hashmap_clear_and_free(&ss->map, struct strset_item, ent);
-}
-
 static void insert_records_from_trailers(struct shortlog *log,
 					 struct strset *dups,
 					 struct commit *commit,
@@ -253,7 +200,7 @@ static void insert_records_from_trailers(struct shortlog *log,
 		if (!parse_ident(log, &ident, value))
 			value = ident.buf;
 
-		if (strset_check_and_add(dups, value))
+		if (!strset_add(dups, value))
 			continue;
 		insert_one_record(log, value, oneline);
 	}
@@ -291,7 +238,7 @@ void shortlog_add_commit(struct shortlog *log, struct commit *commit)
 				      log->email ? "%aN <%aE>" : "%aN",
 				      &ident, &ctx);
 		if (!HAS_MULTI_BITS(log->groups) ||
-		    !strset_check_and_add(&dups, ident.buf))
+		    strset_add(&dups, ident.buf))
 			insert_one_record(log, ident.buf, oneline_str);
 	}
 	if (log->groups & SHORTLOG_GROUP_COMMITTER) {
@@ -300,7 +247,7 @@ void shortlog_add_commit(struct shortlog *log, struct commit *commit)
 				      log->email ? "%cN <%cE>" : "%cN",
 				      &ident, &ctx);
 		if (!HAS_MULTI_BITS(log->groups) ||
-		    !strset_check_and_add(&dups, ident.buf))
+		    strset_add(&dups, ident.buf))
 			insert_one_record(log, ident.buf, oneline_str);
 	}
 	if (log->groups & SHORTLOG_GROUP_TRAILER) {
Signature · 1 line
gitgitgadget
#127 lore raw

v6 cover Add struct strmap and associated utility functions

In reply to Elijah Newren via GitGitGadget

Here I introduce new strmap, strintmap, and strset types.

Changes since v5:

* Fixed a typo in forward declaration of struct mem_pool, spotted by Phillip. (Usage via pointers meant gcc & clang wouldn't complain.)

[1]
https://lore.kernel.org/git/[email protected]/

Elijah Newren (15):
hashmap: add usage documentation explaining hashmap_free[_entries]()
hashmap: adjust spacing to fix argument alignment
hashmap: allow re-use after hashmap_free()
hashmap: introduce a new hashmap_partial_clear()
hashmap: provide deallocation function names
strmap: new utility functions
strmap: add more utility functions
strmap: enable faster clearing and reusing of strmaps
strmap: add functions facilitating use as a string->int map
strmap: split create_entry() out of strmap_put()
strmap: add a strset sub-type
strmap: enable allocations to come from a mem_pool
strmap: take advantage of FLEXPTR_ALLOC_STR when relevant Use new HASHMAP_INIT macro to simplify hashmap initialization
shortlog: use strset from strmap.h

 Makefile                |   1 +
 add-interactive.c       |   2 +-
 attr.c                  |  26 ++--
 blame.c                 |   2 +-
 bloom.c                 |   5 +-
 builtin/difftool.c      |   9 +-
 builtin/fetch.c         |   6 +-
 builtin/shortlog.c      |  61 +--------
 config.c                |   2 +-
 diff.c                  |   4 +-
 diffcore-rename.c       |   2 +-
 dir.c                   |   8 +-
 hashmap.c               |  74 +++++++----
 hashmap.h               |  91 +++++++++++---
 merge-recursive.c       |   6 +-
 name-hash.c             |   4 +-
 object.c                |   2 +-
 oidmap.c                |   2 +-
 patch-ids.c             |   2 +-
 range-diff.c            |   6 +-
 ref-filter.c            |   2 +-
 revision.c              |  11 +-
 sequencer.c             |   4 +-
 strmap.c                | 178 ++++++++++++++++++++++++++
 strmap.h                | 268 ++++++++++++++++++++++++++++++++++++++++
 submodule-config.c      |   4 +-
 t/helper/test-hashmap.c |   9 +-
 27 files changed, 621 insertions(+), 170 deletions(-)
 create mode 100644 strmap.c
 create mode 100644 strmap.h

base-commit: d4a392452e292ff924e79ec8458611c0f679d6d4
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-835%2Fnewren%2Fstrmap-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-835/newren/strmap-v6
Pull-Request: https://github.com/git/git/pull/835

Range-diff vs v5:

  1:  af6b6fcb46 =  1:  af6b6fcb46 hashmap: add usage documentation explaining hashmap_free[_entries]()
  2:  591161fd78 =  2:  591161fd78 hashmap: adjust spacing to fix argument alignment
  3:  f2718d036d =  3:  f2718d036d hashmap: allow re-use after hashmap_free()
  4:  61f1da3c51 =  4:  61f1da3c51 hashmap: introduce a new hashmap_partial_clear()
  5:  861e8d65ae =  5:  861e8d65ae hashmap: provide deallocation function names
  6:  448d3b219f =  6:  448d3b219f strmap: new utility functions
  7:  5e8004c728 =  7:  5e8004c728 strmap: add more utility functions
  8:  fd96e9fc8d =  8:  fd96e9fc8d strmap: enable faster clearing and reusing of strmaps
  9:  f499934f54 =  9:  f499934f54 strmap: add functions facilitating use as a string->int map
 10:  3bcceb8cdb = 10:  3bcceb8cdb strmap: split create_entry() out of strmap_put()
 11:  e128a71fec = 11:  e128a71fec strmap: add a strset sub-type
 12:  34f542d9dd ! 12:  3926c4c97b strmap: enable allocations to come from a mem_pool
     @@ strmap.h
       
       #include "hashmap.h"
       
     -+struct mempool;
     ++struct mem_pool;
       struct strmap {
       	struct hashmap map;
      +	struct mem_pool *pool;
 13:  39ec2fa411 = 13:  562595224b strmap: take advantage of FLEXPTR_ALLOC_STR when relevant
 14:  d3713d88f2 = 14:  058e7a6b76 Use new HASHMAP_INIT macro to simplify hashmap initialization
 15:  24e5ce60f5 = 15:  9b494c26c1 shortlog: use strset from strmap.h
Signature · 1 line
gitgitgadget
#134 lore raw

PATCH v6 7/15 strmap: add more utility functions

From: Elijah Newren <[email protected]>

This adds a number of additional convienence functions I want/need:
* strmap_get_size()
* strmap_empty()
* 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.

---
 strmap.c | 20 ++++++++++++++++++++
 strmap.h | 34 ++++++++++++++++++++++++++++++++++
 2 files changed, 54 insertions(+)
strmap.c +20 -0
index 53f284eb20..829f1bc095 100644
@@ -87,6 +87,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);
@@ -97,3 +102,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_value)
+{
+	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_value)
+		free(ret->value);
+	if (map->strdup_strings)
+		free((char*)ret->key);
+	free(ret);
+}
strmap.h +34 -0
index 96888c23ad..f74bc582e4 100644
@@ -50,6 +50,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.
@@ -62,4 +68,32 @@ 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 how many entries the strmap has.
+ */
+static inline unsigned int strmap_get_size(struct strmap *map)
+{
+	return hashmap_get_size(&map->map);
+}
+
+/*
+ * Return whether the strmap is empty.
+ */
+static inline int strmap_empty(struct strmap *map)
+{
+	return strmap_get_size(map) == 0;
+}
+
+/*
+ * iterate through @map using @iter, @var is a pointer to a type strmap_entry
+ */
+#define strmap_for_each_entry(mystrmap, iter, var)	\
+	hashmap_for_each_entry(&(mystrmap)->map, iter, var, ent)
+
 #endif /* STRMAP_H */
Signature · 1 line
gitgitgadget
#140 lore raw

PATCH v6 13/15 strmap: take advantage of FLEXPTR_ALLOC_STR when relevant

In reply to Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

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.

---
 strmap.c | 35 +++++++++++++++++++----------------
 strmap.h |  1 +
 2 files changed, 20 insertions(+), 16 deletions(-)
strmap.c +19 -16
index 139afb9d4b..4fb9f6100e 100644
@@ -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);
-		}
 	}
 }
 
@@ -84,16 +81,25 @@ static struct strmap_entry *create_entry(struct strmap *map,
 					 void *data)
 {
 	struct strmap_entry *entry;
-	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 {
+			size_t len = st_add(strlen(str), 1); /* include NUL */
+			entry = mem_pool_alloc(map->pool,
+					       st_add(sizeof(*entry), len));
+			memcpy(entry + 1, str, len);
+			entry->key = (void *)(entry + 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;
+	if (!map->strdup_strings)
+		entry->key = str;
 	entry->value = data;
 	return entry;
 }
@@ -139,11 +145,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)
strmap.h +1 -0
index 8745b7ceb1..c4c104411b 100644
@@ -14,6 +14,7 @@ struct strmap_entry {
 	struct hashmap_entry ent;
 	const char *key;
 	void *value;
+	/* strmap_entry may be allocated extra space to store the key at end */
 };
 
 int cmp_strmap_entry(const void *hashmap_cmp_fn_data,
Signature · 1 line
gitgitgadget
#143 lore raw
In reply to Elijah Newren via GitGitGadget
Quoted 6 lines · Elijah Newren via GitGitGadget

Here I introduce new strmap, strintmap, and strset types.

Changes since v5:

* Fixed a typo in forward declaration of struct mem_pool, spotted by Phillip. (Usage via pointers meant gcc & clang wouldn't complain.)

Yep, this version looks good to me. I think this is probably ready for 'next'.

-Peff

#119 lore raw

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

In reply to Jeff King
Quoted 4 lines · Jeff King

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