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

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

src/ucx/map.h

Thu, 21 Jun 2018 16:00:37 +0200

author: Mike Becker <universe@uap-core.de>
date: Thu, 21 Jun 2018 16:00:37 +0200
changeset 327: fbc33813265b
parent 277: f819fe5e20f5
child 374: be77fb2da242
permissions: -rw-r--r--

UcxMap now separates internal non-const keys from public const keys

This simplifies function calls with constant keys like scstr_t or const char*.

 /*
  * 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        *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 *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 *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 *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 *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);
 #ifdef	__cplusplus
 }
 #endif
 #endif	/* UCX_MAP_H */

Mercurial > hg > ucx / annotate

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

src/ucx/map.h