LCOV - code coverage report
Current view: top level - lib - dynamicsizehash.c (source / functions) Hit Total Coverage
Test: lcov.out Lines: 65 69 94.2 %
Date: 2017-01-05 09:15:16 Functions: 14 15 93.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000-2010 Red Hat, Inc.
       2             :    This file is part of elfutils.
       3             :    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
       4             : 
       5             :    This file is free software; you can redistribute it and/or modify
       6             :    it under the terms of either
       7             : 
       8             :      * the GNU Lesser General Public License as published by the Free
       9             :        Software Foundation; either version 3 of the License, or (at
      10             :        your option) any later version
      11             : 
      12             :    or
      13             : 
      14             :      * the GNU General Public License as published by the Free
      15             :        Software Foundation; either version 2 of the License, or (at
      16             :        your option) any later version
      17             : 
      18             :    or both in parallel, as here.
      19             : 
      20             :    elfutils is distributed in the hope that it will be useful, but
      21             :    WITHOUT ANY WARRANTY; without even the implied warranty of
      22             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      23             :    General Public License for more details.
      24             : 
      25             :    You should have received copies of the GNU General Public License and
      26             :    the GNU Lesser General Public License along with this program.  If
      27             :    not, see <http://www.gnu.org/licenses/>.  */
      28             : 
      29             : #include <assert.h>
      30             : #include <stdlib.h>
      31             : #include <system.h>
      32             : 
      33             : /* Before including this file the following macros must be defined:
      34             : 
      35             :    NAME      name of the hash table structure.
      36             :    TYPE      data type of the hash table entries
      37             :    COMPARE   comparison function taking two pointers to TYPE objects
      38             : 
      39             :    The following macros if present select features:
      40             : 
      41             :    ITERATE   iterating over the table entries is possible
      42             :    REVERSE   iterate in reverse order of insert
      43             :  */
      44             : 
      45             : 
      46             : static size_t
      47     4659119 : lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
      48             : {
      49             :   /* First hash function: simply take the modul but prevent zero.  Small values
      50             :      can skip the division, which helps performance when this is common.  */
      51     4659119 :   size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
      52             : 
      53     4659119 :   if (htab->table[idx].hashval != 0)
      54             :     {
      55             :       HASHTYPE hash;
      56             : 
      57     2940787 :       if (htab->table[idx].hashval == hval
      58           0 :           && COMPARE (htab->table[idx].data, val) == 0)
      59             :         return idx;
      60             : 
      61             :       /* Second hash function as suggested in [Knuth].  */
      62       75816 :       hash = 1 + hval % (htab->size - 2);
      63             : 
      64             :       do
      65             :         {
      66      333643 :           if (idx <= hash)
      67      165387 :             idx = htab->size + idx - hash;
      68             :           else
      69      168256 :             idx -= hash;
      70             : 
      71             :           /* If entry is found use it.  */
      72      333643 :           if (htab->table[idx].hashval == hval
      73           0 :               && COMPARE (htab->table[idx].data, val) == 0)
      74             :             return idx;
      75             :         }
      76      333643 :       while (htab->table[idx].hashval);
      77             :     }
      78             :   return idx;
      79             : }
      80             : 
      81             : 
      82             : static void
      83     1063793 : insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
      84             : {
      85             : #ifdef ITERATE
      86      249237 :   if (htab->table[idx].hashval == 0)
      87             :     {
      88             : # ifdef REVERSE
      89      249237 :       htab->table[idx].next = htab->first;
      90      249237 :       htab->first = &htab->table[idx];
      91             : # else
      92             :       /* Add the new value to the list.  */
      93             :       if (htab->first == NULL)
      94             :         htab->first = htab->table[idx].next = &htab->table[idx];
      95             :       else
      96             :         {
      97             :           htab->table[idx].next = htab->first->next;
      98             :           htab->first = htab->first->next = &htab->table[idx];
      99             :         }
     100             : # endif
     101             :     }
     102             : #endif
     103             : 
     104     1063793 :   htab->table[idx].hashval = hval;
     105     1063793 :   htab->table[idx].data = data;
     106             : 
     107     1063793 :   ++htab->filled;
     108     1063793 :   if (100 * htab->filled > 90 * htab->size)
     109             :     {
     110             :       /* Table is filled more than 90%.  Resize the table.  */
     111             : #ifdef ITERATE
     112             :       __typeof__ (htab->first) first;
     113             : # ifndef REVERSE
     114             :       __typeof__ (htab->first) runp;
     115             : # endif
     116             : #else
     117        8076 :       size_t old_size = htab->size;
     118             : #endif
     119             : #define _TABLE(name) \
     120             :       name##_ent *table = htab->table
     121             : #define TABLE(name) _TABLE (name)
     122        8096 :       TABLE(NAME);
     123             : 
     124       16192 :       htab->size = next_prime (htab->size * 2);
     125        8096 :       htab->filled = 0;
     126             : #ifdef ITERATE
     127          20 :       first = htab->first;
     128          20 :       htab->first = NULL;
     129             : #endif
     130        8096 :       htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
     131        8096 :       if (htab->table == NULL)
     132             :         {
     133             :           /* We cannot enlarge the table.  Live with what we got.  This
     134             :              might lead to an infinite loop at some point, though.  */
     135           0 :           htab->table = table;
     136           0 :           return;
     137             :         }
     138             : 
     139             :       /* Add the old entries to the new table.  When iteration is
     140             :          supported we maintain the order.  */
     141             : #ifdef ITERATE
     142             : # ifdef REVERSE
     143      161252 :       while (first != NULL)
     144             :         {
     145      161232 :           insert_entry_2 (htab, first->hashval,
     146             :                           lookup (htab, first->hashval, first->data),
     147             :                           first->data);
     148             : 
     149      161232 :           first = first->next;
     150             :         }
     151             : # else
     152             :       assert (first != NULL);
     153             :       runp = first = first->next;
     154             :       do
     155             :         insert_entry_2 (htab, runp->hashval,
     156             :                         lookup (htab, runp->hashval, runp->data), runp->data);
     157             :       while ((runp = runp->next) != first);
     158             : # endif
     159             : #else
     160      394620 :       for (idx = 1; idx <= old_size; ++idx)
     161      394620 :         if (table[idx].hashval != 0)
     162      356268 :           insert_entry_2 (htab, table[idx].hashval,
     163             :                           lookup (htab, table[idx].hashval, table[idx].data),
     164             :                           table[idx].data);
     165             : #endif
     166             : 
     167        8096 :       free (table);
     168             :     }
     169             : }
     170             : 
     171             : 
     172             : int
     173             : #define INIT(name) _INIT (name)
     174             : #define _INIT(name) \
     175             :   name##_init
     176       15723 : INIT(NAME) (NAME *htab, size_t init_size)
     177             : {
     178             :   /* We need the size to be a prime.  */
     179       15723 :   init_size = next_prime (init_size);
     180             : 
     181             :   /* Initialize the data structure.  */
     182       15723 :   htab->size = init_size;
     183       15723 :   htab->filled = 0;
     184             : #ifdef ITERATE
     185           9 :   htab->first = NULL;
     186             : #endif
     187       15723 :   htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
     188       15723 :   if (htab->table == NULL)
     189             :     return -1;
     190             : 
     191       15723 :   return 0;
     192             : }
     193             : 
     194             : 
     195             : int
     196             : #define FREE(name) _FREE (name)
     197             : #define _FREE(name) \
     198             :   name##_free
     199       20856 : FREE(NAME) (NAME *htab)
     200             : {
     201       20856 :   free (htab->table);
     202       20856 :   return 0;
     203             : }
     204             : 
     205             : 
     206             : int
     207             : #define INSERT(name) _INSERT (name)
     208             : #define _INSERT(name) \
     209             :   name##_insert
     210      546293 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
     211             : {
     212             :   size_t idx;
     213             : 
     214             :   /* Make the hash value nonzero.  */
     215      546293 :   hval = hval ?: 1;
     216             : 
     217      546293 :   idx = lookup (htab, hval, data);
     218             : 
     219      546293 :   if (htab->table[idx].hashval != 0)
     220             :     /* We don't want to overwrite the old value.  */
     221             :     return -1;
     222             : 
     223             :   /* An empty bucket has been found.  */
     224      546293 :   insert_entry_2 (htab, hval, idx, data);
     225      546293 :   return 0;
     226             : }
     227             : 
     228             : 
     229             : #ifdef OVERWRITE
     230             : int
     231             : #define INSERT(name) _INSERT (name)
     232             : #define _INSERT(name) \
     233             :   name##_overwrite
     234             : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
     235             : {
     236             :   size_t idx;
     237             : 
     238             :   /* Make the hash value nonzero.  */
     239             :   hval = hval ?: 1;
     240             : 
     241             :   idx = lookup (htab, hval, data);
     242             : 
     243             :   /* The correct bucket has been found.  */
     244             :   insert_entry_2 (htab, hval, idx, data);
     245             :   return 0;
     246             : }
     247             : #endif
     248             : 
     249             : 
     250             : TYPE
     251             : #define FIND(name) _FIND (name)
     252             : #define _FIND(name) \
     253             :   name##_find
     254     3595326 : FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
     255             : {
     256             :   size_t idx;
     257             : 
     258             :   /* Make the hash value nonzero.  */
     259     3595326 :   hval = hval ?: 1;
     260             : 
     261     3595326 :   idx = lookup (htab, hval, val);
     262             : 
     263     3595326 :   if (htab->table[idx].hashval == 0)
     264             :     return NULL;
     265             : 
     266     2864971 :   return htab->table[idx].data;
     267             : }
     268             : 
     269             : 
     270             : #ifdef ITERATE
     271             : # define ITERATEFCT(name) _ITERATEFCT (name)
     272             : # define _ITERATEFCT(name) \
     273             :   name##_iterate
     274             : TYPE
     275      176024 : ITERATEFCT(NAME) (NAME *htab, void **ptr)
     276             : {
     277      176024 :   void *p = *ptr;
     278             : 
     279             : # define TYPENAME(name) _TYPENAME (name)
     280             : # define _TYPENAME(name) name##_ent
     281             : 
     282             : # ifdef REVERSE
     283      176024 :   if (p == NULL)
     284          14 :     p = htab->first;
     285             :   else
     286      176010 :     p = ((TYPENAME(NAME) *) p)->next;
     287             : 
     288      176024 :   if (p == NULL)
     289             :     {
     290          14 :       *ptr = NULL;
     291          14 :       return NULL;
     292             :     }
     293             : # else
     294             :   if (p == NULL)
     295             :     {
     296             :       if (htab->first == NULL)
     297             :         return NULL;
     298             :       p = htab->first->next;
     299             :     }
     300             :   else
     301             :     {
     302             :       if (p == htab->first)
     303             :         return NULL;
     304             : 
     305             :       p = ((TYPENAME(NAME) *) p)->next;
     306             :     }
     307             : # endif
     308             : 
     309             :   /* Prepare the next element.  If possible this will pull the data
     310             :      into the cache, for reading.  */
     311      176010 :   __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
     312             : 
     313      176010 :   return ((TYPENAME(NAME) *) (*ptr = p))->data;
     314             : }
     315             : #endif

Generated by: LCOV version 1.12