1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 * 26 * stable.c -- string table module 27 * 28 * simple string table module. all read-only strings are entered in 29 * this table, allowing us to compare pointers rather than characters 30 * to see if two strings are equal. 31 * 32 */ 33 34 #pragma ident "%Z%%M% %I% %E% SMI" 35 36 #include <stdio.h> 37 #include <strings.h> 38 #include "alloc.h" 39 #include "out.h" 40 #include "stats.h" 41 #include "stable.h" 42 43 #define MINPTR_ALIGN sizeof (char *) /* alignment boundary for pointers */ 44 #define DEF_HASH_SIZE 11113 /* default hash table size */ 45 #define CHUNK_SIZE 8192 /* grab more memory with this chunk size */ 46 47 static char **Stable; /* the hash table */ 48 static unsigned Stablesz; 49 static char *Stableblock; 50 static char *Stablenext; 51 52 static struct stats *Stablecount; 53 static struct stats *Blockcount; 54 static struct stats *Add0; 55 static struct stats *Add1; 56 static struct stats *Add2; 57 static struct stats *Add3; 58 static struct stats *Addn; 59 60 struct chunklst { 61 struct chunklst *next; 62 char *chunkp; 63 }; 64 65 struct chunklst *Stablechunks; 66 67 /* 68 * stable_init -- initialize the stable module 69 * 70 * hash table is sized according to sz. sz of zero means pick 71 * reasonable default size. 72 */ 73 74 void 75 stable_init(unsigned sz) 76 { 77 /* allocate hash table */ 78 if (sz == 0) 79 Stablesz = DEF_HASH_SIZE; 80 else 81 Stablesz = sz; 82 83 Stable = MALLOC(Stablesz * sizeof (*Stable)); 84 bzero((void *)Stable, Stablesz * sizeof (*Stable)); 85 86 Stablecount = stats_new_counter("stable.size", "hash table size", 1); 87 Blockcount = stats_new_counter("stable.blocks", "blocks allocated", 1); 88 Add0 = stats_new_counter("stable.add0", "adds to empty buckets", 1); 89 Add1 = stats_new_counter("stable.add1", "adds to 1-entry buckets", 1); 90 Add2 = stats_new_counter("stable.add2", "adds to 2-entry buckets", 1); 91 Add3 = stats_new_counter("stable.add3", "adds to 3-entry buckets", 1); 92 Addn = stats_new_counter("stable.addn", "adds to n-entry buckets", 1); 93 94 stats_counter_add(Stablecount, Stablesz); 95 } 96 97 void 98 stable_fini(void) 99 { 100 struct chunklst *cp, *nc; 101 102 stats_delete(Stablecount); 103 stats_delete(Blockcount); 104 stats_delete(Add0); 105 stats_delete(Add1); 106 stats_delete(Add2); 107 stats_delete(Add3); 108 stats_delete(Addn); 109 110 FREE(Stable); 111 cp = Stablechunks; 112 nc = NULL; 113 while (cp != NULL) { 114 nc = cp->next; 115 FREE(cp->chunkp); 116 FREE(cp); 117 cp = nc; 118 } 119 Stablechunks = NULL; 120 } 121 122 static char * 123 stable_newchunk(void) 124 { 125 struct chunklst *save = Stablechunks; 126 char *n; 127 128 n = MALLOC(CHUNK_SIZE); 129 bzero((void *)n, CHUNK_SIZE); 130 stats_counter_bump(Blockcount); 131 132 Stablechunks = MALLOC(sizeof (struct chunklst)); 133 Stablechunks->next = save; 134 Stablechunks->chunkp = n; 135 return (n); 136 } 137 138 /* 139 * stable -- create/lookup a string table entry 140 */ 141 142 const char * 143 stable(const char *s) 144 { 145 unsigned slen = 0; 146 unsigned hash = DEF_HASH_SIZE ^ ((unsigned)*s << 2); 147 char **ptrp; 148 char *ptr; 149 char *eptr; 150 const char *sptr; 151 int collisions = 0; 152 153 if (Stablesz == 0) 154 out(O_DIE, "internal error: Stablesz not set"); 155 156 for (sptr = &s[1]; *sptr; sptr++) { 157 slen++; 158 hash ^= (((unsigned)*sptr) << (slen % 3)) + 159 ((unsigned)*(sptr - 1) << ((slen % 3 + 7))); 160 } 161 hash ^= slen; 162 if (slen > CHUNK_SIZE - sizeof (char *) - 1 - 4) 163 out(O_DIE, "too big for string table %.20s...", s); 164 hash %= Stablesz; 165 166 ptrp = &Stable[hash]; 167 ptr = *ptrp; 168 while (ptr) { 169 /* hash brought us to something, see if it is the string */ 170 sptr = s; 171 eptr = ptr; 172 while (*sptr && *eptr && *sptr++ == *eptr++) 173 ; 174 if (*sptr == '\0' && *eptr == '\0') 175 return (ptr); /* found it */ 176 /* strings didn't match, advance eptr to end of string */ 177 while (*eptr) 178 eptr++; 179 eptr++; /* move past '\0' */ 180 while ((unsigned)eptr % MINPTR_ALIGN) 181 eptr++; 182 /* pull in next pointer in bucket */ 183 ptrp = (char **)(void *)eptr; 184 ptr = *ptrp; 185 collisions++; 186 } 187 188 /* string wasn't in table, add it and point ptr to it */ 189 if (Stablenext == NULL || (&Stableblock[CHUNK_SIZE] - Stablenext) < 190 (slen + sizeof (char *) + MINPTR_ALIGN + 4)) { 191 /* need more room */ 192 Stablenext = Stableblock = stable_newchunk(); 193 } 194 /* current chunk has room in it */ 195 ptr = *ptrp = Stablenext; 196 sptr = s; 197 while (*Stablenext++ = *sptr++) 198 ; 199 while ((unsigned)Stablenext % MINPTR_ALIGN) 200 Stablenext++; 201 ptrp = (char **)(void *)Stablenext; 202 Stablenext += sizeof (char *); 203 *ptrp = NULL; 204 205 /* just did an add, update stats */ 206 if (collisions == 0) 207 stats_counter_bump(Add0); 208 else if (collisions == 1) 209 stats_counter_bump(Add1); 210 else if (collisions == 2) 211 stats_counter_bump(Add2); 212 else if (collisions == 3) 213 stats_counter_bump(Add3); 214 else 215 stats_counter_bump(Addn); 216 217 return (ptr); 218 } 219