headers/private/kernel/util/RadixBitmap.h

   1 /*-
   2  * Copyright (c) 1998 Matthew Dillon.  All Rights Reserved.
   3  * Redistribution and use in source and binary forms, with or without
   4  * modification, are permitted provided that the following conditions
   5  * are met:
   6  * 1. Redistributions of source code must retain the above copyright
   7  *    notice, this list of conditions and the following disclaimer.
   8  * 2. Redistributions in binary form must reproduce the above copyright
   9  *    notice, this list of conditions and the following disclaimer in the
  10  *    documentation and/or other materials provided with the distribution.
  11  * 4. Neither the name of the University nor the names of its contributors
  12  *    may be used to endorse or promote products derived from this software
  13  *    without specific prior written permission.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  16  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  19  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  21  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  22  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  24  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 /*
  29  * The radix bitmap structure is ported from FreeBSD.
  30  */
  31
  32
  33 #ifndef _KERNEL_UTIL_RADIX_BITMAP_H
  34 #define _KERNEL_UTIL_RADIX_BITMAP_H
  35
  36
  37 #include <SupportDefs.h>
  38
  39
  40 typedef uint32 radix_slot_t;
  41 typedef uint32 bitmap_t;
  42
  43 typedef struct radix_node {
  44         union {
  45                 bitmap_t  bitmap;      // bitmap for the slots if we are a leaf
  46                 int32     available;   // available slots under us if we are not a leaf
  47         } u;
  48         int32  big_hint;  // the biggest continuous slots under us
  49 } radix_node;
  50
  51 // Bitmap which uses radix tree for hinting.
  52 // The radix tree is stored in an array.
  53 typedef struct radix_bitmap {
  54         radix_slot_t    free_slots;     // # of free slots
  55         radix_slot_t    radix;          // coverage radix
  56         radix_slot_t    skip;           // starting skip
  57         radix_node              *root;          // root of radix tree, actually it is an array
  58         radix_slot_t    root_size;      // size of the array(# of nodes in the tree)
  59 } radix_bitmap;
  60
  61
  62 #define BITMAP_RADIX  (sizeof(radix_slot_t) * 8)
  63 #define NODE_RADIX    16
  64
  65 #define RADIX_SLOT_NONE ((radix_slot_t)-1)
  66
  67
  68 extern radix_bitmap *radix_bitmap_create(uint32 slots);
  69 extern radix_slot_t radix_bitmap_alloc(radix_bitmap *bmp, uint32 count);
  70 extern void radix_bitmap_dealloc(radix_bitmap *bmp, radix_slot_t slotIndex,
  71                 uint32 count);
  72 extern void radix_bitmap_destroy(radix_bitmap *bmp);
  73
  74 #endif  // _KERNEL_UTIL_RADIX_BITMAP_H
  75