1 /* -*- mode: c; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; c-file-style: "stroustrup"; -*-
4 * This source code is part of
8 * GROningen MAchine for Chemical Simulations
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.
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.
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.
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.
30 * For more info, check our website at http://www.gromacs.org
33 * Gromacs Runs On Most of All Computer Systems
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.
49 * The type definition is placed in types/commrec.h, as it is used there:
50 * typedef struct gmx_hash *gmx_hash_t
59 typedef struct gmx_hash
{
66 int start_space_search
;
69 /* Clear all the entries in the hash table */
70 static void gmx_hash_clear(gmx_hash_t hash
)
74 for(i
=0; i
<hash
->nalloc
; i
++)
76 hash
->hash
[i
].key
= -1;
77 hash
->hash
[i
].next
= -1;
79 hash
->start_space_search
= hash
->mod
;
84 static void gmx_hash_realloc(gmx_hash_t hash
,int nkey_used_estimate
)
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.
90 * Make the direct list twice as long as the number of local keys.
91 * The fraction of entries in the list with:
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.
98 /* Make the hash table a power of 2 and at least double the number of keys */
100 while (2*nkey_used_estimate
> hash
->mod
)
104 hash
->mask
= hash
->mod
- 1;
105 hash
->nalloc
= over_alloc_dd(hash
->mod
);
106 srenew(hash
->hash
,hash
->nalloc
);
110 fprintf(debug
,"Hash table mod %d nalloc %d\n",hash
->mod
,hash
->nalloc
);
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.
118 static void gmx_hash_clear_and_optimize(gmx_hash_t hash
)
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
))
126 fprintf(debug
,"Hash table size %d #key %d: resizing\n",
127 hash
->mod
,hash
->nkey
);
129 gmx_hash_realloc(hash
,hash
->nkey
);
132 gmx_hash_clear(hash
);
135 static gmx_hash_t
gmx_hash_init(int nkey_used_estimate
)
142 gmx_hash_realloc(hash
,nkey_used_estimate
);
144 gmx_hash_clear(hash
);
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
)
154 ind
= key
& hash
->mask
;
156 if (hash
->hash
[ind
].key
>= 0)
158 /* Search the last entry in the linked list for this index */
160 while(hash
->hash
[ind_prev
].next
>= 0)
162 ind_prev
= hash
->hash
[ind_prev
].next
;
164 /* Search for space in the array */
165 ind
= hash
->start_space_search
;
166 while (ind
< hash
->nalloc
&& hash
->hash
[ind
].key
>= 0)
170 /* If we are at the end of the list we need to increase the size */
171 if (ind
== hash
->nalloc
)
173 hash
->nalloc
= over_alloc_dd(ind
+1);
174 srenew(hash
->hash
,hash
->nalloc
);
175 for(i
=ind
; i
<hash
->nalloc
; i
++)
177 hash
->hash
[i
].key
= -1;
178 hash
->hash
[i
].next
= -1;
181 hash
->hash
[ind_prev
].next
= ind
;
183 hash
->start_space_search
= ind
+ 1;
185 hash
->hash
[ind
].key
= key
;
186 hash
->hash
[ind
].val
= value
;
191 /* Delete the hash entry for key */
192 static void gmx_hash_del(gmx_hash_t hash
,int key
)
197 ind
= key
& hash
->mask
;
200 if (hash
->hash
[ind
].key
== key
)
204 hash
->hash
[ind_prev
].next
= hash
->hash
[ind
].next
;
206 /* This index is a linked entry, so we free an entry.
207 * Check if we are creating the first empty space.
209 if (ind
< hash
->start_space_search
)
211 hash
->start_space_search
= ind
;
214 hash
->hash
[ind
].key
= -1;
215 hash
->hash
[ind
].val
= -1;
216 hash
->hash
[ind
].next
= -1;
223 ind
= hash
->hash
[ind
].next
;
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
)
235 ind
= key
& hash
->mask
;
238 if (hash
->hash
[ind
].key
== key
)
240 hash
->hash
[ind
].val
= value
;
244 ind
= hash
->hash
[ind
].next
;
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
)
256 ind
= key
& hash
->mask
;
259 if (hash
->hash
[ind
].key
== key
)
261 hash
->hash
[ind
].val
= value
;
265 ind
= hash
->hash
[ind
].next
;
269 gmx_hash_set(hash
,key
,value
);
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
)
279 ind
= key
& hash
->mask
;
282 if (hash
->hash
[ind
].key
== key
)
284 *value
= hash
->hash
[ind
].val
;
288 ind
= hash
->hash
[ind
].next
;
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
)
300 ind
= key
& hash
->mask
;
303 if (hash
->hash
[ind
].key
== key
)
305 return hash
->hash
[ind
].val
;
307 ind
= hash
->hash
[ind
].next
;
318 #endif /* _gmx_hash_h */