| 1 | /* hashlib.h -- the data structures used in hashing in Bash. */
|
|---|
| 2 |
|
|---|
| 3 | /* Copyright (C) 1993 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 it under
|
|---|
| 8 | the terms of the GNU General Public License as published by the Free
|
|---|
| 9 | Software Foundation; either version 2, or (at your option) any later
|
|---|
| 10 | version.
|
|---|
| 11 |
|
|---|
| 12 | Bash is distributed in the hope that it will be useful, but WITHOUT ANY
|
|---|
| 13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|---|
| 14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|---|
| 15 | for more details.
|
|---|
| 16 |
|
|---|
| 17 | You should have received a copy of the GNU General Public License along
|
|---|
| 18 | with Bash; see the file COPYING. If not, write to the Free Software
|
|---|
| 19 | Foundation, 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
|
|---|
| 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 */
|
|---|
