xref: /illumos-gate/usr/src/common/ctf/ctf_hash.c (revision 3dfdac06)
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