[PATCH 2/5] strmap: new utility functions

From

Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>

Date

Aug 21, 2020, 18:52 UTC

Message-ID

<a86fd5fdcc47baf85046eb07257f4db9f9498084.1598035949.git.gitgitgadget@gmail.com>

In-Reply-To

<pull.835.git.git.1598035949.gitgitgadget@gmail.com>

From: Elijah Newren <newren@gmail.com>

  1) a strmap is often the data structure we want where string_list has
     been used in the past.  Using the same building block for
     individual entries in both makes it easier to adopt and reuse
     parts of the string_list API in strmap.

  2) In some cases, after doing lots of other work, I want to be able
     to iterate over the items in my strmap in sorted order.  hashmap
     obviously doesn't support that, but I wanted to be able to export
     the strmap to a string_list easily and then use its functions.
     (Note: I do not need the data structure to both be sorted and have
     efficient lookup at all times.  If I did, I might use a B-tree
     instead, as suggested by brian in response to Peff in the thread
     noted above.  In my case, most strmaps will never need sorting, but
     in one special case at the very end of a bunch of other work I want
     to iterate over the items in sorted order without doing any more
     lookups afterward.)

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Makefile |  1 +
 strmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 strmap.h | 47 ++++++++++++++++++++++++++++++++
 3 files changed, 129 insertions(+)
 create mode 100644 strmap.c
 create mode 100644 strmap.h

diff --git a/Makefile b/Makefile
index 65f8cfb236..0da15a9ee5 100644
--- a/Makefile
+++ b/Makefile
@@ -988,6 +988,7 @@ LIB_OBJS += strbuf.o
 LIB_OBJS += strvec.o
 LIB_OBJS += streaming.o
 LIB_OBJS += string-list.o
+LIB_OBJS += strmap.o
 LIB_OBJS += sub-process.o
 LIB_OBJS += submodule-config.o
 LIB_OBJS += submodule.o
diff --git a/strmap.c b/strmap.c
new file mode 100644
index 0000000000..1c9fdb3b1e
--- /dev/null
+++ b/strmap.c
@@ -0,0 +1,81 @@
+#include "git-compat-util.h"
+#include "strmap.h"
+
+static int cmp_str_entry(const void *hashmap_cmp_fn_data,
+			 const struct hashmap_entry *entry1,
+			 const struct hashmap_entry *entry2,
+			 const void *keydata)
+{
+	const struct str_entry *e1, *e2;
+
+	e1 = container_of(entry1, const struct str_entry, ent);
+	e2 = container_of(entry2, const struct str_entry, ent);
+	return strcmp(e1->item.string, e2->item.string);
+}
+
+static struct str_entry *find_str_entry(struct strmap *map,
+					const char *str)
+{
+	struct str_entry entry;
+	hashmap_entry_init(&entry.ent, strhash(str));
+	entry.item.string = (char *)str;
+	return hashmap_get_entry(&map->map, &entry, ent, NULL);
+}
+
+void strmap_init(struct strmap *map)
+{
+	hashmap_init(&map->map, cmp_str_entry, NULL, 0);
+}
+
+void strmap_clear(struct strmap *map, int free_util)
+{
+	struct hashmap_iter iter;
+	struct str_entry *e;
+
+	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);
+	}
+	hashmap_free_entries(&map->map, struct str_entry, ent);
+	strmap_init(map);
+}
+
+/*
+ * Insert "str" into the map, pointing to "data". A copy of "str" is made, so
+ * it does not need to persist after the this function is called.
+ *
+ * If an entry for "str" already exists, its data pointer is overwritten, and
+ * the original data pointer returned. Otherwise, returns NULL.
+ */
+void *strmap_put(struct strmap *map, const char *str, void *data)
+{
+	struct str_entry *entry = find_str_entry(map, str);
+	void *old = NULL;
+
+	if (entry) {
+		old = entry->item.util;
+		entry->item.util = data;
+	} else {
+		entry = xmalloc(sizeof(*entry));
+		hashmap_entry_init(&entry->ent, strhash(str));
+		entry->item.string = strdup(str);
+		entry->item.util = data;
+		hashmap_add(&map->map, &entry->ent);
+	}
+	return old;
+}
+
+void *strmap_get(struct strmap *map, const char *str)
+{
+	struct str_entry *entry = find_str_entry(map, str);
+	return entry ? entry->item.util : NULL;
+}
+
+int strmap_contains(struct strmap *map, const char *str)
+{
+	return find_str_entry(map, str) != NULL;
+}
diff --git a/strmap.h b/strmap.h
new file mode 100644
index 0000000000..eb5807f6fa
--- /dev/null
+++ b/strmap.h
@@ -0,0 +1,47 @@
+#ifndef STRMAP_H
+#define STRMAP_H
+
+#include "hashmap.h"
+#include "string-list.h"
+
+struct strmap {
+	struct hashmap map;
+};
+
+struct str_entry {
+	struct hashmap_entry ent;
+	struct string_list_item item;
+};
+
+/*
+ * Initialize an empty strmap
+ */
+void strmap_init(struct strmap *map);
+
+/*
+ * Remove all entries from the map, releasing any allocated resources.
+ */
+void strmap_clear(struct strmap *map, int free_values);
+
+/*
+ * Insert "str" into the map, pointing to "data". A copy of "str" is made, so
+ * it does not need to persist after the this function is called.
+ *
+ * If an entry for "str" already exists, its data pointer is overwritten, and
+ * the original data pointer returned. Otherwise, returns NULL.
+ */
+void *strmap_put(struct strmap *map, const char *str, void *data);
+
+/*
+ * Return the data pointer mapped by "str", or NULL if the entry does not
+ * exist.
+ */
+void *strmap_get(struct strmap *map, const char *str);
+
+/*
+ * Return non-zero iff "str" is present in the map. This differs from
+ * strmap_get() in that it can distinguish entries with a NULL data pointer.
+ */
+int strmap_contains(struct strmap *map, const char *str);
+
+#endif /* STRMAP_H */

-- 
gitgitgadget