Implementation of sorted hashmap iteration

Implementation of sorted hashmap iteration

[Daniel Ferreira]

---
Hi there! When implementing a patch series to port git-add--interactive
from Perl to C[1] I ended up implementing this quirk to iterate through
a hashmap in the order elements were added to it. In the end, it did
not make it into the series but I figured I'd share it anyway if it
interests anyone.

[1]: https://public-inbox.org/git/1494907234-28903-1-git-send-email-bnmvco@gmail.com/T/#t

-- Daniel.

 hashmap.c | 25 +++++++++++++++++++++++++
 hashmap.h | 12 ++++++++++++
 2 files changed, 37 insertions(+)

diff --git a/hashmap.c b/hashmap.c
index 7d1044e..948576c 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -196,6 +196,7 @@ void hashmap_add(struct hashmap *map, void *entry)
 	unsigned int b = bucket(map, entry);

 	/* add entry */
+	((struct hashmap_entry *) entry)->index = map->size;
 	((struct hashmap_entry *) entry)->next = map->table[b];
 	map->table[b] = entry;

@@ -254,6 +255,30 @@ void *hashmap_iter_next(struct hashmap_iter *iter)
 	}
 }

+void hashmap_iter_init_sorted(struct hashmap *map,
+		struct hashmap_iter_sorted *iter)
+{
+	hashmap_iter_init(map, (struct hashmap_iter *)iter);
+	iter->pos = 0;
+	iter->sorted_entries = xcalloc(map->size,
+			sizeof(struct hashmap_entry *));
+
+	struct hashmap_entry *ent;
+	while ((ent = hashmap_iter_next((struct hashmap_iter *)iter))) {
+		iter->sorted_entries[ent->index] = ent;
+	}
+}
+
+void *hashmap_iter_next_sorted(struct hashmap_iter_sorted *iter)
+{
+	return iter->sorted_entries[iter->pos++];
+}
+
+void hashmap_iter_free_sorted(struct hashmap_iter_sorted *iter)
+{
+	free(iter->sorted_entries);
+}
+
 struct pool_entry {
 	struct hashmap_entry ent;
 	size_t len;
diff --git a/hashmap.h b/hashmap.h
index de6022a..f2a5d36 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -30,6 +30,7 @@ static inline unsigned int sha1hash(const unsigned char *sha1)
 struct hashmap_entry {
 	struct hashmap_entry *next;
 	unsigned int hash;
+	unsigned int index;
 };

 typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,
@@ -48,6 +49,12 @@ struct hashmap_iter {
 	unsigned int tablepos;
 };

+struct hashmap_iter_sorted {
+	struct hashmap_iter base;
+	struct hashmap_entry **sorted_entries;
+	unsigned int pos;
+};
+
 /* hashmap functions */

 extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
@@ -112,6 +119,11 @@ static inline void *hashmap_iter_first(struct hashmap *map,
 	return hashmap_iter_next(iter);
 }

+extern void hashmap_iter_init_sorted(struct hashmap *map,
+		struct hashmap_iter_sorted *iter);
+extern void *hashmap_iter_next_sorted(struct hashmap_iter_sorted *iter);
+extern void hashmap_iter_free_sorted(struct hashmap_iter_sorted *iter);
+
 /* string interning */

 extern const void *memintern(const void *data, size_t len);
--
2.7.4 (Apple Git-66)