hashmap: fix iterators to not skip entries

Currently, the HASHMAP iterators stop at the first NULL entry in a
hashmap. This is non-obvious and breaks users like sd-device, which
legitimately store NULL values in a hashmap.

Fix all the iterators by taking a pointer to the value storage, instead of
returning it. The iterators now return a boolean that tells whether the
end of the list was reached.

Current users of HASHMAP_FOREACH() are *NOT* changed to explicitly check
for NULL. If it turns out, there were users that inserted NULL into
hashmaps, but didn't properly check for it during iteration, then we
really want to find those and fix them.

diff --git a/src/libelogind/sd-bus/bus-track.c b/src/libelogind/sd-bus/bus-track.c
index ec9340f8e1a1f4a90326ba095621ca6180efff60..e43891be258477a686b397855e741d979e2e613e 100644 (file)
--- a/src/libelogind/sd-bus/bus-track.c
+++ b/src/libelogind/sd-bus/bus-track.c
@@ -248,7 +248,7 @@ _public_ const char* sd_bus_track_first(sd_bus_track *track) {
         track->modified = false;
         track->iterator = ITERATOR_FIRST;
 
-        hashmap_iterate(track->names, &track->iterator, (const void**) &n);
+        hashmap_iterate(track->names, &track->iterator, NULL, (const void**) &n);
         return n;
 }
 
@@ -261,7 +261,7 @@ _public_ const char* sd_bus_track_next(sd_bus_track *track) {
         if (track->modified)
                 return NULL;
 
-        hashmap_iterate(track->names, &track->iterator, (const void**) &n);
+        hashmap_iterate(track->names, &track->iterator, NULL, (const void**) &n);
         return n;
 }
 

diff --git a/src/libelogind/sd-device/sd-device.c b/src/libelogind/sd-device/sd-device.c
index 8e63b9ef560921b0bdedcf266e0483b88dedc286..b274f710935841f027c94c45d5dcf04dc9a58373 100644 (file)
--- a/src/libelogind/sd-device/sd-device.c
+++ b/src/libelogind/sd-device/sd-device.c
@@ -1371,6 +1371,8 @@ _public_ int sd_device_get_usec_since_initialized(sd_device *device, uint64_t *u
 }
 
 _public_ const char *sd_device_get_tag_first(sd_device *device) {
+        void *v;
+
         assert_return(device, NULL);
 
         (void) device_read_db(device);
@@ -1378,10 +1380,13 @@ _public_ const char *sd_device_get_tag_first(sd_device *device) {
         device->tags_iterator_generation = device->tags_generation;
         device->tags_iterator = ITERATOR_FIRST;
 
-        return set_iterate(device->tags, &device->tags_iterator);
+        set_iterate(device->tags, &device->tags_iterator, &v);
+        return v;
 }
 
 _public_ const char *sd_device_get_tag_next(sd_device *device) {
+        void *v;
+
         assert_return(device, NULL);
 
         (void) device_read_db(device);
@@ -1389,10 +1394,13 @@ _public_ const char *sd_device_get_tag_next(sd_device *device) {
         if (device->tags_iterator_generation != device->tags_generation)
                 return NULL;
 
-        return set_iterate(device->tags, &device->tags_iterator);
+        set_iterate(device->tags, &device->tags_iterator, &v);
+        return v;
 }
 
 _public_ const char *sd_device_get_devlink_first(sd_device *device) {
+        void *v;
+
         assert_return(device, NULL);
 
         (void) device_read_db(device);
@@ -1400,10 +1408,13 @@ _public_ const char *sd_device_get_devlink_first(sd_device *device) {
         device->devlinks_iterator_generation = device->devlinks_generation;
         device->devlinks_iterator = ITERATOR_FIRST;
 
-        return set_iterate(device->devlinks, &device->devlinks_iterator);
+        set_iterate(device->devlinks, &device->devlinks_iterator, &v);
+        return v;
 }
 
 _public_ const char *sd_device_get_devlink_next(sd_device *device) {
+        void *v;
+
         assert_return(device, NULL);
 
         (void) device_read_db(device);
@@ -1411,7 +1422,8 @@ _public_ const char *sd_device_get_devlink_next(sd_device *device) {
         if (device->devlinks_iterator_generation != device->devlinks_generation)
                 return NULL;
 
-        return set_iterate(device->devlinks, &device->devlinks_iterator);
+        set_iterate(device->devlinks, &device->devlinks_iterator, &v);
+        return v;
 }
 
 static int device_properties_prepare(sd_device *device) {
@@ -1482,7 +1494,7 @@ _public_ const char *sd_device_get_property_first(sd_device *device, const char
         device->properties_iterator_generation = device->properties_generation;
         device->properties_iterator = ITERATOR_FIRST;
 
-        value = ordered_hashmap_iterate(device->properties, &device->properties_iterator, (const void**)&key);
+        ordered_hashmap_iterate(device->properties, &device->properties_iterator, (void**)&value, (const void**)&key);
 
         if (_value)
                 *_value = value;
@@ -1504,7 +1516,7 @@ _public_ const char *sd_device_get_property_next(sd_device *device, const char *
         if (device->properties_iterator_generation != device->properties_generation)
                 return NULL;
 
-        value = ordered_hashmap_iterate(device->properties, &device->properties_iterator, (const void**)&key);
+        ordered_hashmap_iterate(device->properties, &device->properties_iterator, (void**)&value, (const void**)&key);
 
         if (_value)
                 *_value = value;
@@ -1562,6 +1574,7 @@ static int device_sysattrs_read_all(sd_device *device) {
 }
 
 _public_ const char *sd_device_get_sysattr_first(sd_device *device) {
+        void *v;
         int r;
 
         assert_return(device, NULL);
@@ -1576,16 +1589,20 @@ _public_ const char *sd_device_get_sysattr_first(sd_device *device) {
 
         device->sysattrs_iterator = ITERATOR_FIRST;
 
-        return set_iterate(device->sysattrs, &device->sysattrs_iterator);
+        set_iterate(device->sysattrs, &device->sysattrs_iterator, &v);
+        return v;
 }
 
 _public_ const char *sd_device_get_sysattr_next(sd_device *device) {
+        void *v;
+
         assert_return(device, NULL);
 
         if (!device->sysattrs_read)
                 return NULL;
 
-        return set_iterate(device->sysattrs, &device->sysattrs_iterator);
+        set_iterate(device->sysattrs, &device->sysattrs_iterator, &v);
+        return v;
 }
 
 _public_ int sd_device_has_tag(sd_device *device, const char *tag) {

diff --git a/src/libelogind/sd-hwdb/sd-hwdb.c b/src/libelogind/sd-hwdb/sd-hwdb.c
index 2a0e00f7d234a5b5b10f37c2735964df5dd56124..40aa77ee5ca2af1c441cd16a90a532250e7a9350 100644 (file)
--- a/src/libelogind/sd-hwdb/sd-hwdb.c
+++ b/src/libelogind/sd-hwdb/sd-hwdb.c
@@ -449,7 +449,8 @@ _public_ int sd_hwdb_seek(sd_hwdb *hwdb, const char *modalias) {
 }
 
 _public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **value) {
-        const void *k, *v;
+        const void *k;
+        void *v;
 
         assert_return(hwdb, -EINVAL);
         assert_return(key, -EINVAL);
@@ -458,7 +459,7 @@ _public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **val
         if (hwdb->properties_modified)
                 return -EAGAIN;
 
-        v = ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, &k);
+        ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, &v, &k);
         if (!k)
                 return 0;
 

diff --git a/src/shared/fdset.c b/src/shared/fdset.c
index 6101b628ec2fd245656c50e01324f6ee6cf7c0af..a4823e6659623602d71227929e797d83d87e38ef 100644 (file)
--- a/src/shared/fdset.c
+++ b/src/shared/fdset.c
@@ -267,8 +267,7 @@ bool fdset_isempty(FDSet *fds) {
 int fdset_iterate(FDSet *s, Iterator *i) {
         void *p;
 
-        p = set_iterate(MAKE_SET(s), i);
-        if (!p)
+        if (!set_iterate(MAKE_SET(s), i, &p))
                 return -ENOENT;
 
         return PTR_TO_FD(p);

diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 20d599d04b3a04ab1c6525e36e40669cd2b388bb..0ee2f3bd317ce50abfe7729a919cb9ed8a4b6a36 100644 (file)
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -733,29 +733,33 @@ static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
                                                : hashmap_iterate_in_internal_order(h, i);
 }
 
-void *internal_hashmap_iterate(HashmapBase *h, Iterator *i, const void **key) {
+bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {
         struct hashmap_base_entry *e;
         void *data;
         unsigned idx;
 
         idx = hashmap_iterate_entry(h, i);
         if (idx == IDX_NIL) {
+                if (value)
+                        *value = NULL;
                 if (key)
                         *key = NULL;
 
-                return NULL;
+                return false;
         }
 
         e = bucket_at(h, idx);
         data = entry_value(h, e);
+        if (value)
+                *value = data;
         if (key)
                 *key = e->key;
 
-        return data;
+        return true;
 }
 
-void *set_iterate(Set *s, Iterator *i) {
-        return internal_hashmap_iterate(HASHMAP_BASE(s), i, NULL);
+bool set_iterate(Set *s, Iterator *i, void **value) {
+        return internal_hashmap_iterate(HASHMAP_BASE(s), i, value, NULL);
 }
 
 #define HASHMAP_FOREACH_IDX(idx, h, i) \

diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h
index a03ee5812a677d470e1f3878fac14b27ee2d442f..5723f09ca9134c117652439d92426ccf8b5efadc 100644 (file)
--- a/src/shared/hashmap.h
+++ b/src/shared/hashmap.h
@@ -65,6 +65,7 @@ typedef struct {
 } Iterator;
 
 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
+#define _IDX_ITERATOR_NIL (UINT_MAX)
 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
 
 typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
@@ -296,12 +297,12 @@ static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
         return internal_hashmap_buckets(HASHMAP_BASE(h));
 }
 
-void *internal_hashmap_iterate(HashmapBase *h, Iterator *i, const void **key);
-static inline void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
-        return internal_hashmap_iterate(HASHMAP_BASE(h), i, key);
+bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key);
+static inline bool hashmap_iterate(Hashmap *h, Iterator *i, void **value, const void **key) {
+        return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 }
-static inline void *ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, const void **key) {
-        return internal_hashmap_iterate(HASHMAP_BASE(h), i, key);
+static inline bool ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, void **value, const void **key) {
+        return internal_hashmap_iterate(HASHMAP_BASE(h), i, value, key);
 }
 
 void internal_hashmap_clear(HashmapBase *h);
@@ -386,24 +387,16 @@ static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
  * It is safe to remove the current entry.
  */
 #define HASHMAP_FOREACH(e, h, i) \
-        for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); \
-             (e); \
-             (e) = hashmap_iterate((h), &(i), NULL))
+        for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), 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))
+        for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), 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)))
+        for ((i) = ITERATOR_FIRST; hashmap_iterate((h), &(i), (void**)&(e), (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)))
+        for ((i) = ITERATOR_FIRST; ordered_hashmap_iterate((h), &(i), (void**)&(e), (const void**) &(k)); )
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);

diff --git a/src/shared/set.h b/src/shared/set.h
index 4dffecd39d9de947786c919c7eca17f63428d419..51e40d3a6c506c9ccfce9a51bb9587c2483807c4 100644 (file)
--- a/src/shared/set.h
+++ b/src/shared/set.h
@@ -91,7 +91,7 @@ static inline unsigned set_buckets(Set *s) {
         return internal_hashmap_buckets(HASHMAP_BASE(s));
 }
 
-void *set_iterate(Set *s, Iterator *i);
+bool set_iterate(Set *s, Iterator *i, void **value);
 
 static inline void set_clear(Set *s) {
         internal_hashmap_clear(HASHMAP_BASE(s));
@@ -125,7 +125,7 @@ int set_put_strdup(Set *s, const char *p);
 int set_put_strdupv(Set *s, char **l);
 
 #define SET_FOREACH(e, s, i) \
-        for ((i) = ITERATOR_FIRST, (e) = set_iterate((s), &(i)); (e); (e) = set_iterate((s), &(i)))
+        for ((i) = ITERATOR_FIRST; set_iterate((s), &(i), (void**)&(e)); )
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(Set*, set_free);
 DEFINE_TRIVIAL_CLEANUP_FUNC(Set*, set_free_free);