usr/src/cmd/fm/eversholt/common/stable.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 (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  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  *
  25  * stable.c -- string table module
  26  *
  27  * simple string table module.  all read-only strings are entered in
  28  * this table, allowing us to compare pointers rather than characters
  29  * to see if two strings are equal.
  30  *
  31  */
  32
  33 #pragma ident   "%Z%%M% %I%     %E% SMI"
  34
  35 #include <stdio.h>
  36 #include <strings.h>
  37 #include "alloc.h"
  38 #include "out.h"
  39 #include "stats.h"
  40 #include "stable.h"
  41
  42 #define MINPTR_ALIGN    sizeof (char *) /* alignment boundary for pointers */
  43 #define DEF_HASH_SIZE   11113   /* default hash table size */
  44 #define CHUNK_SIZE      8192    /* grab more memory with this chunk size */
  45
  46 static char **Stable;   /* the hash table */
  47 static unsigned Stablesz;
  48 static char *Stableblock;
  49 static char *Stablenext;
  50
  51 static struct stats *Stablecount;
  52 static struct stats *Blockcount;
  53 static struct stats *Add0;
  54 static struct stats *Add1;
  55 static struct stats *Add2;
  56 static struct stats *Add3;
  57 static struct stats *Addn;
  58
  59 struct chunklst {
  60         struct chunklst *next;
  61         char *chunkp;
  62 };
  63
  64 struct chunklst *Stablechunks;
  65
  66 /*
  67  * stable_init -- initialize the stable module
  68  *
  69  * hash table is sized according to sz.  sz of zero means pick
  70  * reasonable default size.
  71  */
  72
  73 void
  74 stable_init(unsigned sz)
  75 {
  76         /* allocate hash table */
  77         if (sz == 0)
  78                 Stablesz = DEF_HASH_SIZE;
  79         else
  80                 Stablesz = sz;
  81
  82         Stable = MALLOC(Stablesz * sizeof (*Stable));
  83         bzero((void *)Stable, Stablesz * sizeof (*Stable));
  84
  85         Stablecount = stats_new_counter("stable.size", "hash table size", 1);
  86         Blockcount = stats_new_counter("stable.blocks", "blocks allocated", 1);
  87         Add0 = stats_new_counter("stable.add0", "adds to empty buckets", 1);
  88         Add1 = stats_new_counter("stable.add1", "adds to 1-entry buckets", 1);
  89         Add2 = stats_new_counter("stable.add2", "adds to 2-entry buckets", 1);
  90         Add3 = stats_new_counter("stable.add3", "adds to 3-entry buckets", 1);
  91         Addn = stats_new_counter("stable.addn", "adds to n-entry buckets", 1);
  92
  93         stats_counter_add(Stablecount, Stablesz);
  94 }
  95
  96 void
  97 stable_fini(void)
  98 {
  99         struct chunklst *cp, *nc;
 100
 101         stats_delete(Stablecount);
 102         stats_delete(Blockcount);
 103         stats_delete(Add0);
 104         stats_delete(Add1);
 105         stats_delete(Add2);
 106         stats_delete(Add3);
 107         stats_delete(Addn);
 108
 109         FREE(Stable);
 110         cp = Stablechunks;
 111         nc = NULL;
 112         while (cp != NULL) {
 113                 nc = cp->next;
 114                 FREE(cp->chunkp);
 115                 FREE(cp);
 116                 cp = nc;
 117         }
 118         Stablechunks = NULL;
 119 }
 120
 121 static char *
 122 stable_newchunk(void)
 123 {
 124         struct chunklst *save = Stablechunks;
 125         char *n;
 126
 127         n = MALLOC(CHUNK_SIZE);
 128         bzero((void *)n, CHUNK_SIZE);
 129         stats_counter_bump(Blockcount);
 130
 131         Stablechunks = MALLOC(sizeof (struct chunklst));
 132         Stablechunks->next = save;
 133         Stablechunks->chunkp = n;
 134         return (n);
 135 }
 136
 137 /*
 138  * stable -- create/lookup a string table entry
 139  */
 140
 141 const char *
 142 stable(const char *s)
 143 {
 144         unsigned slen = 0;
 145         unsigned hash = DEF_HASH_SIZE ^ ((unsigned)*s << 2);
 146         char **ptrp;
 147         char *ptr;
 148         char *eptr;
 149         const char *sptr;
 150         int collisions = 0;
 151
 152         if (Stablesz == 0)
 153                 out(O_DIE, "internal error: Stablesz not set");
 154
 155         for (sptr = &s[1]; *sptr; sptr++) {
 156                 slen++;
 157                 hash ^= (((unsigned)*sptr) << (slen % 3)) +
 158                     ((unsigned)*(sptr - 1) << ((slen % 3 + 7)));
 159         }
 160         hash ^= slen;
 161         if (slen > CHUNK_SIZE - sizeof (char *) - 1 - 4)
 162                 out(O_DIE, "too big for string table %.20s...", s);
 163         hash %= Stablesz;
 164
 165         ptrp = &Stable[hash];
 166         ptr = *ptrp;
 167         while (ptr) {
 168                 /* hash brought us to something, see if it is the string */
 169                 sptr = s;
 170                 eptr = ptr;
 171                 while (*sptr && *eptr && *sptr++ == *eptr++)
 172                         ;
 173                 if (*sptr == '\0' && *eptr == '\0')
 174                         return (ptr);   /* found it */
 175                 /* strings didn't match, advance eptr to end of string */
 176                 while (*eptr)
 177                         eptr++;
 178                 eptr++;         /* move past '\0' */
 179                 while ((uintptr_t)eptr % MINPTR_ALIGN)
 180                         eptr++;
 181                 /* pull in next pointer in bucket */
 182                 ptrp = (char **)(void *)eptr;
 183                 ptr = *ptrp;
 184                 collisions++;
 185         }
 186
 187         /* string wasn't in table, add it and point ptr to it */
 188         if (Stablenext == NULL || (&Stableblock[CHUNK_SIZE] - Stablenext) <
 189             (slen + sizeof (char *) + MINPTR_ALIGN + 4)) {
 190                 /* need more room */
 191                 Stablenext = Stableblock = stable_newchunk();
 192         }
 193         /* current chunk has room in it */
 194         ptr = *ptrp = Stablenext;
 195         sptr = s;
 196         while (*Stablenext++ = *sptr++)
 197                 ;
 198         while ((uintptr_t)Stablenext % MINPTR_ALIGN)
 199                 Stablenext++;
 200         ptrp = (char **)(void *)Stablenext;
 201         Stablenext += sizeof (char *);
 202         *ptrp = NULL;
 203
 204         /* just did an add, update stats */
 205         if (collisions == 0)
 206                 stats_counter_bump(Add0);
 207         else if (collisions == 1)
 208                 stats_counter_bump(Add1);
 209         else if (collisions == 2)
 210                 stats_counter_bump(Add2);
 211         else if (collisions == 3)
 212                 stats_counter_bump(Add3);
 213         else
 214                 stats_counter_bump(Addn);
 215
 216         return (ptr);
 217 }