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, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright (c) 2001 by Sun Microsystems, Inc.
24 * All rights reserved.
25 */
26
27 #pragma ident "%Z%%M% %I% %E% SMI"
28
29 #include <sys/types.h>
30 #include <sys/sysmacros.h>
31 #include <strings.h>
32 #include <stdlib.h>
33 #include <stdio.h>
34
35 #include "strtab.h"
36 #include "memory.h"
37
38 #define STRTAB_HASHSZ 211 /* use a prime number of hash buckets */
39 #define STRTAB_BUFSZ (64 * 1024) /* use 64K data buffers by default */
40
41 static void
42 strtab_grow(strtab_t *sp)
43 {
44 sp->str_nbufs++;
45 sp->str_bufs = xrealloc(sp->str_bufs, sp->str_nbufs * sizeof (char *));
46 sp->str_ptr = xmalloc(sp->str_bufsz);
47 sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr;
48 }
49
50 void
51 strtab_create(strtab_t *sp)
52 {
53 sp->str_hash = xcalloc(STRTAB_HASHSZ * sizeof (strhash_t *));
54 sp->str_hashsz = STRTAB_HASHSZ;
55 sp->str_bufs = NULL;
56 sp->str_ptr = NULL;
57 sp->str_nbufs = 0;
58 sp->str_bufsz = STRTAB_BUFSZ;
59 sp->str_nstrs = 1;
60 sp->str_size = 1;
61
62 strtab_grow(sp);
63 *sp->str_ptr++ = '\0';
64 }
65
66 void
67 strtab_destroy(strtab_t *sp)
68 {
69 strhash_t *hp, *hq;
70 ulong_t i;
71
72 for (i = 0; i < sp->str_hashsz; i++) {
73 for (hp = sp->str_hash[i]; hp != NULL; hp = hq) {
74 hq = hp->str_next;
75 free(hp);
76 }
77 }
78
79 for (i = 0; i < sp->str_nbufs; i++)
80 free(sp->str_bufs[i]);
81
82 free(sp->str_hash);
83 free(sp->str_bufs);
84 }
85
86 static ulong_t
87 strtab_hash(const char *key, size_t *len)
88 {
89 ulong_t g, h = 0;
90 const char *p;
91 size_t n = 0;
92
93 for (p = key; *p != '\0'; p++, n++) {
94 h = (h << 4) + *p;
95
96 if ((g = (h & 0xf0000000)) != 0) {
97 h ^= (g >> 24);
98 h ^= g;
99 }
100 }
101
102 *len = n;
103 return (h);
104 }
105
106 static int
107 strtab_compare(strtab_t *sp, strhash_t *hp, const char *str, size_t len)
108 {
109 ulong_t b = hp->str_buf;
110 const char *buf = hp->str_data;
111 size_t resid, n;
112 int rv;
113
114 while (len != 0) {
115 if (buf == sp->str_bufs[b] + sp->str_bufsz)
116 buf = sp->str_bufs[++b];
117
118 resid = sp->str_bufs[b] + sp->str_bufsz - buf;
119 n = MIN(resid, len);
120
121 if ((rv = strncmp(buf, str, n)) != 0)
122 return (rv);
123
124 buf += n;
125 str += n;
126 len -= n;
127 }
128
129 return (0);
130 }
131
132 static void
133 strtab_copyin(strtab_t *sp, const char *str, size_t len)
134 {
135 ulong_t b = sp->str_nbufs - 1;
136 size_t resid, n;
137
138 while (len != 0) {
139 if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) {
140 strtab_grow(sp);
141 b++;
142 }
143
144 resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr;
145 n = MIN(resid, len);
146 bcopy(str, sp->str_ptr, n);
147
148 sp->str_ptr += n;
149 str += n;
150 len -= n;
151 }
152 }
153
154 size_t
155 strtab_insert(strtab_t *sp, const char *str)
156 {
157 strhash_t *hp;
158 size_t len;
159 ulong_t h;
160
161 if (str == NULL || str[0] == '\0')
162 return (0); /* we keep a \0 at offset 0 to simplify things */
163
164 h = strtab_hash(str, &len) % sp->str_hashsz;
165
166 /*
167 * If the string is already in our hash table, just return the offset
168 * of the existing string element and do not add a duplicate string.
169 */
170 for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) {
171 if (strtab_compare(sp, hp, str, len + 1) == 0)
172 return (hp->str_off);
173 }
174
175 /*
176 * Create a new hash bucket, initialize it, and insert it at the front
177 * of the hash chain for the appropriate bucket.
178 */
179 hp = xmalloc(sizeof (strhash_t));
180
181 hp->str_data = sp->str_ptr;
182 hp->str_buf = sp->str_nbufs - 1;
183 hp->str_off = sp->str_size;
184 hp->str_len = len;
185 hp->str_next = sp->str_hash[h];
186
187 sp->str_hash[h] = hp;
188
189 /*
190 * Now copy the string data into our buffer list, and then update
191 * the global counts of strings and bytes. Return str's byte offset.
192 */
193 strtab_copyin(sp, str, len + 1);
194 sp->str_nstrs++;
195 sp->str_size += len + 1;
196
197 return (hp->str_off);
198 }
199
200 size_t
201 strtab_size(const strtab_t *sp)
202 {
203 return (sp->str_size);
204 }
205
206 ssize_t
207 strtab_write(const strtab_t *sp,
208 ssize_t (*func)(const void *, size_t, void *), void *priv)
209 {
210 ssize_t res, total = 0;
211 ulong_t i;
212 size_t n;
213
214 for (i = 0; i < sp->str_nbufs; i++, total += res) {
215 if (i == sp->str_nbufs - 1)
216 n = sp->str_ptr - sp->str_bufs[i];
217 else
218 n = sp->str_bufsz;
219
220 if ((res = func(sp->str_bufs[i], n, priv)) <= 0)
221 break;
222 }
223
224 if (total == 0 && sp->str_size != 0)
225 return (-1);
226
227 return (total);
228 }
229
230 void
231 strtab_print(const strtab_t *sp)
232 {
233 const strhash_t *hp;
234 ulong_t i;
235
236 for (i = 0; i < sp->str_hashsz; i++) {
237 for (hp = sp->str_hash[i]; hp != NULL; hp = hp->str_next) {
238 const char *buf = hp->str_data;
239 ulong_t b = hp->str_buf;
240 size_t resid, len, n;
241
242 (void) printf("[%lu] %lu \"", (ulong_t)hp->str_off, b);
243
244 for (len = hp->str_len; len != 0; len -= n) {
245 if (buf == sp->str_bufs[b] + sp->str_bufsz)
246 buf = sp->str_bufs[++b];
247
248 resid = sp->str_bufs[b] + sp->str_bufsz - buf;
249 n = MIN(resid, len);
250
251 (void) printf("%.*s", (int)n, buf);
252 buf += n;
253 }
254
255 (void) printf("\"\n");
256 }
257 }
258 }