LCOV - code coverage report
Current view: top level - tommyds - tommyhashdyn.h (source / functions) Hit Total Coverage
Test: lcov.info Lines: 11 11 100.0 %
Date: 2017-11-06 22:14:04 Functions: 3 3 100.0 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
       3             :  *
       4             :  * Redistribution and use in source and binary forms, with or without
       5             :  * modification, are permitted provided that the following conditions
       6             :  * are met:
       7             :  *
       8             :  * 1. Redistributions of source code must retain the above copyright
       9             :  *    notice, this list of conditions and the following disclaimer.
      10             :  *
      11             :  * 2. Redistributions in binary form must reproduce the above copyright
      12             :  *    notice, this list of conditions and the following disclaimer in the
      13             :  *    documentation and/or other materials provided with the distribution.
      14             :  *
      15             :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
      16             :  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      17             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      18             :  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
      19             :  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
      20             :  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
      21             :  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
      22             :  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
      23             :  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
      24             :  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
      25             :  * POSSIBILITY OF SUCH DAMAGE.
      26             :  */
      27             : 
      28             : /** \file
      29             :  * Dynamic chained hashtable.
      30             :  *
      31             :  * This hashtable resizes dynamically. It starts with the minimal size of 16 buckets, it doubles
      32             :  * the size then it reaches a load factor greater than 0.5 and it halves the size with a load
      33             :  * factor lower than 0.125.
      34             :  *
      35             :  * All the elements are reallocated in a single resize operation done inside
      36             :  * tommy_hashdyn_insert() or tommy_hashdyn_remove().
      37             :  *
      38             :  * Note that the resize operation takes approximatively 100 [ms] with 1 million of elements,
      39             :  * and 1 [second] with 10 millions. This could be a problem in real-time applications.
      40             :  *
      41             :  * The resize also fragment the heap, as it involves allocating a double-sized table, copy elements,
      42             :  * and deallocating the older table. Leaving a big hole in the heap.
      43             :  *
      44             :  * The ::tommy_hashlin hashtable fixes both problems.
      45             :  *
      46             :  * To initialize the hashtable you have to call tommy_hashdyn_init().
      47             :  *
      48             :  * \code
      49             :  * tommy_hashslin hashdyn;
      50             :  *
      51             :  * tommy_hashdyn_init(&hashdyn);
      52             :  * \endcode
      53             :  *
      54             :  * To insert elements in the hashtable you have to call tommy_hashdyn_insert() for
      55             :  * each element.
      56             :  * In the insertion call you have to specify the address of the node, the
      57             :  * address of the object, and the hash value of the key to use.
      58             :  * The address of the object is used to initialize the tommy_node::data field
      59             :  * of the node, and the hash to initialize the tommy_node::key field.
      60             :  *
      61             :  * \code
      62             :  * struct object {
      63             :  *     int value;
      64             :  *     // other fields
      65             :  *     tommy_node node;
      66             :  * };
      67             :  *
      68             :  * struct object* obj = malloc(sizeof(struct object)); // creates the object
      69             :  *
      70             :  * obj->value = ...; // initializes the object
      71             :  *
      72             :  * tommy_hashdyn_insert(&hashdyn, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object
      73             :  * \endcode
      74             :  *
      75             :  * To find and element in the hashtable you have to call tommy_hashtable_search()
      76             :  * providing a comparison function, its argument, and the hash of the key to search.
      77             :  *
      78             :  * \code
      79             :  * int compare(const void* arg, const void* obj)
      80             :  * {
      81             :  *     return *(const int*)arg != ((const struct object*)obj)->value;
      82             :  * }
      83             :  *
      84             :  * int value_to_find = 1;
      85             :  * struct object* obj = tommy_hashdyn_search(&hashdyn, compare, &value_to_find, tommy_inthash_u32(value_to_find));
      86             :  * if (!obj) {
      87             :  *     // not found
      88             :  * } else {
      89             :  *     // found
      90             :  * }
      91             :  * \endcode
      92             :  *
      93             :  * To iterate over all the elements in the hashtable with the same key, you have to
      94             :  * use tommy_hashdyn_bucket() and follow the tommy_node::next pointer until NULL.
      95             :  * You have also to check explicitely for the key, as the bucket may contains
      96             :  * different keys.
      97             :  *
      98             :  * \code
      99             :  * int value_to_find = 1;
     100             :  * tommy_node* i = tommy_hashdyn_bucket(&hashdyn, tommy_inthash_u32(value_to_find));
     101             :  * while (i) {
     102             :  *     struct object* obj = i->data; // gets the object pointer
     103             :  *
     104             :  *     if (obj->value == value_to_find) {
     105             :  *         printf("%d\n", obj->value); // process the object
     106             :  *     }
     107             :  *
     108             :  *     i = i->next; // goes to the next element
     109             :  * }
     110             :  * \endcode
     111             :  *
     112             :  * To remove an element from the hashtable you have to call tommy_hashdyn_remove()
     113             :  * providing a comparison function, its argument, and the hash of the key to search
     114             :  * and remove.
     115             :  *
     116             :  * \code
     117             :  * struct object* obj = tommy_hashdyn_remove(&hashdyn, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
     118             :  * if (obj) {
     119             :  *     free(obj); // frees the object allocated memory
     120             :  * }
     121             :  * \endcode
     122             :  *
     123             :  * To destroy the hashtable you have to remove all the elements, and deinitialize
     124             :  * the hashtable calling tommy_hashdyn_done().
     125             :  *
     126             :  * \code
     127             :  * tommy_hashdyn_done(&hashdyn);
     128             :  * \endcode
     129             :  *
     130             :  * If you need to iterate over all the elements in the hashtable, you can use
     131             :  * tommy_hashdyn_foreach() or tommy_hashdyn_foreach_arg().
     132             :  * If you need a more precise control with a real iteration, you have to insert
     133             :  * all the elements also in a ::tommy_list, and use the list to iterate.
     134             :  * See the \ref multiindex example for more detail.
     135             :  */
     136             : 
     137             : #ifndef __TOMMYHASHDYN_H
     138             : #define __TOMMYHASHDYN_H
     139             : 
     140             : #include "tommyhash.h"
     141             : 
     142             : /******************************************************************************/
     143             : /* hashdyn */
     144             : 
     145             : /** \internal
     146             :  * Initial and minimal size of the hashtable expressed as a power of 2.
     147             :  * The initial size is 2^TOMMY_HASHDYN_BIT.
     148             :  */
     149             : #define TOMMY_HASHDYN_BIT 4
     150             : 
     151             : /**
     152             :  * Hashtable node.
     153             :  * This is the node that you have to include inside your objects.
     154             :  */
     155             : typedef tommy_node tommy_hashdyn_node;
     156             : 
     157             : /**
     158             :  * Hashtable container type.
     159             :  * \note Don't use internal fields directly, but access the container only using functions.
     160             :  */
     161             : typedef struct tommy_hashdyn_struct {
     162             :         tommy_hashdyn_node** bucket; /**< Hash buckets. One list for each hash modulus. */
     163             :         tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
     164             :         tommy_count_t bucket_max; /**< Number of buckets. */
     165             :         tommy_count_t bucket_mask; /**< Bit mask to access the buckets. */
     166             :         tommy_count_t count; /**< Number of elements. */
     167             : } tommy_hashdyn;
     168             : 
     169             : /**
     170             :  * Initializes the hashtable.
     171             :  */
     172             : void tommy_hashdyn_init(tommy_hashdyn* hashdyn);
     173             : 
     174             : /**
     175             :  * Deinitializes the hashtable.
     176             :  *
     177             :  * You can call this function with elements still contained,
     178             :  * but such elements are not going to be freed by this call.
     179             :  */
     180             : void tommy_hashdyn_done(tommy_hashdyn* hashdyn);
     181             : 
     182             : /**
     183             :  * Inserts an element in the hashtable.
     184             :  */
     185             : void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash);
     186             : 
     187             : /**
     188             :  * Searches and removes an element from the hashtable.
     189             :  * You have to provide a compare function and the hash of the element you want to remove.
     190             :  * If the element is not found, 0 is returned.
     191             :  * If more equal elements are present, the first one is removed.
     192             :  * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
     193             :  * The function should return 0 for equal elements, anything other for different elements.
     194             :  * \param cmp_arg Compare argument passed as first argument of the compare function.
     195             :  * \param hash Hash of the element to find and remove.
     196             :  * \return The removed element, or 0 if not found.
     197             :  */
     198             : void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
     199             : 
     200             : /**
     201             :  * Gets the bucket of the specified hash.
     202             :  * The bucket is guaranteed to contain ALL the elements with the specified hash,
     203             :  * but it can contain also others.
     204             :  * You can access elements in the bucket following the ::next pointer until 0.
     205             :  * \param hash Hash of the element to find.
     206             :  * \return The head of the bucket, or 0 if empty.
     207             :  */
     208     3133766 : tommy_inline tommy_hashdyn_node* tommy_hashdyn_bucket(tommy_hashdyn* hashdyn, tommy_hash_t hash)
     209             : {
     210     3133766 :         return hashdyn->bucket[hash & hashdyn->bucket_mask];
     211             : }
     212             : 
     213             : /**
     214             :  * Searches an element in the hashtable.
     215             :  * You have to provide a compare function and the hash of the element you want to find.
     216             :  * If more equal elements are present, the first one is returned.
     217             :  * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
     218             :  * The function should return 0 for equal elements, anything other for different elements.
     219             :  * \param cmp_arg Compare argument passed as first argument of the compare function.
     220             :  * \param hash Hash of the element to find.
     221             :  * \return The first element found, or 0 if none.
     222             :  */
     223     3133766 : tommy_inline void* tommy_hashdyn_search(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
     224             : {
     225     3133766 :         tommy_hashdyn_node* i = tommy_hashdyn_bucket(hashdyn, hash);
     226             : 
     227     6936237 :         while (i) {
     228             :                 /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
     229     1845703 :                 if (i->key == hash && cmp(cmp_arg, i->data) == 0)
     230     1176998 :                         return i->data;
     231      668705 :                 i = i->next;
     232             :         }
     233     1956768 :         return 0;
     234             : }
     235             : 
     236             : /**
     237             :  * Removes an element from the hashtable.
     238             :  * You must already have the address of the element to remove.
     239             :  * \return The tommy_node::data field of the node removed.
     240             :  */
     241             : void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node);
     242             : 
     243             : /**
     244             :  * Calls the specified function for each element in the hashtable.
     245             :  *
     246             :  * You cannot add or remove elements from the inside of the callback,
     247             :  * but can use it to deallocate them.
     248             :  *
     249             :  * \code
     250             :  * tommy_hashdyn hashdyn;
     251             :  *
     252             :  * // initializes the hashtable
     253             :  * tommy_hashdyn_init(&hashdyn);
     254             :  *
     255             :  * ...
     256             :  *
     257             :  * // creates an object
     258             :  * struct object* obj = malloc(sizeof(struct object));
     259             :  *
     260             :  * ...
     261             :  *
     262             :  * // insert it in the hashtable
     263             :  * tommy_hashdyn_insert(&hashdyn, &obj->node, obj, tommy_inthash_u32(obj->value));
     264             :  *
     265             :  * ...
     266             :  *
     267             :  * // deallocates all the objects iterating the hashtable
     268             :  * tommy_hashdyn_foreach(&hashdyn, free);
     269             :  *
     270             :  * // deallocates the hashtable
     271             :  * tommy_hashdyn_done(&hashdyn);
     272             :  * \endcode
     273             :  */
     274             : void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func);
     275             : 
     276             : /**
     277             :  * Calls the specified function with an argument for each element in the hashtable.
     278             :  */
     279             : void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg);
     280             : 
     281             : /**
     282             :  * Gets the number of elements.
     283             :  */
     284           3 : tommy_inline tommy_count_t tommy_hashdyn_count(tommy_hashdyn* hashdyn)
     285             : {
     286           3 :         return hashdyn->count;
     287             : }
     288             : 
     289             : /**
     290             :  * Gets the size of allocated memory.
     291             :  * It includes the size of the ::tommy_hashdyn_node of the stored elements.
     292             :  */
     293             : tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn);
     294             : 
     295             : #endif
     296             : 

Generated by: LCOV version 1.13