include/gmx_hash.h

   1 /* -*- mode: c; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; c-file-style: "stroustrup"; -*-
   2  *
   3  *
   4  *                This source code is part of
   5  *
   6  *                 G   R   O   M   A   C   S
   7  *
   8  *          GROningen MAchine for Chemical Simulations
   9  *
  10  * Written by David van der Spoel, Erik Lindahl, Berk Hess, and others.
  11  * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
  12  * Copyright (c) 2001-2012, The GROMACS development team,
  13  * check out http://www.gromacs.org for more information.
  14  *
  15  * This program is free software; you can redistribute it and/or
  16  * modify it under the terms of the GNU General Public License
  17  * as published by the Free Software Foundation; either version 2
  18  * of the License, or (at your option) any later version.
  19  *
  20  * If you want to redistribute modifications, please consider that
  21  * scientific software is very special. Version control is crucial -
  22  * bugs must be traceable. We will be happy to consider code for
  23  * inclusion in the official distribution, but derived work must not
  24  * be called official GROMACS. Details are found in the README & COPYING
  25  * files - if they are missing, get the official version at www.gromacs.org.
  26  *
  27  * To help us fund GROMACS development, we humbly ask that you cite
  28  * the papers on the package - you can find them in the top README file.
  29  *
  30  * For more info, check our website at http://www.gromacs.org
  31  *
  32  * And Hey:
  33  * Gromacs Runs On Most of All Computer Systems
  34  */
  35 #ifndef _gmx_hash_h
  36 #define _gmx_hash_h
  37
  38 #include "typedefs.h"
  39 #include "smalloc.h"
  40
  41 #ifdef __cplusplus
  42 extern "C" {
  43 #endif
  44
  45 /* This include file implements the simplest hash table possible.
  46  * It is limited to integer keys and integer values.
  47  * The purpose is highest efficiency and lowest memory usage possible.
  48  *
  49  * The type definition is placed in types/commrec.h, as it is used there:
  50  * typedef struct gmx_hash *gmx_hash_t
  51  */
  52
  53 typedef struct {
  54     int  key;
  55     int  val;
  56     int  next;
  57 } gmx_hash_e_t;
  58
  59 typedef struct gmx_hash {
  60     int          mod;
  61     int          mask;
  62     int          nalloc;
  63     int          *direct;
  64     gmx_hash_e_t *hash;
  65     int          nkey;
  66     int          start_space_search;
  67 } t_gmx_hash;
  68
  69 /* Clear all the entries in the hash table */
  70 static void gmx_hash_clear(gmx_hash_t hash)
  71 {
  72     int i;
  73
  74     for(i=0; i<hash->nalloc; i++)
  75     {
  76         hash->hash[i].key  = -1;
  77         hash->hash[i].next = -1;
  78     }
  79     hash->start_space_search = hash->mod;
  80
  81     hash->nkey = 0;
  82 }
  83
  84 static void gmx_hash_realloc(gmx_hash_t hash,int nkey_used_estimate)
  85 {
  86     /* Memory requirements:
  87      * nkey_used_est*(2+1-2(1-e^-1/2))*3 ints
  88      * where nkey_used_est is the local number of keys used.
  89      *
  90      * Make the direct list twice as long as the number of local keys.
  91      * The fraction of entries in the list with:
  92      * 0   size lists: e^-f
  93      * >=1 size lists: 1 - e^-f
  94      * where f is: the #keys / mod
  95      * The fraction of keys not in the direct list is: 1-1/f(1-e^-f).
  96      * The optimal table size is roughly double the number of keys.
  97      */
  98     /* Make the hash table a power of 2 and at least double the number of keys */
  99     hash->mod = 4;
 100     while (2*nkey_used_estimate > hash->mod)
 101     {
 102         hash->mod *= 2;
 103     }
 104     hash->mask = hash->mod - 1;
 105     hash->nalloc = over_alloc_dd(hash->mod);
 106     srenew(hash->hash,hash->nalloc);
 107
 108     if (debug != NULL)
 109     {
 110         fprintf(debug,"Hash table mod %d nalloc %d\n",hash->mod,hash->nalloc);
 111     }
 112 }
 113
 114 /* Clear all the entries in the hash table.
 115  * With the current number of keys check if the table size is still good,
 116  * if not optimize it with the currenr number of keys.
 117  */
 118 static void gmx_hash_clear_and_optimize(gmx_hash_t hash)
 119 {
 120     /* Resize the hash table when the occupation is < 1/4 or > 2/3 */
 121     if (hash->nkey > 0 &&
 122         (4*hash->nkey < hash->mod || 3*hash->nkey > 2*hash->mod))
 123     {
 124         if (debug != NULL)
 125         {
 126             fprintf(debug,"Hash table size %d #key %d: resizing\n",
 127                     hash->mod,hash->nkey);
 128         }
 129         gmx_hash_realloc(hash,hash->nkey);
 130     }
 131
 132     gmx_hash_clear(hash);
 133 }
 134
 135 static gmx_hash_t gmx_hash_init(int nkey_used_estimate)
 136 {
 137     gmx_hash_t hash;
 138
 139     snew(hash,1);
 140     hash->hash = NULL;
 141
 142     gmx_hash_realloc(hash,nkey_used_estimate);
 143
 144     gmx_hash_clear(hash);
 145
 146     return hash;
 147 }
 148
 149 /* Set the hash entry for global atom a_gl to local atom a_loc and cell. */
 150 static void gmx_hash_set(gmx_hash_t hash,int key,int value)
 151 {
 152     int ind,ind_prev,i;
 153
 154     ind = key & hash->mask;
 155
 156     if (hash->hash[ind].key >= 0)
 157     {
 158         /* Search the last entry in the linked list for this index */
 159         ind_prev = ind;
 160         while(hash->hash[ind_prev].next >= 0)
 161         {
 162             ind_prev = hash->hash[ind_prev].next;
 163         }
 164         /* Search for space in the array */
 165         ind = hash->start_space_search;
 166         while (ind < hash->nalloc && hash->hash[ind].key >= 0)
 167         {
 168             ind++;
 169         }
 170         /* If we are at the end of the list we need to increase the size */
 171         if (ind == hash->nalloc)
 172         {
 173             hash->nalloc = over_alloc_dd(ind+1);
 174             srenew(hash->hash,hash->nalloc);
 175             for(i=ind; i<hash->nalloc; i++)
 176             {
 177                 hash->hash[i].key  = -1;
 178                 hash->hash[i].next = -1;
 179             }
 180         }
 181         hash->hash[ind_prev].next = ind;
 182
 183         hash->start_space_search = ind + 1;
 184     }
 185     hash->hash[ind].key = key;
 186     hash->hash[ind].val = value;
 187
 188     hash->nkey++;
 189 }
 190
 191 /* Delete the hash entry for key */
 192 static void gmx_hash_del(gmx_hash_t hash,int key)
 193 {
 194     int ind,ind_prev;
 195
 196     ind_prev = -1;
 197     ind = key & hash->mask;
 198     do
 199     {
 200         if (hash->hash[ind].key == key)
 201         {
 202             if (ind_prev >= 0)
 203             {
 204                 hash->hash[ind_prev].next = hash->hash[ind].next;
 205
 206                 /* This index is a linked entry, so we free an entry.
 207                  * Check if we are creating the first empty space.
 208                  */
 209                 if (ind < hash->start_space_search)
 210                 {
 211                     hash->start_space_search = ind;
 212                 }
 213             }
 214             hash->hash[ind].key  = -1;
 215             hash->hash[ind].val  = -1;
 216             hash->hash[ind].next = -1;
 217
 218             hash->nkey--;
 219
 220             return;
 221         }
 222         ind_prev = ind;
 223         ind = hash->hash[ind].next;
 224     }
 225     while (ind >= 0);
 226
 227     return;
 228 }
 229
 230 /* Change the value for present hash entry for key */
 231 static void gmx_hash_change_value(gmx_hash_t hash,int key,int value)
 232 {
 233     int ind;
 234
 235     ind = key & hash->mask;
 236     do
 237     {
 238         if (hash->hash[ind].key == key)
 239         {
 240             hash->hash[ind].val = value;
 241
 242             return;
 243         }
 244         ind = hash->hash[ind].next;
 245     }
 246     while (ind >= 0);
 247
 248     return;
 249 }
 250
 251 /* Change the hash value if already set, otherwise set the hash value */
 252 static void gmx_hash_change_or_set(gmx_hash_t hash,int key,int value)
 253 {
 254     int ind;
 255
 256     ind = key & hash->mask;
 257     do
 258     {
 259         if (hash->hash[ind].key == key)
 260         {
 261             hash->hash[ind].val = value;
 262
 263             return;
 264         }
 265         ind = hash->hash[ind].next;
 266     }
 267     while (ind >= 0);
 268
 269     gmx_hash_set(hash,key,value);
 270
 271     return;
 272 }
 273
 274 /* Returns if the key is present, if the key is present *value is set */
 275 static gmx_bool gmx_hash_get(const gmx_hash_t hash,int key,int *value)
 276 {
 277     int ind;
 278
 279     ind = key & hash->mask;
 280     do
 281     {
 282         if (hash->hash[ind].key == key)
 283         {
 284             *value = hash->hash[ind].val;
 285
 286             return TRUE;
 287         }
 288         ind = hash->hash[ind].next;
 289     }
 290     while (ind >= 0);
 291
 292     return FALSE;
 293 }
 294
 295 /* Returns the value or -1 if the key is not present */
 296 static int gmx_hash_get_minone(const gmx_hash_t hash,int key)
 297 {
 298     int ind;
 299
 300     ind = key & hash->mask;
 301     do
 302     {
 303         if (hash->hash[ind].key == key)
 304         {
 305             return hash->hash[ind].val;
 306         }
 307         ind = hash->hash[ind].next;
 308     }
 309     while (ind >= 0);
 310
 311     return -1;
 312 }
 313
 314 #ifdef __cplusplus
 315 }
 316 #endif
 317
 318 #endif /* _gmx_hash_h */