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             : #include "tommyhashtbl.h"
      29             : #include "tommylist.h"
      30             : 
      31             : #include <string.h> /* for memset */
      32             : 
      33             : /******************************************************************************/
      34             : /* hashtable */
      35             : 
      36        5065 : TOMMY_API void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_size_t bucket_max)
      37             : {
      38        5065 :         if (bucket_max < 16)
      39           1 :                 bucket_max = 16;
      40             :         else
      41        5064 :                 bucket_max = tommy_roundup_pow2(bucket_max);
      42             : 
      43        5065 :         hashtable->bucket_max = bucket_max;
      44        5065 :         hashtable->bucket_mask = hashtable->bucket_max - 1;
      45             : 
      46             :         /* initialize the vector using malloc()+memset() instead of calloc() */
      47             :         /* to ensure that all the memory in really allocated immediately */
      48             :         /* by the OS, and not deferred at later time. */
      49             :         /* this improves performance, because we start with a fully initialized hashtable. */
      50        5065 :         hashtable->bucket = tommy_cast(tommy_hashtable_node**, tommy_malloc(hashtable->bucket_max * sizeof(tommy_hashtable_node*)));
      51        5065 :         memset(hashtable->bucket, 0, hashtable->bucket_max * sizeof(tommy_hashtable_node*));
      52             : 
      53        5065 :         hashtable->count = 0;
      54        5065 : }
      55             : 
      56        5065 : TOMMY_API void tommy_hashtable_done(tommy_hashtable* hashtable)
      57             : {
      58        5065 :         tommy_free(hashtable->bucket);
      59        5065 : }
      60             : 
      61    76497500 : TOMMY_API void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash)
      62             : {
      63    76497500 :         tommy_size_t pos = hash & hashtable->bucket_mask;
      64             : 
      65    76497500 :         tommy_list_insert_tail(&hashtable->bucket[pos], node, data);
      66             : 
      67    76497500 :         node->index = hash;
      68             : 
      69    76497500 :         ++hashtable->count;
      70    76497500 : }
      71             : 
      72    68745609 : TOMMY_API void* tommy_hashtable_remove_existing(tommy_hashtable* hashtable, tommy_hashtable_node* node)
      73             : {
      74    68745609 :         tommy_size_t pos = node->index & hashtable->bucket_mask;
      75             : 
      76    68745609 :         tommy_list_remove_existing(&hashtable->bucket[pos], node);
      77             : 
      78    68745609 :         --hashtable->count;
      79             : 
      80    68745609 :         return node->data;
      81             : }
      82             : 
      83    14496891 : TOMMY_API void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
      84             : {
      85    14496891 :         tommy_size_t pos = hash & hashtable->bucket_mask;
      86    14496891 :         tommy_hashtable_node* node = hashtable->bucket[pos];
      87             : 
      88    16155047 :         while (node) {
      89             :                 /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
      90     9407547 :                 if (node->index == hash && cmp(cmp_arg, node->data) == 0) {
      91     7749391 :                         tommy_list_remove_existing(&hashtable->bucket[pos], node);
      92             : 
      93     7749391 :                         --hashtable->count;
      94             : 
      95     7749391 :                         return node->data;
      96             :                 }
      97     1658156 :                 node = node->next;
      98             :         }
      99             : 
     100     6747500 :         return 0;
     101             : }
     102             : 
     103        5001 : TOMMY_API void tommy_hashtable_foreach(tommy_hashtable* hashtable, tommy_foreach_func* func)
     104             : {
     105        5001 :         tommy_size_t bucket_max = hashtable->bucket_max;
     106        5001 :         tommy_hashtable_node** bucket = hashtable->bucket;
     107             :         tommy_size_t pos;
     108             : 
     109    21009289 :         for (pos = 0; pos < bucket_max; ++pos) {
     110    21004288 :                 tommy_hashtable_node* node = bucket[pos];
     111             : 
     112    34501788 :                 while (node) {
     113    13497500 :                         void* data = node->data;
     114    13497500 :                         node = node->next;
     115    13497500 :                         func(data);
     116             :                 }
     117             :         }
     118        5001 : }
     119             : 
     120          63 : TOMMY_API void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg)
     121             : {
     122          63 :         tommy_size_t bucket_max = hashtable->bucket_max;
     123          63 :         tommy_hashtable_node** bucket = hashtable->bucket;
     124             :         tommy_size_t pos;
     125             : 
     126      526335 :         for (pos = 0; pos < bucket_max; ++pos) {
     127      526272 :                 tommy_hashtable_node* node = bucket[pos];
     128             : 
     129     1528163 :                 while (node) {
     130     1001891 :                         void* data = node->data;
     131     1001891 :                         node = node->next;
     132     1001891 :                         func(arg, data);
     133             :                 }
     134             :         }
     135          63 : }
     136             : 
     137        5001 : TOMMY_API tommy_size_t tommy_hashtable_memory_usage(tommy_hashtable* hashtable)
     138             : {
     139        5001 :         return hashtable->bucket_max * (tommy_size_t)sizeof(hashtable->bucket[0])
     140        5001 :                + tommy_hashtable_count(hashtable) * (tommy_size_t)sizeof(tommy_hashtable_node);
     141             : }
     142             :