hashmap: add OrderedHashmap as a distinct type

Few Hashmaps/Sets need to remember the insertion order. Most don't care
about the order when iterating. It would be possible to use more compact
hashmap storage in the latter cases.

Add OrderedHashmap as a distinct type from Hashmap, with functions
prefixed with "ordered_". For now, the functions are nothing more than
inline wrappers for plain Hashmap functions.

diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h
index e25840f47f46c69375febe244161a46933042644..9789ad77babd790513c5d2c0e39eadaabc628846 100644 (file)
--- a/src/shared/hashmap.h
+++ b/src/shared/hashmap.h
@@ -34,6 +34,7 @@
 #define HASH_KEY_SIZE 16
 
 typedef struct Hashmap Hashmap;
 #define HASH_KEY_SIZE 16
 
 typedef struct Hashmap Hashmap;

+typedef struct OrderedHashmap OrderedHashmap;

 typedef struct _IteratorStruct _IteratorStruct;
 typedef _IteratorStruct* Iterator;
 
 typedef struct _IteratorStruct _IteratorStruct;
 typedef _IteratorStruct* Iterator;
 


@@ -82,56 +83,171 @@ extern const struct hash_ops devt_hash_ops = {
 #endif
 
 Hashmap *hashmap_new(const struct hash_ops *hash_ops);
 #endif
 
 Hashmap *hashmap_new(const struct hash_ops *hash_ops);

+static inline OrderedHashmap *ordered_hashmap_new(const struct hash_ops *hash_ops) {
+        return (OrderedHashmap*) hashmap_new(hash_ops);
+}

 void hashmap_free(Hashmap *h);
 void hashmap_free(Hashmap *h);

+static inline void ordered_hashmap_free(OrderedHashmap *h) {
+        hashmap_free((Hashmap*) h);
+}

 void hashmap_free_free(Hashmap *h);
 void hashmap_free_free(Hashmap *h);

+static inline void ordered_hashmap_free_free(OrderedHashmap *h) {
+        hashmap_free_free((Hashmap*) h);
+}

 void hashmap_free_free_free(Hashmap *h);
 void hashmap_free_free_free(Hashmap *h);

+static inline void ordered_hashmap_free_free_free(OrderedHashmap *h) {
+        hashmap_free_free_free((Hashmap*) h);
+}

 Hashmap *hashmap_copy(Hashmap *h);
 Hashmap *hashmap_copy(Hashmap *h);

+static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
+        return (OrderedHashmap*) hashmap_copy((Hashmap*) h);
+}

 int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops);
 int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops);

+static inline int ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops) {
+        return hashmap_ensure_allocated((Hashmap**) h, hash_ops);
+}

 
 int hashmap_put(Hashmap *h, const void *key, void *value);
 
 int hashmap_put(Hashmap *h, const void *key, void *value);

+static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
+        return hashmap_put((Hashmap*) h, key, value);
+}

 int hashmap_update(Hashmap *h, const void *key, void *value);
 int hashmap_update(Hashmap *h, const void *key, void *value);

+static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
+        return hashmap_update((Hashmap*) h, key, value);
+}

 int hashmap_replace(Hashmap *h, const void *key, void *value);
 int hashmap_replace(Hashmap *h, const void *key, void *value);

+static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
+        return hashmap_replace((Hashmap*) h, key, value);
+}

 void *hashmap_get(Hashmap *h, const void *key);
 void *hashmap_get(Hashmap *h, const void *key);

+static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
+        return hashmap_get((Hashmap*) h, key);
+}

 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);

+static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
+        return hashmap_get2((Hashmap*) h, key, rkey);
+}

 bool hashmap_contains(Hashmap *h, const void *key);
 bool hashmap_contains(Hashmap *h, const void *key);

+static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
+        return hashmap_contains((Hashmap*) h, key);
+}

 void *hashmap_remove(Hashmap *h, const void *key);
 void *hashmap_remove(Hashmap *h, const void *key);

+static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
+        return hashmap_remove((Hashmap*) h, key);
+}

 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);

+static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
+        return hashmap_remove2((Hashmap*) h, key, rkey);
+}

 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);

+static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
+        return hashmap_remove_value((Hashmap*) h, key, value);
+}

 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);

+static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
+        return hashmap_remove_and_put((Hashmap*) h, old_key, new_key, value);
+}

 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);

+static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
+        return hashmap_remove_and_replace((Hashmap*) h, old_key, new_key, value);
+}

 
 int hashmap_merge(Hashmap *h, Hashmap *other);
 
 int hashmap_merge(Hashmap *h, Hashmap *other);

+static inline int ordered_hashmap_merge(OrderedHashmap *h, OrderedHashmap *other) {
+        return hashmap_merge((Hashmap*) h, (Hashmap*) other);
+}

 void hashmap_move(Hashmap *h, Hashmap *other);
 void hashmap_move(Hashmap *h, Hashmap *other);

+static inline void ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
+        hashmap_move((Hashmap*) h, (Hashmap*) other);
+}

 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);
 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);

+static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
+        return hashmap_move_one((Hashmap*) h, (Hashmap*) other, key);
+}

 
 unsigned hashmap_size(Hashmap *h) _pure_;
 
 unsigned hashmap_size(Hashmap *h) _pure_;

+static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
+        return hashmap_size((Hashmap*) h);
+}

 bool hashmap_isempty(Hashmap *h) _pure_;
 bool hashmap_isempty(Hashmap *h) _pure_;

+static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
+        return hashmap_isempty((Hashmap*) h);
+}

 unsigned hashmap_buckets(Hashmap *h) _pure_;
 unsigned hashmap_buckets(Hashmap *h) _pure_;

+static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
+        return hashmap_buckets((Hashmap*) h);
+}

 
 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key);
 
 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key);

+static inline void *ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, const void **key) {
+        return hashmap_iterate((Hashmap*) h, i, key);
+}

 
 void hashmap_clear(Hashmap *h);
 
 void hashmap_clear(Hashmap *h);

+static inline void ordered_hashmap_clear(OrderedHashmap *h) {
+        hashmap_clear((Hashmap*) h);
+}

 void hashmap_clear_free(Hashmap *h);
 void hashmap_clear_free(Hashmap *h);

+static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
+        hashmap_clear_free((Hashmap*) h);
+}

 void hashmap_clear_free_free(Hashmap *h);
 void hashmap_clear_free_free(Hashmap *h);

+static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
+        hashmap_clear_free_free((Hashmap*) h);
+}

 
 void *hashmap_steal_first(Hashmap *h);
 
 void *hashmap_steal_first(Hashmap *h);

+static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
+        return hashmap_steal_first((Hashmap*) h);
+}

 void *hashmap_steal_first_key(Hashmap *h);
 void *hashmap_steal_first_key(Hashmap *h);

+static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
+        return hashmap_steal_first_key((Hashmap*) h);
+}

 void *hashmap_first(Hashmap *h) _pure_;
 void *hashmap_first(Hashmap *h) _pure_;

+static inline void *ordered_hashmap_first(OrderedHashmap *h) {
+        return hashmap_first((Hashmap*) h);
+}

 void *hashmap_first_key(Hashmap *h) _pure_;
 void *hashmap_first_key(Hashmap *h) _pure_;

+static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
+        return hashmap_first_key((Hashmap*) h);
+}

 
 void *hashmap_next(Hashmap *h, const void *key);
 
 void *hashmap_next(Hashmap *h, const void *key);

+static inline void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
+        return hashmap_next((Hashmap*) h, key);
+}

 
 char **hashmap_get_strv(Hashmap *h);
 
 char **hashmap_get_strv(Hashmap *h);

+static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
+        return hashmap_get_strv((Hashmap*) h);
+}

 
 #define HASHMAP_FOREACH(e, h, i) \
         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); (e); (e) = hashmap_iterate((h), &(i), NULL))
 
 
 #define HASHMAP_FOREACH(e, h, i) \
         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); (e); (e) = hashmap_iterate((h), &(i), NULL))
 

+#define ORDERED_HASHMAP_FOREACH(e, h, i) \
+        for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), NULL); \
+             (e); \
+             (e) = ordered_hashmap_iterate((h), &(i), NULL))
+

 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); (e); (e) = hashmap_iterate((h), &(i), (const void**) &(k)))
 
 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); (e); (e) = hashmap_iterate((h), &(i), (const void**) &(k)))
 

+#define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
+        for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)); \
+             (e); \
+             (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)))
+

 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);

+DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
+DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
+DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);

 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)

+#define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
+#define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
+#define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)