1 /* $NetBSD: hash.c,v 1.24 2022/05/20 21:18:55 rillig Exp $ */ 2 3 /* 4 * Copyright (c) 1994, 1995 Jochen Pohl 5 * All Rights Reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Jochen Pohl for 18 * The NetBSD Project. 19 * 4. The name of the author may not be used to endorse or promote products 20 * derived from this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #if HAVE_NBTOOL_CONFIG_H 35 #include "nbtool_config.h" 36 #endif 37 38 #include <sys/cdefs.h> 39 #if defined(__RCSID) 40 __RCSID("$NetBSD: hash.c,v 1.24 2022/05/20 21:18:55 rillig Exp $"); 41 #endif 42 43 /* 44 * XXX Really need a generalized hash table package 45 */ 46 47 #include <limits.h> 48 #include <stddef.h> 49 #include <stdlib.h> 50 #include <string.h> 51 52 #include "lint2.h" 53 54 /* pointer to hash table, initialized in inithash() */ 55 static hte_t **htab; 56 57 /* 58 * Initialize hash table. 59 */ 60 hte_t ** 61 htab_new(void) 62 { 63 return xcalloc(HSHSIZ2, sizeof(*htab_new())); 64 } 65 66 /* 67 * Compute hash value from a string. 68 */ 69 static unsigned int 70 hash(const char *s) 71 { 72 unsigned int v; 73 const char *p; 74 75 v = 0; 76 for (p = s; *p != '\0'; p++) { 77 v = (v << 4) + (unsigned char)*p; 78 v ^= v >> 28; 79 } 80 return v % HSHSIZ2; 81 } 82 83 /* 84 * Look for a hash table entry. If no hash table entry for the 85 * given name exists and mknew is set, create a new one. 86 */ 87 hte_t * 88 _hsearch(hte_t **table, const char *s, bool mknew) 89 { 90 unsigned int h; 91 hte_t *hte; 92 93 if (table == NULL) 94 table = htab; 95 96 h = hash(s); 97 for (hte = table[h]; hte != NULL; hte = hte->h_link) { 98 if (strcmp(hte->h_name, s) == 0) 99 break; 100 } 101 102 if (hte != NULL || !mknew) 103 return hte; 104 105 /* create a new hte */ 106 hte = xmalloc(sizeof(*hte)); 107 hte->h_name = xstrdup(s); 108 hte->h_used = false; 109 hte->h_def = false; 110 hte->h_static = false; 111 hte->h_syms = NULL; 112 hte->h_lsym = &hte->h_syms; 113 hte->h_calls = NULL; 114 hte->h_lcall = &hte->h_calls; 115 hte->h_usyms = NULL; 116 hte->h_lusym = &hte->h_usyms; 117 hte->h_link = table[h]; 118 hte->h_hte = NULL; 119 table[h] = hte; 120 121 return hte; 122 } 123 124 struct hte_list { 125 hte_t **items; 126 size_t len; 127 size_t cap; 128 }; 129 130 static void 131 hte_list_add(struct hte_list *list, hte_t *item) 132 { 133 if (list->len >= list->cap) { 134 list->cap = list->cap == 0 ? 1024 : 2 * list->cap; 135 list->items = xrealloc(list->items, 136 sizeof(list->items[0]) * list->cap); 137 } 138 list->items[list->len++] = item; 139 } 140 141 static int 142 hte_by_name(const void *va, const void *vb) 143 { 144 const hte_t *a = *((const hte_t *const *)va); 145 const hte_t *b = *((const hte_t *const *)vb); 146 147 return strcmp(a->h_name, b->h_name); 148 } 149 150 void 151 symtab_init(void) 152 { 153 htab = htab_new(); 154 } 155 156 /* 157 * Call the action for each name in the hash table. 158 */ 159 void 160 symtab_forall(void (*action)(hte_t *)) 161 { 162 int i; 163 hte_t *hte; 164 hte_t **table = htab; 165 166 for (i = 0; i < HSHSIZ2; i++) { 167 for (hte = table[i]; hte != NULL; hte = hte->h_link) 168 action(hte); 169 } 170 } 171 172 /* Run the action for each name in the symbol table, in alphabetic order. */ 173 void 174 symtab_forall_sorted(void (*action)(hte_t *)) 175 { 176 hte_t *hte; 177 struct hte_list sorted = { NULL, 0, 0 }; 178 size_t i; 179 hte_t **table = htab; 180 181 for (i = 0; i < HSHSIZ2; i++) 182 for (hte = table[i]; hte != NULL; hte = hte->h_link) 183 hte_list_add(&sorted, hte); 184 185 qsort(sorted.items, sorted.len, sizeof(sorted.items[0]), hte_by_name); 186 187 for (i = 0; i < sorted.len; i++) 188 action(sorted.items[i]); 189 190 free(sorted.items); 191 } 192 193 /* 194 * Free all contents of the hash table that this module allocated. 195 */ 196 void 197 _destroyhash(hte_t **table) 198 { 199 int i; 200 hte_t *hte, *nexthte; 201 202 if (table == NULL) 203 err(1, "_destroyhash called on main hash table"); 204 205 for (i = 0; i < HSHSIZ2; i++) { 206 for (hte = table[i]; hte != NULL; hte = nexthte) { 207 free(__UNCONST(hte->h_name)); 208 nexthte = hte->h_link; 209 free(hte); 210 } 211 } 212 free(table); 213 } 214