Home | History | Annotate | Download | only in ctf
      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 }
    179