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
  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