src/hash.h

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
   3    Written by Ben Pfaff <blp@gnu.org>.
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  18    02111-1307, USA. */
  19
  20 #if !hash_h
  21 #define hash_h 1
  22
  23 /* Hash table (opaque). */
  24 struct hsh_table
  25   {
  26     int n;                      /* Number of filled entries. */
  27     int m;                      /* Number of entries. */
  28     int *mp;                    /* Pointer into hsh_prime_tab[]. */
  29     void **table;               /* Hash table proper. */
  30
  31     void *param;
  32     int (*compare) (const void *, const void *, void *param);
  33     unsigned (*hash) (const void *, void *param);
  34     void (*free) (void *, void *param);
  35   };
  36
  37 /* Hash table iterator (opaque). */
  38 struct hsh_iterator
  39   {
  40     int init;                   /* Initialized? */
  41     int next;                   /* Index of next entry. */
  42   };
  43
  44 #define hsh_iterator_init(ITERATOR) (ITERATOR).init = 0
  45
  46 /* Prime numbers and hash functions. */
  47 int *hsh_next_prime (int) __attribute__ ((const));
  48 int hashpjw_d (const char *s1, const char *s2);
  49
  50 #if __GNUC__>=2 && __OPTIMIZE__
  51 extern inline int
  52 hashpjw (const char *s)
  53 {
  54   return hashpjw_d (s, &s[strlen (s)]);
  55 }
  56 #else
  57 int hashpjw (const char *s);
  58 #endif
  59
  60 /* Hash tables. */
  61 struct hsh_table *hsh_create (int m,
  62                               int (*compare) (const void *, const void *,
  63                                               void *param),
  64                               unsigned (*hash) (const void *, void *param),
  65                               void (*free) (void *, void *param),
  66                               void *param);
  67 void hsh_clear (struct hsh_table *);
  68 void hsh_destroy (struct hsh_table *);
  69 void hsh_rehash (struct hsh_table *);
  70 void **hsh_sort (struct hsh_table *,
  71                  int (*compare) (const void *, const void *, void *param));
  72 #if GLOBAL_DEBUGGING
  73 void hsh_dump (struct hsh_table *);
  74 #endif
  75
  76 /* Hash entries. */
  77 void **hsh_probe (struct hsh_table *, const void *);
  78 void *hsh_find (struct hsh_table *, const void *);
  79 void *hsh_foreach (struct hsh_table *, struct hsh_iterator *);
  80
  81 #if GLOBAL_DEBUGGING
  82 void force_hsh_insert (struct hsh_table *, void *);
  83 void *force_hsh_find (struct hsh_table *, const void *);
  84 #else
  85 #define force_hsh_insert(A, B)                  \
  86         do *hsh_probe (A, B) = B; while (0)
  87 #define force_hsh_find(A, B)                    \
  88         hsh_find (A, B)
  89 #endif
  90
  91 /* Returns number of used elements in hash table H. */
  92 #define hsh_count(H)                            \
  93         ((H)->n)
  94
  95 #endif /* hash_h */