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 2004 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 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 <assert.h> 34*0Sstevel@tonic-gate 35*0Sstevel@tonic-gate #include <dt_strtab.h> 36*0Sstevel@tonic-gate #include <dt_impl.h> 37*0Sstevel@tonic-gate 38*0Sstevel@tonic-gate static int 39*0Sstevel@tonic-gate dt_strtab_grow(dt_strtab_t *sp) 40*0Sstevel@tonic-gate { 41*0Sstevel@tonic-gate char *ptr, **bufs; 42*0Sstevel@tonic-gate 43*0Sstevel@tonic-gate if ((ptr = malloc(sp->str_bufsz)) == NULL) 44*0Sstevel@tonic-gate return (-1); 45*0Sstevel@tonic-gate 46*0Sstevel@tonic-gate bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *)); 47*0Sstevel@tonic-gate 48*0Sstevel@tonic-gate if (bufs == NULL) { 49*0Sstevel@tonic-gate free(ptr); 50*0Sstevel@tonic-gate return (-1); 51*0Sstevel@tonic-gate } 52*0Sstevel@tonic-gate 53*0Sstevel@tonic-gate sp->str_nbufs++; 54*0Sstevel@tonic-gate sp->str_bufs = bufs; 55*0Sstevel@tonic-gate sp->str_ptr = ptr; 56*0Sstevel@tonic-gate sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr; 57*0Sstevel@tonic-gate 58*0Sstevel@tonic-gate return (0); 59*0Sstevel@tonic-gate } 60*0Sstevel@tonic-gate 61*0Sstevel@tonic-gate dt_strtab_t * 62*0Sstevel@tonic-gate dt_strtab_create(size_t bufsz) 63*0Sstevel@tonic-gate { 64*0Sstevel@tonic-gate dt_strtab_t *sp = malloc(sizeof (dt_strtab_t)); 65*0Sstevel@tonic-gate uint_t nbuckets = _dtrace_strbuckets; 66*0Sstevel@tonic-gate 67*0Sstevel@tonic-gate assert(bufsz != 0); 68*0Sstevel@tonic-gate 69*0Sstevel@tonic-gate if (sp == NULL) 70*0Sstevel@tonic-gate return (NULL); 71*0Sstevel@tonic-gate 72*0Sstevel@tonic-gate bzero(sp, sizeof (dt_strtab_t)); 73*0Sstevel@tonic-gate sp->str_hash = malloc(nbuckets * sizeof (dt_strhash_t *)); 74*0Sstevel@tonic-gate 75*0Sstevel@tonic-gate if (sp->str_hash == NULL) 76*0Sstevel@tonic-gate goto err; 77*0Sstevel@tonic-gate 78*0Sstevel@tonic-gate bzero(sp->str_hash, nbuckets * sizeof (dt_strhash_t *)); 79*0Sstevel@tonic-gate sp->str_hashsz = nbuckets; 80*0Sstevel@tonic-gate sp->str_bufs = NULL; 81*0Sstevel@tonic-gate sp->str_ptr = NULL; 82*0Sstevel@tonic-gate sp->str_nbufs = 0; 83*0Sstevel@tonic-gate sp->str_bufsz = bufsz; 84*0Sstevel@tonic-gate sp->str_nstrs = 1; 85*0Sstevel@tonic-gate sp->str_size = 1; 86*0Sstevel@tonic-gate 87*0Sstevel@tonic-gate if (dt_strtab_grow(sp) == -1) 88*0Sstevel@tonic-gate goto err; 89*0Sstevel@tonic-gate 90*0Sstevel@tonic-gate *sp->str_ptr++ = '\0'; 91*0Sstevel@tonic-gate return (sp); 92*0Sstevel@tonic-gate 93*0Sstevel@tonic-gate err: 94*0Sstevel@tonic-gate dt_strtab_destroy(sp); 95*0Sstevel@tonic-gate return (NULL); 96*0Sstevel@tonic-gate } 97*0Sstevel@tonic-gate 98*0Sstevel@tonic-gate void 99*0Sstevel@tonic-gate dt_strtab_destroy(dt_strtab_t *sp) 100*0Sstevel@tonic-gate { 101*0Sstevel@tonic-gate dt_strhash_t *hp, *hq; 102*0Sstevel@tonic-gate ulong_t i; 103*0Sstevel@tonic-gate 104*0Sstevel@tonic-gate for (i = 0; i < sp->str_hashsz; i++) { 105*0Sstevel@tonic-gate for (hp = sp->str_hash[i]; hp != NULL; hp = hq) { 106*0Sstevel@tonic-gate hq = hp->str_next; 107*0Sstevel@tonic-gate free(hp); 108*0Sstevel@tonic-gate } 109*0Sstevel@tonic-gate } 110*0Sstevel@tonic-gate 111*0Sstevel@tonic-gate for (i = 0; i < sp->str_nbufs; i++) 112*0Sstevel@tonic-gate free(sp->str_bufs[i]); 113*0Sstevel@tonic-gate 114*0Sstevel@tonic-gate if (sp->str_hash != NULL) 115*0Sstevel@tonic-gate free(sp->str_hash); 116*0Sstevel@tonic-gate if (sp->str_bufs != NULL) 117*0Sstevel@tonic-gate free(sp->str_bufs); 118*0Sstevel@tonic-gate 119*0Sstevel@tonic-gate free(sp); 120*0Sstevel@tonic-gate } 121*0Sstevel@tonic-gate 122*0Sstevel@tonic-gate ulong_t 123*0Sstevel@tonic-gate dt_strtab_hash(const char *key, size_t *len) 124*0Sstevel@tonic-gate { 125*0Sstevel@tonic-gate ulong_t g, h = 0; 126*0Sstevel@tonic-gate const char *p; 127*0Sstevel@tonic-gate size_t n = 0; 128*0Sstevel@tonic-gate 129*0Sstevel@tonic-gate for (p = key; *p != '\0'; p++, n++) { 130*0Sstevel@tonic-gate h = (h << 4) + *p; 131*0Sstevel@tonic-gate 132*0Sstevel@tonic-gate if ((g = (h & 0xf0000000)) != 0) { 133*0Sstevel@tonic-gate h ^= (g >> 24); 134*0Sstevel@tonic-gate h ^= g; 135*0Sstevel@tonic-gate } 136*0Sstevel@tonic-gate } 137*0Sstevel@tonic-gate 138*0Sstevel@tonic-gate if (len != NULL) 139*0Sstevel@tonic-gate *len = n; 140*0Sstevel@tonic-gate 141*0Sstevel@tonic-gate return (h); 142*0Sstevel@tonic-gate } 143*0Sstevel@tonic-gate 144*0Sstevel@tonic-gate static int 145*0Sstevel@tonic-gate dt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp, 146*0Sstevel@tonic-gate const char *str, size_t len) 147*0Sstevel@tonic-gate { 148*0Sstevel@tonic-gate ulong_t b = hp->str_buf; 149*0Sstevel@tonic-gate const char *buf = hp->str_data; 150*0Sstevel@tonic-gate size_t resid, n; 151*0Sstevel@tonic-gate int rv; 152*0Sstevel@tonic-gate 153*0Sstevel@tonic-gate while (len != 0) { 154*0Sstevel@tonic-gate if (buf == sp->str_bufs[b] + sp->str_bufsz) 155*0Sstevel@tonic-gate buf = sp->str_bufs[++b]; 156*0Sstevel@tonic-gate 157*0Sstevel@tonic-gate resid = sp->str_bufs[b] + sp->str_bufsz - buf; 158*0Sstevel@tonic-gate n = MIN(resid, len); 159*0Sstevel@tonic-gate 160*0Sstevel@tonic-gate if ((rv = strncmp(buf, str, n)) != 0) 161*0Sstevel@tonic-gate return (rv); 162*0Sstevel@tonic-gate 163*0Sstevel@tonic-gate buf += n; 164*0Sstevel@tonic-gate str += n; 165*0Sstevel@tonic-gate len -= n; 166*0Sstevel@tonic-gate } 167*0Sstevel@tonic-gate 168*0Sstevel@tonic-gate return (0); 169*0Sstevel@tonic-gate } 170*0Sstevel@tonic-gate 171*0Sstevel@tonic-gate static int 172*0Sstevel@tonic-gate dt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len) 173*0Sstevel@tonic-gate { 174*0Sstevel@tonic-gate char *old_p = sp->str_ptr; 175*0Sstevel@tonic-gate ulong_t old_n = sp->str_nbufs; 176*0Sstevel@tonic-gate 177*0Sstevel@tonic-gate ulong_t b = sp->str_nbufs - 1; 178*0Sstevel@tonic-gate size_t resid, n; 179*0Sstevel@tonic-gate 180*0Sstevel@tonic-gate while (len != 0) { 181*0Sstevel@tonic-gate if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) { 182*0Sstevel@tonic-gate if (dt_strtab_grow(sp) == -1) 183*0Sstevel@tonic-gate goto err; 184*0Sstevel@tonic-gate b++; 185*0Sstevel@tonic-gate } 186*0Sstevel@tonic-gate 187*0Sstevel@tonic-gate resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr; 188*0Sstevel@tonic-gate n = MIN(resid, len); 189*0Sstevel@tonic-gate bcopy(str, sp->str_ptr, n); 190*0Sstevel@tonic-gate 191*0Sstevel@tonic-gate sp->str_ptr += n; 192*0Sstevel@tonic-gate str += n; 193*0Sstevel@tonic-gate len -= n; 194*0Sstevel@tonic-gate } 195*0Sstevel@tonic-gate 196*0Sstevel@tonic-gate return (0); 197*0Sstevel@tonic-gate 198*0Sstevel@tonic-gate err: 199*0Sstevel@tonic-gate while (sp->str_nbufs != old_n) 200*0Sstevel@tonic-gate free(sp->str_bufs[--sp->str_nbufs]); 201*0Sstevel@tonic-gate 202*0Sstevel@tonic-gate sp->str_ptr = old_p; 203*0Sstevel@tonic-gate return (-1); 204*0Sstevel@tonic-gate } 205*0Sstevel@tonic-gate 206*0Sstevel@tonic-gate ssize_t 207*0Sstevel@tonic-gate dt_strtab_insert(dt_strtab_t *sp, const char *str) 208*0Sstevel@tonic-gate { 209*0Sstevel@tonic-gate dt_strhash_t *hp; 210*0Sstevel@tonic-gate size_t len; 211*0Sstevel@tonic-gate ulong_t h; 212*0Sstevel@tonic-gate 213*0Sstevel@tonic-gate if (str == NULL || str[0] == '\0') 214*0Sstevel@tonic-gate return (0); /* we keep a \0 at offset 0 to simplify things */ 215*0Sstevel@tonic-gate 216*0Sstevel@tonic-gate h = dt_strtab_hash(str, &len) % sp->str_hashsz; 217*0Sstevel@tonic-gate 218*0Sstevel@tonic-gate /* 219*0Sstevel@tonic-gate * If the string is already in our hash table, just return the offset 220*0Sstevel@tonic-gate * of the existing string element and do not add a duplicate string. 221*0Sstevel@tonic-gate */ 222*0Sstevel@tonic-gate for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) { 223*0Sstevel@tonic-gate if (dt_strtab_compare(sp, hp, str, len + 1) == 0) 224*0Sstevel@tonic-gate return (hp->str_off); 225*0Sstevel@tonic-gate } 226*0Sstevel@tonic-gate 227*0Sstevel@tonic-gate /* 228*0Sstevel@tonic-gate * Create a new hash bucket, initialize it, and insert it at the front 229*0Sstevel@tonic-gate * of the hash chain for the appropriate bucket. 230*0Sstevel@tonic-gate */ 231*0Sstevel@tonic-gate if ((hp = malloc(sizeof (dt_strhash_t))) == NULL) 232*0Sstevel@tonic-gate return (-1L); 233*0Sstevel@tonic-gate 234*0Sstevel@tonic-gate hp->str_data = sp->str_ptr; 235*0Sstevel@tonic-gate hp->str_buf = sp->str_nbufs - 1; 236*0Sstevel@tonic-gate hp->str_off = sp->str_size; 237*0Sstevel@tonic-gate hp->str_len = len; 238*0Sstevel@tonic-gate hp->str_next = sp->str_hash[h]; 239*0Sstevel@tonic-gate 240*0Sstevel@tonic-gate /* 241*0Sstevel@tonic-gate * Now copy the string data into our buffer list, and then update 242*0Sstevel@tonic-gate * the global counts of strings and bytes. Return str's byte offset. 243*0Sstevel@tonic-gate */ 244*0Sstevel@tonic-gate if (dt_strtab_copyin(sp, str, len + 1) == -1) 245*0Sstevel@tonic-gate return (-1L); 246*0Sstevel@tonic-gate 247*0Sstevel@tonic-gate sp->str_nstrs++; 248*0Sstevel@tonic-gate sp->str_size += len + 1; 249*0Sstevel@tonic-gate sp->str_hash[h] = hp; 250*0Sstevel@tonic-gate 251*0Sstevel@tonic-gate return (hp->str_off); 252*0Sstevel@tonic-gate } 253*0Sstevel@tonic-gate 254*0Sstevel@tonic-gate size_t 255*0Sstevel@tonic-gate dt_strtab_size(const dt_strtab_t *sp) 256*0Sstevel@tonic-gate { 257*0Sstevel@tonic-gate return (sp->str_size); 258*0Sstevel@tonic-gate } 259*0Sstevel@tonic-gate 260*0Sstevel@tonic-gate ssize_t 261*0Sstevel@tonic-gate dt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private) 262*0Sstevel@tonic-gate { 263*0Sstevel@tonic-gate ssize_t res, total = 0; 264*0Sstevel@tonic-gate ulong_t i; 265*0Sstevel@tonic-gate size_t n; 266*0Sstevel@tonic-gate 267*0Sstevel@tonic-gate for (i = 0; i < sp->str_nbufs; i++, total += res) { 268*0Sstevel@tonic-gate if (i == sp->str_nbufs - 1) 269*0Sstevel@tonic-gate n = sp->str_ptr - sp->str_bufs[i]; 270*0Sstevel@tonic-gate else 271*0Sstevel@tonic-gate n = sp->str_bufsz; 272*0Sstevel@tonic-gate 273*0Sstevel@tonic-gate if ((res = func(sp->str_bufs[i], n, total, private)) <= 0) 274*0Sstevel@tonic-gate break; 275*0Sstevel@tonic-gate } 276*0Sstevel@tonic-gate 277*0Sstevel@tonic-gate if (total == 0 && sp->str_size != 0) 278*0Sstevel@tonic-gate return (-1); 279*0Sstevel@tonic-gate 280*0Sstevel@tonic-gate return (total); 281*0Sstevel@tonic-gate } 282