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