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 uint_t _CTF_EMPTY[1] = { 0 }; 33 34 int ctf_hash_create(ctf_hash_t * hp,ulong_t nelems)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 = (uint_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 (uint_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 (uint_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 ctf_hash_size(const ctf_hash_t * hp)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 ctf_hash_compute(const char * key,size_t len)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 ctf_hash_insert(ctf_hash_t * hp,ctf_file_t * fp,uint_t type,uint_t name)95 ctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, uint_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 ctf_hash_define(ctf_hash_t * hp,ctf_file_t * fp,uint_t type,uint_t name)132 ctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, uint_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 * ctf_hash_lookup(ctf_hash_t * hp,ctf_file_t * fp,const char * key,size_t len)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 uint_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 ctf_hash_destroy(ctf_hash_t * hp)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 (uint_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