ucx: src/ucx/map.h@be77fb2da242 (annotated)

src/ucx/map.h@be77fb2da242 (annotated)

src/ucx/map.h

Thu, 19 Dec 2019 19:58:41 +0100

author: Mike Becker <universe@uap-core.de>
date: Thu, 19 Dec 2019 19:58:41 +0100
changeset 374: be77fb2da242
parent 327: fbc33813265b
permissions: -rw-r--r--

adds set operations for UcxMap

 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
  * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  *   1. Redistributions of source code must retain the above copyright
  *      notice, this list of conditions and the following disclaimer.
  *
  *   2. Redistributions in binary form must reproduce the above copyright
  *      notice, this list of conditions and the following disclaimer in the
  *      documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 /**
  * @file map.h
  *
  * Hash map implementation.
  *
  * This implementation uses murmur hash 2 and separate chaining with linked
  * lists.
  *
  * @author Mike Becker
  * @author Olaf Wintermann
  */
 #ifndef UCX_MAP_H
 #define	UCX_MAP_H
 #include "ucx.h"
 #include "string.h"
 #include "allocator.h"
 #include <stdio.h>
 #ifdef	__cplusplus
 extern "C" {
 #endif
 /**
  * Loop statement for UCX maps.
  *
  * The <code>key</code> variable is implicitly defined, but the
  * <code>value</code> variable must be already declared as type information
  * cannot be inferred.
  *
  * @param key the variable name for the key
  * @param value the variable name for the value
  * @param iter a UcxMapIterator
  * @see ucx_map_iterator()
  */
 #define UCX_MAP_FOREACH(key,value,iter) \
         for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)
 /** Type for the UCX map. @see UcxMap */
 typedef struct UcxMap          UcxMap;
 /** Type for a key of a UcxMap. @see UcxKey */
 typedef struct UcxKey          UcxKey;
 /** Type for an element of a UcxMap. @see UcxMapElement */
 typedef struct UcxMapElement   UcxMapElement;
 /** Type for an iterator over a UcxMap. @see UcxMapIterator */
 typedef struct UcxMapIterator  UcxMapIterator;
 /** Structure for the UCX map. */
 struct UcxMap {
     /** An allocator that is used for the map elements. */
     UcxAllocator  *allocator;
     /** The array of map element lists. */
     UcxMapElement **map;
     /** The size of the map is the length of the element list array. */
     size_t        size;
     /** The count of elements currently stored in this map. */
     size_t        count;
 };
 /** Structure to publicly denote a key of a UcxMap. */
 struct UcxKey {
     /** The key data. */
     const void *data;
     /** The length of the key data. */
     size_t     len;
     /** A cache for the hash value of the key data. */
     int        hash;
 };
 /** Internal structure for a key of a UcxMap. */
 struct UcxMapKey {
     /** The key data. */
     void    *data;
     /** The length of the key data. */
     size_t  len;
     /** The hash value of the key data. */
     int     hash;
 };
 /** Structure for an element of a UcxMap. */
 struct UcxMapElement {
     /** The value data. */
     void              *data;
     /** A pointer to the next element in the current list. */
     UcxMapElement     *next;
     /** The corresponding key. */
     struct UcxMapKey  key;
 };
 /** Structure for an iterator over a UcxMap. */
 struct UcxMapIterator {
     /** The map to iterate over. */
     UcxMap const  *map;
     /** The current map element. */
     UcxMapElement *cur;
     /**
      * The current index of the element list array.
      * <b>Attention: </b> this is <b>NOT</b> the element index! Do <b>NOT</b>
      * manually iterate over the map by increasing this index. Use
      * ucx_map_iter_next().
      * @see UcxMap.map*/
     size_t        index;
 };
 /**
  * Creates a new hash map with the specified size.
  * @param size the size of the hash map
  * @return a pointer to the new hash map
  */
 UcxMap *ucx_map_new(size_t size);
 /**
  * Creates a new hash map with the specified size using a UcxAllocator.
  * @param allocator the allocator to use
  * @param size the size of the hash map
  * @return a pointer to the new hash map
  */
 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size);
 /**
  * Frees a hash map.
  *
  * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content()
  * before calling this function to achieve that.
  *
  * @param map the map to be freed
  * @see ucx_map_free_content()
  */
 void ucx_map_free(UcxMap *map);
 /**
  * Frees the contents of a hash map.
  *
  * This is a convenience function that iterates over the map and passes all
  * values to the specified destructor function.
  *
  * If no destructor is specified (<code>NULL</code>), the free() function of
  * the map's own allocator is used.
  *
  * You must ensure, that it is valid to pass each value in the map to the same
  * destructor function.
  *
  * You should free or clear the map afterwards, as the contents will be invalid.
  *
  * @param map for which the contents shall be freed
  * @param destr optional pointer to a destructor function
  * @see ucx_map_free()
  * @see ucx_map_clear()
  */
 void ucx_map_free_content(UcxMap *map, ucx_destructor destr);
 /**
  * Clears a hash map.
  *
  * <b>Note:</b> the contents are <b>not</b> freed, use ucx_map_free_content()
  * before calling this function to achieve that.
  *
  * @param map the map to be cleared
  * @see ucx_map_free_content()
  */
 void ucx_map_clear(UcxMap *map);
 /**
  * Copies contents from a map to another map using a copy function.
  *
  * <b>Note:</b> The destination map does not need to be empty. However, if it
  * contains data with keys that are also present in the source map, the contents
  * are overwritten.
  *
  * @param from the source map
  * @param to the destination map
  * @param fnc the copy function or <code>NULL</code> if the pointer address
  * shall be copied
  * @param data additional data for the copy function
  * @return 0 on success or a non-zero value on memory allocation errors
  */
 int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data);
 /**
  * Clones the map and rehashes if necessary.
  *
  * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
  * This function <i>always</i> ensures a new UcxMap.size of at least
  * 2.5*UcxMap.count.
  *
  * @param map the map to clone
  * @param fnc the copy function to use or <code>NULL</code> if the new and
  * the old map shall share the data pointers
  * @param data additional data for the copy function
  * @return the cloned map
  * @see ucx_map_copy()
  */
 UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data);
 /**
  * Clones the map and rehashes if necessary.
  *
  * <b>Note:</b> In contrast to ucx_map_rehash() the load factor is irrelevant.
  * This function <i>always</i> ensures a new UcxMap.size of at least
  * 2.5*UcxMap.count.
  *
  * @param allocator the allocator to use for the cloned map
  * @param map the map to clone
  * @param fnc the copy function to use or <code>NULL</code> if the new and
  * the old map shall share the data pointers
  * @param data additional data for the copy function
  * @return the cloned map
  * @see ucx_map_copy()
  */
 UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
                         UcxMap const *map, copy_func fnc, void *data);
 /**
  * Increases size of the hash map, if necessary.
  *
  * The load value is 0.75*UcxMap.size. If the element count exceeds the load
  * value, the map needs to be rehashed. Otherwise no action is performed and
  * this function simply returns 0.
  *
  * The rehashing process ensures, that the UcxMap.size is at least
  * 2.5*UcxMap.count. So there is enough room for additional elements without
  * the need of another soon rehashing.
  *
  * You can use this function to dramatically increase access performance.
  *
  * @param map the map to rehash
  * @return 1, if a memory allocation error occurred, 0 otherwise
  */
 int ucx_map_rehash(UcxMap *map);
 /**
  * Puts a key/value-pair into the map.
  *
  * @param map the map
  * @param key the key
  * @param value the value
  * @return 0 on success, non-zero value on failure
  */
 int ucx_map_put(UcxMap *map, UcxKey key, void *value);
 /**
  * Retrieves a value by using a key.
  *
  * @param map the map
  * @param key the key
  * @return the value
  */
 void* ucx_map_get(UcxMap const *map, UcxKey key);
 /**
  * Removes a key/value-pair from the map by using the key.
  *
  * @param map the map
  * @param key the key
  * @return the removed value
  */
 void* ucx_map_remove(UcxMap *map, UcxKey key);
 /**
  * Shorthand for putting data with a sstr_t key into the map.
  * @param map the map
  * @param key the key
  * @param value the value
  * @return 0 on success, non-zero value on failure
  * @see ucx_map_put()
  */
 #define ucx_map_sstr_put(map, key, value) \
     ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)
 /**
  * Shorthand for putting data with a C string key into the map.
  * @param map the map
  * @param key the key
  * @param value the value
  * @return 0 on success, non-zero value on failure
  * @see ucx_map_put()
  */
 #define ucx_map_cstr_put(map, key, value) \
     ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value)
 /**
  * Shorthand for putting data with an integer key into the map.
  * @param map the map
  * @param key the key
  * @param value the value
  * @return 0 on success, non-zero value on failure
  * @see ucx_map_put()
  */
 #define ucx_map_int_put(map, key, value) \
     ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value)
 /**
  * Shorthand for getting data from the map with a sstr_t key.
  * @param map the map
  * @param key the key
  * @return the value
  * @see ucx_map_get()
  */
 #define ucx_map_sstr_get(map, key) \
     ucx_map_get(map, ucx_key(key.ptr, key.length))
 /**
  * Shorthand for getting data from the map with a C string key.
  * @param map the map
  * @param key the key
  * @return the value
  * @see ucx_map_get()
  */
 #define ucx_map_cstr_get(map, key) \
     ucx_map_get(map, ucx_key(key, strlen(key)))
 /**
  * Shorthand for getting data from the map with an integer key.
  * @param map the map
  * @param key the key
  * @return the value
  * @see ucx_map_get()
  */
 #define ucx_map_int_get(map, key) \
     ucx_map_get(map, ucx_key(&key, sizeof(int)))
 /**
  * Shorthand for removing data from the map with a sstr_t key.
  * @param map the map
  * @param key the key
  * @return the removed value
  * @see ucx_map_remove()
  */
 #define ucx_map_sstr_remove(map, key) \
     ucx_map_remove(map, ucx_key(key.ptr, key.length))
 /**
  * Shorthand for removing data from the map with a C string key.
  * @param map the map
  * @param key the key
  * @return the removed value
  * @see ucx_map_remove()
  */
 #define ucx_map_cstr_remove(map, key) \
     ucx_map_remove(map, ucx_key(key, strlen(key)))
 /**
  * Shorthand for removing data from the map with an integer key.
  * @param map the map
  * @param key the key
  * @return the removed value
  * @see ucx_map_remove()
  */
 #define ucx_map_int_remove(map, key) \
     ucx_map_remove(map, ucx_key(&key, sizeof(key)))
 /**
  * Creates a UcxKey based on the given data.
  *
  * This function implicitly computes the hash.
  *
  * @param data the data for the key
  * @param len the length of the data
  * @return a UcxKey with implicitly computed hash
  * @see ucx_hash()
  */
 UcxKey ucx_key(const void *data, size_t len);
 /**
  * Computes a murmur hash-2.
  *
  * @param data the data to hash
  * @param len the length of the data
  * @return the murmur hash-2 of the data
  */
 int ucx_hash(const char *data, size_t len);
 /**
  * Creates an iterator for a map.
  *
  * <b>Note:</b> A UcxMapIterator iterates over all elements in all element
  * lists successively. Therefore the order highly depends on the key hashes and
  * may vary under different map sizes. So generally you may <b>NOT</b> rely on
  * the iteration order.
  *
  * <b>Note:</b> The iterator is <b>NOT</b> initialized. You need to call
  * ucx_map_iter_next() at least once before accessing any information. However,
  * it is not recommended to access the fields of a UcxMapIterator directly.
  *
  * @param map the map to create the iterator for
  * @return an iterator initialized on the first element of the
  * first element list
  * @see ucx_map_iter_next()
  */
 UcxMapIterator ucx_map_iterator(UcxMap const *map);
 /**
  * Proceeds to the next element of the map (if any).
  *
  * Subsequent calls on the same iterator proceed to the next element and
  * store the key/value-pair into the memory specified as arguments of this
  * function.
  *
  * If no further elements are found, this function returns zero and leaves the
  * last found key/value-pair in memory.
  *
  * @param iterator the iterator to use
  * @param key a pointer to the memory where to store the key
  * @param value a pointer to the memory where to store the value
  * @return 1, if another element was found, 0 if all elements has been processed
  * @see ucx_map_iterator()
  */
 int ucx_map_iter_next(UcxMapIterator *iterator, UcxKey *key, void **value);
 /**
  * Returns the union of two maps.
  *
  * The union is a fresh map which is filled by two successive calls of
  * ucx_map_copy() on the two input maps.
  *
  * @param first the first source map
  * @param second the second source map
  * @param cpfnc a function to copy the elements
  * @param cpdata additional data for the copy function
  * @return a new map containing the union
  */
 UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
                       copy_func cpfnc, void* cpdata);
 /**
  * Returns the union of two maps.
  *
  * The union is a fresh map which is filled by two successive calls of
  * ucx_map_copy() on the two input maps.
  *
  * @param allocator the allocator that shall be used by the new map
  * @param first the first source map
  * @param second the second source map
  * @param cpfnc a function to copy the elements
  * @param cpdata additional data for the copy function
  * @return a new map containing the union
  */
 UcxMap* ucx_map_union_a(UcxAllocator *allocator,
                         const UcxMap *first, const UcxMap *second,
                         copy_func cpfnc, void* cpdata);
 /**
  * Returns the intersection of two maps.
  *
  * The intersection is defined as a copy of the first map with every element
  * removed that has no valid key in the second map.
  *
  * @param first the first source map
  * @param second the second source map
  * @param cpfnc a function to copy the elements
  * @param cpdata additional data for the copy function
  * @return a new map containing the intersection
  */
 UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
                              copy_func cpfnc, void* cpdata);
 /**
  * Returns the intersection of two maps.
  *
  * The intersection is defined as a copy of the first map with every element
  * removed that has no valid key in the second map.
  *
  * @param allocator the allocator that shall be used by the new map
  * @param first the first source map
  * @param second the second source map
  * @param cpfnc a function to copy the elements
  * @param cpdata additional data for the copy function
  * @return a new map containing the intersection
  */
 UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
                                const UcxMap *first, const UcxMap *second,
                                copy_func cpfnc, void* cpdata);
 /**
  * Returns the difference of two maps.
  *
  * The difference contains a copy of all elements of the first map
  * for which the corresponding keys cannot be found in the second map.
  *
  * @param first the first source map
  * @param second the second source map
  * @param cpfnc a function to copy the elements
  * @param cpdata additional data for the copy function
  * @return a new list containing the difference
  */
 UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
                            copy_func cpfnc, void* cpdata);
 /**
  * Returns the difference of two maps.
  *
  * The difference contains a copy of all elements of the first map
  * for which the corresponding keys cannot be found in the second map.
  *
  * @param allocator the allocator that shall be used by the new map
  * @param first the first source map
  * @param second the second source map
  * @param cpfnc a function to copy the elements
  * @param cpdata additional data for the copy function
  * @return a new list containing the difference
  */
 UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
                              const UcxMap *first, const UcxMap *second,
                              copy_func cpfnc, void* cpdata);
 #ifdef	__cplusplus
 }
 #endif
 #endif	/* UCX_MAP_H */

Mercurial > hg > ucx / annotate

src/ucx/map.h@be77fb2da242 (annotated)

src/ucx/map.h