1139804Simp/*- 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 * 4. Neither the name of the University nor the names of its contributors 191541Srgrimes * may be used to endorse or promote products derived from this software 201541Srgrimes * without specific prior written permission. 211541Srgrimes * 221541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 231541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 241541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 251541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 261541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 271541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 281541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 291541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 301541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 311541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 321541Srgrimes * SUCH DAMAGE. 331541Srgrimes * 341541Srgrimes * @(#)kern_subr.c 8.3 (Berkeley) 1/21/94 351541Srgrimes */ 361541Srgrimes 37116182Sobrien#include <sys/cdefs.h> 38116182Sobrien__FBSDID("$FreeBSD$"); 39116182Sobrien 401541Srgrimes#include <sys/param.h> 411541Srgrimes#include <sys/systm.h> 421541Srgrimes#include <sys/malloc.h> 431541Srgrimes 44138781Salc/* 45166022Srrs * General routine to allocate a hash table with control of memory flags. 461541Srgrimes */ 471541Srgrimesvoid * 48166022Srrshashinit_flags(int elements, struct malloc_type *type, u_long *hashmask, 49166022Srrs int flags) 501541Srgrimes{ 511541Srgrimes long hashsize; 5260938Sjake LIST_HEAD(generic, generic) *hashtbl; 531541Srgrimes int i; 541541Srgrimes 55231587Sglebius KASSERT(elements > 0, ("%s: bad elements", __func__)); 56166022Srrs /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */ 57166022Srrs KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT), 58166042Srrs ("Bad flags (0x%x) passed to hashinit_flags", flags)); 59166022Srrs 601541Srgrimes for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 611541Srgrimes continue; 621541Srgrimes hashsize >>= 1; 63166022Srrs 64166022Srrs if (flags & HASH_NOWAIT) 65166022Srrs hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), 66166022Srrs type, M_NOWAIT); 67166022Srrs else 68166022Srrs hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), 69166022Srrs type, M_WAITOK); 70166022Srrs 71166022Srrs if (hashtbl != NULL) { 72166022Srrs for (i = 0; i < hashsize; i++) 73166022Srrs LIST_INIT(&hashtbl[i]); 74166022Srrs *hashmask = hashsize - 1; 75166022Srrs } 761541Srgrimes return (hashtbl); 771541Srgrimes} 787611Sdg 79166022Srrs/* 80166022Srrs * Allocate and initialize a hash table with default flag: may sleep. 81166022Srrs */ 82166022Srrsvoid * 83166022Srrshashinit(int elements, struct malloc_type *type, u_long *hashmask) 84166022Srrs{ 85166022Srrs 86166022Srrs return (hashinit_flags(elements, type, hashmask, HASH_WAITOK)); 87166022Srrs} 88166022Srrs 8999098Siedowsevoid 90111737Sdeshashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask) 9199098Siedowse{ 9299098Siedowse LIST_HEAD(generic, generic) *hashtbl, *hp; 9399098Siedowse 9499098Siedowse hashtbl = vhashtbl; 9599098Siedowse for (hp = hashtbl; hp <= &hashtbl[hashmask]; hp++) 96231587Sglebius KASSERT(LIST_EMPTY(hp), ("%s: hash not empty", __func__)); 9799098Siedowse free(hashtbl, type); 9899098Siedowse} 9999098Siedowse 100196454Srpaulostatic const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 101196454Srpaulo 2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 102196454Srpaulo 6653, 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 10326205Salex#define NPRIMES (sizeof(primes) / sizeof(primes[0])) 1047611Sdg 1057611Sdg/* 1067611Sdg * General routine to allocate a prime number sized hash table. 1077611Sdg */ 1087611Sdgvoid * 109111737Sdesphashinit(int elements, struct malloc_type *type, u_long *nentries) 1107611Sdg{ 1117611Sdg long hashsize; 11260938Sjake LIST_HEAD(generic, generic) *hashtbl; 1137611Sdg int i; 1147611Sdg 115231587Sglebius KASSERT(elements > 0, ("%s: bad elements", __func__)); 1167611Sdg for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 1177611Sdg i++; 1187611Sdg if (i == NPRIMES) 1197611Sdg break; 1207611Sdg hashsize = primes[i]; 1217611Sdg } 1227611Sdg hashsize = primes[i - 1]; 123111119Simp hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 1247611Sdg for (i = 0; i < hashsize; i++) 1257611Sdg LIST_INIT(&hashtbl[i]); 1267611Sdg *nentries = hashsize; 1277611Sdg return (hashtbl); 1287611Sdg} 129