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 ushort_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 = (ushort_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 (ushort_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 (ushort_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,ushort_t type,uint_t name)95 ctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_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,ushort_t type,uint_t name)132 ctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_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 ushort_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 (ushort_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