{"thread":{"id":"45978","subject":"Implementation of sorted hashmap iteration","startedAt":"2017-05-16T04:04:25Z","lastAt":"2017-05-16T04:04:25Z","messageCount":1,"participants":["Daniel Ferreira"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"319882","messageId":"1494907449-29216-1-git-send-email-bnmvco@gmail.com","threadId":"45978","inReplyTo":null,"subject":"Implementation of sorted hashmap iteration","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-05-16T04:04:09Z","receivedAt":"2017-05-16T04:04:25Z","isPatch":false,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"---\nHi there! When implementing a patch series to port git-add--interactive\nfrom Perl to C[1] I ended up implementing this quirk to iterate through\na hashmap in the order elements were added to it. In the end, it did\nnot make it into the series but I figured I'd share it anyway if it\ninterests anyone.\n\n[1]: https://public-inbox.org/git/1494907234-28903-1-git-send-email-bnmvco@gmail.com/T/#t\n\n-- Daniel.\n\n hashmap.c | 25 +++++++++++++++++++++++++\n hashmap.h | 12 ++++++++++++\n 2 files changed, 37 insertions(+)\n\ndiff --git a/hashmap.c b/hashmap.c\nindex 7d1044e..948576c 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -196,6 +196,7 @@ void hashmap_add(struct hashmap *map, void *entry)\n \tunsigned int b = bucket(map, entry);\n\n \t/* add entry */\n+\t((struct hashmap_entry *) entry)->index = map->size;\n \t((struct hashmap_entry *) entry)->next = map->table[b];\n \tmap->table[b] = entry;\n\n@@ -254,6 +255,30 @@ void *hashmap_iter_next(struct hashmap_iter *iter)\n \t}\n }\n\n+void hashmap_iter_init_sorted(struct hashmap *map,\n+\t\tstruct hashmap_iter_sorted *iter)\n+{\n+\thashmap_iter_init(map, (struct hashmap_iter *)iter);\n+\titer->pos = 0;\n+\titer->sorted_entries = xcalloc(map->size,\n+\t\t\tsizeof(struct hashmap_entry *));\n+\n+\tstruct hashmap_entry *ent;\n+\twhile ((ent = hashmap_iter_next((struct hashmap_iter *)iter))) {\n+\t\titer->sorted_entries[ent->index] = ent;\n+\t}\n+}\n+\n+void *hashmap_iter_next_sorted(struct hashmap_iter_sorted *iter)\n+{\n+\treturn iter->sorted_entries[iter->pos++];\n+}\n+\n+void hashmap_iter_free_sorted(struct hashmap_iter_sorted *iter)\n+{\n+\tfree(iter->sorted_entries);\n+}\n+\n struct pool_entry {\n \tstruct hashmap_entry ent;\n \tsize_t len;\ndiff --git a/hashmap.h b/hashmap.h\nindex de6022a..f2a5d36 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -30,6 +30,7 @@ static inline unsigned int sha1hash(const unsigned char *sha1)\n struct hashmap_entry {\n \tstruct hashmap_entry *next;\n \tunsigned int hash;\n+\tunsigned int index;\n };\n\n typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,\n@@ -48,6 +49,12 @@ struct hashmap_iter {\n \tunsigned int tablepos;\n };\n\n+struct hashmap_iter_sorted {\n+\tstruct hashmap_iter base;\n+\tstruct hashmap_entry **sorted_entries;\n+\tunsigned int pos;\n+};\n+\n /* hashmap functions */\n\n extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n@@ -112,6 +119,11 @@ static inline void *hashmap_iter_first(struct hashmap *map,\n \treturn hashmap_iter_next(iter);\n }\n\n+extern void hashmap_iter_init_sorted(struct hashmap *map,\n+\t\tstruct hashmap_iter_sorted *iter);\n+extern void *hashmap_iter_next_sorted(struct hashmap_iter_sorted *iter);\n+extern void hashmap_iter_free_sorted(struct hashmap_iter_sorted *iter);\n+\n /* string interning */\n\n extern const void *memintern(const void *data, size_t len);\n--\n2.7.4 (Apple Git-66)\n\n"}]}