Releasing 1.1pre17.
[tinc] / src / hash.c
1 /*
2     hash.c -- hash table management
3     Copyright (C) 2012-2013 Guus Sliepen <guus@tinc-vpn.org>
4
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.
9
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.
14
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.
18 */
19
20 #include "system.h"
21
22 #include "hash.h"
23 #include "xalloc.h"
24
25 /* Generic hash function */
26
27 static uint32_t hash_function(const void *p, size_t len) {
28         const uint8_t *q = p;
29         uint32_t hash = 0;
30
31         while(true) {
32                 for(int i = len > 4 ? 4 : len; --i;) {
33                         hash += (uint32_t)q[len - i] << (8 * i);
34                 }
35
36                 hash *= 0x9e370001UL; // Golden ratio prime.
37
38                 if(len <= 4) {
39                         break;
40                 }
41
42                 len -= 4;
43         }
44
45         return hash;
46 }
47
48 /* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */
49
50 static uint32_t modulo(uint32_t hash, size_t n) {
51         if(n == 0x100) {
52                 return (hash >> 24) ^ ((hash >> 16) & 0xff) ^ ((hash >> 8) & 0xff) ^ (hash & 0xff);
53         } else if(n == 0x10000) {
54                 return (hash >> 16) ^ (hash & 0xffff);
55         } else {
56                 return hash % n;
57         }
58 }
59
60 /* (De)allocation */
61
62 hash_t *hash_alloc(size_t n, size_t size) {
63         hash_t *hash = xzalloc(sizeof(*hash));
64         hash->n = n;
65         hash->size = size;
66         hash->keys = xzalloc(hash->n * hash->size);
67         hash->values = xzalloc(hash->n * sizeof(*hash->values));
68         return hash;
69 }
70
71 void hash_free(hash_t *hash) {
72         free(hash->keys);
73         free(hash->values);
74         free(hash);
75 }
76
77 /* Searching and inserting */
78
79 void hash_insert(hash_t *hash, const void *key, const void *value) {
80         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
81         memcpy(hash->keys + i * hash->size, key, hash->size);
82         hash->values[i] = value;
83 }
84
85 void *hash_search(const hash_t *hash, const void *key) {
86         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
87
88         if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) {
89                 return (void *)hash->values[i];
90         }
91
92         return NULL;
93 }
94
95 void *hash_search_or_insert(hash_t *hash, const void *key, const void *value) {
96         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
97
98         if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) {
99                 return (void *)hash->values[i];
100         }
101
102         memcpy(hash->keys + i * hash->size, key, hash->size);
103         hash->values[i] = value;
104         return NULL;
105 }
106
107 /* Deleting */
108
109 void hash_delete(hash_t *hash, const void *key) {
110         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
111         hash->values[i] = NULL;
112 }
113
114 /* Utility functions */
115
116 void hash_clear(hash_t *hash) {
117         memset(hash->values, 0, hash->n * sizeof(*hash->values));
118 }
119
120 void hash_resize(hash_t *hash, size_t n) {
121         hash->keys = xrealloc(hash->keys, n * hash->size);
122         hash->values = xrealloc(hash->values, n * sizeof(*hash->values));
123
124         if(n > hash->n) {
125                 memset(hash->keys + hash->n * hash->size, 0, (n - hash->n) * hash->size);
126                 memset(hash->values + hash->n, 0, (n - hash->n) * sizeof(*hash->values));
127         }
128 }