|
2999
|
1 /* hash.c: hash table operations. |
|
|
2 |
|
|
3 Copyright (C) 1994, 95, 96 Karl Berry. |
|
|
4 |
|
|
5 This library is free software; you can redistribute it and/or |
|
|
6 modify it under the terms of the GNU Library General Public |
|
|
7 License as published by the Free Software Foundation; either |
|
|
8 version 2 of the License, or (at your option) any later version. |
|
|
9 |
|
|
10 This library 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 GNU |
|
|
13 Library General Public License for more details. |
|
|
14 |
|
|
15 You should have received a copy of the GNU Library General Public |
|
|
16 License along with this library; if not, write to the Free Software |
|
|
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ |
|
|
18 |
|
|
19 #include <kpathsea/config.h> |
|
|
20 |
|
|
21 #include <kpathsea/hash.h> |
|
|
22 #include <kpathsea/str-list.h> |
|
|
23 |
|
|
24 |
|
|
25 /* The hash function. We go for simplicity here. */ |
|
|
26 |
|
|
27 /* All our hash tables are related to filenames. */ |
|
|
28 #ifdef MONOCASE_FILENAMES |
|
|
29 #define TRANSFORM(x) toupper (x) |
|
|
30 #else |
|
|
31 #define TRANSFORM(x) (x) |
|
|
32 #endif |
|
|
33 |
|
|
34 static unsigned |
|
|
35 hash P2C(hash_table_type, table, const_string, key) |
|
|
36 { |
|
|
37 unsigned n = 0; |
|
|
38 |
|
|
39 /* Our keys aren't often anagrams of each other, so no point in |
|
|
40 weighting the characters. */ |
|
|
41 while (*key != 0) |
|
|
42 n = (n + n + TRANSFORM (*key++)) % table.size; |
|
|
43 |
|
|
44 return n; |
|
|
45 } |
|
|
46 |
|
|
47 hash_table_type |
|
|
48 hash_create P1C(unsigned, size) |
|
|
49 { |
|
|
50 unsigned b; |
|
|
51 hash_table_type ret; |
|
|
52 ret.buckets = XTALLOC (size, hash_element_type *); |
|
|
53 ret.size = size; |
|
|
54 |
|
|
55 /* calloc's zeroes aren't necessarily NULL, according to ANSI, so be |
|
|
56 safe. (Not that I know of any exceptions in reality.) */ |
|
|
57 for (b = 0; b <ret.size; b++) |
|
|
58 ret.buckets[b] = NULL; |
|
|
59 |
|
|
60 return ret; |
|
|
61 } |
|
|
62 |
|
|
63 /* Whether or not KEY is already in MAP, insert it and VALUE. Do not |
|
|
64 duplicate the strings, in case they're being purposefully shared. */ |
|
|
65 |
|
|
66 void |
|
|
67 hash_insert P3C(hash_table_type *, table, const_string, key, |
|
|
68 const_string, value) |
|
|
69 { |
|
|
70 unsigned n = hash (*table, key); |
|
|
71 hash_element_type *new_elt = XTALLOC1 (hash_element_type); |
|
|
72 |
|
|
73 new_elt->key = key; |
|
|
74 new_elt->value = value; |
|
|
75 new_elt->next = NULL; |
|
|
76 |
|
|
77 /* Insert the new element at the end of the list. */ |
|
|
78 if (!table->buckets[n]) |
|
|
79 /* first element in bucket is a special case. */ |
|
|
80 table->buckets[n] = new_elt; |
|
|
81 else |
|
|
82 { |
|
|
83 hash_element_type *loc = table->buckets[n]; |
|
|
84 while (loc->next) /* Find the last element. */ |
|
|
85 loc = loc->next; |
|
|
86 loc->next = new_elt; /* Insert the new one after. */ |
|
|
87 } |
|
|
88 } |
|
|
89 |
|
|
90 /* Look up STR in MAP. Return a (dynamically-allocated) list of the |
|
|
91 corresponding strings or NULL if no match. */ |
|
|
92 |
|
|
93 #ifdef KPSE_DEBUG |
|
|
94 /* Print the hash values as integers if this is nonzero. */ |
|
|
95 boolean kpse_debug_hash_lookup_int = false; |
|
|
96 #endif |
|
|
97 |
|
|
98 string * |
|
|
99 hash_lookup P2C(hash_table_type, table, const_string, key) |
|
|
100 { |
|
|
101 hash_element_type *p; |
|
|
102 str_list_type ret; |
|
|
103 unsigned n = hash (table, key); |
|
|
104 ret = str_list_init (); |
|
|
105 |
|
|
106 /* Look at everything in this bucket. */ |
|
|
107 for (p = table.buckets[n]; p != NULL; p = p->next) |
|
|
108 if (FILESTRCASEEQ (key, p->key)) |
|
|
109 /* Cast because the general str_list_type shouldn't force const data. */ |
|
|
110 str_list_add (&ret, (string) p->value); |
|
|
111 |
|
|
112 /* If we found anything, mark end of list with null. */ |
|
|
113 if (STR_LIST (ret)) |
|
|
114 str_list_add (&ret, NULL); |
|
|
115 |
|
|
116 #ifdef KPSE_DEBUG |
|
|
117 if (KPSE_DEBUG_P (KPSE_DEBUG_HASH)) |
|
|
118 { |
|
|
119 DEBUGF1 ("hash_lookup(%s) =>", key); |
|
|
120 if (!STR_LIST (ret)) |
|
|
121 fputs (" (nil)\n", stderr); |
|
|
122 else |
|
|
123 { |
|
|
124 string *r; |
|
|
125 for (r = STR_LIST (ret); *r; r++) |
|
|
126 { |
|
|
127 putc (' ', stderr); |
|
|
128 if (kpse_debug_hash_lookup_int) |
|
|
129 fprintf (stderr, "%ld", (long) *r); |
|
|
130 else |
|
|
131 fputs (*r, stderr); |
|
|
132 } |
|
|
133 putc ('\n', stderr); |
|
|
134 } |
|
|
135 fflush (stderr); |
|
|
136 } |
|
|
137 #endif |
|
|
138 |
|
|
139 return STR_LIST (ret); |
|
|
140 } |
|
|
141 |
|
|
142 /* We only print nonempty buckets, to decrease output volume. */ |
|
|
143 |
|
|
144 void |
|
|
145 hash_print P2C(hash_table_type, table, boolean, summary_only) |
|
|
146 { |
|
|
147 unsigned b; |
|
|
148 unsigned total_elements = 0, total_buckets = 0; |
|
|
149 |
|
|
150 for (b = 0; b < table.size; b++) { |
|
|
151 hash_element_type *bucket = table.buckets[b]; |
|
|
152 |
|
|
153 if (bucket) { |
|
|
154 unsigned len = 1; |
|
|
155 hash_element_type *tb; |
|
|
156 |
|
|
157 total_buckets++; |
|
|
158 if (!summary_only) fprintf (stderr, "%4d ", b); |
|
|
159 |
|
|
160 for (tb = bucket->next; tb != NULL; tb = tb->next) |
|
|
161 len++; |
|
|
162 if (!summary_only) fprintf (stderr, ":%-5d", len); |
|
|
163 total_elements += len; |
|
|
164 |
|
|
165 if (!summary_only) { |
|
|
166 for (tb = bucket; tb != NULL; tb = tb->next) |
|
|
167 fprintf (stderr, " %s=>%s", tb->key, tb->value); |
|
|
168 putc ('\n', stderr); |
|
|
169 } |
|
|
170 } |
|
|
171 } |
|
|
172 |
|
|
173 fprintf (stderr, |
|
|
174 "%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n", |
|
|
175 table.size, |
|
|
176 total_buckets, |
|
|
177 100 * total_buckets / table.size, |
|
|
178 total_elements, |
|
|
179 total_buckets ? total_elements / (double) total_buckets : 0.0); |
|
|
180 } |
