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 #include <stdio.h>
347c478bd9Sstevel@tonic-gate #include <strings.h>
357c478bd9Sstevel@tonic-gate #include "alloc.h"
367c478bd9Sstevel@tonic-gate #include "out.h"
377c478bd9Sstevel@tonic-gate #include "stats.h"
387c478bd9Sstevel@tonic-gate #include "stable.h"
397c478bd9Sstevel@tonic-gate
407c478bd9Sstevel@tonic-gate #define MINPTR_ALIGN sizeof (char *) /* alignment boundary for pointers */
417c478bd9Sstevel@tonic-gate #define DEF_HASH_SIZE 11113 /* default hash table size */
427c478bd9Sstevel@tonic-gate #define CHUNK_SIZE 8192 /* grab more memory with this chunk size */
437c478bd9Sstevel@tonic-gate
447c478bd9Sstevel@tonic-gate static char **Stable; /* the hash table */
457c478bd9Sstevel@tonic-gate static unsigned Stablesz;
467c478bd9Sstevel@tonic-gate static char *Stableblock;
477c478bd9Sstevel@tonic-gate static char *Stablenext;
487c478bd9Sstevel@tonic-gate
497c478bd9Sstevel@tonic-gate static struct stats *Stablecount;
507c478bd9Sstevel@tonic-gate static struct stats *Blockcount;
517c478bd9Sstevel@tonic-gate static struct stats *Add0;
527c478bd9Sstevel@tonic-gate static struct stats *Add1;
537c478bd9Sstevel@tonic-gate static struct stats *Add2;
547c478bd9Sstevel@tonic-gate static struct stats *Add3;
557c478bd9Sstevel@tonic-gate static struct stats *Addn;
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate struct chunklst {
587c478bd9Sstevel@tonic-gate struct chunklst *next;
597c478bd9Sstevel@tonic-gate char *chunkp;
607c478bd9Sstevel@tonic-gate };
617c478bd9Sstevel@tonic-gate
627c478bd9Sstevel@tonic-gate struct chunklst *Stablechunks;
637c478bd9Sstevel@tonic-gate
647c478bd9Sstevel@tonic-gate /*
657c478bd9Sstevel@tonic-gate * stable_init -- initialize the stable module
667c478bd9Sstevel@tonic-gate *
677c478bd9Sstevel@tonic-gate * hash table is sized according to sz. sz of zero means pick
687c478bd9Sstevel@tonic-gate * reasonable default size.
697c478bd9Sstevel@tonic-gate */
707c478bd9Sstevel@tonic-gate
717c478bd9Sstevel@tonic-gate void
stable_init(unsigned sz)727c478bd9Sstevel@tonic-gate stable_init(unsigned sz)
737c478bd9Sstevel@tonic-gate {
747c478bd9Sstevel@tonic-gate /* allocate hash table */
757c478bd9Sstevel@tonic-gate if (sz == 0)
767c478bd9Sstevel@tonic-gate Stablesz = DEF_HASH_SIZE;
777c478bd9Sstevel@tonic-gate else
787c478bd9Sstevel@tonic-gate Stablesz = sz;
797c478bd9Sstevel@tonic-gate
807c478bd9Sstevel@tonic-gate Stable = MALLOC(Stablesz * sizeof (*Stable));
817c478bd9Sstevel@tonic-gate bzero((void *)Stable, Stablesz * sizeof (*Stable));
827c478bd9Sstevel@tonic-gate
837c478bd9Sstevel@tonic-gate Stablecount = stats_new_counter("stable.size", "hash table size", 1);
847c478bd9Sstevel@tonic-gate Blockcount = stats_new_counter("stable.blocks", "blocks allocated", 1);
857c478bd9Sstevel@tonic-gate Add0 = stats_new_counter("stable.add0", "adds to empty buckets", 1);
867c478bd9Sstevel@tonic-gate Add1 = stats_new_counter("stable.add1", "adds to 1-entry buckets", 1);
877c478bd9Sstevel@tonic-gate Add2 = stats_new_counter("stable.add2", "adds to 2-entry buckets", 1);
887c478bd9Sstevel@tonic-gate Add3 = stats_new_counter("stable.add3", "adds to 3-entry buckets", 1);
897c478bd9Sstevel@tonic-gate Addn = stats_new_counter("stable.addn", "adds to n-entry buckets", 1);
907c478bd9Sstevel@tonic-gate
917c478bd9Sstevel@tonic-gate stats_counter_add(Stablecount, Stablesz);
927c478bd9Sstevel@tonic-gate }
937c478bd9Sstevel@tonic-gate
947c478bd9Sstevel@tonic-gate void
stable_fini(void)957c478bd9Sstevel@tonic-gate stable_fini(void)
967c478bd9Sstevel@tonic-gate {
977c478bd9Sstevel@tonic-gate struct chunklst *cp, *nc;
987c478bd9Sstevel@tonic-gate
997c478bd9Sstevel@tonic-gate stats_delete(Stablecount);
1007c478bd9Sstevel@tonic-gate stats_delete(Blockcount);
1017c478bd9Sstevel@tonic-gate stats_delete(Add0);
1027c478bd9Sstevel@tonic-gate stats_delete(Add1);
1037c478bd9Sstevel@tonic-gate stats_delete(Add2);
1047c478bd9Sstevel@tonic-gate stats_delete(Add3);
1057c478bd9Sstevel@tonic-gate stats_delete(Addn);
1067c478bd9Sstevel@tonic-gate
1077c478bd9Sstevel@tonic-gate FREE(Stable);
1087c478bd9Sstevel@tonic-gate cp = Stablechunks;
1097c478bd9Sstevel@tonic-gate nc = NULL;
1107c478bd9Sstevel@tonic-gate while (cp != NULL) {
1117c478bd9Sstevel@tonic-gate nc = cp->next;
1127c478bd9Sstevel@tonic-gate FREE(cp->chunkp);
1137c478bd9Sstevel@tonic-gate FREE(cp);
1147c478bd9Sstevel@tonic-gate cp = nc;
1157c478bd9Sstevel@tonic-gate }
1167c478bd9Sstevel@tonic-gate Stablechunks = NULL;
1177c478bd9Sstevel@tonic-gate }
1187c478bd9Sstevel@tonic-gate
1197c478bd9Sstevel@tonic-gate static char *
stable_newchunk(void)1207c478bd9Sstevel@tonic-gate stable_newchunk(void)
1217c478bd9Sstevel@tonic-gate {
1227c478bd9Sstevel@tonic-gate struct chunklst *save = Stablechunks;
1237c478bd9Sstevel@tonic-gate char *n;
1247c478bd9Sstevel@tonic-gate
1257c478bd9Sstevel@tonic-gate n = MALLOC(CHUNK_SIZE);
1267c478bd9Sstevel@tonic-gate bzero((void *)n, CHUNK_SIZE);
1277c478bd9Sstevel@tonic-gate stats_counter_bump(Blockcount);
1287c478bd9Sstevel@tonic-gate
1297c478bd9Sstevel@tonic-gate Stablechunks = MALLOC(sizeof (struct chunklst));
1307c478bd9Sstevel@tonic-gate Stablechunks->next = save;
1317c478bd9Sstevel@tonic-gate Stablechunks->chunkp = n;
1327c478bd9Sstevel@tonic-gate return (n);
1337c478bd9Sstevel@tonic-gate }
1347c478bd9Sstevel@tonic-gate
1357c478bd9Sstevel@tonic-gate /*
1367c478bd9Sstevel@tonic-gate * stable -- create/lookup a string table entry
1377c478bd9Sstevel@tonic-gate */
1387c478bd9Sstevel@tonic-gate
1397c478bd9Sstevel@tonic-gate const char *
stable(const char * s)1407c478bd9Sstevel@tonic-gate stable(const char *s)
1417c478bd9Sstevel@tonic-gate {
1427c478bd9Sstevel@tonic-gate unsigned slen = 0;
1437c478bd9Sstevel@tonic-gate unsigned hash = DEF_HASH_SIZE ^ ((unsigned)*s << 2);
1447c478bd9Sstevel@tonic-gate char **ptrp;
1457c478bd9Sstevel@tonic-gate char *ptr;
1467c478bd9Sstevel@tonic-gate char *eptr;
1477c478bd9Sstevel@tonic-gate const char *sptr;
1487c478bd9Sstevel@tonic-gate int collisions = 0;
1497c478bd9Sstevel@tonic-gate
1507c478bd9Sstevel@tonic-gate if (Stablesz == 0)
1517c478bd9Sstevel@tonic-gate out(O_DIE, "internal error: Stablesz not set");
1527c478bd9Sstevel@tonic-gate
1537c478bd9Sstevel@tonic-gate for (sptr = &s[1]; *sptr; sptr++) {
1547c478bd9Sstevel@tonic-gate slen++;
1557c478bd9Sstevel@tonic-gate hash ^= (((unsigned)*sptr) << (slen % 3)) +
1567c478bd9Sstevel@tonic-gate ((unsigned)*(sptr - 1) << ((slen % 3 + 7)));
1577c478bd9Sstevel@tonic-gate }
1587c478bd9Sstevel@tonic-gate hash ^= slen;
1597c478bd9Sstevel@tonic-gate if (slen > CHUNK_SIZE - sizeof (char *) - 1 - 4)
1607c478bd9Sstevel@tonic-gate out(O_DIE, "too big for string table %.20s...", s);
1617c478bd9Sstevel@tonic-gate hash %= Stablesz;
1627c478bd9Sstevel@tonic-gate
1637c478bd9Sstevel@tonic-gate ptrp = &Stable[hash];
1647c478bd9Sstevel@tonic-gate ptr = *ptrp;
1657c478bd9Sstevel@tonic-gate while (ptr) {
1667c478bd9Sstevel@tonic-gate /* hash brought us to something, see if it is the string */
1677c478bd9Sstevel@tonic-gate sptr = s;
1687c478bd9Sstevel@tonic-gate eptr = ptr;
1697c478bd9Sstevel@tonic-gate while (*sptr && *eptr && *sptr++ == *eptr++)
1707c478bd9Sstevel@tonic-gate ;
1717c478bd9Sstevel@tonic-gate if (*sptr == '\0' && *eptr == '\0')
1727c478bd9Sstevel@tonic-gate return (ptr); /* found it */
1737c478bd9Sstevel@tonic-gate /* strings didn't match, advance eptr to end of string */
1747c478bd9Sstevel@tonic-gate while (*eptr)
1757c478bd9Sstevel@tonic-gate eptr++;
1767c478bd9Sstevel@tonic-gate eptr++; /* move past '\0' */
177*837416c3Scy152378 while ((uintptr_t)eptr % MINPTR_ALIGN)
1787c478bd9Sstevel@tonic-gate eptr++;
1797c478bd9Sstevel@tonic-gate /* pull in next pointer in bucket */
1807c478bd9Sstevel@tonic-gate ptrp = (char **)(void *)eptr;
1817c478bd9Sstevel@tonic-gate ptr = *ptrp;
1827c478bd9Sstevel@tonic-gate collisions++;
1837c478bd9Sstevel@tonic-gate }
1847c478bd9Sstevel@tonic-gate
1857c478bd9Sstevel@tonic-gate /* string wasn't in table, add it and point ptr to it */
1867c478bd9Sstevel@tonic-gate if (Stablenext == NULL || (&Stableblock[CHUNK_SIZE] - Stablenext) <
1877c478bd9Sstevel@tonic-gate (slen + sizeof (char *) + MINPTR_ALIGN + 4)) {
1887c478bd9Sstevel@tonic-gate /* need more room */
1897c478bd9Sstevel@tonic-gate Stablenext = Stableblock = stable_newchunk();
1907c478bd9Sstevel@tonic-gate }
1917c478bd9Sstevel@tonic-gate /* current chunk has room in it */
1927c478bd9Sstevel@tonic-gate ptr = *ptrp = Stablenext;
1937c478bd9Sstevel@tonic-gate sptr = s;
1947c478bd9Sstevel@tonic-gate while (*Stablenext++ = *sptr++)
1957c478bd9Sstevel@tonic-gate ;
196*837416c3Scy152378 while ((uintptr_t)Stablenext % MINPTR_ALIGN)
1977c478bd9Sstevel@tonic-gate Stablenext++;
1987c478bd9Sstevel@tonic-gate ptrp = (char **)(void *)Stablenext;
1997c478bd9Sstevel@tonic-gate Stablenext += sizeof (char *);
2007c478bd9Sstevel@tonic-gate *ptrp = NULL;
2017c478bd9Sstevel@tonic-gate
2027c478bd9Sstevel@tonic-gate /* just did an add, update stats */
2037c478bd9Sstevel@tonic-gate if (collisions == 0)
2047c478bd9Sstevel@tonic-gate stats_counter_bump(Add0);
2057c478bd9Sstevel@tonic-gate else if (collisions == 1)
2067c478bd9Sstevel@tonic-gate stats_counter_bump(Add1);
2077c478bd9Sstevel@tonic-gate else if (collisions == 2)
2087c478bd9Sstevel@tonic-gate stats_counter_bump(Add2);
2097c478bd9Sstevel@tonic-gate else if (collisions == 3)
2107c478bd9Sstevel@tonic-gate stats_counter_bump(Add3);
2117c478bd9Sstevel@tonic-gate else
2127c478bd9Sstevel@tonic-gate stats_counter_bump(Addn);
2137c478bd9Sstevel@tonic-gate
2147c478bd9Sstevel@tonic-gate return (ptr);
2157c478bd9Sstevel@tonic-gate }
216