1/* hash.c -- hash table routines 2 Copyright (C) 1993, 1994, 1998 Free Software Foundation, Inc. 3 Written by Steve Chamberlain <sac@cygnus.com> 4 5This file was lifted from BFD, the Binary File Descriptor library. 6 7This program is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2 of the License, or 10(at your option) any later version. 11 12This program is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with this program; if not, write to the Free Software 19Foundation, 59 Temple Place - Suite 330, 20Boston, MA 02111-1307, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "hash.h" 25#include "obstack.h" 26#include "toplev.h" 27 28/* Obstack allocation and deallocation routines. */ 29#define obstack_chunk_alloc xmalloc 30#define obstack_chunk_free free 31 32/* The default number of entries to use when creating a hash table. */ 33#define DEFAULT_SIZE (1009) 34 35/* Create a new hash table, given a number of entries. */ 36 37boolean 38hash_table_init_n (table, newfunc, hash, comp, size) 39 struct hash_table *table; 40 struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *, 41 struct hash_table *, 42 hash_table_key)); 43 unsigned long (*hash) PARAMS ((hash_table_key)); 44 boolean (*comp) PARAMS ((hash_table_key, hash_table_key)); 45 unsigned int size; 46{ 47 unsigned int alloc; 48 49 alloc = size * sizeof (struct hash_entry *); 50 if (!obstack_begin (&table->memory, alloc)) 51 { 52 error ("no memory"); 53 return false; 54 } 55 table->table = ((struct hash_entry **) 56 obstack_alloc (&table->memory, alloc)); 57 if (!table->table) 58 { 59 error ("no memory"); 60 return false; 61 } 62 memset ((PTR) table->table, 0, alloc); 63 table->size = size; 64 table->newfunc = newfunc; 65 table->hash = hash; 66 table->comp = comp; 67 return true; 68} 69 70/* Create a new hash table with the default number of entries. */ 71 72boolean 73hash_table_init (table, newfunc, hash, comp) 74 struct hash_table *table; 75 struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *, 76 struct hash_table *, 77 hash_table_key)); 78 unsigned long (*hash) PARAMS ((hash_table_key)); 79 boolean (*comp) PARAMS ((hash_table_key, hash_table_key)); 80{ 81 return hash_table_init_n (table, newfunc, hash, comp, DEFAULT_SIZE); 82} 83 84/* Free a hash table. */ 85 86void 87hash_table_free (table) 88 struct hash_table *table; 89{ 90 obstack_free (&table->memory, (PTR) NULL); 91} 92 93/* Look up KEY in TABLE. If CREATE is non-NULL a new entry is 94 created if one does not previously exist. */ 95 96struct hash_entry * 97hash_lookup (table, key, create, copy) 98 struct hash_table *table; 99 hash_table_key key; 100 boolean create; 101 hash_table_key (*copy) PARAMS ((struct obstack* memory, 102 hash_table_key key)); 103{ 104 register unsigned long hash; 105 struct hash_entry *hashp; 106 unsigned int index; 107 108 hash = (*table->hash)(key); 109 110 index = hash % table->size; 111 for (hashp = table->table[index]; 112 hashp != (struct hash_entry *) NULL; 113 hashp = hashp->next) 114 { 115 if (hashp->hash == hash 116 && (*table->comp)(hashp->key, key)) 117 return hashp; 118 } 119 120 if (! create) 121 return (struct hash_entry *) NULL; 122 123 hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, key); 124 if (hashp == (struct hash_entry *) NULL) 125 return (struct hash_entry *) NULL; 126 if (copy) 127 key = (*copy) (&table->memory, key); 128 hashp->key = key; 129 hashp->hash = hash; 130 hashp->next = table->table[index]; 131 table->table[index] = hashp; 132 133 return hashp; 134} 135 136/* Base method for creating a new hash table entry. */ 137 138/*ARGSUSED*/ 139struct hash_entry * 140hash_newfunc (entry, table, p) 141 struct hash_entry *entry; 142 struct hash_table *table; 143 hash_table_key p; 144{ 145 if (entry == (struct hash_entry *) NULL) 146 entry = ((struct hash_entry *) 147 hash_allocate (table, sizeof (struct hash_entry))); 148 return entry; 149} 150 151/* Allocate space in a hash table. */ 152 153PTR 154hash_allocate (table, size) 155 struct hash_table *table; 156 unsigned int size; 157{ 158 PTR ret; 159 160 ret = obstack_alloc (&table->memory, size); 161 if (ret == NULL && size != 0) 162 error ("no memory"); 163 return ret; 164} 165 166/* Traverse a hash table. */ 167 168void 169hash_traverse (table, func, info) 170 struct hash_table *table; 171 boolean (*func) PARAMS ((struct hash_entry *, hash_table_key)); 172 PTR info; 173{ 174 unsigned int i; 175 176 for (i = 0; i < table->size; i++) 177 { 178 struct hash_entry *p; 179 180 for (p = table->table[i]; p != NULL; p = p->next) 181 { 182 if (! (*func) (p, info)) 183 return; 184 } 185 } 186} 187 188/* Hash a string. Return a hash-code for the string. */ 189 190unsigned long 191string_hash (k) 192 hash_table_key k; 193{ 194 const unsigned char *s; 195 unsigned long hash; 196 unsigned char c; 197 unsigned int len; 198 199 s = (const unsigned char *) k; 200 hash = 0; 201 len = 0; 202 203 while ((c = *s++) != '\0') 204 { 205 hash += c + (c << 17); 206 hash ^= hash >> 2; 207 ++len; 208 } 209 hash += len + (len << 17); 210 hash ^= hash >> 2; 211 212 return hash; 213} 214 215/* Compare two strings. Return non-zero iff the two strings are 216 the same. */ 217 218boolean 219string_compare (k1, k2) 220 hash_table_key k1; 221 hash_table_key k2; 222{ 223 return (strcmp ((char*) k1, (char*) k2) == 0); 224} 225 226/* Copy K to OBSTACK. */ 227 228hash_table_key 229string_copy (memory, k) 230 struct obstack* memory; 231 hash_table_key k; 232{ 233 char *new; 234 char *string = (char*) k; 235 236 new = (char *) obstack_alloc (memory, strlen (string) + 1); 237 if (!new) 238 { 239 error ("no memory"); 240 return NULL; 241 } 242 strcpy (new, string); 243 244 return new; 245} 246