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