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