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$");
   39 
   40 #include <sys/param.h>
   41 #include <sys/systm.h>
   42 #include <sys/malloc.h>
   43 
   44 /*
   45  * General routine to allocate a hash table with control of memory flags.
   46  */
   47 void *
   48 hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask,
   49     int flags)
   50 {
   51         long hashsize;
   52         LIST_HEAD(generic, generic) *hashtbl;
   53         int i;
   54 
   55         KASSERT(elements > 0, ("%s: bad elements", __func__));
   56         /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */
   57         KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT),
   58             ("Bad flags (0x%x) passed to hashinit_flags", flags));
   59 
   60         for (hashsize = 1; hashsize <= elements; hashsize <<= 1)
   61                 continue;
   62         hashsize >>= 1;
   63 
   64         if (flags & HASH_NOWAIT)
   65                 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl),
   66                     type, M_NOWAIT);
   67         else
   68                 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl),
   69                     type, M_WAITOK);
   70 
   71         if (hashtbl != NULL) {
   72                 for (i = 0; i < hashsize; i++)
   73                         LIST_INIT(&hashtbl[i]);
   74                 *hashmask = hashsize - 1;
   75         }
   76         return (hashtbl);
   77 }
   78 
   79 /*
   80  * Allocate and initialize a hash table with default flag: may sleep.
   81  */
   82 void *
   83 hashinit(int elements, struct malloc_type *type, u_long *hashmask)
   84 {
   85 
   86         return (hashinit_flags(elements, type, hashmask, HASH_WAITOK));
   87 }
   88 
   89 void
   90 hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask)
   91 {
   92         LIST_HEAD(generic, generic) *hashtbl, *hp;
   93 
   94         hashtbl = vhashtbl;
   95         for (hp = hashtbl; hp <= &hashtbl[hashmask]; hp++)
   96                 KASSERT(LIST_EMPTY(hp), ("%s: hash not empty", __func__));
   97         free(hashtbl, type);
   98 }
   99 
  100 static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531,
  101                         2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143,
  102                         6653, 7159, 7673, 8191, 12281, 16381, 24571, 32749 };
  103 #define NPRIMES (sizeof(primes) / sizeof(primes[0]))
  104 
  105 /*
  106  * General routine to allocate a prime number sized hash table.
  107  */
  108 void *
  109 phashinit(int elements, struct malloc_type *type, u_long *nentries)
  110 {
  111         long hashsize;
  112         LIST_HEAD(generic, generic) *hashtbl;
  113         int i;
  114 
  115         KASSERT(elements > 0, ("%s: bad elements", __func__));
  116         for (i = 1, hashsize = primes[1]; hashsize <= elements;) {
  117                 i++;
  118                 if (i == NPRIMES)
  119                         break;
  120                 hashsize = primes[i];
  121         }
  122         hashsize = primes[i - 1];
  123         hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK);
  124         for (i = 0; i < hashsize; i++)
  125                 LIST_INIT(&hashtbl[i]);
  126         *nentries = hashsize;
  127         return (hashtbl);
  128 }

Cache object: 0804e6e1ac0c7aba5c2e10fa37a12db9


[ 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.