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
41static void
42strtab_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
50void
51strtab_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
66void
67strtab_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
86static ulong_t
87strtab_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
106static int
107strtab_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
132static void
133strtab_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
154size_t
155strtab_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
200size_t
201strtab_size(const strtab_t *sp)
202{
203	return (sp->str_size);
204}
205
206ssize_t
207strtab_write(const strtab_t *sp,
208    ssize_t (*func)(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
230void
231strtab_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}
259