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