coregrind/m_hashtable.c

   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-2015 Nicholas Nethercote
  11       njn@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_libcbase.h"
  36 #include "pub_core_libcprint.h"
  37 #include "pub_core_mallocfree.h"
  38
  39 /*--------------------------------------------------------------------*/
  40 /*--- Declarations                                                 ---*/
  41 /*--------------------------------------------------------------------*/
  42
  43 #define CHAIN_NO(key,tbl) (((UWord)(key)) % tbl->n_chains)
  44
  45 struct _VgHashTable {
  46    UInt         n_chains;   // should be prime
  47    UInt         n_elements;
  48    VgHashNode*  iterNode;   // current iterator node
  49    UInt         iterChain;  // next chain to be traversed by the iterator
  50    VgHashNode** chains;     // expanding array of hash chains
  51    Bool         iterOK;     // table safe to iterate over?
  52    const HChar* name;       // name of table (for debugging only)
  53 };
  54
  55 #define N_HASH_PRIMES 20
  56
  57 static const SizeT primes[N_HASH_PRIMES] = {
  58          769UL,         1543UL,         3079UL,          6151UL,
  59        12289UL,        24593UL,        49157UL,         98317UL,
  60       196613UL,       393241UL,       786433UL,       1572869UL,
  61      3145739UL,      6291469UL,     12582917UL,      25165843UL,
  62     50331653UL,    100663319UL,    201326611UL,     402653189UL
  63 };
  64
  65 /*--------------------------------------------------------------------*/
  66 /*--- Functions                                                    ---*/
  67 /*--------------------------------------------------------------------*/
  68
  69 VgHashTable *VG_(HT_construct) ( const HChar* name )
  70 {
  71    /* Initialises to zero, ie. all entries NULL */
  72    SizeT       n_chains = primes[0];
  73    SizeT       sz       = n_chains * sizeof(VgHashNode*);
  74    VgHashTable *table   = VG_(calloc)("hashtable.Hc.1",
  75                                       1, sizeof(struct _VgHashTable));
  76    table->chains        = VG_(calloc)("hashtable.Hc.2", 1, sz);
  77    table->n_chains      = n_chains;
  78    table->n_elements    = 0;
  79    table->iterOK        = True;
  80    table->name          = name;
  81    vg_assert(name);
  82    return table;
  83 }
  84
  85 UInt VG_(HT_count_nodes) ( const VgHashTable *table )
  86 {
  87    return table->n_elements;
  88 }
  89
  90 static void resize ( VgHashTable *table )
  91 {
  92    Int          i;
  93    SizeT        sz;
  94    SizeT        old_chains = table->n_chains;
  95    SizeT        new_chains = old_chains + 1;
  96    VgHashNode** chains;
  97    VgHashNode * node;
  98
  99    /* If we've run out of primes, do nothing. */
 100    if (old_chains == primes[N_HASH_PRIMES-1])
 101       return;
 102
 103    vg_assert(old_chains >= primes[0]
 104              && old_chains < primes[N_HASH_PRIMES-1]);
 105
 106    for (i = 0; i < N_HASH_PRIMES; i++) {
 107       if (primes[i] > new_chains) {
 108          new_chains = primes[i];
 109          break;
 110       }
 111    }
 112
 113    vg_assert(new_chains > old_chains);
 114    vg_assert(new_chains > primes[0]
 115              && new_chains <= primes[N_HASH_PRIMES-1]);
 116
 117    VG_(debugLog)(
 118       1, "hashtable",
 119          "resizing table `%s' from %lu to %lu (total elems %lu)\n",
 120          table->name, (UWord)old_chains, (UWord)new_chains,
 121          (UWord)table->n_elements );
 122
 123    table->n_chains = new_chains;
 124    sz = new_chains * sizeof(VgHashNode*);
 125    chains = VG_(calloc)("hashtable.resize.1", 1, sz);
 126
 127    for (i = 0; i < old_chains; i++) {
 128       node = table->chains[i];
 129       while (node != NULL) {
 130          VgHashNode* next = node->next;
 131          UWord chain = CHAIN_NO(node->key, table);
 132          node->next = chains[chain];
 133          chains[chain] = node;
 134          node = next;
 135       }
 136    }
 137
 138    VG_(free)(table->chains);
 139    table->chains = chains;
 140 }
 141
 142 /* Puts a new, heap allocated VgHashNode, into the VgHashTable.  Prepends
 143    the node to the appropriate chain.  No duplicate key detection is done. */
 144 void VG_(HT_add_node) ( VgHashTable *table, void* vnode )
 145 {
 146    VgHashNode* node     = (VgHashNode*)vnode;
 147    UWord chain          = CHAIN_NO(node->key, table);
 148    node->next           = table->chains[chain];
 149    table->chains[chain] = node;
 150    table->n_elements++;
 151    if ( (1 * (ULong)table->n_elements) > (1 * (ULong)table->n_chains) ) {
 152       resize(table);
 153    }
 154
 155    /* Table has been modified; hence HT_Next should assert. */
 156    table->iterOK = False;
 157 }
 158
 159 /* Looks up a VgHashNode by key in the table.  Returns NULL if not found. */
 160 void* VG_(HT_lookup) ( const VgHashTable *table, UWord key )
 161 {
 162    VgHashNode* curr = table->chains[ CHAIN_NO(key, table) ];
 163
 164    while (curr) {
 165       if (key == curr->key) {
 166          return curr;
 167       }
 168       curr = curr->next;
 169    }
 170    return NULL;
 171 }
 172
 173 /* Looks up a VgHashNode by node in the table.  Returns NULL if not found.
 174    GEN!!! marks the lines that differs from VG_(HT_lookup). */
 175 void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node,
 176                            HT_Cmp_t cmp )
 177 {
 178    const VgHashNode* hnode = node; // GEN!!!
 179    VgHashNode* curr = table->chains[ CHAIN_NO(hnode->key, table) ]; // GEN!!!
 180
 181    while (curr) {
 182       if (hnode->key == curr->key && cmp (hnode, curr) == 0) { // GEN!!!
 183          return curr;
 184       }
 185       curr = curr->next;
 186    }
 187    return NULL;
 188 }
 189
 190 /* Removes a VgHashNode from the table.  Returns NULL if not found. */
 191 void* VG_(HT_remove) ( VgHashTable *table, UWord key )
 192 {
 193    UWord        chain         = CHAIN_NO(key, table);
 194    VgHashNode*  curr          =   table->chains[chain];
 195    VgHashNode** prev_next_ptr = &(table->chains[chain]);
 196
 197    /* Table has been modified; hence HT_Next should assert. */
 198    table->iterOK = False;
 199
 200    while (curr) {
 201       if (key == curr->key) {
 202          *prev_next_ptr = curr->next;
 203          table->n_elements--;
 204          return curr;
 205       }
 206       prev_next_ptr = &(curr->next);
 207       curr = curr->next;
 208    }
 209    return NULL;
 210 }
 211
 212 /* Removes a VgHashNode by node from the table.  Returns NULL if not found.
 213    GEN!!! marks the lines that differs from VG_(HT_remove). */
 214 void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node, HT_Cmp_t cmp  )
 215 {
 216    const VgHashNode* hnode    = node; // GEN!!!
 217    UWord        chain         = CHAIN_NO(hnode->key, table); // GEN!!!
 218    VgHashNode*  curr          =   table->chains[chain];
 219    VgHashNode** prev_next_ptr = &(table->chains[chain]);
 220
 221    /* Table has been modified; hence HT_Next should assert. */
 222    table->iterOK = False;
 223
 224    while (curr) {
 225       if (hnode->key == curr->key && cmp(hnode, curr) == 0) { // GEN!!!
 226          *prev_next_ptr = curr->next;
 227          table->n_elements--;
 228          return curr;
 229       }
 230       prev_next_ptr = &(curr->next);
 231       curr = curr->next;
 232    }
 233    return NULL;
 234 }
 235
 236 void VG_(HT_print_stats) ( const VgHashTable *table, HT_Cmp_t cmp )
 237 {
 238    #define MAXOCCUR 20
 239    UInt elt_occurences[MAXOCCUR+1];
 240    UInt key_occurences[MAXOCCUR+1];
 241    UInt cno_occurences[MAXOCCUR+1];
 242    /* Key occurence  : how many ht elements have the same key.
 243       elt_occurences : how many elements are inserted multiple time.
 244       cno_occurences : how many chains have that length.
 245       The last entry in these arrays collects all occurences >= MAXOCCUR. */
 246    #define INCOCCUR(occur,n) (n >= MAXOCCUR ? occur[MAXOCCUR]++ : occur[n]++)
 247    UInt i;
 248    UInt nkey, nelt, ncno;
 249    VgHashNode *cnode, *node;
 250
 251    VG_(memset)(key_occurences, 0, sizeof(key_occurences));
 252    VG_(memset)(elt_occurences, 0, sizeof(elt_occurences));
 253    VG_(memset)(cno_occurences, 0, sizeof(cno_occurences));
 254
 255    // Note that the below algorithm is quadractic in nr of elements in a chain
 256    // but if that happens, the hash table/function is really bad and that
 257    // should be fixed.
 258    for (i = 0; i < table->n_chains; i++) {
 259       ncno = 0;
 260       for (cnode = table->chains[i]; cnode != NULL; cnode = cnode->next) {
 261          ncno++;
 262
 263          nkey = 0;
 264          // Is the same cnode->key existing before cnode ?
 265          for (node = table->chains[i]; node != cnode; node = node->next) {
 266             if (node->key == cnode->key)
 267                nkey++;
 268          }
 269          // If cnode->key not in a previous node, count occurences of key.
 270          if (nkey == 0) {
 271             for (node = cnode; node != NULL; node = node->next) {
 272                if (node->key == cnode->key)
 273                   nkey++;
 274             }
 275             INCOCCUR(key_occurences, nkey);
 276          }
 277
 278          nelt = 0;
 279          // Is the same cnode element existing before cnode ?
 280          for (node = table->chains[i]; node != cnode; node = node->next) {
 281             if (node->key == cnode->key
 282                 && (cmp == NULL || cmp (node, cnode) == 0)) {
 283                nelt++;
 284             }
 285          }
 286          // If cnode element not in a previous node, count occurences of elt.
 287          if (nelt == 0) {
 288             for (node = cnode; node != NULL; node = node->next) {
 289                if (node->key == cnode->key
 290                    && (cmp == NULL || cmp (node, cnode) == 0)) {
 291                   nelt++;
 292                }
 293             }
 294             INCOCCUR(elt_occurences, nelt);
 295          }
 296       }
 297       INCOCCUR(cno_occurences, ncno);
 298    }
 299
 300    VG_(message)(Vg_DebugMsg,
 301                 "nr occurences of"
 302                 " chains of len N,"
 303                 " N-plicated keys,"
 304                 " N-plicated elts\n");
 305    nkey = nelt = ncno = 0;
 306    for (i = 0; i <= MAXOCCUR; i++) {
 307       if (elt_occurences[i] > 0
 308           || key_occurences[i] > 0
 309           || cno_occurences[i] > 0)
 310          VG_(message)(Vg_DebugMsg,
 311                       "%s=%2u : nr chain %6u, nr keys %6u, nr elts %6u\n",
 312                       i == MAXOCCUR ? ">" : "N", i,
 313                       cno_occurences[i], key_occurences[i], elt_occurences[i]);
 314       nkey += key_occurences[i];
 315       nelt += elt_occurences[i];
 316       ncno += cno_occurences[i];
 317    }
 318    VG_(message)(Vg_DebugMsg,
 319                 "total nr of unique   slots: %6u, keys %6u, elts %6u."
 320                 " Avg chain len %3.1f\n",
 321                 ncno, nkey, nelt,
 322                 (Double)nelt/(Double)(ncno == cno_occurences[0] ?
 323                                       1 : ncno - cno_occurences[0]));
 324 }
 325
 326
 327 /* Allocates a suitably-sized array, copies pointers to all the hashtable
 328    elements into it, then returns both the array and the size of it.  The
 329    array must be freed with VG_(free).
 330 */
 331 VgHashNode** VG_(HT_to_array) (const VgHashTable *table, /*OUT*/ UInt* n_elems)
 332 {
 333    UInt       i, j;
 334    VgHashNode** arr;
 335    VgHashNode*  node;
 336
 337    *n_elems = table->n_elements;
 338    if (*n_elems == 0)
 339       return NULL;
 340
 341    arr = VG_(malloc)( "hashtable.Hta.1", *n_elems * sizeof(VgHashNode*) );
 342
 343    j = 0;
 344    for (i = 0; i < table->n_chains; i++) {
 345       for (node = table->chains[i]; node != NULL; node = node->next) {
 346          arr[j++] = node;
 347       }
 348    }
 349    vg_assert(j == *n_elems);
 350
 351    return arr;
 352 }
 353
 354 void VG_(HT_ResetIter)(VgHashTable *table)
 355 {
 356    vg_assert(table);
 357    table->iterNode  = NULL;
 358    table->iterChain = 0;
 359    table->iterOK    = True;
 360 }
 361
 362 void* VG_(HT_Next)(VgHashTable *table)
 363 {
 364    Int i;
 365    vg_assert(table);
 366    /* See long comment on HT_Next prototype in pub_tool_hashtable.h.
 367       In short if this fails, it means the caller tried to modify the
 368       table whilst iterating over it, which is a bug. */
 369    vg_assert(table->iterOK);
 370
 371    if (table->iterNode && table->iterNode->next) {
 372       table->iterNode = table->iterNode->next;
 373       return table->iterNode;
 374    }
 375
 376    for (i = table->iterChain; i < table->n_chains; i++) {
 377       if (table->chains[i]) {
 378          table->iterNode  = table->chains[i];
 379          table->iterChain = i + 1;  // Next chain to be traversed
 380          return table->iterNode;
 381       }
 382    }
 383    return NULL;
 384 }
 385
 386 void VG_(HT_destruct)(VgHashTable *table, void(*freenode_fn)(void*))
 387 {
 388    UInt       i;
 389    VgHashNode *node, *node_next;
 390
 391    for (i = 0; i < table->n_chains; i++) {
 392       for (node = table->chains[i]; node != NULL; node = node_next) {
 393          node_next = node->next;
 394          freenode_fn(node);
 395       }
 396    }
 397    VG_(free)(table->chains);
 398    VG_(free)(table);
 399 }
 400
 401 /*--------------------------------------------------------------------*/
 402 /*--- end                                                          ---*/
 403 /*--------------------------------------------------------------------*/