ucx/map.h

changeset 138
7800811078b8
parent 136
b798f2eed26a
child 139
dddb9348ea42
     1.1 --- a/ucx/map.h	Fri Aug 09 15:29:26 2013 +0200
     1.2 +++ b/ucx/map.h	Mon Aug 12 14:39:51 2013 +0200
     1.3 @@ -50,36 +50,74 @@
     1.4  extern "C" {
     1.5  #endif
     1.6  
     1.7 -#define UCX_MAP_FOREACH(key,elm,iter) \
     1.8 -        for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&elm)==0;)
     1.9 +/**
    1.10 + * Loop statement for UCX maps.
    1.11 + * 
    1.12 + * The <code>key</code> variable is implicitly defined, but the
    1.13 + * <code>value</code> variable must be already declared as type information
    1.14 + * cannot be inferred.
    1.15 + * 
    1.16 + * @param key the variable name for the key
    1.17 + * @param value the variable name for the value
    1.18 + * @param iter an UcxMapIterator
    1.19 + * @see ucx_map_iterator()
    1.20 + */
    1.21 +#define UCX_MAP_FOREACH(key,value,iter) \
    1.22 +        for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)
    1.23  
    1.24 +/** Type for the UCX map. @see UcxMap */
    1.25  typedef struct UcxMap          UcxMap;
    1.26 +/** Type for a key of an UcxMap. @see UcxKey */
    1.27  typedef struct UcxKey          UcxKey;
    1.28 +/** Type for an element of an UcxMap. @see UcxMapElement */
    1.29  typedef struct UcxMapElement   UcxMapElement;
    1.30 +/** Type for an iterator over an UcxMap. @see UcxMapIterator */
    1.31  typedef struct UcxMapIterator  UcxMapIterator;
    1.32  
    1.33 +/** Structure for the UCX map. */
    1.34  struct UcxMap {
    1.35 +    /** An allocator that is used for the map elements. */
    1.36      UcxAllocator  *allocator;
    1.37 +    /** The array of map element lists. */
    1.38      UcxMapElement **map;
    1.39 +    /** The size of the map is the length of the element list array. */
    1.40      size_t        size;
    1.41 +    /** The count of elements currently stored in this map. */
    1.42      size_t        count;
    1.43  };
    1.44  
    1.45 +/** Structure for a key of an UcxMap. */
    1.46  struct UcxKey {
    1.47 +    /** The key data. */
    1.48      void   *data;
    1.49 +    /** The length of the key data. */
    1.50      size_t len;
    1.51 +    /** The hash value of the key data. */
    1.52      int    hash;
    1.53  };
    1.54  
    1.55 +/** Structure for an element of an UcxMap. */
    1.56  struct UcxMapElement {
    1.57 +    /** The value data. */
    1.58      void          *data;
    1.59 +    /** A pointer to the next element in the current list. */
    1.60      UcxMapElement *next;
    1.61 +    /** The corresponding key. */
    1.62      UcxKey        key;
    1.63  };
    1.64  
    1.65 +/** Structure for an iterator over an UcxMap. */
    1.66  struct UcxMapIterator {
    1.67 +    /** The map to iterate over. */
    1.68      UcxMap        *map;
    1.69 +    /** The current map element. */
    1.70      UcxMapElement *cur;
    1.71 +    /**
    1.72 +     * The current index of the element list array.
    1.73 +     * <b>Attention: </b> this is <b>NOT</b> the element index! Do <b>NOT</b>
    1.74 +     * manually iterate over the map by increasing this index. Use
    1.75 +     * ucx_map_iter_next().
    1.76 +     * @see UcxMap.map*/
    1.77      size_t        index;
    1.78  };
    1.79  
    1.80 @@ -108,14 +146,83 @@
    1.81   */
    1.82  void ucx_map_free(UcxMap *map);
    1.83  
    1.84 -/* you cannot clone maps with more than 390 mio entries */
    1.85 +/**
    1.86 + * Copies contents from a map to another map using a copy function.
    1.87 + * 
    1.88 + * <b>Note:</b> The destination map does not need to be empty. However, if it
    1.89 + * contains data with keys that are also present in the source map, the contents
    1.90 + * are overwritten.
    1.91 + * 
    1.92 + * @param from the source map
    1.93 + * @param to the destination map
    1.94 + * @param fnc the copy function or <code>NULL</code> if the pointer address
    1.95 + * shall be copied
    1.96 + * @param data additional data for the copy function
    1.97 + * @return 0 on success or a non-zero value on memory allocation errors
    1.98 + */
    1.99  int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,
   1.100          copy_func fnc, void *data);
   1.101 +
   1.102 +/**
   1.103 + * Clones the map and rehashes if necessary.
   1.104 + * 
   1.105 + * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
   1.106 + * This function <i>always</i> ensures a new UcxMap.size of at least
   1.107 + * 2.5*UcxMap.count.
   1.108 + * 
   1.109 + * @param map the map to clone
   1.110 + * @param fnc the copy function to use or <code>NULL</code> if the new and
   1.111 + * the old map shall share the data pointers
   1.112 + * @param data additional data for the copy function
   1.113 + * @return the cloned map
   1.114 + * @see ucx_map_copy()
   1.115 + */
   1.116  UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data);
   1.117 +
   1.118 +/**
   1.119 + * Increases size of the hash map, if necessary.
   1.120 + * 
   1.121 + * The load value is 0.75*UcxMap.size. If the element count exceeds the load
   1.122 + * value, the map needs to be rehashed. Otherwise no action is performed and
   1.123 + * this function simply returns 0.
   1.124 + * 
   1.125 + * The rehashing process ensures, that the UcxMap.size is at least
   1.126 + * 2.5*UcxMap.count. So there is enough room for additional elements without
   1.127 + * the need of another soon rehashing.
   1.128 + * 
   1.129 + * You can use this function to dramatically increase access performance.
   1.130 + * 
   1.131 + * @param map the map to rehash
   1.132 + * @return 1, if a memory allocation error occurred, 0 otherwise
   1.133 + */
   1.134  int ucx_map_rehash(UcxMap *map);
   1.135  
   1.136 -int ucx_map_put(UcxMap *map, UcxKey key, void *data);
   1.137 +/**
   1.138 + * Puts a key/value-pair into the map.
   1.139 + * 
   1.140 + * @param map the map
   1.141 + * @param key the key
   1.142 + * @param value the value
   1.143 + * @return 0 on success, non-zero value on failure
   1.144 + */
   1.145 +int ucx_map_put(UcxMap *map, UcxKey key, void *value);
   1.146 +
   1.147 +/**
   1.148 + * Retrieves a value by using a key.
   1.149 + * 
   1.150 + * @param map the map
   1.151 + * @param key the key
   1.152 + * @return the value
   1.153 + */
   1.154  void* ucx_map_get(UcxMap *map, UcxKey key);
   1.155 +
   1.156 +/**
   1.157 + * Removes a key/value-pair from the map by using the key.
   1.158 + * 
   1.159 + * @param map the map
   1.160 + * @param key the key
   1.161 + * @return the removed value
   1.162 + */
   1.163  void* ucx_map_remove(UcxMap *map, UcxKey key);
   1.164  
   1.165  /**
   1.166 @@ -123,6 +230,7 @@
   1.167   * @param map the map
   1.168   * @param key the key
   1.169   * @param value the value
   1.170 + * @return 0 on success, non-zero value on failure
   1.171   * @see ucx_map_put()
   1.172   */
   1.173  #define ucx_map_sstr_put(map, key, value) \
   1.174 @@ -132,6 +240,7 @@
   1.175   * @param map the map
   1.176   * @param key the key
   1.177   * @param value the value
   1.178 + * @return 0 on success, non-zero value on failure
   1.179   * @see ucx_map_put()
   1.180   */
   1.181  #define ucx_map_cstr_put(map, key, value) \
   1.182 @@ -141,6 +250,7 @@
   1.183   * @param map the map
   1.184   * @param key the key
   1.185   * @param value the value
   1.186 + * @return 0 on success, non-zero value on failure
   1.187   * @see ucx_map_put()
   1.188   */
   1.189  #define ucx_map_int_put(map, key, value) \
   1.190 @@ -151,12 +261,16 @@
   1.191   * Shorthand for getting data from the map with a sstr_t key.
   1.192   * @param map the map
   1.193   * @param key the key
   1.194 + * @return the value
   1.195   * @see ucx_map_get()
   1.196   */
   1.197  #define ucx_map_sstr_get(map, key) \
   1.198      ucx_map_get(map, ucx_key(key.ptr, key.length))
   1.199  /**
   1.200   * Shorthand for getting data from the map with a C string key.
   1.201 + * @param map the map
   1.202 + * @param key the key
   1.203 + * @return the value
   1.204   * @see ucx_map_get()
   1.205   */
   1.206  #define ucx_map_cstr_get(map, key) \
   1.207 @@ -165,6 +279,7 @@
   1.208   * Shorthand for getting data from the map with an integer key.
   1.209   * @param map the map
   1.210   * @param key the key
   1.211 + * @return the value
   1.212   * @see ucx_map_get()
   1.213   */
   1.214  #define ucx_map_int_get(map, key) \
   1.215 @@ -173,6 +288,7 @@
   1.216   * Shorthand for removing data from the map with a sstr_t key.
   1.217   * @param map the map
   1.218   * @param key the key
   1.219 + * @return the removed value
   1.220   * @see ucx_map_remove()
   1.221   */
   1.222  #define ucx_map_sstr_remove(map, key) \
   1.223 @@ -181,6 +297,7 @@
   1.224   * Shorthand for removing data from the map with a C string key.
   1.225   * @param map the map
   1.226   * @param key the key
   1.227 + * @return the removed value
   1.228   * @see ucx_map_remove()
   1.229   */
   1.230  #define ucx_map_cstr_remove(map, key) \
   1.231 @@ -189,18 +306,69 @@
   1.232   * Shorthand for removing data from the map with an integer key.
   1.233   * @param map the map
   1.234   * @param key the key
   1.235 + * @return the removed value
   1.236   * @see ucx_map_remove()
   1.237   */
   1.238  #define ucx_map_int_remove(map, key) \
   1.239      ucx_map_remove(map, ucx_key((void*)&key, sizeof(key)))
   1.240  
   1.241 +/**
   1.242 + * Creates an UcxKey based on the given data.
   1.243 + * 
   1.244 + * This function implicitly computes the hash.
   1.245 + * 
   1.246 + * @param data the data for the key
   1.247 + * @param len the length of the data
   1.248 + * @return an UcxKey with implicitly computed hash
   1.249 + * @see ucx_hash()
   1.250 + */
   1.251  UcxKey ucx_key(void *data, size_t len);
   1.252  
   1.253 +/**
   1.254 + * Computes a murmur hash-2.
   1.255 + * 
   1.256 + * @param data the data to hash
   1.257 + * @param len the length of the data
   1.258 + * @return the murmur hash-2 of the data
   1.259 + */
   1.260  int ucx_hash(const char *data, size_t len);
   1.261  
   1.262 +/**
   1.263 + * Creates an iterator for a map.
   1.264 + * 
   1.265 + * <b>Note:</b> An UcxMapIterator iterates over all elements in all element
   1.266 + * lists successively. Therefore the order highly depends on the key hashes and
   1.267 + * may vary under different map sizes. So generally you may <b>NOT</b> rely on
   1.268 + * the iteration order.
   1.269 + * 
   1.270 + * <b>Note:</b> The iterator is <b>NOT</b> initialized. You need to call
   1.271 + * ucx_map_iter_next() at least once before accessing any information. However,
   1.272 + * it is not recommended to access the fields of an UcxMapIterator directly.
   1.273 + * 
   1.274 + * @param map the map to create the iterator for
   1.275 + * @return an iterator initialized on the first element of the
   1.276 + * first element list
   1.277 + * @see ucx_map_iter_next()
   1.278 + */
   1.279  UcxMapIterator ucx_map_iterator(UcxMap *map);
   1.280  
   1.281 -int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm);
   1.282 +/**
   1.283 + * Proceeds to the next element of the map (if any).
   1.284 + * 
   1.285 + * Subsequent calls on the same iterator proceed to the next element and
   1.286 + * store the key/value-pair into the memory specified as arguments of this
   1.287 + * function.
   1.288 + * 
   1.289 + * If no further elements are found, this function returns zero and leaves the
   1.290 + * last found key/value-pair in memory.
   1.291 + * 
   1.292 + * @param iterator the iterator to use
   1.293 + * @param key a pointer to the memory where to store the key
   1.294 + * @param value a pointer to the memory where to store the value
   1.295 + * @return 1, if another element was found, 0 if all elements has been processed
   1.296 + * @see ucx_map_iterator()
   1.297 + */
   1.298 +int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value);
   1.299  
   1.300  
   1.301  #ifdef	__cplusplus

mercurial