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
stable_init(unsigned sz)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
stable_fini(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 *
stable_newchunk(void)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 *
stable(const char * s)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