git.tinc-vpn.org Git - tinc/blob - src/hash.h

   1 #ifndef TINC_HASH_H
   2 #define TINC_HASH_H
   3
   4 /*
   5     hash.h -- header file for hash.c
   6     Copyright (C) 2012-2022 Guus Sliepen <guus@tinc-vpn.org>
   7
   8     This program is free software; you can redistribute it and/or modify
   9     it under the terms of the GNU General Public License as published by
  10     the Free Software Foundation; either version 2 of the License, or
  11     (at your option) any later version.
  12
  13     This program is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License along
  19     with this program; if not, write to the Free Software Foundation, Inc.,
  20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21 */
  22
  23
  24 /* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */
  25
  26 uint32_t modulo(uint32_t hash, size_t n);
  27
  28 #define HASH_SEARCH_ITERATIONS 4
  29
  30 #define hash_insert(t, ...) hash_insert_ ## t (__VA_ARGS__)
  31 #define hash_delete(t, ...) hash_delete_ ## t (__VA_ARGS__)
  32 #define hash_search(t, ...) hash_search_ ## t (__VA_ARGS__)
  33 #define hash_clear(t, n) hash_clear_ ## t ((n))
  34
  35 #define hash_define(t, n) \
  36         typedef struct hash_ ## t { \
  37                 t keys[n]; \
  38                 const void *values[n]; \
  39         } hash_ ## t; \
  40         static inline uint32_t hash_modulo_ ## t(uint32_t hash) { \
  41                 return hash & (n - 1); \
  42         } \
  43         static inline void hash_insert_ ## t (hash_ ##t *hash, const t *key, const void *value) { \
  44                 uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \
  45                 for(uint8_t f=0; f< (HASH_SEARCH_ITERATIONS - 1); f++){ \
  46                         if(hash->values[i] == NULL || !memcmp(key, &hash->keys[i], sizeof(t))) { \
  47                                 memcpy(&hash->keys[i], key, sizeof(t)); \
  48                                 hash->values[i] = value; \
  49                                 return; \
  50                         } \
  51                         if(++i == n) i = 0; \
  52                 } \
  53                 /* We always pick the last slot. It's unfair. But thats life */ \
  54                 memcpy(&hash->keys[i], key, sizeof(t)); \
  55                 hash->values[i] = value; \
  56         } \
  57         static inline void *hash_search_ ## t (const hash_ ##t *hash, const t *key) { \
  58                 uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \
  59                 for(uint8_t f=0; f<HASH_SEARCH_ITERATIONS; f++){ \
  60                         if(!memcmp(key, &hash->keys[i], sizeof(t))) { \
  61                                 return (void *)hash->values[i]; \
  62                         } \
  63                         if(++i == n) i = 0; \
  64                 } \
  65                 return NULL; \
  66         } \
  67         static inline void hash_delete_ ## t (hash_ ##t *hash, const t *key) { \
  68                 uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \
  69                 for(uint8_t f=0; f<HASH_SEARCH_ITERATIONS; f++){ \
  70                         if(!memcmp(key, &hash->keys[i], sizeof(t))) { \
  71                                 hash->values[i] = NULL; \
  72                                 return; \
  73                         } \
  74                         if(++i == n) i = 0; \
  75                 } \
  76         } \
  77         static inline void hash_clear_ ## t(hash_ ##t *hash) { \
  78                 memset(hash->values, 0, n * sizeof(*hash->values)); \
  79                 memset(hash->keys, 0, n * sizeof(*hash->keys)); \
  80         }
  81
  82
  83 #define hash_new(t, name) static hash_ ## t name
  84
  85 #endif