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