1 /*
2  * Copyright 2008-2009 Katholieke Universiteit Leuven
3  *
4  * Use of this software is governed by the MIT license
5  *
6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8  */
9 
10 #ifndef ISL_HASH_H
11 #define ISL_HASH_H
12 
13 #include <stdlib.h>
14 #include <isl/stdint.h>
15 
16 #if defined(__cplusplus)
17 extern "C" {
18 #endif
19 
20 #define isl_hash_init()		(2166136261u)
21 #define isl_hash_byte(h,b)	do {					\
22 					h *= 16777619;			\
23 					h ^= b;				\
24 				} while(0)
25 #define isl_hash_hash(h,h2)						\
26 	do {								\
27 		isl_hash_byte(h, (h2) & 0xFF);				\
28 		isl_hash_byte(h, ((h2) >> 8) & 0xFF);			\
29 		isl_hash_byte(h, ((h2) >> 16) & 0xFF);			\
30 		isl_hash_byte(h, ((h2) >> 24) & 0xFF);			\
31 	} while(0)
32 #define isl_hash_bits(h,bits)						\
33 	((bits) == 32) ? (h) :						\
34 	((bits) >= 16) ?						\
35 	      ((h) >> (bits)) ^ ((h) & (((uint32_t)1 << (bits)) - 1)) :	\
36 	      (((h) >> (bits)) ^ (h)) & (((uint32_t)1 << (bits)) - 1)
37 
38 uint32_t isl_hash_string(uint32_t hash, const char *s);
39 uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len);
40 
41 #define isl_hash_builtin(h,l)	isl_hash_mem(h, &l, sizeof(l))
42 
43 struct isl_hash_table_entry
44 {
45 	uint32_t  hash;
46 	void     *data;
47 };
48 
49 struct isl_hash_table {
50 	int    bits;
51 	int    n;
52 	struct isl_hash_table_entry *entries;
53 };
54 
55 struct isl_ctx;
56 
57 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size);
58 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table);
59 
60 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
61 			int min_size);
62 void isl_hash_table_clear(struct isl_hash_table *table);
63 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
64 				struct isl_hash_table *table,
65 				uint32_t key_hash,
66 				int (*eq)(const void *entry, const void *val),
67 				const void *val, int reserve);
68 int isl_hash_table_foreach(struct isl_ctx *ctx,
69 			    struct isl_hash_table *table,
70 			    int (*fn)(void **entry, void *user), void *user);
71 void isl_hash_table_remove(struct isl_ctx *ctx,
72 				struct isl_hash_table *table,
73 				struct isl_hash_table_entry *entry);
74 
75 #if defined(__cplusplus)
76 }
77 #endif
78 
79 #endif
80