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