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