subr_hash.c revision 7683 
1/*
2 * Copyright (c) 1982, 1986, 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 * (c) UNIX System Laboratories, Inc.
5 * All or some portions of this file are derived from material licensed
6 * to the University of California by American Telephone and Telegraph
7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
8 * the permission of UNIX System Laboratories, Inc.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 *    must display the following acknowledgement:
20 *	This product includes software developed by the University of
21 *	California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 *    may be used to endorse or promote products derived from this software
24 *    without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 *
38 *	@(#)kern_subr.c	8.3 (Berkeley) 1/21/94
39 * $Id: kern_subr.c,v 1.5 1995/04/04 02:01:12 davidg Exp $
40 */
41
42#include <sys/param.h>
43#include <sys/systm.h>
44#include <sys/proc.h>
45#include <sys/malloc.h>
46#include <sys/queue.h>
47
48int
49uiomove(cp, n, uio)
50	register caddr_t cp;
51	register int n;
52	register struct uio *uio;
53{
54	register struct iovec *iov;
55	u_int cnt;
56	int error;
57
58#ifdef DIAGNOSTIC
59	if (uio->uio_rw != UIO_READ && uio->uio_rw != UIO_WRITE)
60		panic("uiomove: mode");
61	if (uio->uio_segflg == UIO_USERSPACE && uio->uio_procp != curproc)
62		panic("uiomove proc");
63#endif
64	while (n > 0 && uio->uio_resid) {
65		iov = uio->uio_iov;
66		cnt = iov->iov_len;
67		if (cnt == 0) {
68			uio->uio_iov++;
69			uio->uio_iovcnt--;
70			continue;
71		}
72		if (cnt > n)
73			cnt = n;
74
75		switch (uio->uio_segflg) {
76
77		case UIO_USERSPACE:
78		case UIO_USERISPACE:
79			if (uio->uio_rw == UIO_READ)
80				error = copyout(cp, iov->iov_base, cnt);
81			else
82				error = copyin(iov->iov_base, cp, cnt);
83			if (error)
84				return (error);
85			break;
86
87		case UIO_SYSSPACE:
88			if (uio->uio_rw == UIO_READ)
89				bcopy((caddr_t)cp, iov->iov_base, cnt);
90			else
91				bcopy(iov->iov_base, (caddr_t)cp, cnt);
92			break;
93		case UIO_NOCOPY:
94			break;
95		}
96		iov->iov_base += cnt;
97		iov->iov_len -= cnt;
98		uio->uio_resid -= cnt;
99		uio->uio_offset += cnt;
100		cp += cnt;
101		n -= cnt;
102	}
103	return (0);
104}
105
106/*
107 * Give next character to user as result of read.
108 */
109int
110ureadc(c, uio)
111	register int c;
112	register struct uio *uio;
113{
114	register struct iovec *iov;
115
116again:
117	if (uio->uio_iovcnt == 0 || uio->uio_resid == 0)
118		panic("ureadc");
119	iov = uio->uio_iov;
120	if (iov->iov_len == 0) {
121		uio->uio_iovcnt--;
122		uio->uio_iov++;
123		goto again;
124	}
125	switch (uio->uio_segflg) {
126
127	case UIO_USERSPACE:
128		if (subyte(iov->iov_base, c) < 0)
129			return (EFAULT);
130		break;
131
132	case UIO_SYSSPACE:
133		*iov->iov_base = c;
134		break;
135
136	case UIO_USERISPACE:
137		if (suibyte(iov->iov_base, c) < 0)
138			return (EFAULT);
139		break;
140	}
141	iov->iov_base++;
142	iov->iov_len--;
143	uio->uio_resid--;
144	uio->uio_offset++;
145	return (0);
146}
147
148#ifdef vax	/* unused except by ct.c, other oddities XXX */
149/*
150 * Get next character written in by user from uio.
151 */
152int
153uwritec(uio)
154	struct uio *uio;
155{
156	register struct iovec *iov;
157	register int c;
158
159	if (uio->uio_resid <= 0)
160		return (-1);
161again:
162	if (uio->uio_iovcnt <= 0)
163		panic("uwritec");
164	iov = uio->uio_iov;
165	if (iov->iov_len == 0) {
166		uio->uio_iov++;
167		if (--uio->uio_iovcnt == 0)
168			return (-1);
169		goto again;
170	}
171	switch (uio->uio_segflg) {
172
173	case UIO_USERSPACE:
174		c = fubyte(iov->iov_base);
175		break;
176
177	case UIO_SYSSPACE:
178		c = *(u_char *) iov->iov_base;
179		break;
180
181	case UIO_USERISPACE:
182		c = fuibyte(iov->iov_base);
183		break;
184	}
185	if (c < 0)
186		return (-1);
187	iov->iov_base++;
188	iov->iov_len--;
189	uio->uio_resid--;
190	uio->uio_offset++;
191	return (c);
192}
193#endif /* vax */
194
195/*
196 * General routine to allocate a hash table.
197 */
198void *
199hashinit(elements, type, hashmask)
200	int elements, type;
201	u_long *hashmask;
202{
203	long hashsize;
204	LIST_HEAD(generic, generic) *hashtbl;
205	int i;
206
207	if (elements <= 0)
208		panic("hashinit: bad cnt");
209	for (hashsize = 1; hashsize <= elements; hashsize <<= 1)
210		continue;
211	hashsize >>= 1;
212	hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK);
213	for (i = 0; i < hashsize; i++)
214		LIST_INIT(&hashtbl[i]);
215	*hashmask = hashsize - 1;
216	return (hashtbl);
217}
218
219#define NPRIMES 27
220static int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039,
221			2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653,
222			7159, 7673, 8191, 12281, 16381, 24571, 32749 };
223
224/*
225 * General routine to allocate a prime number sized hash table.
226 */
227void *
228phashinit(elements, type, nentries)
229	int elements, type;
230	u_long *nentries;
231{
232	long hashsize;
233	LIST_HEAD(generic, generic) *hashtbl;
234	int i;
235
236	if (elements <= 0)
237		panic("hashinit: bad cnt");
238	for (i = 1, hashsize = primes[1]; hashsize <= elements;) {
239		i++;
240		if (i == NPRIMES)
241			break;
242		hashsize = primes[i];
243	}
244	hashsize = primes[i - 1];
245	hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK);
246	for (i = 0; i < hashsize; i++)
247		LIST_INIT(&hashtbl[i]);
248	*nentries = hashsize;
249	return (hashtbl);
250}
251