import: Only read last time from sql if --incremental lacks timestamp
[nagios-reports-module.git] / hash.c
blob5fc2c6eb3db67dc2f321c796c793c78263b0b6ce
1 #include <stdlib.h>
2 #include <string.h>
3 #include "hash.h"
5 #define hash_func(k) sdbm((unsigned char *)k)
6 #define hash_func2(k1, k2) (hash_func(k1) ^ hash_func(k2))
8 typedef struct hash_bucket {
9 const char *key;
10 const char *key2;
11 void *data;
12 struct hash_bucket *next;
13 } hash_bucket;
15 struct hash_table {
16 hash_bucket **buckets;
17 unsigned int num_buckets;
18 unsigned int added, removed;
19 unsigned int entries;
20 unsigned int max_entries;
23 /* struct data access functions */
24 unsigned int hash_entries(hash_table *table)
26 return table ? table->entries : 0;
29 unsigned int hash_entries_max(hash_table *table)
31 return table ? table->max_entries : 0;
34 unsigned int hash_entries_added(hash_table *table)
36 return table ? table->added : 0;
39 unsigned int hash_entries_removed(hash_table *table)
41 return table ? table->removed : 0;
44 unsigned int hash_table_size(hash_table *table)
46 return table ? table->num_buckets : 0;
49 void hash_debug_print_table_data(hash_table *table, const char *name, int force)
51 int delta = hash_check_table(table);
52 unsigned int count;
53 if (!delta && !force)
54 return;
56 count = hash_count_entries(table);
57 printf("debug data for hash table '%s'\n", name);
58 printf(" entries: %u; counted: %u; delta: %d\n",
59 table->entries, count, delta);
60 printf(" added: %u; removed: %u; delta: %d\n",
61 table->added, table->removed, table->added - table->removed);
65 * polynomial conversion ignoring overflows
67 * Ozan Yigit's original sdbm algorithm, but without Duff's device
68 * so we can use it without knowing the length of the string
70 static inline unsigned int sdbm(const unsigned register char *k)
72 register unsigned int h = 0;
74 while (*k)
75 h = *k++ + 65599 * h;
77 return h;
80 static inline int hash_add_bucket(hash_table *table, const char *k1, const char *k2, void *data, unsigned int h)
82 hash_bucket *bkt;
84 if (!(bkt = malloc(sizeof(*bkt))))
85 return -1;
87 h = h % table->num_buckets;
89 table->added++;
90 bkt->data = data;
91 bkt->key = k1;
92 bkt->key2 = k2;
93 bkt->next = table->buckets[h];
94 table->buckets[h] = bkt;
96 if (++table->entries > table->max_entries)
97 table->max_entries = table->entries;
99 return 0;
102 int hash_add2(hash_table *table, const char *k1, const char *k2, void *data)
104 return hash_add_bucket(table, k1, k2, data, hash_func2(k1, k2));
107 int hash_add(hash_table *table, const char *key, void *data)
109 return hash_add_bucket(table, key, NULL, data, hash_func(key));
112 static hash_bucket *hash_get_bucket(hash_table *table, const char *key)
114 hash_bucket *bkt;
116 if (!table)
117 return NULL;
119 bkt = table->buckets[hash_func(key) % table->num_buckets];
120 for (; bkt; bkt = bkt->next) {
121 if (!strcmp(key, bkt->key))
122 return bkt;
125 return NULL;
128 static hash_bucket *hash_get_bucket2(hash_table *table, const char *k1, const char *k2)
130 hash_bucket *bkt;
132 if (!table)
133 return NULL;
135 bkt = table->buckets[hash_func2(k1, k2) % table->num_buckets];
136 for (; bkt; bkt = bkt->next) {
137 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2))
138 return bkt;
141 return NULL;
144 void *hash_find(hash_table *table, const char *key)
146 hash_bucket *bkt;
148 bkt = hash_get_bucket(table, key);
150 return bkt ? bkt->data : NULL;
153 void *hash_find2(hash_table *table, const char *k1, const char *k2)
155 hash_bucket *bkt;
157 bkt = hash_get_bucket2(table, k1, k2);
159 return bkt ? bkt->data : NULL;
162 hash_table *hash_init(unsigned int buckets)
164 hash_table *table = calloc(sizeof(hash_table), 1);
166 if (table) {
167 table->buckets = calloc(buckets, sizeof(hash_bucket *));
168 if (table->buckets) {
169 table->num_buckets = buckets;
170 return table;
173 free(table);
176 return NULL;
179 void *hash_update(hash_table *table, const char *key, void *data)
181 hash_bucket *bkt;
182 void *current_data;
184 bkt = hash_get_bucket(table, key);
185 if (!bkt) {
186 hash_add(table, key, data);
187 return NULL;
190 current_data = bkt->data;
191 bkt->data = data;
192 return current_data;
195 void *hash_update2(hash_table *table, const char *key, const char *key2, void *data)
197 hash_bucket *bkt;
199 bkt = hash_get_bucket2(table, key, key2);
200 if (!bkt) {
201 hash_add2(table, key, key2, data);
202 return NULL;
205 bkt->data = data;
206 return NULL;
209 static inline void *hash_destroy_bucket(hash_bucket *bkt)
211 void *data;
213 data = bkt->data;
214 free(bkt);
215 return data;
218 void *hash_remove(hash_table *table, const char *key)
220 unsigned int h;
221 hash_bucket *bkt, *prev;
223 h = hash_func(key) % table->num_buckets;
225 if (!(bkt = table->buckets[h]))
226 return NULL;
228 if (!strcmp(key, bkt->key)) {
229 table->buckets[h] = bkt->next;
230 table->entries--;
231 table->removed++;
232 return hash_destroy_bucket(bkt);
235 prev = bkt;
236 for (bkt = bkt->next; bkt; bkt = bkt->next) {
237 if (!strcmp(key, bkt->key)) {
238 prev->next = bkt->next;
239 table->entries--;
240 table->removed++;
241 return hash_destroy_bucket(bkt);
245 return NULL;
248 void *hash_remove2(hash_table *table, const char *k1, const char *k2)
250 unsigned int h;
251 hash_bucket *bkt, *prev;
253 h = hash_func2(k1, k2) % table->num_buckets;
255 if (!(bkt = table->buckets[h]))
256 return NULL;
258 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2)) {
259 table->buckets[h] = bkt->next;
260 table->entries--;
261 table->removed++;
262 return hash_destroy_bucket(bkt);
265 prev = bkt;
266 for (bkt = bkt->next; bkt; bkt = bkt->next) {
267 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2)) {
268 prev->next = bkt->next;
269 table->entries--;
270 table->removed++;
271 return hash_destroy_bucket(bkt);
275 return NULL;
278 unsigned int hash_count_entries(hash_table *table)
280 int i;
281 unsigned int count = 0;
283 for (i = 0; i < table->num_buckets; i++) {
284 hash_bucket *bkt;
285 for (bkt = table->buckets[i]; bkt; bkt = bkt->next)
286 count++;
289 return count;
292 int hash_check_table(hash_table *table)
294 return table ? table->entries - hash_count_entries(table) : 0;
297 void hash_walk_data(hash_table *table, int (*walker)(void *))
299 hash_bucket *bkt, *prev;
300 int i;
302 if (!table->entries)
303 return;
305 for (i = 0; i < table->num_buckets; i++) {
306 int depth = 0;
308 prev = table->buckets[i];
309 hash_bucket *next;
310 for (bkt = table->buckets[i]; bkt; bkt = next) {
311 next = bkt->next;
313 if (walker(bkt->data) != HASH_WALK_REMOVE) {
314 /* only update prev if we don't remove current */
315 prev = bkt;
316 depth++;
317 continue;
319 table->removed++;
320 table->entries--;
321 hash_destroy_bucket(bkt);
322 prev->next = next;
323 if (!depth) {
324 table->buckets[i] = next;
330 /* inserts a guaranteed unique entry to the hash-table */
331 int hash_add_unique(hash_table *table, const char *key, void *data)
333 unsigned int h;
334 hash_bucket *bkt;
336 h = hash_func(key) % table->num_buckets;
337 for (bkt = table->buckets[h]; bkt; bkt = bkt->next)
338 if (!strcmp(bkt->key, key))
339 return -1;
341 /* it's a unique key */
342 return hash_add_bucket(table, key, NULL, data, h);
345 int hash_add_unique2(hash_table *table, const char *k1, const char *k2, void *data)
347 unsigned int h;
348 hash_bucket *bkt;
350 h = hash_func2(k1, k2) % table->num_buckets;
351 for (bkt = table->buckets[h]; bkt; bkt = bkt->next)
352 if (!strcmp(bkt->key, k1) && !strcmp(bkt->key2, k2))
353 return -1;
355 return hash_add_bucket(table, k1, k2, data, h);