include/hash.h

   1 /*
   2  * Copyright (C) 1996-2014 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 typedef struct _hash_link hash_link;
  16 typedef struct _hash_table hash_table;
  17
  18 struct _hash_link {
  19     void *key;
  20     hash_link *next;
  21 };
  22
  23 struct _hash_table {
  24     hash_link **buckets;
  25     HASHCMP *cmp;
  26     HASHHASH *hash;
  27     unsigned int size;
  28     unsigned int current_slot;
  29     hash_link *next;
  30     int count;
  31 };
  32
  33 SQUIDCEXTERN hash_table *hash_create(HASHCMP *, int, HASHHASH *);
  34 SQUIDCEXTERN void hash_join(hash_table *, hash_link *);
  35 SQUIDCEXTERN void hash_remove_link(hash_table *, hash_link *);
  36 SQUIDCEXTERN int hashPrime(int n);
  37 SQUIDCEXTERN hash_link *hash_lookup(hash_table *, const void *);
  38 SQUIDCEXTERN void hash_first(hash_table *);
  39 SQUIDCEXTERN hash_link *hash_next(hash_table *);
  40 SQUIDCEXTERN void hash_last(hash_table *);
  41 SQUIDCEXTERN hash_link *hash_get_bucket(hash_table *, unsigned int);
  42 SQUIDCEXTERN void hashFreeMemory(hash_table *);
  43 SQUIDCEXTERN void hashFreeItems(hash_table *, HASHFREE *);
  44 SQUIDCEXTERN HASHHASH hash_string;
  45 SQUIDCEXTERN HASHHASH hash4;
  46 SQUIDCEXTERN const char *hashKeyStr(hash_link *);
  47
  48 /*
  49  *  Here are some good prime number choices.  It's important not to
  50  *  choose a prime number that is too close to exact powers of 2.
  51  *
  52  *  HASH_SIZE 103               // prime number < 128
  53  *  HASH_SIZE 229               // prime number < 256
  54  *  HASH_SIZE 467               // prime number < 512
  55  *  HASH_SIZE 977               // prime number < 1024
  56  *  HASH_SIZE 1979              // prime number < 2048
  57  *  HASH_SIZE 4019              // prime number < 4096
  58  *  HASH_SIZE 6037              // prime number < 6144
  59  *  HASH_SIZE 7951              // prime number < 8192
  60  *  HASH_SIZE 12149             // prime number < 12288
  61  *  HASH_SIZE 16231             // prime number < 16384
  62  *  HASH_SIZE 33493             // prime number < 32768
  63  *  HASH_SIZE 65357             // prime number < 65536
  64  */
  65 #define  DEFAULT_HASH_SIZE 7951 /* prime number < 8192 */
  66
  67 #endif /* SQUID_HASH_H */
  68