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