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