Home | History | Annotate | Download | only in coregrind
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- A separately-chained hash table.               m_hashtable.c ---*/
      4 /*--------------------------------------------------------------------*/
      5 
      6 /*
      7    This file is part of Valgrind, a dynamic binary instrumentation
      8    framework.
      9 
     10    Copyright (C) 2005-2010 Nicholas Nethercote
     11       njn (at) valgrind.org
     12 
     13    This program is free software; you can redistribute it and/or
     14    modify it under the terms of the GNU General Public License as
     15    published by the Free Software Foundation; either version 2 of the
     16    License, or (at your option) any later version.
     17 
     18    This program is distributed in the hope that it will be useful, but
     19    WITHOUT ANY WARRANTY; without even the implied warranty of
     20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     21    General Public License for more details.
     22 
     23    You should have received a copy of the GNU General Public License
     24    along with this program; if not, write to the Free Software
     25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     26    02111-1307, USA.
     27 
     28    The GNU General Public License is contained in the file COPYING.
     29 */
     30 
     31 #include "pub_core_basics.h"
     32 #include "pub_core_debuglog.h"
     33 #include "pub_core_hashtable.h"
     34 #include "pub_core_libcassert.h"
     35 #include "pub_core_mallocfree.h"
     36 
     37 /*--------------------------------------------------------------------*/
     38 /*--- Declarations                                                 ---*/
     39 /*--------------------------------------------------------------------*/
     40 
     41 #define CHAIN_NO(key,tbl) (((UWord)(key)) % tbl->n_chains)
     42 
     43 struct _VgHashTable {
     44    UInt         n_chains;   // should be prime
     45    UInt         n_elements;
     46    VgHashNode*  iterNode;   // current iterator node
     47    UInt         iterChain;  // next chain to be traversed by the iterator
     48    VgHashNode** chains;     // expanding array of hash chains
     49    Bool         iterOK;     // table safe to iterate over?
     50    HChar*       name;       // name of table (for debugging only)
     51 };
     52 
     53 #define N_HASH_PRIMES 20
     54 
     55 static SizeT primes[N_HASH_PRIMES] = {
     56          769UL,         1543UL,         3079UL,          6151UL,
     57        12289UL,        24593UL,        49157UL,         98317UL,
     58       196613UL,       393241UL,       786433UL,       1572869UL,
     59      3145739UL,      6291469UL,     12582917UL,      25165843UL,
     60     50331653UL,    100663319UL,    201326611UL,     402653189UL
     61 };
     62 
     63 /*--------------------------------------------------------------------*/
     64 /*--- Functions                                                    ---*/
     65 /*--------------------------------------------------------------------*/
     66 
     67 VgHashTable VG_(HT_construct) ( HChar* name )
     68 {
     69    /* Initialises to zero, ie. all entries NULL */
     70    SizeT       n_chains = primes[0];
     71    SizeT       sz       = n_chains * sizeof(VgHashNode*);
     72    VgHashTable table    = VG_(calloc)("hashtable.Hc.1",
     73                                       1, sizeof(struct _VgHashTable));
     74    table->chains        = VG_(calloc)("hashtable.Hc.2", 1, sz);
     75    table->n_chains      = n_chains;
     76    table->n_elements    = 0;
     77    table->iterOK        = True;
     78    table->name          = name;
     79    vg_assert(name);
     80    return table;
     81 }
     82 
     83 Int VG_(HT_count_nodes) ( VgHashTable table )
     84 {
     85    return table->n_elements;
     86 }
     87 
     88 static void resize ( VgHashTable table )
     89 {
     90    Int          i;
     91    SizeT        sz;
     92    SizeT        old_chains = table->n_chains;
     93    SizeT        new_chains = old_chains + 1;
     94    VgHashNode** chains;
     95    VgHashNode * node;
     96 
     97    /* If we've run out of primes, do nothing. */
     98    if (old_chains == primes[N_HASH_PRIMES-1])
     99       return;
    100 
    101    vg_assert(old_chains >= primes[0]
    102              && old_chains < primes[N_HASH_PRIMES-1]);
    103 
    104    for (i = 0; i < N_HASH_PRIMES; i++) {
    105       if (primes[i] > new_chains) {
    106          new_chains = primes[i];
    107          break;
    108       }
    109    }
    110 
    111    vg_assert(new_chains > old_chains);
    112    vg_assert(new_chains > primes[0]
    113              && new_chains <= primes[N_HASH_PRIMES-1]);
    114 
    115    VG_(debugLog)(
    116       1, "hashtable",
    117          "resizing table `%s' from %lu to %lu (total elems %lu)\n",
    118          table->name, (UWord)old_chains, (UWord)new_chains,
    119          (UWord)table->n_elements );
    120 
    121    table->n_chains = new_chains;
    122    sz = new_chains * sizeof(VgHashNode*);
    123    chains = VG_(calloc)("hashtable.resize.1", 1, sz);
    124 
    125    for (i = 0; i < old_chains; i++) {
    126       node = table->chains[i];
    127       while (node != NULL) {
    128          VgHashNode* next = node->next;
    129          UWord chain = CHAIN_NO(node->key, table);
    130          node->next = chains[chain];
    131          chains[chain] = node;
    132          node = next;
    133       }
    134    }
    135 
    136    VG_(free)(table->chains);
    137    table->chains = chains;
    138 }
    139 
    140 /* Puts a new, heap allocated VgHashNode, into the VgHashTable.  Prepends
    141    the node to the appropriate chain.  No duplicate key detection is done. */
    142 void VG_(HT_add_node) ( VgHashTable table, void* vnode )
    143 {
    144    VgHashNode* node     = (VgHashNode*)vnode;
    145    UWord chain          = CHAIN_NO(node->key, table);
    146    node->next           = table->chains[chain];
    147    table->chains[chain] = node;
    148    table->n_elements++;
    149    if ( (1 * (ULong)table->n_elements) > (1 * (ULong)table->n_chains) ) {
    150       resize(table);
    151    }
    152 
    153    /* Table has been modified; hence HT_Next should assert. */
    154    table->iterOK = False;
    155 }
    156 
    157 /* Looks up a VgHashNode in the table.  Returns NULL if not found. */
    158 void* VG_(HT_lookup) ( VgHashTable table, UWord key )
    159 {
    160    VgHashNode* curr = table->chains[ CHAIN_NO(key, table) ];
    161 
    162    while (curr) {
    163       if (key == curr->key) {
    164          return curr;
    165       }
    166       curr = curr->next;
    167    }
    168    return NULL;
    169 }
    170 
    171 /* Removes a VgHashNode from the table.  Returns NULL if not found. */
    172 void* VG_(HT_remove) ( VgHashTable table, UWord key )
    173 {
    174    UWord        chain         = CHAIN_NO(key, table);
    175    VgHashNode*  curr          =   table->chains[chain];
    176    VgHashNode** prev_next_ptr = &(table->chains[chain]);
    177 
    178    /* Table has been modified; hence HT_Next should assert. */
    179    table->iterOK = False;
    180 
    181    while (curr) {
    182       if (key == curr->key) {
    183          *prev_next_ptr = curr->next;
    184          table->n_elements--;
    185          return curr;
    186       }
    187       prev_next_ptr = &(curr->next);
    188       curr = curr->next;
    189    }
    190    return NULL;
    191 }
    192 
    193 /* Allocates a suitably-sized array, copies pointers to all the hashtable
    194    elements into it, then returns both the array and the size of it.  The
    195    array must be freed with VG_(free).
    196 */
    197 VgHashNode** VG_(HT_to_array) ( VgHashTable table, /*OUT*/ UInt* n_elems )
    198 {
    199    UInt       i, j;
    200    VgHashNode** arr;
    201    VgHashNode*  node;
    202 
    203    *n_elems = table->n_elements;
    204    if (*n_elems == 0)
    205       return NULL;
    206 
    207    arr = VG_(malloc)( "hashtable.Hta.1", *n_elems * sizeof(VgHashNode*) );
    208 
    209    j = 0;
    210    for (i = 0; i < table->n_chains; i++) {
    211       for (node = table->chains[i]; node != NULL; node = node->next) {
    212          arr[j++] = node;
    213       }
    214    }
    215    vg_assert(j == *n_elems);
    216 
    217    return arr;
    218 }
    219 
    220 void VG_(HT_ResetIter)(VgHashTable table)
    221 {
    222    vg_assert(table);
    223    table->iterNode  = NULL;
    224    table->iterChain = 0;
    225    table->iterOK    = True;
    226 }
    227 
    228 void* VG_(HT_Next)(VgHashTable table)
    229 {
    230    Int i;
    231    vg_assert(table);
    232    /* See long comment on HT_Next prototype in pub_tool_hashtable.h.
    233       In short if this fails, it means the caller tried to modify the
    234       table whilst iterating over it, which is a bug. */
    235    vg_assert(table->iterOK);
    236 
    237    if (table->iterNode && table->iterNode->next) {
    238       table->iterNode = table->iterNode->next;
    239       return table->iterNode;
    240    }
    241 
    242    for (i = table->iterChain; i < table->n_chains; i++) {
    243       if (table->chains[i]) {
    244          table->iterNode  = table->chains[i];
    245          table->iterChain = i + 1;  // Next chain to be traversed
    246          return table->iterNode;
    247       }
    248    }
    249    return NULL;
    250 }
    251 
    252 void VG_(HT_destruct)(VgHashTable table)
    253 {
    254    UInt       i;
    255    VgHashNode *node, *node_next;
    256 
    257    for (i = 0; i < table->n_chains; i++) {
    258       for (node = table->chains[i]; node != NULL; node = node_next) {
    259          node_next = node->next;
    260          VG_(free)(node);
    261       }
    262    }
    263    VG_(free)(table->chains);
    264    VG_(free)(table);
    265 }
    266 
    267 /*--------------------------------------------------------------------*/
    268 /*--- end                                                          ---*/
    269 /*--------------------------------------------------------------------*/
    270