17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*837416c3Scy152378 * Common Development and Distribution License (the "License").
6*837416c3Scy152378 * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate /*
22*837416c3Scy152378 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
237c478bd9Sstevel@tonic-gate * Use is subject to license terms.
247c478bd9Sstevel@tonic-gate *
257c478bd9Sstevel@tonic-gate * stable.c -- string table module
267c478bd9Sstevel@tonic-gate *
277c478bd9Sstevel@tonic-gate * simple string table module. all read-only strings are entered in
287c478bd9Sstevel@tonic-gate * this table, allowing us to compare pointers rather than characters
297c478bd9Sstevel@tonic-gate * to see if two strings are equal.
307c478bd9Sstevel@tonic-gate *
317c478bd9Sstevel@tonic-gate */
327c478bd9Sstevel@tonic-gate
337c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
347c478bd9Sstevel@tonic-gate
357c478bd9Sstevel@tonic-gate #include <stdio.h>
367c478bd9Sstevel@tonic-gate #include <strings.h>
377c478bd9Sstevel@tonic-gate #include "alloc.h"
387c478bd9Sstevel@tonic-gate #include "out.h"
397c478bd9Sstevel@tonic-gate #include "stats.h"
407c478bd9Sstevel@tonic-gate #include "stable.h"
417c478bd9Sstevel@tonic-gate
427c478bd9Sstevel@tonic-gate #define MINPTR_ALIGN sizeof (char *) /* alignment boundary for pointers */
437c478bd9Sstevel@tonic-gate #define DEF_HASH_SIZE 11113 /* default hash table size */
447c478bd9Sstevel@tonic-gate #define CHUNK_SIZE 8192 /* grab more memory with this chunk size */
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate static char **Stable; /* the hash table */
477c478bd9Sstevel@tonic-gate static unsigned Stablesz;
487c478bd9Sstevel@tonic-gate static char *Stableblock;
497c478bd9Sstevel@tonic-gate static char *Stablenext;
507c478bd9Sstevel@tonic-gate
517c478bd9Sstevel@tonic-gate static struct stats *Stablecount;
527c478bd9Sstevel@tonic-gate static struct stats *Blockcount;
537c478bd9Sstevel@tonic-gate static struct stats *Add0;
547c478bd9Sstevel@tonic-gate static struct stats *Add1;
557c478bd9Sstevel@tonic-gate static struct stats *Add2;
567c478bd9Sstevel@tonic-gate static struct stats *Add3;
577c478bd9Sstevel@tonic-gate static struct stats *Addn;
587c478bd9Sstevel@tonic-gate
597c478bd9Sstevel@tonic-gate struct chunklst {
607c478bd9Sstevel@tonic-gate struct chunklst *next;
617c478bd9Sstevel@tonic-gate char *chunkp;
627c478bd9Sstevel@tonic-gate };
637c478bd9Sstevel@tonic-gate
647c478bd9Sstevel@tonic-gate struct chunklst *Stablechunks;
657c478bd9Sstevel@tonic-gate
667c478bd9Sstevel@tonic-gate /*
677c478bd9Sstevel@tonic-gate * stable_init -- initialize the stable module
687c478bd9Sstevel@tonic-gate *
697c478bd9Sstevel@tonic-gate * hash table is sized according to sz. sz of zero means pick
707c478bd9Sstevel@tonic-gate * reasonable default size.
717c478bd9Sstevel@tonic-gate */
727c478bd9Sstevel@tonic-gate
737c478bd9Sstevel@tonic-gate void
stable_init(unsigned sz)747c478bd9Sstevel@tonic-gate stable_init(unsigned sz)
757c478bd9Sstevel@tonic-gate {
767c478bd9Sstevel@tonic-gate /* allocate hash table */
777c478bd9Sstevel@tonic-gate if (sz == 0)
787c478bd9Sstevel@tonic-gate Stablesz = DEF_HASH_SIZE;
797c478bd9Sstevel@tonic-gate else
807c478bd9Sstevel@tonic-gate Stablesz = sz;
817c478bd9Sstevel@tonic-gate
827c478bd9Sstevel@tonic-gate Stable = MALLOC(Stablesz * sizeof (*Stable));
837c478bd9Sstevel@tonic-gate bzero((void *)Stable, Stablesz * sizeof (*Stable));
847c478bd9Sstevel@tonic-gate
857c478bd9Sstevel@tonic-gate Stablecount = stats_new_counter("stable.size", "hash table size", 1);
867c478bd9Sstevel@tonic-gate Blockcount = stats_new_counter("stable.blocks", "blocks allocated", 1);
877c478bd9Sstevel@tonic-gate Add0 = stats_new_counter("stable.add0", "adds to empty buckets", 1);
887c478bd9Sstevel@tonic-gate Add1 = stats_new_counter("stable.add1", "adds to 1-entry buckets", 1);
897c478bd9Sstevel@tonic-gate Add2 = stats_new_counter("stable.add2", "adds to 2-entry buckets", 1);
907c478bd9Sstevel@tonic-gate Add3 = stats_new_counter("stable.add3", "adds to 3-entry buckets", 1);
917c478bd9Sstevel@tonic-gate Addn = stats_new_counter("stable.addn", "adds to n-entry buckets", 1);
927c478bd9Sstevel@tonic-gate
937c478bd9Sstevel@tonic-gate stats_counter_add(Stablecount, Stablesz);
947c478bd9Sstevel@tonic-gate }
957c478bd9Sstevel@tonic-gate
967c478bd9Sstevel@tonic-gate void
stable_fini(void)977c478bd9Sstevel@tonic-gate stable_fini(void)
987c478bd9Sstevel@tonic-gate {
997c478bd9Sstevel@tonic-gate struct chunklst *cp, *nc;
1007c478bd9Sstevel@tonic-gate
1017c478bd9Sstevel@tonic-gate stats_delete(Stablecount);
1027c478bd9Sstevel@tonic-gate stats_delete(Blockcount);
1037c478bd9Sstevel@tonic-gate stats_delete(Add0);
1047c478bd9Sstevel@tonic-gate stats_delete(Add1);
1057c478bd9Sstevel@tonic-gate stats_delete(Add2);
1067c478bd9Sstevel@tonic-gate stats_delete(Add3);
1077c478bd9Sstevel@tonic-gate stats_delete(Addn);
1087c478bd9Sstevel@tonic-gate
1097c478bd9Sstevel@tonic-gate FREE(Stable);
1107c478bd9Sstevel@tonic-gate cp = Stablechunks;
1117c478bd9Sstevel@tonic-gate nc = NULL;
1127c478bd9Sstevel@tonic-gate while (cp != NULL) {
1137c478bd9Sstevel@tonic-gate nc = cp->next;
1147c478bd9Sstevel@tonic-gate FREE(cp->chunkp);
1157c478bd9Sstevel@tonic-gate FREE(cp);
1167c478bd9Sstevel@tonic-gate cp = nc;
1177c478bd9Sstevel@tonic-gate }
1187c478bd9Sstevel@tonic-gate Stablechunks = NULL;
1197c478bd9Sstevel@tonic-gate }
1207c478bd9Sstevel@tonic-gate
1217c478bd9Sstevel@tonic-gate static char *
stable_newchunk(void)1227c478bd9Sstevel@tonic-gate stable_newchunk(void)
1237c478bd9Sstevel@tonic-gate {
1247c478bd9Sstevel@tonic-gate struct chunklst *save = Stablechunks;
1257c478bd9Sstevel@tonic-gate char *n;
1267c478bd9Sstevel@tonic-gate
1277c478bd9Sstevel@tonic-gate n = MALLOC(CHUNK_SIZE);
1287c478bd9Sstevel@tonic-gate bzero((void *)n, CHUNK_SIZE);
1297c478bd9Sstevel@tonic-gate stats_counter_bump(Blockcount);
1307c478bd9Sstevel@tonic-gate
1317c478bd9Sstevel@tonic-gate Stablechunks = MALLOC(sizeof (struct chunklst));
1327c478bd9Sstevel@tonic-gate Stablechunks->next = save;
1337c478bd9Sstevel@tonic-gate Stablechunks->chunkp = n;
1347c478bd9Sstevel@tonic-gate return (n);
1357c478bd9Sstevel@tonic-gate }
1367c478bd9Sstevel@tonic-gate
1377c478bd9Sstevel@tonic-gate /*
1387c478bd9Sstevel@tonic-gate * stable -- create/lookup a string table entry
1397c478bd9Sstevel@tonic-gate */
1407c478bd9Sstevel@tonic-gate
1417c478bd9Sstevel@tonic-gate const char *
stable(const char * s)1427c478bd9Sstevel@tonic-gate stable(const char *s)
1437c478bd9Sstevel@tonic-gate {
1447c478bd9Sstevel@tonic-gate unsigned slen = 0;
1457c478bd9Sstevel@tonic-gate unsigned hash = DEF_HASH_SIZE ^ ((unsigned)*s << 2);
1467c478bd9Sstevel@tonic-gate char **ptrp;
1477c478bd9Sstevel@tonic-gate char *ptr;
1487c478bd9Sstevel@tonic-gate char *eptr;
1497c478bd9Sstevel@tonic-gate const char *sptr;
1507c478bd9Sstevel@tonic-gate int collisions = 0;
1517c478bd9Sstevel@tonic-gate
1527c478bd9Sstevel@tonic-gate if (Stablesz == 0)
1537c478bd9Sstevel@tonic-gate out(O_DIE, "internal error: Stablesz not set");
1547c478bd9Sstevel@tonic-gate
1557c478bd9Sstevel@tonic-gate for (sptr = &s[1]; *sptr; sptr++) {
1567c478bd9Sstevel@tonic-gate slen++;
1577c478bd9Sstevel@tonic-gate hash ^= (((unsigned)*sptr) << (slen % 3)) +
1587c478bd9Sstevel@tonic-gate ((unsigned)*(sptr - 1) << ((slen % 3 + 7)));
1597c478bd9Sstevel@tonic-gate }
1607c478bd9Sstevel@tonic-gate hash ^= slen;
1617c478bd9Sstevel@tonic-gate if (slen > CHUNK_SIZE - sizeof (char *) - 1 - 4)
1627c478bd9Sstevel@tonic-gate out(O_DIE, "too big for string table %.20s...", s);
1637c478bd9Sstevel@tonic-gate hash %= Stablesz;
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate ptrp = &Stable[hash];
1667c478bd9Sstevel@tonic-gate ptr = *ptrp;
1677c478bd9Sstevel@tonic-gate while (ptr) {
1687c478bd9Sstevel@tonic-gate /* hash brought us to something, see if it is the string */
1697c478bd9Sstevel@tonic-gate sptr = s;
1707c478bd9Sstevel@tonic-gate eptr = ptr;
1717c478bd9Sstevel@tonic-gate while (*sptr && *eptr && *sptr++ == *eptr++)
1727c478bd9Sstevel@tonic-gate ;
1737c478bd9Sstevel@tonic-gate if (*sptr == '\0' && *eptr == '\0')
1747c478bd9Sstevel@tonic-gate return (ptr); /* found it */
1757c478bd9Sstevel@tonic-gate /* strings didn't match, advance eptr to end of string */
1767c478bd9Sstevel@tonic-gate while (*eptr)
1777c478bd9Sstevel@tonic-gate eptr++;
1787c478bd9Sstevel@tonic-gate eptr++; /* move past '\0' */
179*837416c3Scy152378 while ((uintptr_t)eptr % MINPTR_ALIGN)
1807c478bd9Sstevel@tonic-gate eptr++;
1817c478bd9Sstevel@tonic-gate /* pull in next pointer in bucket */
1827c478bd9Sstevel@tonic-gate ptrp = (char **)(void *)eptr;
1837c478bd9Sstevel@tonic-gate ptr = *ptrp;
1847c478bd9Sstevel@tonic-gate collisions++;
1857c478bd9Sstevel@tonic-gate }
1867c478bd9Sstevel@tonic-gate
1877c478bd9Sstevel@tonic-gate /* string wasn't in table, add it and point ptr to it */
1887c478bd9Sstevel@tonic-gate if (Stablenext == NULL || (&Stableblock[CHUNK_SIZE] - Stablenext) <
1897c478bd9Sstevel@tonic-gate (slen + sizeof (char *) + MINPTR_ALIGN + 4)) {
1907c478bd9Sstevel@tonic-gate /* need more room */
1917c478bd9Sstevel@tonic-gate Stablenext = Stableblock = stable_newchunk();
1927c478bd9Sstevel@tonic-gate }
1937c478bd9Sstevel@tonic-gate /* current chunk has room in it */
1947c478bd9Sstevel@tonic-gate ptr = *ptrp = Stablenext;
1957c478bd9Sstevel@tonic-gate sptr = s;
1967c478bd9Sstevel@tonic-gate while (*Stablenext++ = *sptr++)
1977c478bd9Sstevel@tonic-gate ;
198*837416c3Scy152378 while ((uintptr_t)Stablenext % MINPTR_ALIGN)
1997c478bd9Sstevel@tonic-gate Stablenext++;
2007c478bd9Sstevel@tonic-gate ptrp = (char **)(void *)Stablenext;
2017c478bd9Sstevel@tonic-gate Stablenext += sizeof (char *);
2027c478bd9Sstevel@tonic-gate *ptrp = NULL;
2037c478bd9Sstevel@tonic-gate
2047c478bd9Sstevel@tonic-gate /* just did an add, update stats */
2057c478bd9Sstevel@tonic-gate if (collisions == 0)
2067c478bd9Sstevel@tonic-gate stats_counter_bump(Add0);
2077c478bd9Sstevel@tonic-gate else if (collisions == 1)
2087c478bd9Sstevel@tonic-gate stats_counter_bump(Add1);
2097c478bd9Sstevel@tonic-gate else if (collisions == 2)
2107c478bd9Sstevel@tonic-gate stats_counter_bump(Add2);
2117c478bd9Sstevel@tonic-gate else if (collisions == 3)
2127c478bd9Sstevel@tonic-gate stats_counter_bump(Add3);
2137c478bd9Sstevel@tonic-gate else
2147c478bd9Sstevel@tonic-gate stats_counter_bump(Addn);
2157c478bd9Sstevel@tonic-gate
2167c478bd9Sstevel@tonic-gate return (ptr);
2177c478bd9Sstevel@tonic-gate }
218