polly/isl/hash.h

0001 /*
0002  * Copyright 2008-2009 Katholieke Universiteit Leuven
0003  *
0004  * Use of this software is governed by the MIT license
0005  *
0006  * Written by Sven Verdoolaege, K.U.Leuven, Departement
0007  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
0008  */
0009
0010 #ifndef ISL_HASH_H
0011 #define ISL_HASH_H
0012
0013 #include <stdlib.h>
0014 #include <isl/stdint.h>
0015 #include <isl/ctx.h>
0016
0017 #if defined(__cplusplus)
0018 extern "C" {
0019 #endif
0020
0021 #define isl_hash_init()     (2166136261u)
0022 #define isl_hash_byte(h,b)  do {                    \
0023                     h *= 16777619;          \
0024                     h ^= b;             \
0025                 } while(0)
0026 #define isl_hash_hash(h,h2)                     \
0027     do {                                \
0028         isl_hash_byte(h, (h2) & 0xFF);              \
0029         isl_hash_byte(h, ((h2) >> 8) & 0xFF);           \
0030         isl_hash_byte(h, ((h2) >> 16) & 0xFF);          \
0031         isl_hash_byte(h, ((h2) >> 24) & 0xFF);          \
0032     } while(0)
0033 #define isl_hash_bits(h,bits)                       \
0034     ((bits) == 32) ? (h) :                      \
0035     ((bits) >= 16) ?                        \
0036           ((h) >> (bits)) ^ ((h) & (((uint32_t)1 << (bits)) - 1)) : \
0037           (((h) >> (bits)) ^ (h)) & (((uint32_t)1 << (bits)) - 1)
0038
0039 uint32_t isl_hash_string(uint32_t hash, const char *s);
0040 uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len);
0041
0042 #define isl_hash_builtin(h,l)   isl_hash_mem(h, &l, sizeof(l))
0043
0044 struct isl_hash_table_entry
0045 {
0046     uint32_t  hash;
0047     void     *data;
0048 };
0049
0050 struct isl_hash_table {
0051     int    bits;
0052     int    n;
0053     struct isl_hash_table_entry *entries;
0054 };
0055
0056 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size);
0057 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table);
0058
0059 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
0060             int min_size);
0061 void isl_hash_table_clear(struct isl_hash_table *table);
0062 extern struct isl_hash_table_entry *isl_hash_table_entry_none;
0063 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
0064                 struct isl_hash_table *table,
0065                 uint32_t key_hash,
0066                 isl_bool (*eq)(const void *entry, const void *val),
0067                 const void *val, int reserve);
0068 isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
0069     isl_stat (*fn)(void **entry, void *user), void *user);
0070 isl_bool isl_hash_table_every(isl_ctx *ctx, struct isl_hash_table *table,
0071     isl_bool (*test)(void **entry, void *user), void *user);
0072 void isl_hash_table_remove(struct isl_ctx *ctx,
0073                 struct isl_hash_table *table,
0074                 struct isl_hash_table_entry *entry);
0075
0076 #if defined(__cplusplus)
0077 }
0078 #endif
0079
0080 #endif