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