1 /* hashlib.h -- the data structures used in hashing in Bash. */ 2 3 /* Copyright (C) 1993-2020 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 PARAMS((BUCKET_CONTENTS *)); 49 50 /* Operations on tables as a whole */ 51 extern HASH_TABLE *hash_create PARAMS((int)); 52 extern HASH_TABLE *hash_copy PARAMS((HASH_TABLE *, sh_string_func_t *)); 53 extern void hash_flush PARAMS((HASH_TABLE *, sh_free_func_t *)); 54 extern void hash_dispose PARAMS((HASH_TABLE *)); 55 extern void hash_walk PARAMS((HASH_TABLE *, hash_wfunc *)); 56 57 /* Operations to extract information from or pieces of tables */ 58 extern int hash_bucket PARAMS((const char *, HASH_TABLE *)); 59 extern int hash_size PARAMS((HASH_TABLE *)); 60 61 /* Operations on hash table entries */ 62 extern BUCKET_CONTENTS *hash_search PARAMS((const char *, HASH_TABLE *, int)); 63 extern BUCKET_CONTENTS *hash_insert PARAMS((char *, HASH_TABLE *, int)); 64 extern BUCKET_CONTENTS *hash_remove PARAMS((const char *, HASH_TABLE *, int)); 65 66 /* Miscellaneous */ 67 extern unsigned int hash_string PARAMS((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 128 /* must be power of two */ 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 */ 93