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 44299040Ssephestatic __inline int 45299040Ssephehash_mflags(int flags) 46299040Ssephe{ 47299040Ssephe 48299040Ssephe return ((flags & HASH_NOWAIT) ? M_NOWAIT : M_WAITOK); 49299040Ssephe} 50299040Ssephe 51138781Salc/* 52166022Srrs * General routine to allocate a hash table with control of memory flags. 531541Srgrimes */ 541541Srgrimesvoid * 55166022Srrshashinit_flags(int elements, struct malloc_type *type, u_long *hashmask, 56166022Srrs int flags) 571541Srgrimes{ 581541Srgrimes long hashsize; 5960938Sjake LIST_HEAD(generic, generic) *hashtbl; 601541Srgrimes int i; 611541Srgrimes 62230486Sglebius KASSERT(elements > 0, ("%s: bad elements", __func__)); 63166022Srrs /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */ 64166022Srrs KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT), 65166042Srrs ("Bad flags (0x%x) passed to hashinit_flags", flags)); 66166022Srrs 671541Srgrimes for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 681541Srgrimes continue; 691541Srgrimes hashsize >>= 1; 70166022Srrs 71299040Ssephe hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, 72299040Ssephe hash_mflags(flags)); 73166022Srrs if (hashtbl != NULL) { 74166022Srrs for (i = 0; i < hashsize; i++) 75166022Srrs LIST_INIT(&hashtbl[i]); 76166022Srrs *hashmask = hashsize - 1; 77166022Srrs } 781541Srgrimes return (hashtbl); 791541Srgrimes} 807611Sdg 81166022Srrs/* 82166022Srrs * Allocate and initialize a hash table with default flag: may sleep. 83166022Srrs */ 84166022Srrsvoid * 85166022Srrshashinit(int elements, struct malloc_type *type, u_long *hashmask) 86166022Srrs{ 87166022Srrs 88166022Srrs return (hashinit_flags(elements, type, hashmask, HASH_WAITOK)); 89166022Srrs} 90166022Srrs 9199098Siedowsevoid 92111737Sdeshashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask) 9399098Siedowse{ 9499098Siedowse LIST_HEAD(generic, generic) *hashtbl, *hp; 9599098Siedowse 9699098Siedowse hashtbl = vhashtbl; 9799098Siedowse for (hp = hashtbl; hp <= &hashtbl[hashmask]; hp++) 98297732Sbz KASSERT(LIST_EMPTY(hp), ("%s: hashtbl %p not empty " 99297732Sbz "(malloc type %s)", __func__, hashtbl, type->ks_shortdesc)); 10099098Siedowse free(hashtbl, type); 10199098Siedowse} 10299098Siedowse 103196454Srpaulostatic const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 104196454Srpaulo 2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 105196454Srpaulo 6653, 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 106298310Spfg#define NPRIMES nitems(primes) 1077611Sdg 1087611Sdg/* 109298956Ssephe * General routine to allocate a prime number sized hash table with control of 110298956Ssephe * memory flags. 1117611Sdg */ 1127611Sdgvoid * 113298956Ssephephashinit_flags(int elements, struct malloc_type *type, u_long *nentries, int flags) 1147611Sdg{ 1157611Sdg long hashsize; 11660938Sjake LIST_HEAD(generic, generic) *hashtbl; 117299040Ssephe int i; 1187611Sdg 119230486Sglebius KASSERT(elements > 0, ("%s: bad elements", __func__)); 120298956Ssephe /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */ 121298956Ssephe KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT), 122298956Ssephe ("Bad flags (0x%x) passed to phashinit_flags", flags)); 123298956Ssephe 1247611Sdg for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 1257611Sdg i++; 1267611Sdg if (i == NPRIMES) 1277611Sdg break; 1287611Sdg hashsize = primes[i]; 1297611Sdg } 1307611Sdg hashsize = primes[i - 1]; 131298956Ssephe 132299040Ssephe hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, 133299040Ssephe hash_mflags(flags)); 134298956Ssephe if (hashtbl == NULL) 135298956Ssephe return (NULL); 136298956Ssephe 1377611Sdg for (i = 0; i < hashsize; i++) 1387611Sdg LIST_INIT(&hashtbl[i]); 1397611Sdg *nentries = hashsize; 1407611Sdg return (hashtbl); 1417611Sdg} 142298956Ssephe 143298956Ssephe/* 144298956Ssephe * Allocate and initialize a prime number sized hash table with default flag: 145298956Ssephe * may sleep. 146298956Ssephe */ 147298956Ssephevoid * 148298956Ssephephashinit(int elements, struct malloc_type *type, u_long *nentries) 149298956Ssephe{ 150298956Ssephe 151298956Ssephe return (phashinit_flags(elements, type, nentries, HASH_WAITOK)); 152298956Ssephe} 153