include/hash.h

   1 /*
   2  * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #ifndef SQUID_HASH_H
  10 #define SQUID_HASH_H
  11
  12 typedef void HASHFREE(void *);
  13 typedef int HASHCMP(const void *, const void *);
  14 typedef unsigned int HASHHASH(const void *, unsigned int);
  15
  16 class hash_link {
  17 public:
  18     hash_link() : key(nullptr), next(nullptr) {}
  19     void *key;
  20     hash_link *next;
  21 };
  22
  23 class hash_table {
  24 public:
  25     hash_link **buckets;
  26     HASHCMP *cmp;
  27     HASHHASH *hash;
  28     unsigned int size;
  29     unsigned int current_slot;
  30     hash_link *next;
  31     int count;
  32 };
  33
  34 SQUIDCEXTERN hash_table *hash_create(HASHCMP *, int, HASHHASH *);
  35 SQUIDCEXTERN void hash_join(hash_table *, hash_link *);
  36 SQUIDCEXTERN void hash_remove_link(hash_table *, hash_link *);
  37 SQUIDCEXTERN int hashPrime(int n);
  38 SQUIDCEXTERN hash_link *hash_lookup(hash_table *, const void *);
  39 SQUIDCEXTERN void hash_first(hash_table *);
  40 SQUIDCEXTERN hash_link *hash_next(hash_table *);
  41 SQUIDCEXTERN void hash_last(hash_table *);
  42 SQUIDCEXTERN hash_link *hash_get_bucket(hash_table *, unsigned int);
  43 SQUIDCEXTERN void hashFreeMemory(hash_table *);
  44 SQUIDCEXTERN void hashFreeItems(hash_table *, HASHFREE *);
  45 SQUIDCEXTERN HASHHASH hash_string;
  46 SQUIDCEXTERN HASHHASH hash4;
  47 SQUIDCEXTERN const char *hashKeyStr(hash_link *);
  48
  49 /*
  50  *  Here are some good prime number choices.  It's important not to
  51  *  choose a prime number that is too close to exact powers of 2.
  52  *
  53  *  HASH_SIZE 103               // prime number < 128
  54  *  HASH_SIZE 229               // prime number < 256
  55  *  HASH_SIZE 467               // prime number < 512
  56  *  HASH_SIZE 977               // prime number < 1024
  57  *  HASH_SIZE 1979              // prime number < 2048
  58  *  HASH_SIZE 4019              // prime number < 4096
  59  *  HASH_SIZE 6037              // prime number < 6144
  60  *  HASH_SIZE 7951              // prime number < 8192
  61  *  HASH_SIZE 12149             // prime number < 12288
  62  *  HASH_SIZE 16231             // prime number < 16384
  63  *  HASH_SIZE 33493             // prime number < 32768
  64  *  HASH_SIZE 65357             // prime number < 65536
  65  */
  66 #define  DEFAULT_HASH_SIZE 7951 /* prime number < 8192 */
  67
  68 #endif /* SQUID_HASH_H */
  69