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/*
23 * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27#pragma ident	"@(#)dt_strtab.c	1.4	06/09/19 SMI"
28
29#if !defined(__APPLE__)
30#include <sys/types.h>
31#include <sys/sysmacros.h>
32#include <strings.h>
33#include <stdlib.h>
34#include <assert.h>
35#else /* is Apple Mac OS X */
36#include <sys/types.h>
37/* NOTHING */ /* In lieu of Solaris <sys/sysmacros.h> */
38#include <strings.h>
39#include <stdlib.h>
40#include <assert.h>
41#endif /* __APPLE__ */
42
43#include <dt_strtab.h>
44#include <dt_impl.h>
45
46static int
47dt_strtab_grow(dt_strtab_t *sp)
48{
49	char *ptr, **bufs;
50
51	if ((ptr = malloc(sp->str_bufsz)) == NULL)
52		return (-1);
53
54	bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *));
55
56	if (bufs == NULL) {
57		free(ptr);
58		return (-1);
59	}
60
61	sp->str_nbufs++;
62	sp->str_bufs = bufs;
63	sp->str_ptr = ptr;
64	sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr;
65
66	return (0);
67}
68
69dt_strtab_t *
70dt_strtab_create(size_t bufsz)
71{
72	dt_strtab_t *sp = malloc(sizeof (dt_strtab_t));
73	uint_t nbuckets = _dtrace_strbuckets;
74
75	assert(bufsz != 0);
76
77	if (sp == NULL)
78		return (NULL);
79
80	bzero(sp, sizeof (dt_strtab_t));
81	sp->str_hash = malloc(nbuckets * sizeof (dt_strhash_t *));
82
83	if (sp->str_hash == NULL)
84		goto err;
85
86	bzero(sp->str_hash, nbuckets * sizeof (dt_strhash_t *));
87	sp->str_hashsz = nbuckets;
88	sp->str_bufs = NULL;
89	sp->str_ptr = NULL;
90	sp->str_nbufs = 0;
91	sp->str_bufsz = bufsz;
92	sp->str_nstrs = 1;
93	sp->str_size = 1;
94
95	if (dt_strtab_grow(sp) == -1)
96		goto err;
97
98	*sp->str_ptr++ = '\0';
99	return (sp);
100
101err:
102	dt_strtab_destroy(sp);
103	return (NULL);
104}
105
106void
107dt_strtab_destroy(dt_strtab_t *sp)
108{
109	dt_strhash_t *hp, *hq;
110	ulong_t i;
111
112	for (i = 0; i < sp->str_hashsz; i++) {
113		for (hp = sp->str_hash[i]; hp != NULL; hp = hq) {
114			hq = hp->str_next;
115			free(hp);
116		}
117	}
118
119	for (i = 0; i < sp->str_nbufs; i++)
120		free(sp->str_bufs[i]);
121
122	if (sp->str_hash != NULL)
123		free(sp->str_hash);
124	if (sp->str_bufs != NULL)
125		free(sp->str_bufs);
126
127	free(sp);
128}
129
130ulong_t
131dt_strtab_hash(const char *key, size_t *len)
132{
133	ulong_t g, h = 0;
134	const char *p;
135	size_t n = 0;
136
137	for (p = key; *p != '\0'; p++, n++) {
138		h = (h << 4) + *p;
139
140		if ((g = (h & 0xf0000000)) != 0) {
141			h ^= (g >> 24);
142			h ^= g;
143		}
144	}
145
146	if (len != NULL)
147		*len = n;
148
149	return (h);
150}
151
152static int
153dt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp,
154    const char *str, size_t len)
155{
156	ulong_t b = hp->str_buf;
157	const char *buf = hp->str_data;
158	size_t resid, n;
159	int rv;
160
161	while (len != 0) {
162		if (buf == sp->str_bufs[b] + sp->str_bufsz)
163			buf = sp->str_bufs[++b];
164
165		resid = sp->str_bufs[b] + sp->str_bufsz - buf;
166		n = MIN(resid, len);
167
168		if ((rv = strncmp(buf, str, n)) != 0)
169			return (rv);
170
171		buf += n;
172		str += n;
173		len -= n;
174	}
175
176	return (0);
177}
178
179static int
180dt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len)
181{
182	char *old_p = sp->str_ptr;
183	ulong_t old_n = sp->str_nbufs;
184
185	ulong_t b = sp->str_nbufs - 1;
186	size_t resid, n;
187
188	while (len != 0) {
189		if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) {
190			if (dt_strtab_grow(sp) == -1)
191				goto err;
192			b++;
193		}
194
195		resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr;
196		n = MIN(resid, len);
197		bcopy(str, sp->str_ptr, n);
198
199		sp->str_ptr += n;
200		str += n;
201		len -= n;
202	}
203
204	return (0);
205
206err:
207	while (sp->str_nbufs != old_n)
208		free(sp->str_bufs[--sp->str_nbufs]);
209
210	sp->str_ptr = old_p;
211	return (-1);
212}
213
214ssize_t
215dt_strtab_index(dt_strtab_t *sp, const char *str)
216{
217	dt_strhash_t *hp;
218	size_t len;
219	ulong_t h;
220
221	if (str == NULL || str[0] == '\0')
222		return (0); /* we keep a \0 at offset 0 to simplify things */
223
224	h = dt_strtab_hash(str, &len) % sp->str_hashsz;
225
226	for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) {
227		if (dt_strtab_compare(sp, hp, str, len + 1) == 0)
228			return (hp->str_off);
229	}
230
231	return (-1);
232}
233
234ssize_t
235dt_strtab_insert(dt_strtab_t *sp, const char *str)
236{
237	dt_strhash_t *hp;
238	size_t len;
239	ssize_t off;
240	ulong_t h;
241
242	if ((off = dt_strtab_index(sp, str)) != -1)
243		return (off);
244
245	h = dt_strtab_hash(str, &len) % sp->str_hashsz;
246
247	/*
248	 * Create a new hash bucket, initialize it, and insert it at the front
249	 * of the hash chain for the appropriate bucket.
250	 */
251	if ((hp = malloc(sizeof (dt_strhash_t))) == NULL)
252		return (-1L);
253
254	hp->str_data = sp->str_ptr;
255	hp->str_buf = sp->str_nbufs - 1;
256	hp->str_off = sp->str_size;
257	hp->str_len = len;
258	hp->str_next = sp->str_hash[h];
259
260	/*
261	 * Now copy the string data into our buffer list, and then update
262	 * the global counts of strings and bytes.  Return str's byte offset.
263	 */
264	if (dt_strtab_copyin(sp, str, len + 1) == -1)
265		return (-1L);
266
267	sp->str_nstrs++;
268	sp->str_size += len + 1;
269	sp->str_hash[h] = hp;
270
271	return (hp->str_off);
272}
273
274size_t
275dt_strtab_size(const dt_strtab_t *sp)
276{
277	return (sp->str_size);
278}
279
280ssize_t
281dt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private)
282{
283	ssize_t res, total = 0;
284	ulong_t i;
285	size_t n;
286
287	for (i = 0; i < sp->str_nbufs; i++, total += res) {
288		if (i == sp->str_nbufs - 1)
289			n = sp->str_ptr - sp->str_bufs[i];
290		else
291			n = sp->str_bufsz;
292
293		if ((res = func(sp->str_bufs[i], n, total, private)) <= 0)
294			break;
295	}
296
297	if (total == 0 && sp->str_size != 0)
298		return (-1);
299
300	return (total);
301}
302