2 * This file is part of the GROMACS molecular simulation package.
4 * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
5 * Copyright (c) 2001-2012, The GROMACS development team,
6 * check out http://www.gromacs.org for more information.
7 * Copyright (c) 2012, by the GROMACS development team, led by
8 * David van der Spoel, Berk Hess, Erik Lindahl, and including many
9 * others, as listed in the AUTHORS file in the top-level source
10 * directory and at http://www.gromacs.org.
12 * GROMACS is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public License
14 * as published by the Free Software Foundation; either version 2.1
15 * of the License, or (at your option) any later version.
17 * GROMACS is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * Lesser General Public License for more details.
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with GROMACS; if not, see
24 * http://www.gnu.org/licenses, or write to the Free Software Foundation,
25 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 * If you want to redistribute modifications to GROMACS, please
28 * consider that scientific software is very special. Version
29 * control is crucial - bugs must be traceable. We will be happy to
30 * consider code for inclusion in the official distribution, but
31 * derived work must not be called official GROMACS. Details are found
32 * in the README & COPYING files - if they are missing, get the
33 * official version at http://www.gromacs.org.
35 * To help us fund GROMACS development, we humbly ask that you cite
36 * the research papers on the package. Check out http://www.gromacs.org.
48 /* This include file implements the simplest hash table possible.
49 * It is limited to integer keys and integer values.
50 * The purpose is highest efficiency and lowest memory usage possible.
52 * The type definition is placed in types/commrec.h, as it is used there:
53 * typedef struct gmx_hash *gmx_hash_t
62 typedef struct gmx_hash
{
69 int start_space_search
;
72 /* Clear all the entries in the hash table */
73 static void gmx_hash_clear(gmx_hash_t hash
)
77 for(i
=0; i
<hash
->nalloc
; i
++)
79 hash
->hash
[i
].key
= -1;
80 hash
->hash
[i
].next
= -1;
82 hash
->start_space_search
= hash
->mod
;
87 static void gmx_hash_realloc(gmx_hash_t hash
,int nkey_used_estimate
)
89 /* Memory requirements:
90 * nkey_used_est*(2+1-2(1-e^-1/2))*3 ints
91 * where nkey_used_est is the local number of keys used.
93 * Make the direct list twice as long as the number of local keys.
94 * The fraction of entries in the list with:
96 * >=1 size lists: 1 - e^-f
97 * where f is: the #keys / mod
98 * The fraction of keys not in the direct list is: 1-1/f(1-e^-f).
99 * The optimal table size is roughly double the number of keys.
101 /* Make the hash table a power of 2 and at least double the number of keys */
103 while (2*nkey_used_estimate
> hash
->mod
)
107 hash
->mask
= hash
->mod
- 1;
108 hash
->nalloc
= over_alloc_dd(hash
->mod
);
109 srenew(hash
->hash
,hash
->nalloc
);
113 fprintf(debug
,"Hash table mod %d nalloc %d\n",hash
->mod
,hash
->nalloc
);
117 /* Clear all the entries in the hash table.
118 * With the current number of keys check if the table size is still good,
119 * if not optimize it with the currenr number of keys.
121 static void gmx_hash_clear_and_optimize(gmx_hash_t hash
)
123 /* Resize the hash table when the occupation is < 1/4 or > 2/3 */
124 if (hash
->nkey
> 0 &&
125 (4*hash
->nkey
< hash
->mod
|| 3*hash
->nkey
> 2*hash
->mod
))
129 fprintf(debug
,"Hash table size %d #key %d: resizing\n",
130 hash
->mod
,hash
->nkey
);
132 gmx_hash_realloc(hash
,hash
->nkey
);
135 gmx_hash_clear(hash
);
138 static gmx_hash_t
gmx_hash_init(int nkey_used_estimate
)
145 gmx_hash_realloc(hash
,nkey_used_estimate
);
147 gmx_hash_clear(hash
);
152 /* Set the hash entry for global atom a_gl to local atom a_loc and cell. */
153 static void gmx_hash_set(gmx_hash_t hash
,int key
,int value
)
157 ind
= key
& hash
->mask
;
159 if (hash
->hash
[ind
].key
>= 0)
161 /* Search the last entry in the linked list for this index */
163 while(hash
->hash
[ind_prev
].next
>= 0)
165 ind_prev
= hash
->hash
[ind_prev
].next
;
167 /* Search for space in the array */
168 ind
= hash
->start_space_search
;
169 while (ind
< hash
->nalloc
&& hash
->hash
[ind
].key
>= 0)
173 /* If we are at the end of the list we need to increase the size */
174 if (ind
== hash
->nalloc
)
176 hash
->nalloc
= over_alloc_dd(ind
+1);
177 srenew(hash
->hash
,hash
->nalloc
);
178 for(i
=ind
; i
<hash
->nalloc
; i
++)
180 hash
->hash
[i
].key
= -1;
181 hash
->hash
[i
].next
= -1;
184 hash
->hash
[ind_prev
].next
= ind
;
186 hash
->start_space_search
= ind
+ 1;
188 hash
->hash
[ind
].key
= key
;
189 hash
->hash
[ind
].val
= value
;
194 /* Delete the hash entry for key */
195 static void gmx_hash_del(gmx_hash_t hash
,int key
)
200 ind
= key
& hash
->mask
;
203 if (hash
->hash
[ind
].key
== key
)
207 hash
->hash
[ind_prev
].next
= hash
->hash
[ind
].next
;
209 /* This index is a linked entry, so we free an entry.
210 * Check if we are creating the first empty space.
212 if (ind
< hash
->start_space_search
)
214 hash
->start_space_search
= ind
;
217 hash
->hash
[ind
].key
= -1;
218 hash
->hash
[ind
].val
= -1;
219 hash
->hash
[ind
].next
= -1;
226 ind
= hash
->hash
[ind
].next
;
233 /* Change the value for present hash entry for key */
234 static void gmx_hash_change_value(gmx_hash_t hash
,int key
,int value
)
238 ind
= key
& hash
->mask
;
241 if (hash
->hash
[ind
].key
== key
)
243 hash
->hash
[ind
].val
= value
;
247 ind
= hash
->hash
[ind
].next
;
254 /* Change the hash value if already set, otherwise set the hash value */
255 static void gmx_hash_change_or_set(gmx_hash_t hash
,int key
,int value
)
259 ind
= key
& hash
->mask
;
262 if (hash
->hash
[ind
].key
== key
)
264 hash
->hash
[ind
].val
= value
;
268 ind
= hash
->hash
[ind
].next
;
272 gmx_hash_set(hash
,key
,value
);
277 /* Returns if the key is present, if the key is present *value is set */
278 static gmx_bool
gmx_hash_get(const gmx_hash_t hash
,int key
,int *value
)
282 ind
= key
& hash
->mask
;
285 if (hash
->hash
[ind
].key
== key
)
287 *value
= hash
->hash
[ind
].val
;
291 ind
= hash
->hash
[ind
].next
;
298 /* Returns the value or -1 if the key is not present */
299 static int gmx_hash_get_minone(const gmx_hash_t hash
,int key
)
303 ind
= key
& hash
->mask
;
306 if (hash
->hash
[ind
].key
== key
)
308 return hash
->hash
[ind
].val
;
310 ind
= hash
->hash
[ind
].next
;
321 #endif /* _gmx_hash_h */