1 /* $NetBSD: subr_hash.c,v 1.7 2016/07/06 05:20:48 ozaki-r Exp $ */ 2 3 /* 4 * Copyright (c) 1982, 1986, 1991, 1993 5 * The Regents of the University of California. All rights reserved. 6 * (c) UNIX System Laboratories, Inc. 7 * All or some portions of this file are derived from material licensed 8 * to the University of California by American Telephone and Telegraph 9 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 10 * the permission of UNIX System Laboratories, Inc. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * @(#)kern_subr.c 8.4 (Berkeley) 2/14/95 37 */ 38 39 #include <sys/cdefs.h> 40 __KERNEL_RCSID(0, "$NetBSD: subr_hash.c,v 1.7 2016/07/06 05:20:48 ozaki-r Exp $"); 41 42 #include <sys/param.h> 43 #include <sys/bitops.h> 44 #include <sys/kmem.h> 45 #include <sys/systm.h> 46 #include <sys/pslist.h> 47 48 static size_t 49 hash_list_size(enum hashtype htype) 50 { 51 LIST_HEAD(, generic) *hashtbl_list; 52 SLIST_HEAD(, generic) *hashtbl_slist; 53 TAILQ_HEAD(, generic) *hashtbl_tailq; 54 struct pslist_head *hashtbl_pslist; 55 size_t esize; 56 57 switch (htype) { 58 case HASH_LIST: 59 esize = sizeof(*hashtbl_list); 60 break; 61 case HASH_PSLIST: 62 esize = sizeof(*hashtbl_pslist); 63 break; 64 case HASH_SLIST: 65 esize = sizeof(*hashtbl_slist); 66 break; 67 case HASH_TAILQ: 68 esize = sizeof(*hashtbl_tailq); 69 break; 70 default: 71 panic("hashdone: invalid table type"); 72 } 73 return esize; 74 } 75 76 /* 77 * General routine to allocate a hash table. 78 * Allocate enough memory to hold at least `elements' list-head pointers. 79 * Return a pointer to the allocated space and set *hashmask to a pattern 80 * suitable for masking a value to use as an index into the returned array. 81 */ 82 void * 83 hashinit(u_int elements, enum hashtype htype, bool waitok, u_long *hashmask) 84 { 85 LIST_HEAD(, generic) *hashtbl_list; 86 SLIST_HEAD(, generic) *hashtbl_slist; 87 TAILQ_HEAD(, generic) *hashtbl_tailq; 88 struct pslist_head *hashtbl_pslist; 89 u_long hashsize, i; 90 size_t esize; 91 void *p; 92 93 KASSERT(elements > 0); 94 95 #define MAXELEMENTS (1U << ((sizeof(elements) * NBBY) - 1)) 96 if (elements > MAXELEMENTS) 97 elements = MAXELEMENTS; 98 99 hashsize = 1UL << (ilog2(elements - 1) + 1); 100 esize = hash_list_size(htype); 101 102 p = kmem_alloc(hashsize * esize, waitok ? KM_SLEEP : KM_NOSLEEP); 103 if (p == NULL) 104 return NULL; 105 106 switch (htype) { 107 case HASH_LIST: 108 hashtbl_list = p; 109 for (i = 0; i < hashsize; i++) 110 LIST_INIT(&hashtbl_list[i]); 111 break; 112 case HASH_PSLIST: 113 hashtbl_pslist = p; 114 for (i = 0; i < hashsize; i++) 115 PSLIST_INIT(&hashtbl_pslist[i]); 116 break; 117 case HASH_SLIST: 118 hashtbl_slist = p; 119 for (i = 0; i < hashsize; i++) 120 SLIST_INIT(&hashtbl_slist[i]); 121 break; 122 case HASH_TAILQ: 123 hashtbl_tailq = p; 124 for (i = 0; i < hashsize; i++) 125 TAILQ_INIT(&hashtbl_tailq[i]); 126 break; 127 } 128 *hashmask = hashsize - 1; 129 return p; 130 } 131 132 /* 133 * Free memory from hash table previosly allocated via hashinit(). 134 */ 135 void 136 hashdone(void *hashtbl, enum hashtype htype, u_long hashmask) 137 { 138 const size_t esize = hash_list_size(htype); 139 kmem_free(hashtbl, esize * (hashmask + 1)); 140 } 141