--- 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@xxxxxxxxx/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)