]>
Commit | Line | Data |
---|---|---|
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 */ |