src/gromacs/domdec/hash.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2012,2014,2015,2017, 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 /*! \internal \file
  36  * \brief
  37  * This file declares functions for a simple hash map used by domain
  38  * decomposition.
  39  *
  40  * It is limited to integer keys and integer values. The purpose is highest
  41  * efficiency and lowest memory usage possible.  Thus the code is in a header,
  42  * so it can be inlined where it is used.
  43  *
  44  * \author Berk Hess <hess@kth.se>
  45  * \ingroup module_domdec
  46  */
  47
  48 #ifndef GMX_DOMDEC_HASH_H
  49 #define GMX_DOMDEC_HASH_H
  50
  51 #include <stdio.h>
  52
  53 #include "gromacs/mdtypes/commrec.h"
  54 #include "gromacs/utility/fatalerror.h"
  55 #include "gromacs/utility/smalloc.h"
  56
  57 /*! \internal \brief Hashing key-generation helper struct */
  58 struct gmx_hash_e_t
  59 {
  60     public:
  61         //! The (unique) key for storing/looking up a value
  62         int  key;
  63         //! The value belonging to key
  64         int  val;
  65         //! Index for the next element in the array with indentical value key%mod, -1 if there is no next element
  66         int  next;
  67 };
  68
  69 /*! \internal \brief Hashing helper struct */
  70 struct gmx_hash_t
  71 {
  72     public:
  73         //! Keys are looked up by first checking array index key%mod in hash
  74         int           mod;
  75         //! mask=log2(mod), used to replace a % by the faster & operation
  76         int           mask;
  77         //! Allocated size of hash
  78         int           nalloc;
  79         //! The actual array containing the keys, values and next indices
  80         gmx_hash_e_t *hash;
  81         //! The number of keys stored
  82         int           nkey;
  83         //! Index in hash where we should start searching for space to store a new key/value
  84         int           start_space_search;
  85 };
  86
  87 //! Clear all the entries in the hash table.
  88 static void gmx_hash_clear(gmx_hash_t *hash)
  89 {
  90     int i;
  91
  92     for (i = 0; i < hash->nalloc; i++)
  93     {
  94         hash->hash[i].key  = -1;
  95         hash->hash[i].next = -1;
  96     }
  97     hash->start_space_search = hash->mod;
  98
  99     hash->nkey = 0;
 100 }
 101
 102 //! Reallocate hash table data structures.
 103 static void gmx_hash_realloc(gmx_hash_t *hash, int nkey_used_estimate)
 104 {
 105     /* Memory requirements:
 106      * nkey_used_est*(2+1-2(1-e^-1/2))*3 ints
 107      * where nkey_used_est is the local number of keys used.
 108      *
 109      * Make the direct list twice as long as the number of local keys.
 110      * The fraction of entries in the list with:
 111      * 0   size lists: e^-f
 112      * >=1 size lists: 1 - e^-f
 113      * where f is: the #keys / mod
 114      * The fraction of keys not in the direct list is: 1-1/f(1-e^-f).
 115      * The optimal table size is roughly double the number of keys.
 116      */
 117     /* Make the hash table a power of 2 and at least double the number of keys */
 118     hash->mod = 4;
 119     while (2*nkey_used_estimate > hash->mod)
 120     {
 121         hash->mod *= 2;
 122     }
 123     hash->mask   = hash->mod - 1;
 124     hash->nalloc = over_alloc_dd(hash->mod);
 125     srenew(hash->hash, hash->nalloc);
 126
 127     if (debug != nullptr)
 128     {
 129         fprintf(debug, "Hash table mod %d nalloc %d\n", hash->mod, hash->nalloc);
 130     }
 131 }
 132
 133 /*! \brief Clear all the entries in the hash table.
 134  *
 135  * With the current number of keys check if the table size is still
 136  * good, if not optimize it with the current number of keys.
 137  */
 138 static void gmx_hash_clear_and_optimize(gmx_hash_t *hash)
 139 {
 140     /* Resize the hash table when the occupation is < 1/4 or > 2/3 */
 141     if (hash->nkey > 0 &&
 142         (4*hash->nkey < hash->mod || 3*hash->nkey > 2*hash->mod))
 143     {
 144         if (debug != nullptr)
 145         {
 146             fprintf(debug, "Hash table size %d #key %d: resizing\n",
 147                     hash->mod, hash->nkey);
 148         }
 149         gmx_hash_realloc(hash, hash->nkey);
 150     }
 151
 152     gmx_hash_clear(hash);
 153 }
 154
 155 //! Initialize hash table.
 156 static gmx_hash_t *gmx_hash_init(int nkey_used_estimate)
 157 {
 158     gmx_hash_t *hash;
 159
 160     snew(hash, 1);
 161     hash->hash = nullptr;
 162
 163     gmx_hash_realloc(hash, nkey_used_estimate);
 164
 165     gmx_hash_clear(hash);
 166
 167     return hash;
 168 }
 169
 170 //! Set the hash entry for key to value.
 171 static void gmx_hash_set(gmx_hash_t *hash, int key, int value)
 172 {
 173     int ind, ind_prev, i;
 174
 175     ind = key & hash->mask;
 176
 177     if (hash->hash[ind].key >= 0)
 178     {
 179         /* Search the last entry in the linked list for this index */
 180         ind_prev = ind;
 181         while (hash->hash[ind_prev].next >= 0)
 182         {
 183             ind_prev = hash->hash[ind_prev].next;
 184         }
 185         /* Search for space in the array */
 186         ind = hash->start_space_search;
 187         while (ind < hash->nalloc && hash->hash[ind].key >= 0)
 188         {
 189             ind++;
 190         }
 191         /* If we are at the end of the list we need to increase the size */
 192         if (ind == hash->nalloc)
 193         {
 194             hash->nalloc = over_alloc_dd(ind+1);
 195             srenew(hash->hash, hash->nalloc);
 196             for (i = ind; i < hash->nalloc; i++)
 197             {
 198                 hash->hash[i].key  = -1;
 199                 hash->hash[i].next = -1;
 200             }
 201         }
 202         hash->hash[ind_prev].next = ind;
 203
 204         hash->start_space_search = ind + 1;
 205     }
 206     hash->hash[ind].key = key;
 207     hash->hash[ind].val = value;
 208
 209     hash->nkey++;
 210 }
 211
 212 //! Delete the hash entry for key.
 213 static void gmx_hash_del(gmx_hash_t *hash, int key)
 214 {
 215     int ind, ind_prev;
 216
 217     ind_prev = -1;
 218     ind      = key & hash->mask;
 219     do
 220     {
 221         if (hash->hash[ind].key == key)
 222         {
 223             if (ind_prev >= 0)
 224             {
 225                 hash->hash[ind_prev].next = hash->hash[ind].next;
 226
 227                 /* This index is a linked entry, so we free an entry.
 228                  * Check if we are creating the first empty space.
 229                  */
 230                 if (ind < hash->start_space_search)
 231                 {
 232                     hash->start_space_search = ind;
 233                 }
 234             }
 235             hash->hash[ind].key  = -1;
 236             hash->hash[ind].val  = -1;
 237             hash->hash[ind].next = -1;
 238
 239             hash->nkey--;
 240
 241             return;
 242         }
 243         ind_prev = ind;
 244         ind      = hash->hash[ind].next;
 245     }
 246     while (ind >= 0);
 247
 248     return;
 249 }
 250
 251 //! Change the value for present hash entry for key.
 252 static void gmx_hash_change_value(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     return;
 270 }
 271
 272 //! Change the hash value if already set, otherwise set the hash value.
 273 static void gmx_hash_change_or_set(gmx_hash_t *hash, int key, int value)
 274 {
 275     int ind;
 276
 277     ind = key & hash->mask;
 278     do
 279     {
 280         if (hash->hash[ind].key == key)
 281         {
 282             hash->hash[ind].val = value;
 283
 284             return;
 285         }
 286         ind = hash->hash[ind].next;
 287     }
 288     while (ind >= 0);
 289
 290     gmx_hash_set(hash, key, value);
 291
 292     return;
 293 }
 294
 295 //! Returns if the key is present, if the key is present *value is set.
 296 static gmx_bool gmx_hash_get(const gmx_hash_t *hash, int key, int *value)
 297 {
 298     int ind;
 299
 300     ind = key & hash->mask;
 301     do
 302     {
 303         if (hash->hash[ind].key == key)
 304         {
 305             *value = hash->hash[ind].val;
 306
 307             return TRUE;
 308         }
 309         ind = hash->hash[ind].next;
 310     }
 311     while (ind >= 0);
 312
 313     return FALSE;
 314 }
 315
 316 //! Returns the value or -1 if the key is not present.
 317 static int gmx_hash_get_minone(const gmx_hash_t *hash, int key)
 318 {
 319     int ind;
 320
 321     ind = key & hash->mask;
 322     do
 323     {
 324         if (hash->hash[ind].key == key)
 325         {
 326             return hash->hash[ind].val;
 327         }
 328         ind = hash->hash[ind].next;
 329     }
 330     while (ind >= 0);
 331
 332     return -1;
 333 }
 334
 335 #endif