cddl/contrib/opensolaris/common/ctf/ctf_hash.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 /*
  24  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
  25  * Use is subject to license terms.
  26  */
  27
  28 #pragma ident   "%Z%%M% %I%     %E% SMI"
  29
  30 #include <ctf_impl.h>
  31
  32 static const ushort_t _CTF_EMPTY[1] = { 0 };
  33
  34 int
  35 ctf_hash_create(ctf_hash_t *hp, ulong_t nelems)
  36 {
  37         if (nelems > USHRT_MAX)
  38                 return (EOVERFLOW);
  39
  40         /*
  41          * If the hash table is going to be empty, don't bother allocating any
  42          * memory and make the only bucket point to a zero so lookups fail.
  43          */
  44         if (nelems == 0) {
  45                 bzero(hp, sizeof (ctf_hash_t));
  46                 hp->h_buckets = (ushort_t *)_CTF_EMPTY;
  47                 hp->h_nbuckets = 1;
  48                 return (0);
  49         }
  50
  51         hp->h_nbuckets = 211;           /* use a prime number of hash buckets */
  52         hp->h_nelems = nelems + 1;      /* we use index zero as a sentinel */
  53         hp->h_free = 1;                 /* first free element is index 1 */
  54
  55         hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets);
  56         hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems);
  57
  58         if (hp->h_buckets == NULL || hp->h_chains == NULL) {
  59                 ctf_hash_destroy(hp);
  60                 return (EAGAIN);
  61         }
  62
  63         bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets);
  64         bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems);
  65
  66         return (0);
  67 }
  68
  69 uint_t
  70 ctf_hash_size(const ctf_hash_t *hp)
  71 {
  72         return (hp->h_nelems ? hp->h_nelems - 1 : 0);
  73 }
  74
  75 static ulong_t
  76 ctf_hash_compute(const char *key, size_t len)
  77 {
  78         ulong_t g, h = 0;
  79         const char *p, *q = key + len;
  80         size_t n = 0;
  81
  82         for (p = key; p < q; p++, n++) {
  83                 h = (h << 4) + *p;
  84
  85                 if ((g = (h & 0xf0000000)) != 0) {
  86                         h ^= (g >> 24);
  87                         h ^= g;
  88                 }
  89         }
  90
  91         return (h);
  92 }
  93
  94 int
  95 ctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name)
  96 {
  97         ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)];
  98         const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name);
  99         ctf_helem_t *hep = &hp->h_chains[hp->h_free];
 100         ulong_t h;
 101
 102         if (type == 0)
 103                 return (EINVAL);
 104
 105         if (hp->h_free >= hp->h_nelems)
 106                 return (EOVERFLOW);
 107
 108         if (ctsp->cts_strs == NULL)
 109                 return (ECTF_STRTAB);
 110
 111         if (ctsp->cts_len <= CTF_NAME_OFFSET(name))
 112                 return (ECTF_BADNAME);
 113
 114         if (str[0] == '\0')
 115                 return (0); /* just ignore empty strings on behalf of caller */
 116
 117         hep->h_name = name;
 118         hep->h_type = type;
 119         h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets;
 120         hep->h_next = hp->h_buckets[h];
 121         hp->h_buckets[h] = hp->h_free++;
 122
 123         return (0);
 124 }
 125
 126 /*
 127  * Wrapper for ctf_hash_lookup/ctf_hash_insert: if the key is already in the
 128  * hash, override the previous definition with this new official definition.
 129  * If the key is not present, then call ctf_hash_insert() and hash it in.
 130  */
 131 int
 132 ctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name)
 133 {
 134         const char *str = ctf_strptr(fp, name);
 135         ctf_helem_t *hep = ctf_hash_lookup(hp, fp, str, strlen(str));
 136
 137         if (hep == NULL)
 138                 return (ctf_hash_insert(hp, fp, type, name));
 139
 140         hep->h_type = type;
 141         return (0);
 142 }
 143
 144 ctf_helem_t *
 145 ctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len)
 146 {
 147         ctf_helem_t *hep;
 148         ctf_strs_t *ctsp;
 149         const char *str;
 150         ushort_t i;
 151
 152         ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets;
 153
 154         for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) {
 155                 hep = &hp->h_chains[i];
 156                 ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)];
 157                 str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name);
 158
 159                 if (strncmp(key, str, len) == 0 && str[len] == '\0')
 160                         return (hep);
 161         }
 162
 163         return (NULL);
 164 }
 165
 166 void
 167 ctf_hash_destroy(ctf_hash_t *hp)
 168 {
 169         if (hp->h_buckets != NULL && hp->h_nbuckets != 1) {
 170                 ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets);
 171                 hp->h_buckets = NULL;
 172         }
 173
 174         if (hp->h_chains != NULL) {
 175                 ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems);
 176                 hp->h_chains = NULL;
 177         }
 178 }