src/gromacs/legacyheaders/gmx_hash.h

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