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
32static const ushort_t _CTF_EMPTY[1] = { 0 };
33
34int
35ctf_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
69uint_t
70ctf_hash_size(const ctf_hash_t *hp)
71{
72	return (hp->h_nelems ? hp->h_nelems - 1 : 0);
73}
74
75static ulong_t
76ctf_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
94int
95ctf_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 */
131int
132ctf_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
144ctf_helem_t *
145ctf_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
166void
167ctf_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