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 ushort_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 bzero(hp, 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 (ushort_t) * 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 bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 67 bzero(hp->h_chains, sizeof (ctf_helem_t) * 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, ushort_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, ushort_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 ushort_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 (ushort_t) * 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