subr_hash.c revision 7611
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1982, 1986, 1991, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * (c) UNIX System Laboratories, Inc. 51541Srgrimes * All or some portions of this file are derived from material licensed 61541Srgrimes * to the University of California by American Telephone and Telegraph 71541Srgrimes * Co. or Unix System Laboratories, Inc. and are reproduced herein with 81541Srgrimes * the permission of UNIX System Laboratories, Inc. 91541Srgrimes * 101541Srgrimes * Redistribution and use in source and binary forms, with or without 111541Srgrimes * modification, are permitted provided that the following conditions 121541Srgrimes * are met: 131541Srgrimes * 1. Redistributions of source code must retain the above copyright 141541Srgrimes * notice, this list of conditions and the following disclaimer. 151541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 161541Srgrimes * notice, this list of conditions and the following disclaimer in the 171541Srgrimes * documentation and/or other materials provided with the distribution. 181541Srgrimes * 3. All advertising materials mentioning features or use of this software 191541Srgrimes * must display the following acknowledgement: 201541Srgrimes * This product includes software developed by the University of 211541Srgrimes * California, Berkeley and its contributors. 221541Srgrimes * 4. Neither the name of the University nor the names of its contributors 231541Srgrimes * may be used to endorse or promote products derived from this software 241541Srgrimes * without specific prior written permission. 251541Srgrimes * 261541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 271541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 301541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 361541Srgrimes * SUCH DAMAGE. 371541Srgrimes * 381541Srgrimes * @(#)kern_subr.c 8.3 (Berkeley) 1/21/94 397611Sdg * $Id: kern_subr.c,v 1.4 1995/02/12 09:11:47 davidg Exp $ 401541Srgrimes */ 411541Srgrimes 421541Srgrimes#include <sys/param.h> 431541Srgrimes#include <sys/systm.h> 441541Srgrimes#include <sys/proc.h> 451541Srgrimes#include <sys/malloc.h> 461541Srgrimes#include <sys/queue.h> 471541Srgrimes 481549Srgrimesint 491541Srgrimesuiomove(cp, n, uio) 501541Srgrimes register caddr_t cp; 511541Srgrimes register int n; 521541Srgrimes register struct uio *uio; 531541Srgrimes{ 541541Srgrimes register struct iovec *iov; 551541Srgrimes u_int cnt; 566324Sdg int error; 571541Srgrimes 581541Srgrimes#ifdef DIAGNOSTIC 591541Srgrimes if (uio->uio_rw != UIO_READ && uio->uio_rw != UIO_WRITE) 601541Srgrimes panic("uiomove: mode"); 611541Srgrimes if (uio->uio_segflg == UIO_USERSPACE && uio->uio_procp != curproc) 621541Srgrimes panic("uiomove proc"); 631541Srgrimes#endif 641541Srgrimes while (n > 0 && uio->uio_resid) { 651541Srgrimes iov = uio->uio_iov; 661541Srgrimes cnt = iov->iov_len; 671541Srgrimes if (cnt == 0) { 681541Srgrimes uio->uio_iov++; 691541Srgrimes uio->uio_iovcnt--; 701541Srgrimes continue; 711541Srgrimes } 721541Srgrimes if (cnt > n) 731541Srgrimes cnt = n; 746324Sdg 751541Srgrimes switch (uio->uio_segflg) { 761541Srgrimes 771541Srgrimes case UIO_USERSPACE: 781541Srgrimes case UIO_USERISPACE: 791541Srgrimes if (uio->uio_rw == UIO_READ) 801541Srgrimes error = copyout(cp, iov->iov_base, cnt); 811541Srgrimes else 821541Srgrimes error = copyin(iov->iov_base, cp, cnt); 831541Srgrimes if (error) 841541Srgrimes return (error); 851541Srgrimes break; 861541Srgrimes 871541Srgrimes case UIO_SYSSPACE: 881541Srgrimes if (uio->uio_rw == UIO_READ) 891541Srgrimes bcopy((caddr_t)cp, iov->iov_base, cnt); 901541Srgrimes else 911541Srgrimes bcopy(iov->iov_base, (caddr_t)cp, cnt); 921541Srgrimes break; 937611Sdg case UIO_NOCOPY: 947611Sdg break; 951541Srgrimes } 961541Srgrimes iov->iov_base += cnt; 971541Srgrimes iov->iov_len -= cnt; 981541Srgrimes uio->uio_resid -= cnt; 991541Srgrimes uio->uio_offset += cnt; 1001541Srgrimes cp += cnt; 1011541Srgrimes n -= cnt; 1021541Srgrimes } 1036324Sdg return (0); 1041541Srgrimes} 1051541Srgrimes 1061541Srgrimes/* 1071541Srgrimes * Give next character to user as result of read. 1081541Srgrimes */ 1091549Srgrimesint 1101541Srgrimesureadc(c, uio) 1111541Srgrimes register int c; 1121541Srgrimes register struct uio *uio; 1131541Srgrimes{ 1141541Srgrimes register struct iovec *iov; 1151541Srgrimes 1161541Srgrimesagain: 1171541Srgrimes if (uio->uio_iovcnt == 0 || uio->uio_resid == 0) 1181541Srgrimes panic("ureadc"); 1191541Srgrimes iov = uio->uio_iov; 1201541Srgrimes if (iov->iov_len == 0) { 1211541Srgrimes uio->uio_iovcnt--; 1221541Srgrimes uio->uio_iov++; 1231541Srgrimes goto again; 1241541Srgrimes } 1251541Srgrimes switch (uio->uio_segflg) { 1261541Srgrimes 1271541Srgrimes case UIO_USERSPACE: 1281541Srgrimes if (subyte(iov->iov_base, c) < 0) 1291541Srgrimes return (EFAULT); 1301541Srgrimes break; 1311541Srgrimes 1321541Srgrimes case UIO_SYSSPACE: 1331541Srgrimes *iov->iov_base = c; 1341541Srgrimes break; 1351541Srgrimes 1361541Srgrimes case UIO_USERISPACE: 1371541Srgrimes if (suibyte(iov->iov_base, c) < 0) 1381541Srgrimes return (EFAULT); 1391541Srgrimes break; 1401541Srgrimes } 1411541Srgrimes iov->iov_base++; 1421541Srgrimes iov->iov_len--; 1431541Srgrimes uio->uio_resid--; 1441541Srgrimes uio->uio_offset++; 1451541Srgrimes return (0); 1461541Srgrimes} 1471541Srgrimes 1481541Srgrimes#ifdef vax /* unused except by ct.c, other oddities XXX */ 1491541Srgrimes/* 1501541Srgrimes * Get next character written in by user from uio. 1511541Srgrimes */ 1521549Srgrimesint 1531541Srgrimesuwritec(uio) 1541541Srgrimes struct uio *uio; 1551541Srgrimes{ 1561541Srgrimes register struct iovec *iov; 1571541Srgrimes register int c; 1581541Srgrimes 1591541Srgrimes if (uio->uio_resid <= 0) 1601541Srgrimes return (-1); 1611541Srgrimesagain: 1621541Srgrimes if (uio->uio_iovcnt <= 0) 1631541Srgrimes panic("uwritec"); 1641541Srgrimes iov = uio->uio_iov; 1651541Srgrimes if (iov->iov_len == 0) { 1661541Srgrimes uio->uio_iov++; 1671541Srgrimes if (--uio->uio_iovcnt == 0) 1681541Srgrimes return (-1); 1691541Srgrimes goto again; 1701541Srgrimes } 1711541Srgrimes switch (uio->uio_segflg) { 1721541Srgrimes 1731541Srgrimes case UIO_USERSPACE: 1741541Srgrimes c = fubyte(iov->iov_base); 1751541Srgrimes break; 1761541Srgrimes 1771541Srgrimes case UIO_SYSSPACE: 1781541Srgrimes c = *(u_char *) iov->iov_base; 1791541Srgrimes break; 1801541Srgrimes 1811541Srgrimes case UIO_USERISPACE: 1821541Srgrimes c = fuibyte(iov->iov_base); 1831541Srgrimes break; 1841541Srgrimes } 1851541Srgrimes if (c < 0) 1861541Srgrimes return (-1); 1871541Srgrimes iov->iov_base++; 1881541Srgrimes iov->iov_len--; 1891541Srgrimes uio->uio_resid--; 1901541Srgrimes uio->uio_offset++; 1911541Srgrimes return (c); 1921541Srgrimes} 1931541Srgrimes#endif /* vax */ 1941541Srgrimes 1951541Srgrimes/* 1961541Srgrimes * General routine to allocate a hash table. 1971541Srgrimes */ 1981541Srgrimesvoid * 1991541Srgrimeshashinit(elements, type, hashmask) 2001541Srgrimes int elements, type; 2011541Srgrimes u_long *hashmask; 2021541Srgrimes{ 2031541Srgrimes long hashsize; 2041541Srgrimes LIST_HEAD(generic, generic) *hashtbl; 2051541Srgrimes int i; 2061541Srgrimes 2071541Srgrimes if (elements <= 0) 2081541Srgrimes panic("hashinit: bad cnt"); 2091541Srgrimes for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 2101541Srgrimes continue; 2111541Srgrimes hashsize >>= 1; 2121541Srgrimes hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 2131541Srgrimes for (i = 0; i < hashsize; i++) 2141541Srgrimes LIST_INIT(&hashtbl[i]); 2151541Srgrimes *hashmask = hashsize - 1; 2161541Srgrimes return (hashtbl); 2171541Srgrimes} 2187611Sdg 2197611Sdg#define NPRIMES 24 2207611Sdgstatic int primes[] = { 61, 127, 251, 509, 761, 1021, 1531, 2039, 2557, 2217611Sdg 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 2227611Sdg 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 2237611Sdg 2247611Sdg/* 2257611Sdg * General routine to allocate a prime number sized hash table. 2267611Sdg */ 2277611Sdgvoid * 2287611Sdgphashinit(elements, type, nentries) 2297611Sdg int elements, type; 2307611Sdg u_long *nentries; 2317611Sdg{ 2327611Sdg long hashsize; 2337611Sdg LIST_HEAD(generic, generic) *hashtbl; 2347611Sdg int i; 2357611Sdg 2367611Sdg if (elements <= 0) 2377611Sdg panic("hashinit: bad cnt"); 2387611Sdg for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 2397611Sdg i++; 2407611Sdg if (i == NPRIMES) 2417611Sdg break; 2427611Sdg hashsize = primes[i]; 2437611Sdg } 2447611Sdg hashsize = primes[i - 1]; 2457611Sdg hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 2467611Sdg for (i = 0; i < hashsize; i++) 2477611Sdg LIST_INIT(&hashtbl[i]); 2487611Sdg *nentries = hashsize; 2497611Sdg return (hashtbl); 2507611Sdg} 251