hashlib.h

   1 /* hashlib.h -- the data structures used in hashing in Bash. */
   2
   3 /* Copyright (C) 1993-2009 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne Again SHell.
   6
   7    Bash is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #if !defined (_HASHLIB_H_)
  22 #define _HASHLIB_H_
  23
  24 #include "stdc.h"
  25
  26 #ifndef PTR_T
  27 #  ifdef __STDC__
  28 #    define PTR_T void *
  29 #  else
  30 #    define PTR_T char *
  31 #  endif
  32 #endif
  33
  34 typedef struct bucket_contents {
  35   struct bucket_contents *next; /* Link to next hashed key in this bucket. */
  36   char *key;                    /* What we look up. */
  37   PTR_T data;                   /* What we really want. */
  38   unsigned int khash;           /* What key hashes to */
  39   int times_found;              /* Number of times this item has been found. */
  40 } BUCKET_CONTENTS;
  41
  42 typedef struct hash_table {
  43   BUCKET_CONTENTS **bucket_array;       /* Where the data is kept. */
  44   int nbuckets;                 /* How many buckets does this table have. */
  45   int nentries;                 /* How many entries does this table have. */
  46 } HASH_TABLE;
  47
  48 typedef int hash_wfunc __P((BUCKET_CONTENTS *));
  49
  50 /* Operations on tables as a whole */
  51 extern HASH_TABLE *hash_create __P((int));
  52 extern HASH_TABLE *hash_copy __P((HASH_TABLE *, sh_string_func_t *));
  53 extern void hash_flush __P((HASH_TABLE *, sh_free_func_t *));
  54 extern void hash_dispose __P((HASH_TABLE *));
  55 extern void hash_walk __P((HASH_TABLE *, hash_wfunc *));
  56
  57 /* Operations to extract information from or pieces of tables */
  58 extern int hash_bucket __P((const char *, HASH_TABLE *));
  59 extern int hash_size __P((HASH_TABLE *));
  60
  61 /* Operations on hash table entries */
  62 extern BUCKET_CONTENTS *hash_search __P((const char *, HASH_TABLE *, int));
  63 extern BUCKET_CONTENTS *hash_insert __P((char *, HASH_TABLE *, int));
  64 extern BUCKET_CONTENTS *hash_remove __P((const char *, HASH_TABLE *, int));
  65
  66 /* Miscellaneous */
  67 extern unsigned int hash_string __P((const char *));
  68
  69 /* Redefine the function as a macro for speed. */
  70 #define hash_items(bucket, table) \
  71         ((table && (bucket < table->nbuckets)) ?  \
  72                 table->bucket_array[bucket] : \
  73                 (BUCKET_CONTENTS *)NULL)
  74
  75 /* Default number of buckets in the hash table. */
  76 #define DEFAULT_HASH_BUCKETS 64 /* was 107, then 53, must be power of two now */
  77
  78 #define HASH_ENTRIES(ht)        ((ht) ? (ht)->nentries : 0)
  79
  80 /* flags for hash_search and hash_insert */
  81 #define HASH_NOSRCH     0x01
  82 #define HASH_CREATE     0x02
  83
  84 #if !defined (NULL)
  85 #  if defined (__STDC__)
  86 #    define NULL ((void *) 0)
  87 #  else
  88 #    define NULL 0x0
  89 #  endif /* !__STDC__ */
  90 #endif /* !NULL */
  91
  92 #endif /* _HASHLIB_H */