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