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