Mercurial > hg > ucx / changeset

     1.1 --- a/src/CMakeLists.txt	Fri May 27 17:40:27 2022 +0200
     1.2 +++ b/src/CMakeLists.txt	Wed Jun 08 21:33:31 2022 +0200
     1.3 @@ -5,7 +5,7 @@
     1.4          linked_list.c
     1.5          tree.c
     1.6          buffer.c
     1.7 -        map.c
     1.8 +        hash_key.c
     1.9          hash_map.c
    1.10  )
    1.11  set(headers
    1.12 @@ -18,6 +18,7 @@
    1.13          cx/tree.h
    1.14          cx/buffer.h
    1.15          cx/map.h
    1.16 +        cx/hash_key.h
    1.17          cx/hash_map.h
    1.18          )
    1.19  

     2.1 --- a/src/cx/common.h	Fri May 27 17:40:27 2022 +0200
     2.2 +++ b/src/cx/common.h	Wed Jun 08 21:33:31 2022 +0200
     2.3 @@ -94,25 +94,6 @@
     2.4  #include <stdbool.h>
     2.5  
     2.6  /**
     2.7 - * Structure that contains a pointer to arbitrary data.
     2.8 - */
     2.9 -struct cx_data_ptr_s {
    2.10 -    /**
    2.11 -     * A pointer to the data.
    2.12 -     */
    2.13 -    unsigned char const *data;
    2.14 -    /**
    2.15 -     * The length of the data.
    2.16 -     */
    2.17 -    size_t len;
    2.18 -};
    2.19 -
    2.20 -/**
    2.21 - * Type for a data pointer with length information.
    2.22 - */
    2.23 -typedef struct cx_data_ptr_s CxDataPtr;
    2.24 -
    2.25 -/**
    2.26   * Function pointer compatible with fwrite-like functions.
    2.27   */
    2.28  typedef size_t (*cx_write_func)(

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/cx/hash_key.h	Wed Jun 08 21:33:31 2022 +0200
     3.3 @@ -0,0 +1,125 @@
     3.4 +/*
     3.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     3.6 + *
     3.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     3.8 + *
     3.9 + * Redistribution and use in source and binary forms, with or without
    3.10 + * modification, are permitted provided that the following conditions are met:
    3.11 + *
    3.12 + *   1. Redistributions of source code must retain the above copyright
    3.13 + *      notice, this list of conditions and the following disclaimer.
    3.14 + *
    3.15 + *   2. Redistributions in binary form must reproduce the above copyright
    3.16 + *      notice, this list of conditions and the following disclaimer in the
    3.17 + *      documentation and/or other materials provided with the distribution.
    3.18 + *
    3.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    3.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    3.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    3.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    3.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    3.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    3.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    3.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    3.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    3.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    3.29 + * POSSIBILITY OF SUCH DAMAGE.
    3.30 + */
    3.31 +/**
    3.32 + * \file hash_key.h
    3.33 + * \brief Interface for map implementations.
    3.34 + * \author Mike Becker
    3.35 + * \author Olaf Wintermann
    3.36 + * \version 3.0
    3.37 + * \copyright 2-Clause BSD License
    3.38 + */
    3.39 +
    3.40 +
    3.41 +#ifndef UCX_HASH_KEY_H
    3.42 +#define UCX_HASH_KEY_H
    3.43 +
    3.44 +#include "stddef.h"
    3.45 +
    3.46 +#ifdef __cplusplus
    3.47 +extern "C" {
    3.48 +#endif
    3.49 +
    3.50 +/** Internal structure for a key within a hash map. */
    3.51 +struct cx_hash_key_s {
    3.52 +    /** The key data. */
    3.53 +    union {
    3.54 +        unsigned char *bytes;
    3.55 +        unsigned char const *cbytes;
    3.56 +        char const *cstr;
    3.57 +        char *str;
    3.58 +        void *obj;
    3.59 +    } data;
    3.60 +    /**
    3.61 +     * The key data length.
    3.62 +     */
    3.63 +    size_t len;
    3.64 +    /** The hash value of the key data. */
    3.65 +    unsigned hash;
    3.66 +};
    3.67 +
    3.68 +/**
    3.69 + * Type for a hash key.
    3.70 + */
    3.71 +typedef struct cx_hash_key_s CxHashKey;
    3.72 +
    3.73 +/**
    3.74 + * Computes a murmur hash-2.
    3.75 + *
    3.76 + * You need to initialize data and len in the key struct.
    3.77 + * The hash is then directly written to that struct.
    3.78 + *
    3.79 + * @param key the key, the hash shall be computed for
    3.80 + */
    3.81 +void cx_hash_murmur(CxHashKey *key);
    3.82 +
    3.83 +/**
    3.84 + * Computes a hash key from a string.
    3.85 + *
    3.86 + * The string needs to be zero-terminated.
    3.87 + *
    3.88 + * @param str the string
    3.89 + * @return the hash key
    3.90 + */
    3.91 +__attribute__((__warn_unused_result__))
    3.92 +CxHashKey cx_hash_key_str(char const *str);
    3.93 +
    3.94 +/**
    3.95 + * Computes a hash key from a byte array.
    3.96 + *
    3.97 + * @param bytes the array
    3.98 + * @param len the length
    3.99 + * @return the hash key
   3.100 + */
   3.101 +__attribute__((__warn_unused_result__))
   3.102 +CxHashKey cx_hash_key_bytes(
   3.103 +        unsigned char const *bytes,
   3.104 +        size_t len
   3.105 +);
   3.106 +
   3.107 +/**
   3.108 + * Computes a hash key for an arbitrary object.
   3.109 + *
   3.110 + * The computation uses the in-memory representation that might not be
   3.111 + * the same on different platforms. Therefore, this hash should not be
   3.112 + * used for data exchange with different machines.
   3.113 + *
   3.114 + * @param obj a pointer to an arbitrary object
   3.115 + * @param len the length of object in memory
   3.116 + * @return the hash key
   3.117 + */
   3.118 +__attribute__((__warn_unused_result__))
   3.119 +CxHashKey cx_hash_key(
   3.120 +        void *obj,
   3.121 +        size_t len
   3.122 +);
   3.123 +
   3.124 +#ifdef __cplusplus
   3.125 +} // extern "C"
   3.126 +#endif
   3.127 +
   3.128 +#endif /* UCX_HASH_KEY_H */

     4.1 --- a/src/cx/hash_map.h	Fri May 27 17:40:27 2022 +0200
     4.2 +++ b/src/cx/hash_map.h	Wed Jun 08 21:33:31 2022 +0200
     4.3 @@ -26,8 +26,8 @@
     4.4   * POSSIBILITY OF SUCH DAMAGE.
     4.5   */
     4.6  /**
     4.7 - * \file map.h
     4.8 - * \brief Interface for map implementations.
     4.9 + * \file hash_map.h
    4.10 + * \brief Hash map implementation.
    4.11   * \author Mike Becker
    4.12   * \author Olaf Wintermann
    4.13   * \version 3.0
    4.14 @@ -43,18 +43,6 @@
    4.15  extern "C" {
    4.16  #endif
    4.17  
    4.18 -/** Internal structure for a key within a hash map. */
    4.19 -struct cx_hash_map_key_s {
    4.20 -    /** The key data. */
    4.21 -    unsigned char *data;
    4.22 -    /**
    4.23 -     * The key data length.
    4.24 -     */
    4.25 -    size_t len;
    4.26 -    /** The hash value of the key data. */
    4.27 -    unsigned hash;
    4.28 -};
    4.29 -
    4.30  /** Internal structure for an element of a hash map. */
    4.31  struct cx_hash_map_element_s {
    4.32      /** The value data. */
    4.33 @@ -64,7 +52,7 @@
    4.34      struct cx_hash_map_element_s *next;
    4.35  
    4.36      /** The corresponding key. */
    4.37 -    struct cx_hash_map_key_s key;
    4.38 +    CxHashKey key;
    4.39  };
    4.40  
    4.41  /**

     5.1 --- a/src/cx/map.h	Fri May 27 17:40:27 2022 +0200
     5.2 +++ b/src/cx/map.h	Wed Jun 08 21:33:31 2022 +0200
     5.3 @@ -40,6 +40,7 @@
     5.4  #include "common.h"
     5.5  #include "allocator.h"
     5.6  #include "iterator.h"
     5.7 +#include "hash_key.h"
     5.8  
     5.9  #ifdef    __cplusplus
    5.10  extern "C" {
    5.11 @@ -87,7 +88,7 @@
    5.12      __attribute__((__nonnull__))
    5.13      int (*put)(
    5.14              CxMap *map,
    5.15 -            CxDataPtr key,
    5.16 +            CxHashKey key,
    5.17              void *value
    5.18      );
    5.19  
    5.20 @@ -97,7 +98,7 @@
    5.21      __attribute__((__nonnull__, __warn_unused_result__))
    5.22      void *(*get)(
    5.23              CxMap const *map,
    5.24 -            CxDataPtr key
    5.25 +            CxHashKey key
    5.26      );
    5.27  
    5.28      /**
    5.29 @@ -106,7 +107,7 @@
    5.30      __attribute__((__nonnull__, __warn_unused_result__))
    5.31      void *(*remove)(
    5.32              CxMap *map,
    5.33 -            CxDataPtr key
    5.34 +            CxHashKey key
    5.35      );
    5.36  
    5.37      /**
    5.38 @@ -135,7 +136,7 @@
    5.39      /**
    5.40       * A pointer to the key.
    5.41       */
    5.42 -    CxDataPtr const *key;
    5.43 +    CxHashKey const *key;
    5.44      /**
    5.45       * A pointer to the value.
    5.46       */
    5.47 @@ -176,7 +177,7 @@
    5.48  __attribute__((__nonnull__))
    5.49  static inline int cxMapPut(
    5.50          CxMap *map,
    5.51 -        CxDataPtr key,
    5.52 +        CxHashKey key,
    5.53          void *value
    5.54  ) {
    5.55      return map->cl->put(map, key, value);
    5.56 @@ -192,7 +193,7 @@
    5.57  __attribute__((__nonnull__, __warn_unused_result__))
    5.58  static inline void *cxMapGet(
    5.59          CxMap const *map,
    5.60 -        CxDataPtr key
    5.61 +        CxHashKey key
    5.62  ) {
    5.63      return map->cl->get(map, key);
    5.64  }
    5.65 @@ -207,7 +208,7 @@
    5.66  __attribute__((__nonnull__, __warn_unused_result__))
    5.67  static inline void *cxMapRemove(
    5.68          CxMap *map,
    5.69 -        CxDataPtr key
    5.70 +        CxHashKey key
    5.71  ) {
    5.72      return map->cl->remove(map, key);
    5.73  }
    5.74 @@ -262,15 +263,6 @@
    5.75      return map->cl->iterator(map);
    5.76  }
    5.77  
    5.78 -/**
    5.79 - * Convenience function to make a key from a NULL-terminated string.
    5.80 - *
    5.81 - * @param str the NULL-terminated string
    5.82 - * @return the string wrapped to be used as a map key
    5.83 - */
    5.84 -__attribute__((__nonnull__, __warn_unused_result__))
    5.85 -CxDataPtr cxMapKeyStr(char const *str);
    5.86 -
    5.87  #ifdef    __cplusplus
    5.88  }
    5.89  #endif

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/src/hash_key.c	Wed Jun 08 21:33:31 2022 +0200
     6.3 @@ -0,0 +1,107 @@
     6.4 +/*
     6.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     6.6 + *
     6.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     6.8 + *
     6.9 + * Redistribution and use in source and binary forms, with or without
    6.10 + * modification, are permitted provided that the following conditions are met:
    6.11 + *
    6.12 + *   1. Redistributions of source code must retain the above copyright
    6.13 + *      notice, this list of conditions and the following disclaimer.
    6.14 + *
    6.15 + *   2. Redistributions in binary form must reproduce the above copyright
    6.16 + *      notice, this list of conditions and the following disclaimer in the
    6.17 + *      documentation and/or other materials provided with the distribution.
    6.18 + *
    6.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    6.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    6.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    6.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    6.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    6.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    6.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    6.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    6.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    6.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    6.29 + * POSSIBILITY OF SUCH DAMAGE.
    6.30 + */
    6.31 +
    6.32 +#include "cx/hash_key.h"
    6.33 +#include <string.h>
    6.34 +
    6.35 +void cx_hash_murmur(CxHashKey *key) {
    6.36 +    size_t len = key->len;
    6.37 +    unsigned char const *data = key->data.cbytes;
    6.38 +
    6.39 +    unsigned m = 0x5bd1e995;
    6.40 +    unsigned r = 24;
    6.41 +    unsigned h = 25 ^ len;
    6.42 +    unsigned i = 0;
    6.43 +    while (len >= 4) {
    6.44 +        unsigned k = data[i + 0] & 0xFF;
    6.45 +        k |= (data[i + 1] & 0xFF) << 8;
    6.46 +        k |= (data[i + 2] & 0xFF) << 16;
    6.47 +        k |= (data[i + 3] & 0xFF) << 24;
    6.48 +
    6.49 +        k *= m;
    6.50 +        k ^= k >> r;
    6.51 +        k *= m;
    6.52 +
    6.53 +        h *= m;
    6.54 +        h ^= k;
    6.55 +
    6.56 +        i += 4;
    6.57 +        len -= 4;
    6.58 +    }
    6.59 +
    6.60 +    switch (len) {
    6.61 +        case 3:
    6.62 +            h ^= (data[i + 2] & 0xFF) << 16;
    6.63 +                    __attribute__((__fallthrough__));
    6.64 +        case 2:
    6.65 +            h ^= (data[i + 1] & 0xFF) << 8;
    6.66 +                    __attribute__((__fallthrough__));
    6.67 +        case 1:
    6.68 +            h ^= (data[i + 0] & 0xFF);
    6.69 +            h *= m;
    6.70 +                    __attribute__((__fallthrough__));
    6.71 +        default:
    6.72 +            /* do nothing */;
    6.73 +    }
    6.74 +
    6.75 +    h ^= h >> 13;
    6.76 +    h *= m;
    6.77 +    h ^= h >> 15;
    6.78 +
    6.79 +    key->hash = h;
    6.80 +}
    6.81 +
    6.82 +CxHashKey cx_hash_key_str(char const *str) {
    6.83 +    CxHashKey key;
    6.84 +    key.data.cstr = str;
    6.85 +    key.len = str == NULL ? 0 : (1 + strlen(str));
    6.86 +    cx_hash_murmur(&key);
    6.87 +    return key;
    6.88 +}
    6.89 +
    6.90 +CxHashKey cx_hash_key_bytes(
    6.91 +        unsigned char const *bytes,
    6.92 +        size_t len
    6.93 +) {
    6.94 +    CxHashKey key;
    6.95 +    key.data.cbytes = bytes;
    6.96 +    key.len = len;
    6.97 +    cx_hash_murmur(&key);
    6.98 +    return key;
    6.99 +}
   6.100 +
   6.101 +CxHashKey cx_hash_key(
   6.102 +        void *obj,
   6.103 +        size_t len
   6.104 +) {
   6.105 +    CxHashKey key;
   6.106 +    key.data.obj = obj;
   6.107 +    key.len = len;
   6.108 +    cx_hash_murmur(&key);
   6.109 +    return key;
   6.110 +}

     7.1 --- a/src/hash_map.c	Fri May 27 17:40:27 2022 +0200
     7.2 +++ b/src/hash_map.c	Wed Jun 08 21:33:31 2022 +0200
     7.3 @@ -30,60 +30,6 @@
     7.4  #include "cx/hash_map.h"
     7.5  #include "cx/utils.h"
     7.6  
     7.7 -/**
     7.8 - * Computes a murmur hash-2.
     7.9 - *
    7.10 - * @param data the data to hash
    7.11 - * @param len the length of the data
    7.12 - * @return the murmur hash-2 of the data
    7.13 - */
    7.14 -static unsigned cx_hash_map_murmur(
    7.15 -        unsigned char const *data,
    7.16 -        size_t len
    7.17 -) {
    7.18 -    unsigned m = 0x5bd1e995;
    7.19 -    unsigned r = 24;
    7.20 -    unsigned h = 25 ^ len;
    7.21 -    unsigned i = 0;
    7.22 -    while (len >= 4) {
    7.23 -        unsigned k = data[i + 0] & 0xFF;
    7.24 -        k |= (data[i + 1] & 0xFF) << 8;
    7.25 -        k |= (data[i + 2] & 0xFF) << 16;
    7.26 -        k |= (data[i + 3] & 0xFF) << 24;
    7.27 -
    7.28 -        k *= m;
    7.29 -        k ^= k >> r;
    7.30 -        k *= m;
    7.31 -
    7.32 -        h *= m;
    7.33 -        h ^= k;
    7.34 -
    7.35 -        i += 4;
    7.36 -        len -= 4;
    7.37 -    }
    7.38 -
    7.39 -    switch (len) {
    7.40 -        case 3:
    7.41 -            h ^= (data[i + 2] & 0xFF) << 16;
    7.42 -                    __attribute__((__fallthrough__));
    7.43 -        case 2:
    7.44 -            h ^= (data[i + 1] & 0xFF) << 8;
    7.45 -                    __attribute__((__fallthrough__));
    7.46 -        case 1:
    7.47 -            h ^= (data[i + 0] & 0xFF);
    7.48 -            h *= m;
    7.49 -                    __attribute__((__fallthrough__));
    7.50 -        default:
    7.51 -            /* do nothing */;
    7.52 -    }
    7.53 -
    7.54 -    h ^= h >> 13;
    7.55 -    h *= m;
    7.56 -    h ^= h >> 15;
    7.57 -
    7.58 -    return h;
    7.59 -}
    7.60 -
    7.61  static void cx_hash_map_clear(struct cx_map_s *map) {
    7.62      struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    7.63      cx_for_n(i, hash_map->bucket_count) {
    7.64 @@ -92,7 +38,7 @@
    7.65              do {
    7.66                  struct cx_hash_map_element_s *next = elem->next;
    7.67                  // free the key data
    7.68 -                cxFree(map->allocator, elem->key.data);
    7.69 +                cxFree(map->allocator, elem->key.data.obj);
    7.70                  // free the node
    7.71                  cxFree(map->allocator, elem);
    7.72                  // proceed
    7.73 @@ -119,13 +65,17 @@
    7.74  
    7.75  static int cx_hash_map_put(
    7.76          CxMap *map,
    7.77 -        CxDataPtr key,
    7.78 +        CxHashKey key,
    7.79          void *value
    7.80  ) {
    7.81      struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
    7.82      CxAllocator *allocator = map->allocator;
    7.83  
    7.84 -    unsigned hash = cx_hash_map_murmur(key.data, key.len);
    7.85 +    unsigned hash = key.hash;
    7.86 +    if (hash == 0) {
    7.87 +        cx_hash_murmur(&key);
    7.88 +        hash = key.hash;
    7.89 +    }
    7.90  
    7.91      size_t slot = hash % hash_map->bucket_count;
    7.92      struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
    7.93 @@ -151,8 +101,8 @@
    7.94          if (kd == NULL) {
    7.95              return -1;
    7.96          }
    7.97 -        memcpy(kd, key.data, key.len);
    7.98 -        e->key.data = kd;
    7.99 +        memcpy(kd, key.data.obj, key.len);
   7.100 +        e->key.data.obj = kd;
   7.101          e->key.len = key.len;
   7.102          e->key.hash = hash;
   7.103  
   7.104 @@ -187,7 +137,7 @@
   7.105          prev->next = elm->next;
   7.106      }
   7.107      // free element
   7.108 -    cxFree(hash_map->base.allocator, elm->key.data);
   7.109 +    cxFree(hash_map->base.allocator, elm->key.data.obj);
   7.110      cxFree(hash_map->base.allocator, elm);
   7.111      // decrease size
   7.112      hash_map->base.size--;
   7.113 @@ -203,19 +153,23 @@
   7.114   */
   7.115  static void *cx_hash_map_get_remove(
   7.116          CxMap *map,
   7.117 -        CxDataPtr key,
   7.118 +        CxHashKey key,
   7.119          bool remove
   7.120  ) {
   7.121      struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
   7.122  
   7.123 -    unsigned hash = cx_hash_map_murmur(key.data, key.len);
   7.124 +    unsigned hash = key.hash;
   7.125 +    if (hash == 0) {
   7.126 +        cx_hash_murmur(&key);
   7.127 +        hash = key.hash;
   7.128 +    }
   7.129  
   7.130      size_t slot = hash % hash_map->bucket_count;
   7.131      struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
   7.132      struct cx_hash_map_element_s *prev = NULL;
   7.133      while (elm && elm->key.hash <= hash) {
   7.134          if (elm->key.hash == hash && elm->key.len == key.len) {
   7.135 -            if (memcmp(elm->key.data, key.data, key.len) == 0) {
   7.136 +            if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
   7.137                  void *data = elm->data;
   7.138                  if (remove) {
   7.139                      cx_hash_map_unlink(hash_map, slot, prev, elm);
   7.140 @@ -232,7 +186,7 @@
   7.141  
   7.142  static void *cx_hash_map_get(
   7.143          CxMap const *map,
   7.144 -        CxDataPtr key
   7.145 +        CxHashKey key
   7.146  ) {
   7.147      // we can safely cast, because we know when remove=false, the map stays untouched
   7.148      return cx_hash_map_get_remove((CxMap *) map, key, false);
   7.149 @@ -240,7 +194,7 @@
   7.150  
   7.151  static void *cx_hash_map_remove(
   7.152          CxMap *map,
   7.153 -        CxDataPtr key
   7.154 +        CxHashKey key
   7.155  ) {
   7.156      return cx_hash_map_get_remove(map, key, true);
   7.157  }

     8.1 --- a/src/map.c	Fri May 27 17:40:27 2022 +0200
     8.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.3 @@ -1,35 +0,0 @@
     8.4 -/*
     8.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     8.6 - *
     8.7 - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     8.8 - *
     8.9 - * Redistribution and use in source and binary forms, with or without
    8.10 - * modification, are permitted provided that the following conditions are met:
    8.11 - *
    8.12 - *   1. Redistributions of source code must retain the above copyright
    8.13 - *      notice, this list of conditions and the following disclaimer.
    8.14 - *
    8.15 - *   2. Redistributions in binary form must reproduce the above copyright
    8.16 - *      notice, this list of conditions and the following disclaimer in the
    8.17 - *      documentation and/or other materials provided with the distribution.
    8.18 - *
    8.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    8.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    8.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    8.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    8.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    8.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    8.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    8.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    8.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    8.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    8.29 - * POSSIBILITY OF SUCH DAMAGE.
    8.30 - */
    8.31 -
    8.32 -#include <string.h>
    8.33 -#include "cx/map.h"
    8.34 -
    8.35 -CxDataPtr cxMapKeyStr(char const *str) {
    8.36 -    CxDataPtr key = {(unsigned char const *) str, 1 + strlen(str)};
    8.37 -    return key;
    8.38 -}
    8.39 \ No newline at end of file

     9.1 --- a/test/test_map.cpp	Fri May 27 17:40:27 2022 +0200
     9.2 +++ b/test/test_map.cpp	Wed Jun 08 21:33:31 2022 +0200
     9.3 @@ -72,9 +72,9 @@
     9.4      {
     9.5          auto keyiter = cxMapIteratorKeys(map);
     9.6          std::unordered_set<std::string> keys;
     9.7 -        cx_foreach(CxDataPtr*, elem, keyiter) {
     9.8 +        cx_foreach(CxHashKey*, elem, keyiter) {
     9.9              // we use that our test keys contain NULL-terminated strings
    9.10 -            keys.insert(std::string(reinterpret_cast<const char *>(elem->data)));
    9.11 +            keys.insert(std::string(elem->data.cstr));
    9.12          }
    9.13          EXPECT_EQ(keyiter.index, map->size);
    9.14          ASSERT_EQ(keys.size(), map->size);
    9.15 @@ -103,7 +103,7 @@
    9.16          auto pairiter = cxMapIterator(map);
    9.17          std::unordered_map<std::string, std::string> pairs;
    9.18          cx_foreach(CxMapEntry*, entry, pairiter) {
    9.19 -            pairs[std::string((char const *) entry->key->data)] = std::string((char *) entry->value);
    9.20 +            pairs[std::string(entry->key->data.cstr)] = std::string((char *) entry->value);
    9.21          }
    9.22          EXPECT_EQ(pairiter.index, map->size);
    9.23          ASSERT_EQ(pairs.size(), refmap.size());
    9.24 @@ -144,7 +144,8 @@
    9.25  
    9.26      // execute operations and verify results
    9.27      for (auto &&op: ops) {
    9.28 -        CxDataPtr key = cxMapKeyStr(op.key);
    9.29 +        CxHashKey key = cx_hash_key_str(op.key);
    9.30 +        key.hash = 0; // force the hash map to compute the hash
    9.31          if (op.op == map_operation::put) {
    9.32              // execute a put operation and verify that the exact value can be read back
    9.33              refmap[std::string(op.key)] = std::string(op.value);
    9.34 @@ -176,26 +177,26 @@
    9.35      CxTestingAllocator allocator;
    9.36      auto map = cxHashMapCreate(&allocator, 4);
    9.37  
    9.38 -    cxMapPut(map, cxMapKeyStr("key 1"), (void *) "val 1");
    9.39 -    cxMapPut(map, cxMapKeyStr("key 2"), (void *) "val 2");
    9.40 -    cxMapPut(map, cxMapKeyStr("key 3"), (void *) "val 3");
    9.41 -    cxMapPut(map, cxMapKeyStr("key 4"), (void *) "val 4");
    9.42 -    cxMapPut(map, cxMapKeyStr("key 5"), (void *) "val 5");
    9.43 -    cxMapPut(map, cxMapKeyStr("key 6"), (void *) "val 6");
    9.44 +    cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
    9.45 +    cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
    9.46 +    cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
    9.47 +    cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
    9.48 +    cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
    9.49 +    cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
    9.50  
    9.51      auto iter = cxMapIterator(map);
    9.52      cx_foreach(CxMapEntry*, entry, iter) {
    9.53 -        if (entry->key->data[4] % 2 == 1) iter.remove = true;
    9.54 +        if (entry->key->data.cstr[4] % 2 == 1) iter.remove = true;
    9.55      }
    9.56      EXPECT_EQ(map->size, 3);
    9.57      EXPECT_EQ(iter.index, map->size);
    9.58  
    9.59 -    EXPECT_EQ(cxMapGet(map, cxMapKeyStr("key 1")), nullptr);
    9.60 -    EXPECT_NE(cxMapGet(map, cxMapKeyStr("key 2")), nullptr);
    9.61 -    EXPECT_EQ(cxMapGet(map, cxMapKeyStr("key 3")), nullptr);
    9.62 -    EXPECT_NE(cxMapGet(map, cxMapKeyStr("key 4")), nullptr);
    9.63 -    EXPECT_EQ(cxMapGet(map, cxMapKeyStr("key 5")), nullptr);
    9.64 -    EXPECT_NE(cxMapGet(map, cxMapKeyStr("key 6")), nullptr);
    9.65 +    EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
    9.66 +    EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
    9.67 +    EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
    9.68 +    EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);
    9.69 +    EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);
    9.70 +    EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);
    9.71  
    9.72      cxMapDestroy(map);
    9.73      EXPECT_TRUE(allocator.verify());
    9.74 @@ -205,12 +206,12 @@
    9.75      CxTestingAllocator allocator;
    9.76      auto map = cxHashMapCreate(&allocator, 8);
    9.77  
    9.78 -    cxMapPut(map, cxMapKeyStr("key 1"), (void *) "val 1");
    9.79 -    cxMapPut(map, cxMapKeyStr("key 2"), (void *) "val 2");
    9.80 -    cxMapPut(map, cxMapKeyStr("key 3"), (void *) "val 3");
    9.81 -    cxMapPut(map, cxMapKeyStr("key 4"), (void *) "val 4");
    9.82 -    cxMapPut(map, cxMapKeyStr("key 5"), (void *) "val 5");
    9.83 -    cxMapPut(map, cxMapKeyStr("key 6"), (void *) "val 6");
    9.84 +    cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
    9.85 +    cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
    9.86 +    cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
    9.87 +    cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
    9.88 +    cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
    9.89 +    cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
    9.90  
    9.91      // 6/8 does not exceed 0.75, therefore the function should not rehash
    9.92      int result = cxMapRehash(map);
    9.93 @@ -225,26 +226,26 @@
    9.94      CxTestingAllocator allocator;
    9.95      auto map = cxHashMapCreate(&allocator, 8);
    9.96  
    9.97 -    cxMapPut(map, cxMapKeyStr("key 1"), (void *) "val 1");
    9.98 -    cxMapPut(map, cxMapKeyStr("key 2"), (void *) "val 2");
    9.99 -    cxMapPut(map, cxMapKeyStr("key 3"), (void *) "val 3");
   9.100 -    cxMapPut(map, cxMapKeyStr("key 4"), (void *) "val 4");
   9.101 -    cxMapPut(map, cxMapKeyStr("key 5"), (void *) "val 5");
   9.102 -    cxMapPut(map, cxMapKeyStr("key 6"), (void *) "val 6");
   9.103 -    cxMapPut(map, cxMapKeyStr("key 7"), (void *) "val 7");
   9.104 +    cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
   9.105 +    cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
   9.106 +    cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
   9.107 +    cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
   9.108 +    cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
   9.109 +    cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
   9.110 +    cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7");
   9.111  
   9.112      int result = cxMapRehash(map);
   9.113      EXPECT_EQ(result, 0);
   9.114      EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);
   9.115      EXPECT_EQ(map->size, 7);
   9.116  
   9.117 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 1")), "val 1"), 0);
   9.118 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 2")), "val 2"), 0);
   9.119 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 3")), "val 3"), 0);
   9.120 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 4")), "val 4"), 0);
   9.121 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 5")), "val 5"), 0);
   9.122 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 6")), "val 6"), 0);
   9.123 -    EXPECT_EQ(strcmp((char *) cxMapGet(map, cxMapKeyStr("key 7")), "val 7"), 0);
   9.124 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);
   9.125 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);
   9.126 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);
   9.127 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0);
   9.128 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);
   9.129 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);
   9.130 +    EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0);
   9.131  
   9.132      cxMapDestroy(map);
   9.133      EXPECT_TRUE(allocator.verify());