Mercurial > hg > ucx / changeset

--- a/src/cx/common.h	Thu May 19 14:30:20 2022 +0200
+++ b/src/cx/common.h	Sat May 21 11:22:47 2022 +0200
@@ -100,7 +100,7 @@
     /**
      * A pointer to the data.
      */
-    unsigned const char *data;
+    unsigned char const *data;
     /**
      * The length of the data.
      */

--- a/src/cx/iterator.h	Thu May 19 14:30:20 2022 +0200
+++ b/src/cx/iterator.h	Sat May 21 11:22:47 2022 +0200
@@ -46,17 +46,20 @@
     /**
      * True iff the iterator points to valid data.
      */
-    bool (*valid)(struct cx_iterator_s const *) __attribute__ ((__nonnull__));
+    __attribute__ ((__nonnull__))
+    bool (*valid)(struct cx_iterator_s const *);
 
     /**
      * Returns a pointer to the current element.
      */
-    void *(*current)(struct cx_iterator_s const *) __attribute__ ((__nonnull__));
+    __attribute__ ((__nonnull__))
+    void *(*current)(struct cx_iterator_s const *);
 
     /**
      * Advances the iterator.
      */
-    void (*next)(struct cx_iterator_s *) __attribute__ ((__nonnull__));
+    __attribute__ ((__nonnull__))
+    void (*next)(struct cx_iterator_s *);
 
     /**
      * Handle for the current element, if required.
@@ -69,6 +72,27 @@
     void *src_handle;
 
     /**
+     * Field for storing a key-value pair.
+     * May be used by iterators that iterate over k/v-collections.
+     */
+    struct {
+        /**
+         * A pointer to the key.
+         */
+        void *key;
+        /**
+         * A pointer to the value.
+         */
+        void *value;
+    } kv_data;
+
+    /**
+     * Field for storing a slot number.
+     * May be used by iterators that iterate over multi-bucket collections.
+     */
+    size_t slot;
+
+    /**
      * If the iterator is position-aware, contains the index of the element in the underlying collection.
      * Otherwise, this field is usually uninitialized.
      */

--- a/src/cx/map.h	Thu May 19 14:30:20 2022 +0200
+++ b/src/cx/map.h	Sat May 21 11:22:47 2022 +0200
@@ -113,19 +113,19 @@
      * Iterator over the key/value pairs.
      */
     __attribute__((__nonnull__, __warn_unused_result__))
-    CxIterator (*iterator)(CxMap const *map);
+    CxIterator (*iterator)(CxMap *map);
 
     /**
      * Iterator over the keys.
      */
     __attribute__((__nonnull__, __warn_unused_result__))
-    CxIterator (*iterator_keys)(CxMap const *map);
+    CxIterator (*iterator_keys)(CxMap *map);
 
     /**
      * Iterator over the values.
      */
     __attribute__((__nonnull__, __warn_unused_result__))
-    CxIterator (*iterator_values)(CxMap const *map);
+    CxIterator (*iterator_values)(CxMap *map);
 };
 
 /**
@@ -133,13 +133,13 @@
  */
 struct cx_map_entry_s {
     /**
-     * The key.
+     * A pointer to the key.
      */
-    CxDataPtr key;
+    CxDataPtr const *key;
     /**
-     * The value.
+     * A pointer to the value.
      */
-    void const *value;
+    void *value;
 };
 
 
@@ -224,7 +224,7 @@
  * @return an iterator for the currently stored values
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxMapIteratorValues(CxMap const *map) {
+static inline CxIterator cxMapIteratorValues(CxMap *map) {
     return map->cl->iterator_values(map);
 }
 
@@ -238,7 +238,7 @@
  * @return an iterator for the currently stored keys
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxMapIteratorKeys(CxMap const *map) {
+static inline CxIterator cxMapIteratorKeys(CxMap *map) {
     return map->cl->iterator_keys(map);
 }
 
@@ -256,7 +256,7 @@
  * @see cxMapIteratorValues()
  */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxMapIterator(CxMap const *map) {
+static inline CxIterator cxMapIterator(CxMap *map) {
     return map->cl->iterator(map);
 }
 

--- a/src/hash_map.c	Thu May 19 14:30:20 2022 +0200
+++ b/src/hash_map.c	Sat May 21 11:22:47 2022 +0200
@@ -175,6 +175,25 @@
     return 0;
 }
 
+static void cx_hash_map_unlink(
+        struct cx_hash_map_s *hash_map,
+        size_t slot,
+        struct cx_hash_map_element_s *prev,
+        struct cx_hash_map_element_s *elm
+) {
+    // unlink
+    if (prev == NULL) {
+        hash_map->buckets[slot] = elm->next;
+    } else {
+        prev->next = elm->next;
+    }
+    // free element
+    cxFree(hash_map->base.allocator, elm->key.data);
+    cxFree(hash_map->base.allocator, elm);
+    // decrease size
+    hash_map->base.size--;
+}
+
 /**
  * Helper function to avoid code duplication.
  *
@@ -200,17 +219,7 @@
             if (memcmp(elm->key.data, key.data, key.len) == 0) {
                 void *data = elm->data;
                 if (remove) {
-                    // unlink
-                    if (prev) {
-                        prev->next = elm->next;
-                    } else {
-                        hash_map->buckets[slot] = elm->next;
-                    }
-                    // free element
-                    cxFree(map->allocator, elm->key.data);
-                    cxFree(map->allocator, elm);
-                    // decrease size
-                    map->size--;
+                    cx_hash_map_unlink(hash_map, slot, prev, elm);
                 }
                 return data;
             }
@@ -237,21 +246,120 @@
     return cx_hash_map_get_remove(map, key, true);
 }
 
-static CxIterator cx_hash_map_iterator(CxMap const *map) {
+static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
+    // struct has to have a compatible signature
+    struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data);
+    return entry;
+}
+
+static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
+    struct cx_hash_map_element_s *elm = iter->elem_handle;
+    return &elm->key;
+}
+
+static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
+    struct cx_hash_map_element_s *elm = iter->elem_handle;
+    // TODO: return a pointer to data if this map is storing copies
+    return elm->data;
+}
+
+static bool cx_hash_map_iter_valid(CxIterator const *iter) {
+    return iter->elem_handle != NULL;
+}
+
+static void cx_hash_map_iter_next(CxIterator *iter) {
+    struct cx_hash_map_s *map = iter->src_handle;
+    struct cx_hash_map_element_s *elm = iter->elem_handle;
+
+    // remove current element, if asked
+    if (iter->remove) {
+        // clear the flag
+        iter->remove = false;
+
+        // determine the next element
+        struct cx_hash_map_element_s *next = elm->next;
+
+        // search the previous element
+        struct cx_hash_map_element_s *prev = NULL;
+        if (map->buckets[iter->slot] != elm) {
+            prev = map->buckets[iter->slot];
+            while (prev->next != elm) {
+                prev = prev->next;
+            }
+        }
+
+        // unlink
+        cx_hash_map_unlink(map, iter->slot, prev, elm);
+
+        // advance
+        elm = next;
+    } else {
+        // just advance
+        elm = elm->next;
+    }
+
+    // do we leave the bucket?
+    if (elm == NULL) {
+        // search the next bucket
+        for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) {
+            elm = map->buckets[iter->slot];
+        }
+    }
+
+    // advance the index in any case
+    iter->index++;
+
+    // fill the struct with the current element
+    iter->elem_handle = elm;
+    if (elm == NULL) {
+        iter->kv_data.key = NULL;
+        iter->kv_data.value = NULL;
+    } else {
+        iter->kv_data.key = &elm->key;
+        // TODO: pointer to data if this map is storing copies
+        iter->kv_data.value = elm->data;
+    }
+}
+
+static CxIterator cx_hash_map_iterator(CxMap *map) {
     CxIterator iter;
-    // TODO: initialize iter
+
+    iter.src_handle = map;
+    iter.valid = cx_hash_map_iter_valid;
+    iter.next = cx_hash_map_iter_next;
+    iter.current = cx_hash_map_iter_current_entry;
+
+    iter.slot = 0;
+    iter.index = 0;
+    iter.remove = false;
+
+    if (map->size > 0) {
+        struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
+        struct cx_hash_map_element_s *elem = NULL;
+        for (; elem == NULL; iter.slot++) {
+            elem = hash_map->buckets[iter.slot];
+        }
+        iter.elem_handle = elem;
+        iter.kv_data.key = NULL;
+        iter.kv_data.value = NULL;
+    } else {
+        iter.elem_handle = NULL;
+        iter.kv_data.key = NULL;
+        iter.kv_data.value = NULL;
+    }
+
     return iter;
 }
 
-static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
-    CxIterator iter;
-    // TODO: initialize iter
+static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
+    CxIterator iter = cx_hash_map_iterator(map);
+    iter.current = cx_hash_map_iter_current_key;
     return iter;
 }
 
-static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
-    CxIterator iter;
-    // TODO: initialize iter
+static CxIterator cx_hash_map_iterator_values(CxMap *map) {
+    CxIterator iter = cx_hash_map_iterator(map);
+    iter.current = cx_hash_map_iter_current_value;
     return iter;
 }