subr_hash.c revision 26205 
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.10 1997/02/22 09:39:11 peter 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	case UIO_NOCOPY:
141		break;
142	}
143	iov->iov_base++;
144	iov->iov_len--;
145	uio->uio_resid--;
146	uio->uio_offset++;
147	return (0);
148}
149
150#ifdef vax	/* unused except by ct.c, other oddities XXX */
151/*
152 * Get next character written in by user from uio.
153 */
154int
155uwritec(uio)
156	struct uio *uio;
157{
158	register struct iovec *iov;
159	register int c;
160
161	if (uio->uio_resid <= 0)
162		return (-1);
163again:
164	if (uio->uio_iovcnt <= 0)
165		panic("uwritec");
166	iov = uio->uio_iov;
167	if (iov->iov_len == 0) {
168		uio->uio_iov++;
169		if (--uio->uio_iovcnt == 0)
170			return (-1);
171		goto again;
172	}
173	switch (uio->uio_segflg) {
174
175	case UIO_USERSPACE:
176		c = fubyte(iov->iov_base);
177		break;
178
179	case UIO_SYSSPACE:
180		c = *(u_char *) iov->iov_base;
181		break;
182
183	case UIO_USERISPACE:
184		c = fuibyte(iov->iov_base);
185		break;
186	}
187	if (c < 0)
188		return (-1);
189	iov->iov_base++;
190	iov->iov_len--;
191	uio->uio_resid--;
192	uio->uio_offset++;
193	return (c);
194}
195#endif /* vax */
196
197/*
198 * General routine to allocate a hash table.
199 */
200void *
201hashinit(elements, type, hashmask)
202	int elements, type;
203	u_long *hashmask;
204{
205	long hashsize;
206	LIST_HEAD(generic, generic) *hashtbl;
207	int i;
208
209	if (elements <= 0)
210		panic("hashinit: bad elements");
211	for (hashsize = 1; hashsize <= elements; hashsize <<= 1)
212		continue;
213	hashsize >>= 1;
214	hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK);
215	for (i = 0; i < hashsize; i++)
216		LIST_INIT(&hashtbl[i]);
217	*hashmask = hashsize - 1;
218	return (hashtbl);
219}
220
221static int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039,
222			2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653,
223			7159, 7673, 8191, 12281, 16381, 24571, 32749 };
224#define NPRIMES (sizeof(primes) / sizeof(primes[0]))
225
226/*
227 * General routine to allocate a prime number sized hash table.
228 */
229void *
230phashinit(elements, type, nentries)
231	int elements, type;
232	u_long *nentries;
233{
234	long hashsize;
235	LIST_HEAD(generic, generic) *hashtbl;
236	int i;
237
238	if (elements <= 0)
239		panic("phashinit: bad elements");
240	for (i = 1, hashsize = primes[1]; hashsize <= elements;) {
241		i++;
242		if (i == NPRIMES)
243			break;
244		hashsize = primes[i];
245	}
246	hashsize = primes[i - 1];
247	hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK);
248	for (i = 0; i < hashsize; i++)
249		LIST_INIT(&hashtbl[i]);
250	*nentries = hashsize;
251	return (hashtbl);
252}
253