The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_hash.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 1982, 1986, 1991, 1993
    3  *      The Regents of the University of California.  All rights reserved.
    4  * (c) UNIX System Laboratories, Inc.
    5  * All or some portions of this file are derived from material licensed
    6  * to the University of California by American Telephone and Telegraph
    7  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
    8  * the permission of UNIX System Laboratories, Inc.
    9  *
   10  * Redistribution and use in source and binary forms, with or without
   11  * modification, are permitted provided that the following conditions
   12  * are met:
   13  * 1. Redistributions of source code must retain the above copyright
   14  *    notice, this list of conditions and the following disclaimer.
   15  * 2. Redistributions in binary form must reproduce the above copyright
   16  *    notice, this list of conditions and the following disclaimer in the
   17  *    documentation and/or other materials provided with the distribution.
   18  * 4. Neither the name of the University nor the names of its contributors
   19  *    may be used to endorse or promote products derived from this software
   20  *    without specific prior written permission.
   21  *
   22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   32  * SUCH DAMAGE.
   33  *
   34  *      @(#)kern_subr.c 8.3 (Berkeley) 1/21/94
   35  */
   36 
   37 #include <sys/cdefs.h>
   38 __FBSDID("$FreeBSD: releng/11.2/sys/kern/subr_hash.c 331722 2018-03-29 02:50:57Z eadler $");
   39 
   40 #include <sys/param.h>
   41 #include <sys/systm.h>
   42 #include <sys/malloc.h>
   43 
   44 static __inline int
   45 hash_mflags(int flags)
   46 {
   47 
   48         return ((flags & HASH_NOWAIT) ? M_NOWAIT : M_WAITOK);
   49 }
   50 
   51 /*
   52  * General routine to allocate a hash table with control of memory flags.
   53  */
   54 void *
   55 hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask,
   56     int flags)
   57 {
   58         long hashsize;
   59         LIST_HEAD(generic, generic) *hashtbl;
   60         int i;
   61 
   62         KASSERT(elements > 0, ("%s: bad elements", __func__));
   63         /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */
   64         KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT),
   65             ("Bad flags (0x%x) passed to hashinit_flags", flags));
   66 
   67         for (hashsize = 1; hashsize <= elements; hashsize <<= 1)
   68                 continue;
   69         hashsize >>= 1;
   70 
   71         hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type,
   72             hash_mflags(flags));
   73         if (hashtbl != NULL) {
   74                 for (i = 0; i < hashsize; i++)
   75                         LIST_INIT(&hashtbl[i]);
   76                 *hashmask = hashsize - 1;
   77         }
   78         return (hashtbl);
   79 }
   80 
   81 /*
   82  * Allocate and initialize a hash table with default flag: may sleep.
   83  */
   84 void *
   85 hashinit(int elements, struct malloc_type *type, u_long *hashmask)
   86 {
   87 
   88         return (hashinit_flags(elements, type, hashmask, HASH_WAITOK));
   89 }
   90 
   91 void
   92 hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask)
   93 {
   94         LIST_HEAD(generic, generic) *hashtbl, *hp;
   95 
   96         hashtbl = vhashtbl;
   97         for (hp = hashtbl; hp <= &hashtbl[hashmask]; hp++)
   98                 KASSERT(LIST_EMPTY(hp), ("%s: hashtbl %p not empty "
   99                     "(malloc type %s)", __func__, hashtbl, type->ks_shortdesc));
  100         free(hashtbl, type);
  101 }
  102 
  103 static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531,
  104                         2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143,
  105                         6653, 7159, 7673, 8191, 12281, 16381, 24571, 32749 };
  106 #define NPRIMES nitems(primes)
  107 
  108 /*
  109  * General routine to allocate a prime number sized hash table with control of
  110  * memory flags.
  111  */
  112 void *
  113 phashinit_flags(int elements, struct malloc_type *type, u_long *nentries, int flags)
  114 {
  115         long hashsize;
  116         LIST_HEAD(generic, generic) *hashtbl;
  117         int i;
  118 
  119         KASSERT(elements > 0, ("%s: bad elements", __func__));
  120         /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */
  121         KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT),
  122             ("Bad flags (0x%x) passed to phashinit_flags", flags));
  123 
  124         for (i = 1, hashsize = primes[1]; hashsize <= elements;) {
  125                 i++;
  126                 if (i == NPRIMES)
  127                         break;
  128                 hashsize = primes[i];
  129         }
  130         hashsize = primes[i - 1];
  131 
  132         hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type,
  133             hash_mflags(flags));
  134         if (hashtbl == NULL)
  135                 return (NULL);
  136 
  137         for (i = 0; i < hashsize; i++)
  138                 LIST_INIT(&hashtbl[i]);
  139         *nentries = hashsize;
  140         return (hashtbl);
  141 }
  142 
  143 /*
  144  * Allocate and initialize a prime number sized hash table with default flag:
  145  * may sleep.
  146  */
  147 void *
  148 phashinit(int elements, struct malloc_type *type, u_long *nentries)
  149 {
  150 
  151         return (phashinit_flags(elements, type, nentries, HASH_WAITOK));
  152 }

Cache object: fa284b9ed5f1bfd198f25d5a19f0b8a7


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.