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
48static size_t
49hash_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 */
82void *
83hashinit(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 */
135void
136hashdone(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