include/isl/hash.h

   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 #include <isl/ctx.h>
  16
  17 #if defined(__cplusplus)
  18 extern "C" {
  19 #endif
  20
  21 #define isl_hash_init()         (2166136261u)
  22 #define isl_hash_byte(h,b)      do {                                    \
  23                                         h *= 16777619;                  \
  24                                         h ^= b;                         \
  25                                 } while(0)
  26 #define isl_hash_hash(h,h2)                                             \
  27         do {                                                            \
  28                 isl_hash_byte(h, (h2) & 0xFF);                          \
  29                 isl_hash_byte(h, ((h2) >> 8) & 0xFF);                   \
  30                 isl_hash_byte(h, ((h2) >> 16) & 0xFF);                  \
  31                 isl_hash_byte(h, ((h2) >> 24) & 0xFF);                  \
  32         } while(0)
  33 #define isl_hash_bits(h,bits)                                           \
  34         ((bits) == 32) ? (h) :                                          \
  35         ((bits) >= 16) ?                                                \
  36               ((h) >> (bits)) ^ ((h) & (((uint32_t)1 << (bits)) - 1)) : \
  37               (((h) >> (bits)) ^ (h)) & (((uint32_t)1 << (bits)) - 1)
  38
  39 uint32_t isl_hash_string(uint32_t hash, const char *s);
  40 uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len);
  41
  42 #define isl_hash_builtin(h,l)   isl_hash_mem(h, &l, sizeof(l))
  43
  44 struct isl_hash_table_entry
  45 {
  46         uint32_t  hash;
  47         void     *data;
  48 };
  49
  50 struct isl_hash_table {
  51         int    bits;
  52         int    n;
  53         struct isl_hash_table_entry *entries;
  54 };
  55
  56 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size);
  57 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table);
  58
  59 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
  60                         int min_size);
  61 void isl_hash_table_clear(struct isl_hash_table *table);
  62 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
  63                                 struct isl_hash_table *table,
  64                                 uint32_t key_hash,
  65                                 int (*eq)(const void *entry, const void *val),
  66                                 const void *val, int reserve);
  67 isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
  68         isl_stat (*fn)(void **entry, void *user), void *user);
  69 void isl_hash_table_remove(struct isl_ctx *ctx,
  70                                 struct isl_hash_table *table,
  71                                 struct isl_hash_table_entry *entry);
  72
  73 #if defined(__cplusplus)
  74 }
  75 #endif
  76
  77 #endif