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 (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 22/* 23 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27#pragma ident "@(#)dt_strtab.c 1.4 06/09/19 SMI" 28 29#include <sys/types.h> 30#include <strings.h> 31#include <stdlib.h> 32#include <assert.h> 33 34#include <dt_strtab.h> 35#include <dt_impl.h> 36 37static int 38dt_strtab_grow(dt_strtab_t *sp) 39{ 40 char *ptr, **bufs; 41 42 if ((ptr = malloc(sp->str_bufsz)) == NULL) 43 return (-1); 44 45 bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *)); 46 47 if (bufs == NULL) { 48 free(ptr); 49 return (-1); 50 } 51 52 sp->str_nbufs++; 53 sp->str_bufs = bufs; 54 sp->str_ptr = ptr; 55 sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr; 56 57 return (0); 58} 59 60dt_strtab_t * 61dt_strtab_create(size_t bufsz) 62{ 63 dt_strtab_t *sp = malloc(sizeof (dt_strtab_t)); 64 uint_t nbuckets = _dtrace_strbuckets; 65 66 assert(bufsz != 0); 67 68 if (sp == NULL) 69 return (NULL); 70 71 bzero(sp, sizeof (dt_strtab_t)); 72 sp->str_hash = malloc(nbuckets * sizeof (dt_strhash_t *)); 73 74 if (sp->str_hash == NULL) 75 goto err; 76 77 bzero(sp->str_hash, nbuckets * sizeof (dt_strhash_t *)); 78 sp->str_hashsz = nbuckets; 79 sp->str_bufs = NULL; 80 sp->str_ptr = NULL; 81 sp->str_nbufs = 0; 82 sp->str_bufsz = bufsz; 83 sp->str_nstrs = 1; 84 sp->str_size = 1; 85 86 if (dt_strtab_grow(sp) == -1) 87 goto err; 88 89 *sp->str_ptr++ = '\0'; 90 return (sp); 91 92err: 93 dt_strtab_destroy(sp); 94 return (NULL); 95} 96 97void 98dt_strtab_destroy(dt_strtab_t *sp) 99{ 100 dt_strhash_t *hp, *hq; 101 ulong_t i; 102 103 for (i = 0; i < sp->str_hashsz; i++) { 104 for (hp = sp->str_hash[i]; hp != NULL; hp = hq) { 105 hq = hp->str_next; 106 free(hp); 107 } 108 } 109 110 for (i = 0; i < sp->str_nbufs; i++) 111 free(sp->str_bufs[i]); 112 113 if (sp->str_hash != NULL) 114 free(sp->str_hash); 115 if (sp->str_bufs != NULL) 116 free(sp->str_bufs); 117 118 free(sp); 119} 120 121ulong_t 122dt_strtab_hash(const char *key, size_t *len) 123{ 124 ulong_t g, h = 0; 125 const char *p; 126 size_t n = 0; 127 128 for (p = key; *p != '\0'; p++, n++) { 129 h = (h << 4) + *p; 130 131 if ((g = (h & 0xf0000000)) != 0) { 132 h ^= (g >> 24); 133 h ^= g; 134 } 135 } 136 137 if (len != NULL) 138 *len = n; 139 140 return (h); 141} 142 143static int 144dt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp, 145 const char *str, size_t len) 146{ 147 ulong_t b = hp->str_buf; 148 const char *buf = hp->str_data; 149 size_t resid, n; 150 int rv; 151 152 while (len != 0) { 153 if (buf == sp->str_bufs[b] + sp->str_bufsz) 154 buf = sp->str_bufs[++b]; 155 156 resid = sp->str_bufs[b] + sp->str_bufsz - buf; 157 n = MIN(resid, len); 158 159 if ((rv = strncmp(buf, str, n)) != 0) 160 return (rv); 161 162 buf += n; 163 str += n; 164 len -= n; 165 } 166 167 return (0); 168} 169 170static int 171dt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len) 172{ 173 char *old_p = sp->str_ptr; 174 ulong_t old_n = sp->str_nbufs; 175 176 ulong_t b = sp->str_nbufs - 1; 177 size_t resid, n; 178 179 while (len != 0) { 180 if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) { 181 if (dt_strtab_grow(sp) == -1) 182 goto err; 183 b++; 184 } 185 186 resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr; 187 n = MIN(resid, len); 188 bcopy(str, sp->str_ptr, n); 189 190 sp->str_ptr += n; 191 str += n; 192 len -= n; 193 } 194 195 return (0); 196 197err: 198 while (sp->str_nbufs != old_n) 199 free(sp->str_bufs[--sp->str_nbufs]); 200 201 sp->str_ptr = old_p; 202 return (-1); 203} 204 205ssize_t 206dt_strtab_index(dt_strtab_t *sp, const char *str) 207{ 208 dt_strhash_t *hp; 209 size_t len; 210 ulong_t h; 211 212 if (str == NULL || str[0] == '\0') 213 return (0); /* we keep a \0 at offset 0 to simplify things */ 214 215 h = dt_strtab_hash(str, &len) % sp->str_hashsz; 216 217 for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) { 218 if (dt_strtab_compare(sp, hp, str, len + 1) == 0) 219 return (hp->str_off); 220 } 221 222 return (-1); 223} 224 225ssize_t 226dt_strtab_insert(dt_strtab_t *sp, const char *str) 227{ 228 dt_strhash_t *hp; 229 size_t len; 230 ssize_t off; 231 ulong_t h; 232 233 if ((off = dt_strtab_index(sp, str)) != -1) 234 return (off); 235 236 h = dt_strtab_hash(str, &len) % sp->str_hashsz; 237 238 /* 239 * Create a new hash bucket, initialize it, and insert it at the front 240 * of the hash chain for the appropriate bucket. 241 */ 242 if ((hp = malloc(sizeof (dt_strhash_t))) == NULL) 243 return (-1L); 244 245 hp->str_data = sp->str_ptr; 246 hp->str_buf = sp->str_nbufs - 1; 247 hp->str_off = sp->str_size; 248 hp->str_len = len; 249 hp->str_next = sp->str_hash[h]; 250 251 /* 252 * Now copy the string data into our buffer list, and then update 253 * the global counts of strings and bytes. Return str's byte offset. 254 */ 255 if (dt_strtab_copyin(sp, str, len + 1) == -1) 256 return (-1L); 257 258 sp->str_nstrs++; 259 sp->str_size += len + 1; 260 sp->str_hash[h] = hp; 261 262 return (hp->str_off); 263} 264 265size_t 266dt_strtab_size(const dt_strtab_t *sp) 267{ 268 return (sp->str_size); 269} 270 271ssize_t 272dt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private) 273{ 274 ssize_t res, total = 0; 275 ulong_t i; 276 size_t n; 277 278 for (i = 0; i < sp->str_nbufs; i++, total += res) { 279 if (i == sp->str_nbufs - 1) 280 n = sp->str_ptr - sp->str_bufs[i]; 281 else 282 n = sp->str_bufsz; 283 284 if ((res = func(sp->str_bufs[i], n, total, private)) <= 0) 285 break; 286 } 287 288 if (total == 0 && sp->str_size != 0) 289 return (-1); 290 291 return (total); 292} 293