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