1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2009 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* 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