Commit | Line | Data |
---|---|---|
cc89ffe6 ILT |
1 | /* An expandable hash tables datatype. |
2 | Copyright (C) 1999 Free Software Foundation, Inc. | |
3 | Contributed by Vladimir Makarov (vmakarov@cygnus.com). | |
4 | ||
5 | This program is free software; you can redistribute it and/or modify | |
6 | it under the terms of the GNU General Public License as published by | |
7 | the Free Software Foundation; either version 2 of the License, or | |
8 | (at your option) any later version. | |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License | |
16 | along with this program; if not, write to the Free Software | |
17 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ | |
18 | ||
19 | /* This package implements basic hash table functionality. It is possible | |
20 | to search for an entry, create an entry and destroy an entry. | |
21 | ||
22 | Elements in the table are generic pointers. | |
23 | ||
24 | The size of the table is not fixed; if the occupancy of the table | |
25 | grows too high the hash table will be expanded. | |
26 | ||
27 | The abstract data implementation is based on generalized Algorithm D | |
28 | from Knuth's book "The art of computer programming". Hash table is | |
29 | expanded by creation of new hash table and transferring elements from | |
30 | the old table to the new table. */ | |
31 | ||
32 | #ifndef __HASHTAB_H__ | |
33 | #define __HASHTAB_H__ | |
34 | ||
35 | #ifdef __cplusplus | |
36 | extern "C" { | |
37 | #endif /* __cplusplus */ | |
38 | ||
39 | #include <ansidecl.h> | |
40 | ||
41 | /* The hash table element is represented by the following type. */ | |
42 | ||
43 | typedef const void *hash_table_entry_t; | |
44 | ||
45 | /* Hash tables are of the following type. The structure | |
46 | (implementation) of this type is not needed for using the hash | |
47 | tables. All work with hash table should be executed only through | |
48 | functions mentioned below. */ | |
49 | ||
50 | typedef struct hash_table | |
51 | { | |
52 | /* Current size (in entries) of the hash table */ | |
53 | size_t size; | |
54 | /* Current number of elements including also deleted elements */ | |
55 | size_t number_of_elements; | |
56 | /* Current number of deleted elements in the table */ | |
57 | size_t number_of_deleted_elements; | |
58 | /* The following member is used for debugging. Its value is number | |
59 | of all calls of `find_hash_table_entry' for the hash table. */ | |
60 | int searches; | |
61 | /* The following member is used for debugging. Its value is number | |
62 | of collisions fixed for time of work with the hash table. */ | |
63 | int collisions; | |
64 | /* Pointer to function for evaluation of hash value (any unsigned value). | |
65 | This function has one parameter of type hash_table_entry_t. */ | |
66 | unsigned (*hash_function) PARAMS ((hash_table_entry_t)); | |
67 | /* Pointer to function for test on equality of hash table elements (two | |
68 | parameter of type hash_table_entry_t. */ | |
69 | int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t)); | |
70 | /* Table itself */ | |
71 | hash_table_entry_t *entries; | |
72 | } *hash_table_t; | |
73 | ||
74 | ||
75 | /* The prototypes of the package functions. */ | |
76 | ||
77 | extern hash_table_t create_hash_table | |
78 | PARAMS ((size_t, unsigned (*) (hash_table_entry_t), | |
79 | int (*) (hash_table_entry_t, hash_table_entry_t))); | |
80 | ||
81 | extern void delete_hash_table PARAMS ((hash_table_t)); | |
82 | ||
83 | extern void empty_hash_table PARAMS ((hash_table_t)); | |
84 | ||
85 | extern hash_table_entry_t *find_hash_table_entry | |
86 | PARAMS ((hash_table_t, hash_table_entry_t, int)); | |
87 | ||
88 | extern void remove_element_from_hash_table_entry PARAMS ((hash_table_t, | |
89 | hash_table_entry_t)); | |
90 | ||
91 | extern void clear_hash_table_slot PARAMS ((hash_table_t, hash_table_entry_t *)); | |
92 | ||
93 | extern void traverse_hash_table PARAMS ((hash_table_t, | |
94 | int (*) (hash_table_entry_t, void *), | |
95 | void *)); | |
96 | ||
97 | extern size_t hash_table_size PARAMS ((hash_table_t)); | |
98 | ||
99 | extern size_t hash_table_elements_number PARAMS ((hash_table_t)); | |
100 | ||
101 | extern int hash_table_collisions PARAMS ((hash_table_t)); | |
102 | ||
103 | extern int all_hash_table_collisions PARAMS ((void)); | |
104 | ||
105 | #ifdef __cplusplus | |
106 | } | |
107 | #endif /* __cplusplus */ | |
108 | ||
109 | #endif /* __HASHTAB_H */ |