1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24 * Glenn Fowler
25 * AT&T Research
26 *
27 * hash table library
28 */
29
30 static const char id_hash[] = "\n@(#)$Id: hash (AT&T Research) 1996-08-11 $\0\n";
31
32 #include "hashlib.h"
33
34 Hash_info_t hash_info = { 0 };
35
36 /*
37 * create a new hash table
38 */
39
40 Hash_table_t*
hashalloc(Hash_table_t * ref,...)41 hashalloc(Hash_table_t* ref, ...)
42 {
43 register Hash_table_t* tab;
44 register Hash_table_t* ret = 0;
45 register int internal;
46 int n;
47 va_list ap;
48 va_list va[4];
49 va_list* vp = va;
50 Hash_region_f region = 0;
51 void* handle;
52
53 va_start(ap, ref);
54
55 /*
56 * check for HASH_region which must be first
57 */
58
59 n = va_arg(ap, int);
60 if (!ref && n == HASH_region)
61 {
62 region = va_arg(ap, Hash_region_f);
63 handle = va_arg(ap, void*);
64 n = va_arg(ap, int);
65 if (!(tab = (Hash_table_t*)(*region)(handle, NiL, sizeof(Hash_table_t), 0)))
66 goto out;
67 memset(tab, 0, sizeof(Hash_table_t));
68 }
69 else if (!(tab = newof(0, Hash_table_t, 1, 0)))
70 goto out;
71 tab->bucketsize = (sizeof(Hash_header_t) + sizeof(char*) - 1) / sizeof(char*);
72 if (ref)
73 {
74 tab->flags = ref->flags & ~HASH_RESET;
75 tab->root = ref->root;
76 internal = HASH_INTERNAL;
77 }
78 else
79 {
80 if (region)
81 {
82 if (!(tab->root = (Hash_root_t*)(*region)(handle, NiL, sizeof(Hash_root_t), 0)))
83 goto out;
84 memset(tab->root, 0, sizeof(Hash_root_t));
85 }
86 else if (!(tab->root = newof(0, Hash_root_t, 1, 0)))
87 goto out;
88 if (!(tab->root->local = newof(0, Hash_local_t, 1, 0)))
89 goto out;
90 if (tab->root->local->region = region)
91 tab->root->local->handle = handle;
92 tab->root->meanchain = HASHMEANCHAIN;
93 internal = 0;
94 }
95 tab->size = HASHMINSIZE;
96 for (;;)
97 {
98 switch (n)
99 {
100 case HASH_alloc:
101 if (ref) goto out;
102 tab->root->local->alloc = va_arg(ap, Hash_alloc_f);
103 break;
104 case HASH_bucketsize:
105 n = (va_arg(ap, int) + sizeof(char*) - 1) / sizeof(char*);
106 if (n > UCHAR_MAX) goto out;
107 if (n > tab->bucketsize) tab->bucketsize = n;
108 break;
109 case HASH_clear:
110 tab->flags &= ~(va_arg(ap, int) & ~internal);
111 break;
112 case HASH_compare:
113 if (ref) goto out;
114 tab->root->local->compare = va_arg(ap, Hash_compare_f);
115 break;
116 case HASH_free:
117 if (ref) goto out;
118 tab->root->local->free = va_arg(ap, Hash_free_f);
119 break;
120 case HASH_hash:
121 if (ref) goto out;
122 tab->root->local->hash = va_arg(ap, Hash_hash_f);
123 break;
124 case HASH_meanchain:
125 if (ref) goto out;
126 tab->root->meanchain = va_arg(ap, int);
127 break;
128 case HASH_name:
129 tab->name = va_arg(ap, char*);
130 break;
131 case HASH_namesize:
132 if (ref) goto out;
133 tab->root->namesize = va_arg(ap, int);
134 break;
135 case HASH_region:
136 goto out;
137 case HASH_set:
138 tab->flags |= (va_arg(ap, int) & ~internal);
139 break;
140 case HASH_size:
141 tab->size = va_arg(ap, int);
142 if (tab->size & (tab->size - 1)) tab->flags |= HASH_FIXED;
143 break;
144 case HASH_table:
145 tab->table = va_arg(ap, Hash_bucket_t**);
146 tab->flags |= HASH_STATIC;
147 break;
148 case HASH_va_list:
149 if (vp < &va[elementsof(va)])
150 {
151 va_copy(*vp, ap);
152 vp++;
153 }
154 va_copy(ap, va_listval(va_arg(ap, va_listarg)));
155 break;
156 case 0:
157 if (vp > va)
158 {
159 vp--;
160 va_copy(ap, *vp);
161 break;
162 }
163 if (tab->flags & HASH_SCOPE)
164 {
165 if (!(tab->scope = ref)) goto out;
166 ref->frozen++;
167 }
168 if (!tab->table)
169 {
170 if (region)
171 {
172 if (!(tab->table = (Hash_bucket_t**)(*region)(handle, NiL, sizeof(Hash_bucket_t*) * tab->size, 0)))
173 goto out;
174 memset(tab->table, 0, sizeof(Hash_bucket_t*) * tab->size);
175 }
176 else if (!(tab->table = newof(0, Hash_bucket_t*, tab->size, 0))) goto out;
177 }
178 if (!ref)
179 {
180 tab->root->flags = tab->flags & HASH_INTERNAL;
181 tab->root->next = hash_info.list;
182 hash_info.list = tab->root;
183 }
184 if (!region)
185 {
186 tab->next = tab->root->references;
187 tab->root->references = tab;
188 }
189 ret = tab;
190 goto out;
191 default:
192 goto out;
193 }
194 n = va_arg(ap, int);
195 }
196 out:
197 va_end(ap);
198 if (!ret) hashfree(tab);
199 return(ret);
200 }
201