Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/common.h	Thu May 19 14:30:20 2022 +0200
     1.2 +++ b/src/cx/common.h	Sat May 21 11:22:47 2022 +0200
     1.3 @@ -100,7 +100,7 @@
     1.4      /**
     1.5       * A pointer to the data.
     1.6       */
     1.7 -    unsigned const char *data;
     1.8 +    unsigned char const *data;
     1.9      /**
    1.10       * The length of the data.
    1.11       */

     2.1 --- a/src/cx/iterator.h	Thu May 19 14:30:20 2022 +0200
     2.2 +++ b/src/cx/iterator.h	Sat May 21 11:22:47 2022 +0200
     2.3 @@ -46,17 +46,20 @@
     2.4      /**
     2.5       * True iff the iterator points to valid data.
     2.6       */
     2.7 -    bool (*valid)(struct cx_iterator_s const *) __attribute__ ((__nonnull__));
     2.8 +    __attribute__ ((__nonnull__))
     2.9 +    bool (*valid)(struct cx_iterator_s const *);
    2.10  
    2.11      /**
    2.12       * Returns a pointer to the current element.
    2.13       */
    2.14 -    void *(*current)(struct cx_iterator_s const *) __attribute__ ((__nonnull__));
    2.15 +    __attribute__ ((__nonnull__))
    2.16 +    void *(*current)(struct cx_iterator_s const *);
    2.17  
    2.18      /**
    2.19       * Advances the iterator.
    2.20       */
    2.21 -    void (*next)(struct cx_iterator_s *) __attribute__ ((__nonnull__));
    2.22 +    __attribute__ ((__nonnull__))
    2.23 +    void (*next)(struct cx_iterator_s *);
    2.24  
    2.25      /**
    2.26       * Handle for the current element, if required.
    2.27 @@ -69,6 +72,27 @@
    2.28      void *src_handle;
    2.29  
    2.30      /**
    2.31 +     * Field for storing a key-value pair.
    2.32 +     * May be used by iterators that iterate over k/v-collections.
    2.33 +     */
    2.34 +    struct {
    2.35 +        /**
    2.36 +         * A pointer to the key.
    2.37 +         */
    2.38 +        void *key;
    2.39 +        /**
    2.40 +         * A pointer to the value.
    2.41 +         */
    2.42 +        void *value;
    2.43 +    } kv_data;
    2.44 +
    2.45 +    /**
    2.46 +     * Field for storing a slot number.
    2.47 +     * May be used by iterators that iterate over multi-bucket collections.
    2.48 +     */
    2.49 +    size_t slot;
    2.50 +
    2.51 +    /**
    2.52       * If the iterator is position-aware, contains the index of the element in the underlying collection.
    2.53       * Otherwise, this field is usually uninitialized.
    2.54       */

     3.1 --- a/src/cx/map.h	Thu May 19 14:30:20 2022 +0200
     3.2 +++ b/src/cx/map.h	Sat May 21 11:22:47 2022 +0200
     3.3 @@ -113,19 +113,19 @@
     3.4       * Iterator over the key/value pairs.
     3.5       */
     3.6      __attribute__((__nonnull__, __warn_unused_result__))
     3.7 -    CxIterator (*iterator)(CxMap const *map);
     3.8 +    CxIterator (*iterator)(CxMap *map);
     3.9  
    3.10      /**
    3.11       * Iterator over the keys.
    3.12       */
    3.13      __attribute__((__nonnull__, __warn_unused_result__))
    3.14 -    CxIterator (*iterator_keys)(CxMap const *map);
    3.15 +    CxIterator (*iterator_keys)(CxMap *map);
    3.16  
    3.17      /**
    3.18       * Iterator over the values.
    3.19       */
    3.20      __attribute__((__nonnull__, __warn_unused_result__))
    3.21 -    CxIterator (*iterator_values)(CxMap const *map);
    3.22 +    CxIterator (*iterator_values)(CxMap *map);
    3.23  };
    3.24  
    3.25  /**
    3.26 @@ -133,13 +133,13 @@
    3.27   */
    3.28  struct cx_map_entry_s {
    3.29      /**
    3.30 -     * The key.
    3.31 +     * A pointer to the key.
    3.32       */
    3.33 -    CxDataPtr key;
    3.34 +    CxDataPtr const *key;
    3.35      /**
    3.36 -     * The value.
    3.37 +     * A pointer to the value.
    3.38       */
    3.39 -    void const *value;
    3.40 +    void *value;
    3.41  };
    3.42  
    3.43  
    3.44 @@ -224,7 +224,7 @@
    3.45   * @return an iterator for the currently stored values
    3.46   */
    3.47  __attribute__((__nonnull__, __warn_unused_result__))
    3.48 -static inline CxIterator cxMapIteratorValues(CxMap const *map) {
    3.49 +static inline CxIterator cxMapIteratorValues(CxMap *map) {
    3.50      return map->cl->iterator_values(map);
    3.51  }
    3.52  
    3.53 @@ -238,7 +238,7 @@
    3.54   * @return an iterator for the currently stored keys
    3.55   */
    3.56  __attribute__((__nonnull__, __warn_unused_result__))
    3.57 -static inline CxIterator cxMapIteratorKeys(CxMap const *map) {
    3.58 +static inline CxIterator cxMapIteratorKeys(CxMap *map) {
    3.59      return map->cl->iterator_keys(map);
    3.60  }
    3.61  
    3.62 @@ -256,7 +256,7 @@
    3.63   * @see cxMapIteratorValues()
    3.64   */
    3.65  __attribute__((__nonnull__, __warn_unused_result__))
    3.66 -static inline CxIterator cxMapIterator(CxMap const *map) {
    3.67 +static inline CxIterator cxMapIterator(CxMap *map) {
    3.68      return map->cl->iterator(map);
    3.69  }
    3.70  

     4.1 --- a/src/hash_map.c	Thu May 19 14:30:20 2022 +0200
     4.2 +++ b/src/hash_map.c	Sat May 21 11:22:47 2022 +0200
     4.3 @@ -175,6 +175,25 @@
     4.4      return 0;
     4.5  }
     4.6  
     4.7 +static void cx_hash_map_unlink(
     4.8 +        struct cx_hash_map_s *hash_map,
     4.9 +        size_t slot,
    4.10 +        struct cx_hash_map_element_s *prev,
    4.11 +        struct cx_hash_map_element_s *elm
    4.12 +) {
    4.13 +    // unlink
    4.14 +    if (prev == NULL) {
    4.15 +        hash_map->buckets[slot] = elm->next;
    4.16 +    } else {
    4.17 +        prev->next = elm->next;
    4.18 +    }
    4.19 +    // free element
    4.20 +    cxFree(hash_map->base.allocator, elm->key.data);
    4.21 +    cxFree(hash_map->base.allocator, elm);
    4.22 +    // decrease size
    4.23 +    hash_map->base.size--;
    4.24 +}
    4.25 +
    4.26  /**
    4.27   * Helper function to avoid code duplication.
    4.28   *
    4.29 @@ -200,17 +219,7 @@
    4.30              if (memcmp(elm->key.data, key.data, key.len) == 0) {
    4.31                  void *data = elm->data;
    4.32                  if (remove) {
    4.33 -                    // unlink
    4.34 -                    if (prev) {
    4.35 -                        prev->next = elm->next;
    4.36 -                    } else {
    4.37 -                        hash_map->buckets[slot] = elm->next;
    4.38 -                    }
    4.39 -                    // free element
    4.40 -                    cxFree(map->allocator, elm->key.data);
    4.41 -                    cxFree(map->allocator, elm);
    4.42 -                    // decrease size
    4.43 -                    map->size--;
    4.44 +                    cx_hash_map_unlink(hash_map, slot, prev, elm);
    4.45                  }
    4.46                  return data;
    4.47              }
    4.48 @@ -237,21 +246,120 @@
    4.49      return cx_hash_map_get_remove(map, key, true);
    4.50  }
    4.51  
    4.52 -static CxIterator cx_hash_map_iterator(CxMap const *map) {
    4.53 +static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
    4.54 +    // struct has to have a compatible signature
    4.55 +    struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data);
    4.56 +    return entry;
    4.57 +}
    4.58 +
    4.59 +static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
    4.60 +    struct cx_hash_map_element_s *elm = iter->elem_handle;
    4.61 +    return &elm->key;
    4.62 +}
    4.63 +
    4.64 +static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
    4.65 +    struct cx_hash_map_element_s *elm = iter->elem_handle;
    4.66 +    // TODO: return a pointer to data if this map is storing copies
    4.67 +    return elm->data;
    4.68 +}
    4.69 +
    4.70 +static bool cx_hash_map_iter_valid(CxIterator const *iter) {
    4.71 +    return iter->elem_handle != NULL;
    4.72 +}
    4.73 +
    4.74 +static void cx_hash_map_iter_next(CxIterator *iter) {
    4.75 +    struct cx_hash_map_s *map = iter->src_handle;
    4.76 +    struct cx_hash_map_element_s *elm = iter->elem_handle;
    4.77 +
    4.78 +    // remove current element, if asked
    4.79 +    if (iter->remove) {
    4.80 +        // clear the flag
    4.81 +        iter->remove = false;
    4.82 +
    4.83 +        // determine the next element
    4.84 +        struct cx_hash_map_element_s *next = elm->next;
    4.85 +
    4.86 +        // search the previous element
    4.87 +        struct cx_hash_map_element_s *prev = NULL;
    4.88 +        if (map->buckets[iter->slot] != elm) {
    4.89 +            prev = map->buckets[iter->slot];
    4.90 +            while (prev->next != elm) {
    4.91 +                prev = prev->next;
    4.92 +            }
    4.93 +        }
    4.94 +
    4.95 +        // unlink
    4.96 +        cx_hash_map_unlink(map, iter->slot, prev, elm);
    4.97 +
    4.98 +        // advance
    4.99 +        elm = next;
   4.100 +    } else {
   4.101 +        // just advance
   4.102 +        elm = elm->next;
   4.103 +    }
   4.104 +
   4.105 +    // do we leave the bucket?
   4.106 +    if (elm == NULL) {
   4.107 +        // search the next bucket
   4.108 +        for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) {
   4.109 +            elm = map->buckets[iter->slot];
   4.110 +        }
   4.111 +    }
   4.112 +
   4.113 +    // advance the index in any case
   4.114 +    iter->index++;
   4.115 +
   4.116 +    // fill the struct with the current element
   4.117 +    iter->elem_handle = elm;
   4.118 +    if (elm == NULL) {
   4.119 +        iter->kv_data.key = NULL;
   4.120 +        iter->kv_data.value = NULL;
   4.121 +    } else {
   4.122 +        iter->kv_data.key = &elm->key;
   4.123 +        // TODO: pointer to data if this map is storing copies
   4.124 +        iter->kv_data.value = elm->data;
   4.125 +    }
   4.126 +}
   4.127 +
   4.128 +static CxIterator cx_hash_map_iterator(CxMap *map) {
   4.129      CxIterator iter;
   4.130 -    // TODO: initialize iter
   4.131 +
   4.132 +    iter.src_handle = map;
   4.133 +    iter.valid = cx_hash_map_iter_valid;
   4.134 +    iter.next = cx_hash_map_iter_next;
   4.135 +    iter.current = cx_hash_map_iter_current_entry;
   4.136 +
   4.137 +    iter.slot = 0;
   4.138 +    iter.index = 0;
   4.139 +    iter.remove = false;
   4.140 +
   4.141 +    if (map->size > 0) {
   4.142 +        struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
   4.143 +        struct cx_hash_map_element_s *elem = NULL;
   4.144 +        for (; elem == NULL; iter.slot++) {
   4.145 +            elem = hash_map->buckets[iter.slot];
   4.146 +        }
   4.147 +        iter.elem_handle = elem;
   4.148 +        iter.kv_data.key = NULL;
   4.149 +        iter.kv_data.value = NULL;
   4.150 +    } else {
   4.151 +        iter.elem_handle = NULL;
   4.152 +        iter.kv_data.key = NULL;
   4.153 +        iter.kv_data.value = NULL;
   4.154 +    }
   4.155 +
   4.156      return iter;
   4.157  }
   4.158  
   4.159 -static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
   4.160 -    CxIterator iter;
   4.161 -    // TODO: initialize iter
   4.162 +static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
   4.163 +    CxIterator iter = cx_hash_map_iterator(map);
   4.164 +    iter.current = cx_hash_map_iter_current_key;
   4.165      return iter;
   4.166  }
   4.167  
   4.168 -static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
   4.169 -    CxIterator iter;
   4.170 -    // TODO: initialize iter
   4.171 +static CxIterator cx_hash_map_iterator_values(CxMap *map) {
   4.172 +    CxIterator iter = cx_hash_map_iterator(map);
   4.173 +    iter.current = cx_hash_map_iter_current_value;
   4.174      return iter;
   4.175  }
   4.176