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
40typedef uint32 radix_slot_t;
41typedef uint32 bitmap_t;
42
43typedef 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.
53typedef 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
68extern radix_bitmap *radix_bitmap_create(uint32 slots);
69extern radix_slot_t radix_bitmap_alloc(radix_bitmap *bmp, uint32 count);
70extern void radix_bitmap_dealloc(radix_bitmap *bmp, radix_slot_t slotIndex,
71		uint32 count);
72extern void radix_bitmap_destroy(radix_bitmap *bmp);
73
74#endif  // _KERNEL_UTIL_RADIX_BITMAP_H
75
76