2 hash.c -- hash table management
3 Copyright (C) 2012-2013 Guus Sliepen <guus@tinc-vpn.org>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25 /* Generic hash function */
27 static uint32_t hash_function(const void *p
, size_t len
) {
31 for(int i
= len
> 4 ? 4 : len
; --i
;)
32 hash
+= q
[len
- i
] << (8 * i
);
33 hash
*= 0x9e370001UL
; // Golden ratio prime.
41 /* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */
43 static uint32_t modulo(uint32_t hash
, size_t n
) {
45 return (hash
>> 24) ^ ((hash
>> 16) & 0xff) ^ ((hash
>> 8) & 0xff) ^ (hash
& 0xff);
47 return (hash
>> 16) ^ (hash
& 0xffff);
54 hash_t
*hash_alloc(size_t n
, size_t size
) {
55 hash_t
*hash
= xzalloc(sizeof *hash
);
58 hash
->keys
= xzalloc(hash
->n
* hash
->size
);
59 hash
->values
= xzalloc(hash
->n
* sizeof *hash
->values
);
63 void hash_free(hash_t
*hash
) {
69 /* Searching and inserting */
71 void hash_insert(hash_t
*hash
, const void *key
, const void *value
) {
72 uint32_t i
= modulo(hash_function(key
, hash
->size
), hash
->n
);
73 memcpy(hash
->keys
+ i
* hash
->size
, key
, hash
->size
);
74 hash
->values
[i
] = value
;
77 void *hash_search(const hash_t
*hash
, const void *key
) {
78 uint32_t i
= modulo(hash_function(key
, hash
->size
), hash
->n
);
79 if(hash
->values
[i
] && !memcmp(key
, hash
->keys
+ i
* hash
->size
, hash
->size
)) {
80 return (void *)hash
->values
[i
];
85 void *hash_search_or_insert(hash_t
*hash
, const void *key
, const void *value
) {
86 uint32_t i
= modulo(hash_function(key
, hash
->size
), hash
->n
);
87 if(hash
->values
[i
] && !memcmp(key
, hash
->keys
+ i
* hash
->size
, hash
->size
))
88 return (void *)hash
->values
[i
];
89 memcpy(hash
->keys
+ i
* hash
->size
, key
, hash
->size
);
90 hash
->values
[i
] = value
;
94 /* Utility functions */
96 void hash_clear(hash_t
*hash
) {
97 memset(hash
->values
, 0, hash
->n
* sizeof *hash
->values
);
100 void hash_resize(hash_t
*hash
, size_t n
) {
101 hash
->keys
= xrealloc(hash
->keys
, n
* hash
->size
);
102 hash
->values
= xrealloc(hash
->values
, n
* sizeof *hash
->values
);
104 memset(hash
->keys
+ hash
->n
* hash
->size
, 0, (n
- hash
->n
) * hash
->size
);
105 memset(hash
->values
+ hash
->n
, 0, (n
- hash
->n
) * sizeof *hash
->values
);