ucx/ucx/map.h

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /**
  30  * @file map.h
  31  *
  32  * Hash map implementation.
  33  *
  34  * This implementation uses murmur hash 2 and separate chaining with linked
  35  * lists.
  36  *
  37  * @author Mike Becker
  38  * @author Olaf Wintermann
  39  */
  40
  41 #ifndef UCX_MAP_H
  42 #define UCX_MAP_H
  43
  44 #include "ucx.h"
  45 #include "string.h"
  46 #include "allocator.h"
  47 #include <stdio.h>
  48
  49 #ifdef  __cplusplus
  50 extern "C" {
  51 #endif
  52
  53 /**
  54  * Loop statement for UCX maps.
  55  *
  56  * The <code>key</code> variable is implicitly defined, but the
  57  * <code>value</code> variable must be already declared as type information
  58  * cannot be inferred.
  59  *
  60  * @param key the variable name for the key
  61  * @param value the variable name for the value
  62  * @param iter a UcxMapIterator
  63  * @see ucx_map_iterator()
  64  */
  65 #define UCX_MAP_FOREACH(key,value,iter) \
  66         for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)
  67
  68 /** Type for the UCX map. @see UcxMap */
  69 typedef struct UcxMap          UcxMap;
  70
  71 /** Type for a key of a UcxMap. @see UcxKey */
  72 typedef struct UcxKey          UcxKey;
  73
  74 /** Type for an element of a UcxMap. @see UcxMapElement */
  75 typedef struct UcxMapElement   UcxMapElement;
  76
  77 /** Type for an iterator over a UcxMap. @see UcxMapIterator */
  78 typedef struct UcxMapIterator  UcxMapIterator;
  79
  80 /** Structure for the UCX map. */
  81 struct UcxMap {
  82     /** An allocator that is used for the map elements. */
  83     UcxAllocator  *allocator;
  84     /** The array of map element lists. */
  85     UcxMapElement **map;
  86     /** The size of the map is the length of the element list array. */
  87     size_t        size;
  88     /** The count of elements currently stored in this map. */
  89     size_t        count;
  90 };
  91
  92 /** Structure to publicly denote a key of a UcxMap. */
  93 struct UcxKey {
  94     /** The key data. */
  95     const void *data;
  96     /** The length of the key data. */
  97     size_t     len;
  98     /** A cache for the hash value of the key data. */
  99     int        hash;
 100 };
 101
 102 /** Internal structure for a key of a UcxMap. */
 103 struct UcxMapKey {
 104     /** The key data. */
 105     void    *data;
 106     /** The length of the key data. */
 107     size_t  len;
 108     /** The hash value of the key data. */
 109     int     hash;
 110 };
 111
 112 /** Structure for an element of a UcxMap. */
 113 struct UcxMapElement {
 114     /** The value data. */
 115     void              *data;
 116
 117     /** A pointer to the next element in the current list. */
 118     UcxMapElement     *next;
 119
 120     /** The corresponding key. */
 121     struct UcxMapKey  key;
 122 };
 123
 124 /** Structure for an iterator over a UcxMap. */
 125 struct UcxMapIterator {
 126     /** The map to iterate over. */
 127     UcxMap const  *map;
 128
 129     /** The current map element. */
 130     UcxMapElement *cur;
 131
 132     /**
 133      * The current index of the element list array.
 134      * <b>Attention: </b> this is <b>NOT</b> the element index! Do <b>NOT</b>
 135      * manually iterate over the map by increasing this index. Use
 136      * ucx_map_iter_next().
 137      * @see UcxMap.map*/
 138     size_t        index;
 139 };
 140
 141 /**
 142  * Creates a new hash map with the specified size.
 143  * @param size the size of the hash map
 144  * @return a pointer to the new hash map
 145  */
 146 UcxMap *ucx_map_new(size_t size);
 147
 148 /**
 149  * Creates a new hash map with the specified size using a UcxAllocator.
 150  * @param allocator the allocator to use
 151  * @param size the size of the hash map
 152  * @return a pointer to the new hash map
 153  */
 154 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size);
 155
 156 /**
 157  * Frees a hash map.
 158  *
 159  * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content()
 160  * before calling this function to achieve that.
 161  *
 162  * @param map the map to be freed
 163  * @see ucx_map_free_content()
 164  */
 165 void ucx_map_free(UcxMap *map);
 166
 167 /**
 168  * Frees the contents of a hash map.
 169  *
 170  * This is a convenience function that iterates over the map and passes all
 171  * values to the specified destructor function.
 172  *
 173  * If no destructor is specified (<code>NULL</code>), the free() function of
 174  * the map's own allocator is used.
 175  *
 176  * You must ensure, that it is valid to pass each value in the map to the same
 177  * destructor function.
 178  *
 179  * You should free or clear the map afterwards, as the contents will be invalid.
 180  *
 181  * @param map for which the contents shall be freed
 182  * @param destr optional pointer to a destructor function
 183  * @see ucx_map_free()
 184  * @see ucx_map_clear()
 185  */
 186 void ucx_map_free_content(UcxMap *map, ucx_destructor destr);
 187
 188 /**
 189  * Clears a hash map.
 190  *
 191  * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content()
 192  * before calling this function to achieve that.
 193  *
 194  * @param map the map to be cleared
 195  * @see ucx_map_free_content()
 196  */
 197 void ucx_map_clear(UcxMap *map);
 198
 199
 200 /**
 201  * Copies contents from a map to another map using a copy function.
 202  *
 203  * <b>Note:</b> The destination map does not need to be empty. However, if it
 204  * contains data with keys that are also present in the source map, the contents
 205  * are overwritten.
 206  *
 207  * @param from the source map
 208  * @param to the destination map
 209  * @param fnc the copy function or <code>NULL</code> if the pointer address
 210  * shall be copied
 211  * @param data additional data for the copy function
 212  * @return 0 on success or a non-zero value on memory allocation errors
 213  */
 214 int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data);
 215
 216 /**
 217  * Clones the map and rehashes if necessary.
 218  *
 219  * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
 220  * This function <i>always</i> ensures a new UcxMap.size of at least
 221  * 2.5*UcxMap.count.
 222  *
 223  * @param map the map to clone
 224  * @param fnc the copy function to use or <code>NULL</code> if the new and
 225  * the old map shall share the data pointers
 226  * @param data additional data for the copy function
 227  * @return the cloned map
 228  * @see ucx_map_copy()
 229  */
 230 UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data);
 231
 232 /**
 233  * Clones the map and rehashes if necessary.
 234  *
 235  * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
 236  * This function <i>always</i> ensures a new UcxMap.size of at least
 237  * 2.5*UcxMap.count.
 238  *
 239  * @param allocator the allocator to use for the cloned map
 240  * @param map the map to clone
 241  * @param fnc the copy function to use or <code>NULL</code> if the new and
 242  * the old map shall share the data pointers
 243  * @param data additional data for the copy function
 244  * @return the cloned map
 245  * @see ucx_map_copy()
 246  */
 247 UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
 248                         UcxMap const *map, copy_func fnc, void *data);
 249
 250 /**
 251  * Increases size of the hash map, if necessary.
 252  *
 253  * The load value is 0.75*UcxMap.size. If the element count exceeds the load
 254  * value, the map needs to be rehashed. Otherwise no action is performed and
 255  * this function simply returns 0.
 256  *
 257  * The rehashing process ensures, that the UcxMap.size is at least
 258  * 2.5*UcxMap.count. So there is enough room for additional elements without
 259  * the need of another soon rehashing.
 260  *
 261  * You can use this function to dramatically increase access performance.
 262  *
 263  * @param map the map to rehash
 264  * @return 1, if a memory allocation error occurred, 0 otherwise
 265  */
 266 int ucx_map_rehash(UcxMap *map);
 267
 268 /**
 269  * Puts a key/value-pair into the map.
 270  *
 271  * @param map the map
 272  * @param key the key
 273  * @param value the value
 274  * @return 0 on success, non-zero value on failure
 275  */
 276 int ucx_map_put(UcxMap *map, UcxKey key, void *value);
 277
 278 /**
 279  * Retrieves a value by using a key.
 280  *
 281  * @param map the map
 282  * @param key the key
 283  * @return the value
 284  */
 285 void* ucx_map_get(UcxMap const *map, UcxKey key);
 286
 287 /**
 288  * Removes a key/value-pair from the map by using the key.
 289  *
 290  * @param map the map
 291  * @param key the key
 292  * @return the removed value
 293  */
 294 void* ucx_map_remove(UcxMap *map, UcxKey key);
 295
 296 /**
 297  * Shorthand for putting data with a sstr_t key into the map.
 298  * @param map the map
 299  * @param key the key
 300  * @param value the value
 301  * @return 0 on success, non-zero value on failure
 302  * @see ucx_map_put()
 303  */
 304 #define ucx_map_sstr_put(map, key, value) \
 305     ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)
 306
 307 /**
 308  * Shorthand for putting data with a C string key into the map.
 309  * @param map the map
 310  * @param key the key
 311  * @param value the value
 312  * @return 0 on success, non-zero value on failure
 313  * @see ucx_map_put()
 314  */
 315 #define ucx_map_cstr_put(map, key, value) \
 316     ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value)
 317
 318 /**
 319  * Shorthand for putting data with an integer key into the map.
 320  * @param map the map
 321  * @param key the key
 322  * @param value the value
 323  * @return 0 on success, non-zero value on failure
 324  * @see ucx_map_put()
 325  */
 326 #define ucx_map_int_put(map, key, value) \
 327     ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value)
 328
 329 /**
 330  * Shorthand for getting data from the map with a sstr_t key.
 331  * @param map the map
 332  * @param key the key
 333  * @return the value
 334  * @see ucx_map_get()
 335  */
 336 #define ucx_map_sstr_get(map, key) \
 337     ucx_map_get(map, ucx_key(key.ptr, key.length))
 338
 339 /**
 340  * Shorthand for getting data from the map with a C string key.
 341  * @param map the map
 342  * @param key the key
 343  * @return the value
 344  * @see ucx_map_get()
 345  */
 346 #define ucx_map_cstr_get(map, key) \
 347     ucx_map_get(map, ucx_key(key, strlen(key)))
 348
 349 /**
 350  * Shorthand for getting data from the map with an integer key.
 351  * @param map the map
 352  * @param key the key
 353  * @return the value
 354  * @see ucx_map_get()
 355  */
 356 #define ucx_map_int_get(map, key) \
 357     ucx_map_get(map, ucx_key(&key, sizeof(int)))
 358
 359 /**
 360  * Shorthand for removing data from the map with a sstr_t key.
 361  * @param map the map
 362  * @param key the key
 363  * @return the removed value
 364  * @see ucx_map_remove()
 365  */
 366 #define ucx_map_sstr_remove(map, key) \
 367     ucx_map_remove(map, ucx_key(key.ptr, key.length))
 368
 369 /**
 370  * Shorthand for removing data from the map with a C string key.
 371  * @param map the map
 372  * @param key the key
 373  * @return the removed value
 374  * @see ucx_map_remove()
 375  */
 376 #define ucx_map_cstr_remove(map, key) \
 377     ucx_map_remove(map, ucx_key(key, strlen(key)))
 378
 379 /**
 380  * Shorthand for removing data from the map with an integer key.
 381  * @param map the map
 382  * @param key the key
 383  * @return the removed value
 384  * @see ucx_map_remove()
 385  */
 386 #define ucx_map_int_remove(map, key) \
 387     ucx_map_remove(map, ucx_key(&key, sizeof(key)))
 388
 389 /**
 390  * Creates a UcxKey based on the given data.
 391  *
 392  * This function implicitly computes the hash.
 393  *
 394  * @param data the data for the key
 395  * @param len the length of the data
 396  * @return a UcxKey with implicitly computed hash
 397  * @see ucx_hash()
 398  */
 399 UcxKey ucx_key(const void *data, size_t len);
 400
 401 /**
 402  * Computes a murmur hash-2.
 403  *
 404  * @param data the data to hash
 405  * @param len the length of the data
 406  * @return the murmur hash-2 of the data
 407  */
 408 int ucx_hash(const char *data, size_t len);
 409
 410 /**
 411  * Creates an iterator for a map.
 412  *
 413  * <b>Note:</b> A UcxMapIterator iterates over all elements in all element
 414  * lists successively. Therefore the order highly depends on the key hashes and
 415  * may vary under different map sizes. So generally you may <b>NOT</b> rely on
 416  * the iteration order.
 417  *
 418  * <b>Note:</b> The iterator is <b>NOT</b> initialized. You need to call
 419  * ucx_map_iter_next() at least once before accessing any information. However,
 420  * it is not recommended to access the fields of a UcxMapIterator directly.
 421  *
 422  * @param map the map to create the iterator for
 423  * @return an iterator initialized on the first element of the
 424  * first element list
 425  * @see ucx_map_iter_next()
 426  */
 427 UcxMapIterator ucx_map_iterator(UcxMap const *map);
 428
 429 /**
 430  * Proceeds to the next element of the map (if any).
 431  *
 432  * Subsequent calls on the same iterator proceed to the next element and
 433  * store the key/value-pair into the memory specified as arguments of this
 434  * function.
 435  *
 436  * If no further elements are found, this function returns zero and leaves the
 437  * last found key/value-pair in memory.
 438  *
 439  * @param iterator the iterator to use
 440  * @param key a pointer to the memory where to store the key
 441  * @param value a pointer to the memory where to store the value
 442  * @return 1, if another element was found, 0 if all elements has been processed
 443  * @see ucx_map_iterator()
 444  */
 445 int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value);
 446
 447 /**
 448  * Returns the union of two maps.
 449  *
 450  * The union is a fresh map which is filled by two successive calls of
 451  * ucx_map_copy() on the two input maps.
 452  *
 453  * @param first the first source map
 454  * @param second the second source map
 455  * @param cpfnc a function to copy the elements
 456  * @param cpdata additional data for the copy function
 457  * @return a new map containing the union
 458  */
 459 UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
 460                       copy_func cpfnc, void* cpdata);
 461
 462 /**
 463  * Returns the union of two maps.
 464  *
 465  * The union is a fresh map which is filled by two successive calls of
 466  * ucx_map_copy() on the two input maps.
 467  *
 468  * @param allocator the allocator that shall be used by the new map
 469  * @param first the first source map
 470  * @param second the second source map
 471  * @param cpfnc a function to copy the elements
 472  * @param cpdata additional data for the copy function
 473  * @return a new map containing the union
 474  */
 475 UcxMap* ucx_map_union_a(UcxAllocator *allocator,
 476                         const UcxMap *first, const UcxMap *second,
 477                         copy_func cpfnc, void* cpdata);
 478
 479 /**
 480  * Returns the intersection of two maps.
 481  *
 482  * The intersection is defined as a copy of the first map with every element
 483  * removed that has no valid key in the second map.
 484  *
 485  * @param first the first source map
 486  * @param second the second source map
 487  * @param cpfnc a function to copy the elements
 488  * @param cpdata additional data for the copy function
 489  * @return a new map containing the intersection
 490  */
 491 UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
 492                              copy_func cpfnc, void* cpdata);
 493
 494 /**
 495  * Returns the intersection of two maps.
 496  *
 497  * The intersection is defined as a copy of the first map with every element
 498  * removed that has no valid key in the second map.
 499  *
 500  * @param allocator the allocator that shall be used by the new map
 501  * @param first the first source map
 502  * @param second the second source map
 503  * @param cpfnc a function to copy the elements
 504  * @param cpdata additional data for the copy function
 505  * @return a new map containing the intersection
 506  */
 507 UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
 508                                const UcxMap *first, const UcxMap *second,
 509                                copy_func cpfnc, void* cpdata);
 510
 511 /**
 512  * Returns the difference of two maps.
 513  *
 514  * The difference contains a copy of all elements of the first map
 515  * for which the corresponding keys cannot be found in the second map.
 516  *
 517  * @param first the first source map
 518  * @param second the second source map
 519  * @param cpfnc a function to copy the elements
 520  * @param cpdata additional data for the copy function
 521  * @return a new list containing the difference
 522  */
 523 UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
 524                            copy_func cpfnc, void* cpdata);
 525
 526 /**
 527  * Returns the difference of two maps.
 528  *
 529  * The difference contains a copy of all elements of the first map
 530  * for which the corresponding keys cannot be found in the second map.
 531  *
 532  * @param allocator the allocator that shall be used by the new map
 533  * @param first the first source map
 534  * @param second the second source map
 535  * @param cpfnc a function to copy the elements
 536  * @param cpdata additional data for the copy function
 537  * @return a new list containing the difference
 538  */
 539 UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
 540                              const UcxMap *first, const UcxMap *second,
 541                              copy_func cpfnc, void* cpdata);
 542
 543
 544 #ifdef  __cplusplus
 545 }
 546 #endif
 547
 548 #endif  /* UCX_MAP_H */
 549