1178479Sjb/* 2178479Sjb * CDDL HEADER START 3178479Sjb * 4178479Sjb * The contents of this file are subject to the terms of the 5178479Sjb * Common Development and Distribution License (the "License"). 6178479Sjb * You may not use this file except in compliance with the License. 7178479Sjb * 8178479Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9178479Sjb * or http://www.opensolaris.org/os/licensing. 10178479Sjb * See the License for the specific language governing permissions 11178479Sjb * and limitations under the License. 12178479Sjb * 13178479Sjb * When distributing Covered Code, include this CDDL HEADER in each 14178479Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15178479Sjb * If applicable, add the following below this CDDL HEADER, with the 16178479Sjb * fields enclosed by brackets "[]" replaced with your own identifying 17178479Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 18178479Sjb * 19178479Sjb * CDDL HEADER END 20178479Sjb */ 21178479Sjb 22178479Sjb/* 23178479Sjb * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 24178479Sjb * Use is subject to license terms. 25178479Sjb */ 26178479Sjb 27178479Sjb#pragma ident "%Z%%M% %I% %E% SMI" 28178479Sjb 29178479Sjb#include <sys/types.h> 30178479Sjb#include <sys/sysmacros.h> 31178479Sjb#include <strings.h> 32178479Sjb#include <stdlib.h> 33178479Sjb#include <assert.h> 34178479Sjb 35178479Sjb#include <dt_strtab.h> 36178479Sjb#include <dt_impl.h> 37178479Sjb 38178479Sjbstatic int 39178479Sjbdt_strtab_grow(dt_strtab_t *sp) 40178479Sjb{ 41178479Sjb char *ptr, **bufs; 42178479Sjb 43178479Sjb if ((ptr = malloc(sp->str_bufsz)) == NULL) 44178479Sjb return (-1); 45178479Sjb 46178479Sjb bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *)); 47178479Sjb 48178479Sjb if (bufs == NULL) { 49178479Sjb free(ptr); 50178479Sjb return (-1); 51178479Sjb } 52178479Sjb 53178479Sjb sp->str_nbufs++; 54178479Sjb sp->str_bufs = bufs; 55178479Sjb sp->str_ptr = ptr; 56178479Sjb sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr; 57178479Sjb 58178479Sjb return (0); 59178479Sjb} 60178479Sjb 61178479Sjbdt_strtab_t * 62178479Sjbdt_strtab_create(size_t bufsz) 63178479Sjb{ 64178479Sjb dt_strtab_t *sp = malloc(sizeof (dt_strtab_t)); 65178479Sjb uint_t nbuckets = _dtrace_strbuckets; 66178479Sjb 67178479Sjb assert(bufsz != 0); 68178479Sjb 69178479Sjb if (sp == NULL) 70178479Sjb return (NULL); 71178479Sjb 72178479Sjb bzero(sp, sizeof (dt_strtab_t)); 73178479Sjb sp->str_hash = malloc(nbuckets * sizeof (dt_strhash_t *)); 74178479Sjb 75178479Sjb if (sp->str_hash == NULL) 76178479Sjb goto err; 77178479Sjb 78178479Sjb bzero(sp->str_hash, nbuckets * sizeof (dt_strhash_t *)); 79178479Sjb sp->str_hashsz = nbuckets; 80178479Sjb sp->str_bufs = NULL; 81178479Sjb sp->str_ptr = NULL; 82178479Sjb sp->str_nbufs = 0; 83178479Sjb sp->str_bufsz = bufsz; 84178479Sjb sp->str_nstrs = 1; 85178479Sjb sp->str_size = 1; 86178479Sjb 87178479Sjb if (dt_strtab_grow(sp) == -1) 88178479Sjb goto err; 89178479Sjb 90178479Sjb *sp->str_ptr++ = '\0'; 91178479Sjb return (sp); 92178479Sjb 93178479Sjberr: 94178479Sjb dt_strtab_destroy(sp); 95178479Sjb return (NULL); 96178479Sjb} 97178479Sjb 98178479Sjbvoid 99178479Sjbdt_strtab_destroy(dt_strtab_t *sp) 100178479Sjb{ 101178479Sjb dt_strhash_t *hp, *hq; 102178479Sjb ulong_t i; 103178479Sjb 104178479Sjb for (i = 0; i < sp->str_hashsz; i++) { 105178479Sjb for (hp = sp->str_hash[i]; hp != NULL; hp = hq) { 106178479Sjb hq = hp->str_next; 107178479Sjb free(hp); 108178479Sjb } 109178479Sjb } 110178479Sjb 111178479Sjb for (i = 0; i < sp->str_nbufs; i++) 112178479Sjb free(sp->str_bufs[i]); 113178479Sjb 114178479Sjb if (sp->str_hash != NULL) 115178479Sjb free(sp->str_hash); 116178479Sjb if (sp->str_bufs != NULL) 117178479Sjb free(sp->str_bufs); 118178479Sjb 119178479Sjb free(sp); 120178479Sjb} 121178479Sjb 122178479Sjbulong_t 123178479Sjbdt_strtab_hash(const char *key, size_t *len) 124178479Sjb{ 125178479Sjb ulong_t g, h = 0; 126178479Sjb const char *p; 127178479Sjb size_t n = 0; 128178479Sjb 129178479Sjb for (p = key; *p != '\0'; p++, n++) { 130178479Sjb h = (h << 4) + *p; 131178479Sjb 132178479Sjb if ((g = (h & 0xf0000000)) != 0) { 133178479Sjb h ^= (g >> 24); 134178479Sjb h ^= g; 135178479Sjb } 136178479Sjb } 137178479Sjb 138178479Sjb if (len != NULL) 139178479Sjb *len = n; 140178479Sjb 141178479Sjb return (h); 142178479Sjb} 143178479Sjb 144178479Sjbstatic int 145178479Sjbdt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp, 146178479Sjb const char *str, size_t len) 147178479Sjb{ 148178479Sjb ulong_t b = hp->str_buf; 149178479Sjb const char *buf = hp->str_data; 150178479Sjb size_t resid, n; 151178479Sjb int rv; 152178479Sjb 153178479Sjb while (len != 0) { 154178479Sjb if (buf == sp->str_bufs[b] + sp->str_bufsz) 155178479Sjb buf = sp->str_bufs[++b]; 156178479Sjb 157178479Sjb resid = sp->str_bufs[b] + sp->str_bufsz - buf; 158178479Sjb n = MIN(resid, len); 159178479Sjb 160178479Sjb if ((rv = strncmp(buf, str, n)) != 0) 161178479Sjb return (rv); 162178479Sjb 163178479Sjb buf += n; 164178479Sjb str += n; 165178479Sjb len -= n; 166178479Sjb } 167178479Sjb 168178479Sjb return (0); 169178479Sjb} 170178479Sjb 171178479Sjbstatic int 172178479Sjbdt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len) 173178479Sjb{ 174178479Sjb char *old_p = sp->str_ptr; 175178479Sjb ulong_t old_n = sp->str_nbufs; 176178479Sjb 177178479Sjb ulong_t b = sp->str_nbufs - 1; 178178479Sjb size_t resid, n; 179178479Sjb 180178479Sjb while (len != 0) { 181178479Sjb if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) { 182178479Sjb if (dt_strtab_grow(sp) == -1) 183178479Sjb goto err; 184178479Sjb b++; 185178479Sjb } 186178479Sjb 187178479Sjb resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr; 188178479Sjb n = MIN(resid, len); 189178479Sjb bcopy(str, sp->str_ptr, n); 190178479Sjb 191178479Sjb sp->str_ptr += n; 192178479Sjb str += n; 193178479Sjb len -= n; 194178479Sjb } 195178479Sjb 196178479Sjb return (0); 197178479Sjb 198178479Sjberr: 199178479Sjb while (sp->str_nbufs != old_n) 200178479Sjb free(sp->str_bufs[--sp->str_nbufs]); 201178479Sjb 202178479Sjb sp->str_ptr = old_p; 203178479Sjb return (-1); 204178479Sjb} 205178479Sjb 206178479Sjbssize_t 207178479Sjbdt_strtab_index(dt_strtab_t *sp, const char *str) 208178479Sjb{ 209178479Sjb dt_strhash_t *hp; 210178479Sjb size_t len; 211178479Sjb ulong_t h; 212178479Sjb 213178479Sjb if (str == NULL || str[0] == '\0') 214178479Sjb return (0); /* we keep a \0 at offset 0 to simplify things */ 215178479Sjb 216178479Sjb h = dt_strtab_hash(str, &len) % sp->str_hashsz; 217178479Sjb 218178479Sjb for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) { 219178479Sjb if (dt_strtab_compare(sp, hp, str, len + 1) == 0) 220178479Sjb return (hp->str_off); 221178479Sjb } 222178479Sjb 223178479Sjb return (-1); 224178479Sjb} 225178479Sjb 226178479Sjbssize_t 227178479Sjbdt_strtab_insert(dt_strtab_t *sp, const char *str) 228178479Sjb{ 229178479Sjb dt_strhash_t *hp; 230178479Sjb size_t len; 231178479Sjb ssize_t off; 232178479Sjb ulong_t h; 233178479Sjb 234178479Sjb if ((off = dt_strtab_index(sp, str)) != -1) 235178479Sjb return (off); 236178479Sjb 237178479Sjb h = dt_strtab_hash(str, &len) % sp->str_hashsz; 238178479Sjb 239178479Sjb /* 240178479Sjb * Create a new hash bucket, initialize it, and insert it at the front 241178479Sjb * of the hash chain for the appropriate bucket. 242178479Sjb */ 243178479Sjb if ((hp = malloc(sizeof (dt_strhash_t))) == NULL) 244178479Sjb return (-1L); 245178479Sjb 246178479Sjb hp->str_data = sp->str_ptr; 247178479Sjb hp->str_buf = sp->str_nbufs - 1; 248178479Sjb hp->str_off = sp->str_size; 249178479Sjb hp->str_len = len; 250178479Sjb hp->str_next = sp->str_hash[h]; 251178479Sjb 252178479Sjb /* 253178479Sjb * Now copy the string data into our buffer list, and then update 254178479Sjb * the global counts of strings and bytes. Return str's byte offset. 255178479Sjb */ 256178479Sjb if (dt_strtab_copyin(sp, str, len + 1) == -1) 257178479Sjb return (-1L); 258178479Sjb 259178479Sjb sp->str_nstrs++; 260178479Sjb sp->str_size += len + 1; 261178479Sjb sp->str_hash[h] = hp; 262178479Sjb 263178479Sjb return (hp->str_off); 264178479Sjb} 265178479Sjb 266178479Sjbsize_t 267178479Sjbdt_strtab_size(const dt_strtab_t *sp) 268178479Sjb{ 269178479Sjb return (sp->str_size); 270178479Sjb} 271178479Sjb 272178479Sjbssize_t 273178479Sjbdt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private) 274178479Sjb{ 275178479Sjb ssize_t res, total = 0; 276178479Sjb ulong_t i; 277178479Sjb size_t n; 278178479Sjb 279178479Sjb for (i = 0; i < sp->str_nbufs; i++, total += res) { 280178479Sjb if (i == sp->str_nbufs - 1) 281178479Sjb n = sp->str_ptr - sp->str_bufs[i]; 282178479Sjb else 283178479Sjb n = sp->str_bufsz; 284178479Sjb 285178479Sjb if ((res = func(sp->str_bufs[i], n, total, private)) <= 0) 286178479Sjb break; 287178479Sjb } 288178479Sjb 289178479Sjb if (total == 0 && sp->str_size != 0) 290178479Sjb return (-1); 291178479Sjb 292178479Sjb return (total); 293178479Sjb} 294