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