Jari Aalto | ccc6cda | 1996-12-23 17:02:34 +0000 | [diff] [blame] | 1 | /* hashlib.h -- the data structures used in hashing in Bash. */ |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 2 | |
Jari Aalto | 3185942 | 2009-01-12 13:36:28 +0000 | [diff] [blame] | 3 | /* Copyright (C) 1993-2009 Free Software Foundation, Inc. |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 4 | |
| 5 | This file is part of GNU Bash, the Bourne Again SHell. |
| 6 | |
Jari Aalto | 3185942 | 2009-01-12 13:36:28 +0000 | [diff] [blame] | 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. |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 11 | |
Jari Aalto | 3185942 | 2009-01-12 13:36:28 +0000 | [diff] [blame] | 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. |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 16 | |
Jari Aalto | 3185942 | 2009-01-12 13:36:28 +0000 | [diff] [blame] | 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 | */ |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 20 | |
Jari Aalto | ccc6cda | 1996-12-23 17:02:34 +0000 | [diff] [blame] | 21 | #if !defined (_HASHLIB_H_) |
| 22 | #define _HASHLIB_H_ |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 23 | |
Jari Aalto | bb70624 | 2000-03-17 21:46:59 +0000 | [diff] [blame] | 24 | #include "stdc.h" |
| 25 | |
Jari Aalto | 7117c2d | 2002-07-17 14:10:11 +0000 | [diff] [blame] | 26 | #ifndef PTR_T |
| 27 | # ifdef __STDC__ |
| 28 | # define PTR_T void * |
| 29 | # else |
| 30 | # define PTR_T char * |
| 31 | # endif |
| 32 | #endif |
| 33 | |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 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. */ |
Jari Aalto | 7117c2d | 2002-07-17 14:10:11 +0000 | [diff] [blame] | 37 | PTR_T data; /* What we really want. */ |
| 38 | unsigned int khash; /* What key hashes to */ |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 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 | |
Jari Aalto | 7117c2d | 2002-07-17 14:10:11 +0000 | [diff] [blame] | 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 *)); |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 68 | |
| 69 | /* Redefine the function as a macro for speed. */ |
Jari Aalto | 7117c2d | 2002-07-17 14:10:11 +0000 | [diff] [blame] | 70 | #define hash_items(bucket, table) \ |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 71 | ((table && (bucket < table->nbuckets)) ? \ |
| 72 | table->bucket_array[bucket] : \ |
| 73 | (BUCKET_CONTENTS *)NULL) |
| 74 | |
| 75 | /* Default number of buckets in the hash table. */ |
Jari Aalto | 7117c2d | 2002-07-17 14:10:11 +0000 | [diff] [blame] | 76 | #define DEFAULT_HASH_BUCKETS 64 /* was 107, then 53, must be power of two now */ |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 77 | |
Jari Aalto | f73dda0 | 2001-11-13 17:56:06 +0000 | [diff] [blame] | 78 | #define HASH_ENTRIES(ht) ((ht) ? (ht)->nentries : 0) |
Jari Aalto | bb70624 | 2000-03-17 21:46:59 +0000 | [diff] [blame] | 79 | |
Jari Aalto | 7117c2d | 2002-07-17 14:10:11 +0000 | [diff] [blame] | 80 | /* flags for hash_search and hash_insert */ |
| 81 | #define HASH_NOSRCH 0x01 |
| 82 | #define HASH_CREATE 0x02 |
| 83 | |
Jari Aalto | 726f638 | 1996-08-26 18:22:31 +0000 | [diff] [blame] | 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 | |
Jari Aalto | ccc6cda | 1996-12-23 17:02:34 +0000 | [diff] [blame] | 92 | #endif /* _HASHLIB_H */ |