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
ctf_hash_create(ctf_hash_t * hp,ulong_t nelems)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
ctf_hash_size(const ctf_hash_t * hp)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
ctf_hash_compute(const char * key,size_t len)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
ctf_hash_insert(ctf_hash_t * hp,ctf_file_t * fp,ushort_t type,uint_t name)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
ctf_hash_define(ctf_hash_t * hp,ctf_file_t * fp,ushort_t type,uint_t name)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 *
ctf_hash_lookup(ctf_hash_t * hp,ctf_file_t * fp,const char * key,size_t len)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
ctf_hash_destroy(ctf_hash_t * hp)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
ctf_hash_dump(const char * tag,ctf_hash_t * hp,ctf_file_t * fp)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