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