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 #include <stdio.h> 34 #include <strings.h> 35 #include "alloc.h" 36 #include "out.h" 37 #include "stats.h" 38 #include "stable.h" 39 40 #define MINPTR_ALIGN sizeof (char *) /* alignment boundary for pointers */ 41 #define DEF_HASH_SIZE 11113 /* default hash table size */ 42 #define CHUNK_SIZE 8192 /* grab more memory with this chunk size */ 43 44 static char **Stable; /* the hash table */ 45 static unsigned Stablesz; 46 static char *Stableblock; 47 static char *Stablenext; 48 49 static struct stats *Stablecount; 50 static struct stats *Blockcount; 51 static struct stats *Add0; 52 static struct stats *Add1; 53 static struct stats *Add2; 54 static struct stats *Add3; 55 static struct stats *Addn; 56 57 struct chunklst { 58 struct chunklst *next; 59 char *chunkp; 60 }; 61 62 struct chunklst *Stablechunks; 63 64 /* 65 * stable_init -- initialize the stable module 66 * 67 * hash table is sized according to sz. sz of zero means pick 68 * reasonable default size. 69 */ 70 71 void 72 stable_init(unsigned sz) 73 { 74 /* allocate hash table */ 75 if (sz == 0) 76 Stablesz = DEF_HASH_SIZE; 77 else 78 Stablesz = sz; 79 80 Stable = MALLOC(Stablesz * sizeof (*Stable)); 81 bzero((void *)Stable, Stablesz * sizeof (*Stable)); 82 83 Stablecount = stats_new_counter("stable.size", "hash table size", 1); 84 Blockcount = stats_new_counter("stable.blocks", "blocks allocated", 1); 85 Add0 = stats_new_counter("stable.add0", "adds to empty buckets", 1); 86 Add1 = stats_new_counter("stable.add1", "adds to 1-entry buckets", 1); 87 Add2 = stats_new_counter("stable.add2", "adds to 2-entry buckets", 1); 88 Add3 = stats_new_counter("stable.add3", "adds to 3-entry buckets", 1); 89 Addn = stats_new_counter("stable.addn", "adds to n-entry buckets", 1); 90 91 stats_counter_add(Stablecount, Stablesz); 92 } 93 94 void 95 stable_fini(void) 96 { 97 struct chunklst *cp, *nc; 98 99 stats_delete(Stablecount); 100 stats_delete(Blockcount); 101 stats_delete(Add0); 102 stats_delete(Add1); 103 stats_delete(Add2); 104 stats_delete(Add3); 105 stats_delete(Addn); 106 107 FREE(Stable); 108 cp = Stablechunks; 109 nc = NULL; 110 while (cp != NULL) { 111 nc = cp->next; 112 FREE(cp->chunkp); 113 FREE(cp); 114 cp = nc; 115 } 116 Stablechunks = NULL; 117 } 118 119 static char * 120 stable_newchunk(void) 121 { 122 struct chunklst *save = Stablechunks; 123 char *n; 124 125 n = MALLOC(CHUNK_SIZE); 126 bzero((void *)n, CHUNK_SIZE); 127 stats_counter_bump(Blockcount); 128 129 Stablechunks = MALLOC(sizeof (struct chunklst)); 130 Stablechunks->next = save; 131 Stablechunks->chunkp = n; 132 return (n); 133 } 134 135 /* 136 * stable -- create/lookup a string table entry 137 */ 138 139 const char * 140 stable(const char *s) 141 { 142 unsigned slen = 0; 143 unsigned hash = DEF_HASH_SIZE ^ ((unsigned)*s << 2); 144 char **ptrp; 145 char *ptr; 146 char *eptr; 147 const char *sptr; 148 int collisions = 0; 149 150 if (Stablesz == 0) 151 out(O_DIE, "internal error: Stablesz not set"); 152 153 for (sptr = &s[1]; *sptr; sptr++) { 154 slen++; 155 hash ^= (((unsigned)*sptr) << (slen % 3)) + 156 ((unsigned)*(sptr - 1) << ((slen % 3 + 7))); 157 } 158 hash ^= slen; 159 if (slen > CHUNK_SIZE - sizeof (char *) - 1 - 4) 160 out(O_DIE, "too big for string table %.20s...", s); 161 hash %= Stablesz; 162 163 ptrp = &Stable[hash]; 164 ptr = *ptrp; 165 while (ptr) { 166 /* hash brought us to something, see if it is the string */ 167 sptr = s; 168 eptr = ptr; 169 while (*sptr && *eptr && *sptr++ == *eptr++) 170 ; 171 if (*sptr == '\0' && *eptr == '\0') 172 return (ptr); /* found it */ 173 /* strings didn't match, advance eptr to end of string */ 174 while (*eptr) 175 eptr++; 176 eptr++; /* move past '\0' */ 177 while ((uintptr_t)eptr % MINPTR_ALIGN) 178 eptr++; 179 /* pull in next pointer in bucket */ 180 ptrp = (char **)(void *)eptr; 181 ptr = *ptrp; 182 collisions++; 183 } 184 185 /* string wasn't in table, add it and point ptr to it */ 186 if (Stablenext == NULL || (&Stableblock[CHUNK_SIZE] - Stablenext) < 187 (slen + sizeof (char *) + MINPTR_ALIGN + 4)) { 188 /* need more room */ 189 Stablenext = Stableblock = stable_newchunk(); 190 } 191 /* current chunk has room in it */ 192 ptr = *ptrp = Stablenext; 193 sptr = s; 194 while (*Stablenext++ = *sptr++) 195 ; 196 while ((uintptr_t)Stablenext % MINPTR_ALIGN) 197 Stablenext++; 198 ptrp = (char **)(void *)Stablenext; 199 Stablenext += sizeof (char *); 200 *ptrp = NULL; 201 202 /* just did an add, update stats */ 203 if (collisions == 0) 204 stats_counter_bump(Add0); 205 else if (collisions == 1) 206 stats_counter_bump(Add1); 207 else if (collisions == 2) 208 stats_counter_bump(Add2); 209 else if (collisions == 3) 210 stats_counter_bump(Add3); 211 else 212 stats_counter_bump(Addn); 213 214 return (ptr); 215 } 216