usr/src/tools/ctf/cvt/strtab.c

   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, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright (c) 2001 by Sun Microsystems, Inc.
  24  * All rights reserved.
  25  */
  26
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28
  29 #include <sys/types.h>
  30 #include <sys/sysmacros.h>
  31 #include <strings.h>
  32 #include <stdlib.h>
  33 #include <stdio.h>
  34
  35 #include "strtab.h"
  36 #include "memory.h"
  37
  38 #define STRTAB_HASHSZ   211             /* use a prime number of hash buckets */
  39 #define STRTAB_BUFSZ    (64 * 1024)     /* use 64K data buffers by default */
  40
  41 static void
  42 strtab_grow(strtab_t *sp)
  43 {
  44         sp->str_nbufs++;
  45         sp->str_bufs = xrealloc(sp->str_bufs, sp->str_nbufs * sizeof (char *));
  46         sp->str_ptr = xmalloc(sp->str_bufsz);
  47         sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr;
  48 }
  49
  50 void
  51 strtab_create(strtab_t *sp)
  52 {
  53         sp->str_hash = xcalloc(STRTAB_HASHSZ * sizeof (strhash_t *));
  54         sp->str_hashsz = STRTAB_HASHSZ;
  55         sp->str_bufs = NULL;
  56         sp->str_ptr = NULL;
  57         sp->str_nbufs = 0;
  58         sp->str_bufsz = STRTAB_BUFSZ;
  59         sp->str_nstrs = 1;
  60         sp->str_size = 1;
  61
  62         strtab_grow(sp);
  63         *sp->str_ptr++ = '\0';
  64 }
  65
  66 void
  67 strtab_destroy(strtab_t *sp)
  68 {
  69         strhash_t *hp, *hq;
  70         ulong_t i;
  71
  72         for (i = 0; i < sp->str_hashsz; i++) {
  73                 for (hp = sp->str_hash[i]; hp != NULL; hp = hq) {
  74                         hq = hp->str_next;
  75                         free(hp);
  76                 }
  77         }
  78
  79         for (i = 0; i < sp->str_nbufs; i++)
  80                 free(sp->str_bufs[i]);
  81
  82         free(sp->str_hash);
  83         free(sp->str_bufs);
  84 }
  85
  86 static ulong_t
  87 strtab_hash(const char *key, size_t *len)
  88 {
  89         ulong_t g, h = 0;
  90         const char *p;
  91         size_t n = 0;
  92
  93         for (p = key; *p != '\0'; p++, n++) {
  94                 h = (h << 4) + *p;
  95
  96                 if ((g = (h & 0xf0000000)) != 0) {
  97                         h ^= (g >> 24);
  98                         h ^= g;
  99                 }
 100         }
 101
 102         *len = n;
 103         return (h);
 104 }
 105
 106 static int
 107 strtab_compare(strtab_t *sp, strhash_t *hp, const char *str, size_t len)
 108 {
 109         ulong_t b = hp->str_buf;
 110         const char *buf = hp->str_data;
 111         size_t resid, n;
 112         int rv;
 113
 114         while (len != 0) {
 115                 if (buf == sp->str_bufs[b] + sp->str_bufsz)
 116                         buf = sp->str_bufs[++b];
 117
 118                 resid = sp->str_bufs[b] + sp->str_bufsz - buf;
 119                 n = MIN(resid, len);
 120
 121                 if ((rv = strncmp(buf, str, n)) != 0)
 122                         return (rv);
 123
 124                 buf += n;
 125                 str += n;
 126                 len -= n;
 127         }
 128
 129         return (0);
 130 }
 131
 132 static void
 133 strtab_copyin(strtab_t *sp, const char *str, size_t len)
 134 {
 135         ulong_t b = sp->str_nbufs - 1;
 136         size_t resid, n;
 137
 138         while (len != 0) {
 139                 if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) {
 140                         strtab_grow(sp);
 141                         b++;
 142                 }
 143
 144                 resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr;
 145                 n = MIN(resid, len);
 146                 bcopy(str, sp->str_ptr, n);
 147
 148                 sp->str_ptr += n;
 149                 str += n;
 150                 len -= n;
 151         }
 152 }
 153
 154 size_t
 155 strtab_insert(strtab_t *sp, const char *str)
 156 {
 157         strhash_t *hp;
 158         size_t len;
 159         ulong_t h;
 160
 161         if (str == NULL || str[0] == '\0')
 162                 return (0); /* we keep a \0 at offset 0 to simplify things */
 163
 164         h = strtab_hash(str, &len) % sp->str_hashsz;
 165
 166         /*
 167          * If the string is already in our hash table, just return the offset
 168          * of the existing string element and do not add a duplicate string.
 169          */
 170         for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) {
 171                 if (strtab_compare(sp, hp, str, len + 1) == 0)
 172                         return (hp->str_off);
 173         }
 174
 175         /*
 176          * Create a new hash bucket, initialize it, and insert it at the front
 177          * of the hash chain for the appropriate bucket.
 178          */
 179         hp = xmalloc(sizeof (strhash_t));
 180
 181         hp->str_data = sp->str_ptr;
 182         hp->str_buf = sp->str_nbufs - 1;
 183         hp->str_off = sp->str_size;
 184         hp->str_len = len;
 185         hp->str_next = sp->str_hash[h];
 186
 187         sp->str_hash[h] = hp;
 188
 189         /*
 190          * Now copy the string data into our buffer list, and then update
 191          * the global counts of strings and bytes.  Return str's byte offset.
 192          */
 193         strtab_copyin(sp, str, len + 1);
 194         sp->str_nstrs++;
 195         sp->str_size += len + 1;
 196
 197         return (hp->str_off);
 198 }
 199
 200 size_t
 201 strtab_size(const strtab_t *sp)
 202 {
 203         return (sp->str_size);
 204 }
 205
 206 ssize_t
 207 strtab_write(const strtab_t *sp,
 208     ssize_t (*func)(const void *, size_t, void *), void *priv)
 209 {
 210         ssize_t res, total = 0;
 211         ulong_t i;
 212         size_t n;
 213
 214         for (i = 0; i < sp->str_nbufs; i++, total += res) {
 215                 if (i == sp->str_nbufs - 1)
 216                         n = sp->str_ptr - sp->str_bufs[i];
 217                 else
 218                         n = sp->str_bufsz;
 219
 220                 if ((res = func(sp->str_bufs[i], n, priv)) <= 0)
 221                         break;
 222         }
 223
 224         if (total == 0 && sp->str_size != 0)
 225                 return (-1);
 226
 227         return (total);
 228 }
 229
 230 void
 231 strtab_print(const strtab_t *sp)
 232 {
 233         const strhash_t *hp;
 234         ulong_t i;
 235
 236         for (i = 0; i < sp->str_hashsz; i++) {
 237                 for (hp = sp->str_hash[i]; hp != NULL; hp = hp->str_next) {
 238                         const char *buf = hp->str_data;
 239                         ulong_t b = hp->str_buf;
 240                         size_t resid, len, n;
 241
 242                         (void) printf("[%lu] %lu \"", (ulong_t)hp->str_off, b);
 243
 244                         for (len = hp->str_len; len != 0; len -= n) {
 245                                 if (buf == sp->str_bufs[b] + sp->str_bufsz)
 246                                         buf = sp->str_bufs[++b];
 247
 248                                 resid = sp->str_bufs[b] + sp->str_bufsz - buf;
 249                                 n = MIN(resid, len);
 250
 251                                 (void) printf("%.*s", (int)n, buf);
 252                                 buf += n;
 253                         }
 254
 255                         (void) printf("\"\n");
 256                 }
 257         }
 258 }