1178481Sjb/* 2178481Sjb * CDDL HEADER START 3178481Sjb * 4178481Sjb * The contents of this file are subject to the terms of the 5178481Sjb * Common Development and Distribution License, Version 1.0 only 6178481Sjb * (the "License"). You may not use this file except in compliance 7178481Sjb * with the License. 8178481Sjb * 9178481Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10178481Sjb * or http://www.opensolaris.org/os/licensing. 11178481Sjb * See the License for the specific language governing permissions 12178481Sjb * and limitations under the License. 13178481Sjb * 14178481Sjb * When distributing Covered Code, include this CDDL HEADER in each 15178481Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16178481Sjb * If applicable, add the following below this CDDL HEADER, with the 17178481Sjb * fields enclosed by brackets "[]" replaced with your own identifying 18178481Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 19178481Sjb * 20178481Sjb * CDDL HEADER END 21178481Sjb */ 22178481Sjb/* 23178481Sjb * Copyright (c) 2001 by Sun Microsystems, Inc. 24178481Sjb * All rights reserved. 25178481Sjb */ 26178481Sjb 27178481Sjb#pragma ident "%Z%%M% %I% %E% SMI" 28178481Sjb 29178481Sjb#include <sys/types.h> 30178481Sjb#include <sys/sysmacros.h> 31178481Sjb#include <strings.h> 32178481Sjb#include <stdlib.h> 33178481Sjb#include <stdio.h> 34178481Sjb 35178481Sjb#include "strtab.h" 36178481Sjb#include "memory.h" 37178481Sjb 38178481Sjb#define STRTAB_HASHSZ 211 /* use a prime number of hash buckets */ 39178481Sjb#define STRTAB_BUFSZ (64 * 1024) /* use 64K data buffers by default */ 40178481Sjb 41178481Sjbstatic void 42178481Sjbstrtab_grow(strtab_t *sp) 43178481Sjb{ 44178481Sjb sp->str_nbufs++; 45178481Sjb sp->str_bufs = xrealloc(sp->str_bufs, sp->str_nbufs * sizeof (char *)); 46178481Sjb sp->str_ptr = xmalloc(sp->str_bufsz); 47178481Sjb sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr; 48178481Sjb} 49178481Sjb 50178481Sjbvoid 51178481Sjbstrtab_create(strtab_t *sp) 52178481Sjb{ 53178481Sjb sp->str_hash = xcalloc(STRTAB_HASHSZ * sizeof (strhash_t *)); 54178481Sjb sp->str_hashsz = STRTAB_HASHSZ; 55178481Sjb sp->str_bufs = NULL; 56178481Sjb sp->str_ptr = NULL; 57178481Sjb sp->str_nbufs = 0; 58178481Sjb sp->str_bufsz = STRTAB_BUFSZ; 59178481Sjb sp->str_nstrs = 1; 60178481Sjb sp->str_size = 1; 61178481Sjb 62178481Sjb strtab_grow(sp); 63178481Sjb *sp->str_ptr++ = '\0'; 64178481Sjb} 65178481Sjb 66178481Sjbvoid 67178481Sjbstrtab_destroy(strtab_t *sp) 68178481Sjb{ 69178481Sjb strhash_t *hp, *hq; 70178481Sjb ulong_t i; 71178481Sjb 72178481Sjb for (i = 0; i < sp->str_hashsz; i++) { 73178481Sjb for (hp = sp->str_hash[i]; hp != NULL; hp = hq) { 74178481Sjb hq = hp->str_next; 75178481Sjb free(hp); 76178481Sjb } 77178481Sjb } 78178481Sjb 79178481Sjb for (i = 0; i < sp->str_nbufs; i++) 80178481Sjb free(sp->str_bufs[i]); 81178481Sjb 82178481Sjb free(sp->str_hash); 83178481Sjb free(sp->str_bufs); 84178481Sjb} 85178481Sjb 86178481Sjbstatic ulong_t 87178481Sjbstrtab_hash(const char *key, size_t *len) 88178481Sjb{ 89178481Sjb ulong_t g, h = 0; 90178481Sjb const char *p; 91178481Sjb size_t n = 0; 92178481Sjb 93178481Sjb for (p = key; *p != '\0'; p++, n++) { 94178481Sjb h = (h << 4) + *p; 95178481Sjb 96178481Sjb if ((g = (h & 0xf0000000)) != 0) { 97178481Sjb h ^= (g >> 24); 98178481Sjb h ^= g; 99178481Sjb } 100178481Sjb } 101178481Sjb 102178481Sjb *len = n; 103178481Sjb return (h); 104178481Sjb} 105178481Sjb 106178481Sjbstatic int 107178481Sjbstrtab_compare(strtab_t *sp, strhash_t *hp, const char *str, size_t len) 108178481Sjb{ 109178481Sjb ulong_t b = hp->str_buf; 110178481Sjb const char *buf = hp->str_data; 111178481Sjb size_t resid, n; 112178481Sjb int rv; 113178481Sjb 114178481Sjb while (len != 0) { 115178481Sjb if (buf == sp->str_bufs[b] + sp->str_bufsz) 116178481Sjb buf = sp->str_bufs[++b]; 117178481Sjb 118178481Sjb resid = sp->str_bufs[b] + sp->str_bufsz - buf; 119178481Sjb n = MIN(resid, len); 120178481Sjb 121178481Sjb if ((rv = strncmp(buf, str, n)) != 0) 122178481Sjb return (rv); 123178481Sjb 124178481Sjb buf += n; 125178481Sjb str += n; 126178481Sjb len -= n; 127178481Sjb } 128178481Sjb 129178481Sjb return (0); 130178481Sjb} 131178481Sjb 132178481Sjbstatic void 133178481Sjbstrtab_copyin(strtab_t *sp, const char *str, size_t len) 134178481Sjb{ 135178481Sjb ulong_t b = sp->str_nbufs - 1; 136178481Sjb size_t resid, n; 137178481Sjb 138178481Sjb while (len != 0) { 139178481Sjb if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) { 140178481Sjb strtab_grow(sp); 141178481Sjb b++; 142178481Sjb } 143178481Sjb 144178481Sjb resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr; 145178481Sjb n = MIN(resid, len); 146178481Sjb bcopy(str, sp->str_ptr, n); 147178481Sjb 148178481Sjb sp->str_ptr += n; 149178481Sjb str += n; 150178481Sjb len -= n; 151178481Sjb } 152178481Sjb} 153178481Sjb 154178481Sjbsize_t 155178481Sjbstrtab_insert(strtab_t *sp, const char *str) 156178481Sjb{ 157178481Sjb strhash_t *hp; 158178481Sjb size_t len; 159178481Sjb ulong_t h; 160178481Sjb 161178481Sjb if (str == NULL || str[0] == '\0') 162178481Sjb return (0); /* we keep a \0 at offset 0 to simplify things */ 163178481Sjb 164178481Sjb h = strtab_hash(str, &len) % sp->str_hashsz; 165178481Sjb 166178481Sjb /* 167178481Sjb * If the string is already in our hash table, just return the offset 168178481Sjb * of the existing string element and do not add a duplicate string. 169178481Sjb */ 170178481Sjb for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) { 171178481Sjb if (strtab_compare(sp, hp, str, len + 1) == 0) 172178481Sjb return (hp->str_off); 173178481Sjb } 174178481Sjb 175178481Sjb /* 176178481Sjb * Create a new hash bucket, initialize it, and insert it at the front 177178481Sjb * of the hash chain for the appropriate bucket. 178178481Sjb */ 179178481Sjb hp = xmalloc(sizeof (strhash_t)); 180178481Sjb 181178481Sjb hp->str_data = sp->str_ptr; 182178481Sjb hp->str_buf = sp->str_nbufs - 1; 183178481Sjb hp->str_off = sp->str_size; 184178481Sjb hp->str_len = len; 185178481Sjb hp->str_next = sp->str_hash[h]; 186178481Sjb 187178481Sjb sp->str_hash[h] = hp; 188178481Sjb 189178481Sjb /* 190178481Sjb * Now copy the string data into our buffer list, and then update 191178481Sjb * the global counts of strings and bytes. Return str's byte offset. 192178481Sjb */ 193178481Sjb strtab_copyin(sp, str, len + 1); 194178481Sjb sp->str_nstrs++; 195178481Sjb sp->str_size += len + 1; 196178481Sjb 197178481Sjb return (hp->str_off); 198178481Sjb} 199178481Sjb 200178481Sjbsize_t 201178481Sjbstrtab_size(const strtab_t *sp) 202178481Sjb{ 203178481Sjb return (sp->str_size); 204178481Sjb} 205178481Sjb 206178481Sjbssize_t 207178481Sjbstrtab_write(const strtab_t *sp, 208178546Sjb ssize_t (*func)(void *, size_t, void *), void *priv) 209178481Sjb{ 210178481Sjb ssize_t res, total = 0; 211178481Sjb ulong_t i; 212178481Sjb size_t n; 213178481Sjb 214178481Sjb for (i = 0; i < sp->str_nbufs; i++, total += res) { 215178481Sjb if (i == sp->str_nbufs - 1) 216178481Sjb n = sp->str_ptr - sp->str_bufs[i]; 217178481Sjb else 218178481Sjb n = sp->str_bufsz; 219178481Sjb 220178481Sjb if ((res = func(sp->str_bufs[i], n, priv)) <= 0) 221178481Sjb break; 222178481Sjb } 223178481Sjb 224178481Sjb if (total == 0 && sp->str_size != 0) 225178481Sjb return (-1); 226178481Sjb 227178481Sjb return (total); 228178481Sjb} 229178481Sjb 230178481Sjbvoid 231178481Sjbstrtab_print(const strtab_t *sp) 232178481Sjb{ 233178481Sjb const strhash_t *hp; 234178481Sjb ulong_t i; 235178481Sjb 236178481Sjb for (i = 0; i < sp->str_hashsz; i++) { 237178481Sjb for (hp = sp->str_hash[i]; hp != NULL; hp = hp->str_next) { 238178481Sjb const char *buf = hp->str_data; 239178481Sjb ulong_t b = hp->str_buf; 240178481Sjb size_t resid, len, n; 241178481Sjb 242178481Sjb (void) printf("[%lu] %lu \"", (ulong_t)hp->str_off, b); 243178481Sjb 244178481Sjb for (len = hp->str_len; len != 0; len -= n) { 245178481Sjb if (buf == sp->str_bufs[b] + sp->str_bufsz) 246178481Sjb buf = sp->str_bufs[++b]; 247178481Sjb 248178481Sjb resid = sp->str_bufs[b] + sp->str_bufsz - buf; 249178481Sjb n = MIN(resid, len); 250178481Sjb 251178481Sjb (void) printf("%.*s", (int)n, buf); 252178481Sjb buf += n; 253178481Sjb } 254178481Sjb 255178481Sjb (void) printf("\"\n"); 256178481Sjb } 257178481Sjb } 258178481Sjb} 259