1/*
2 * Copyright (c) 2009 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29
30#ifndef __HYBRID_ALLOC__
31#define __HYBRID_ALLOC__
32
33#include <sys/types.h>
34#include "RedBlackTree.h"
35
36typedef struct extent_node extent_node_t;
37
38struct extent_node
39{
40	u_int32_t length;
41	u_int32_t offset;
42	struct extent_node *offset_next;
43	rb_node(extent_node_t) offset_link;
44};
45
46typedef rb_tree(extent_node_t) extent_tree_offset_t;
47
48extern extent_node_t *
49alloc_node(u_int32_t length, u_int32_t offset);
50
51extern void
52free_node(extent_node_t *node);
53
54extern extent_node_t *
55extent_tree_free_space( extent_tree_offset_t *offset_tree, u_int32_t size, u_int32_t offset);
56
57extern void
58extent_tree_offset_print(extent_tree_offset_t *offset_tree);
59
60extern int32_t
61extent_tree_offset_alloc_space(extent_tree_offset_t *offset_tree, u_int32_t size, u_int32_t offset);
62
63extern int32_t
64extent_tree_offset_alloc_unaligned(extent_tree_offset_t *tree, u_int32_t size, u_int32_t offset);
65
66
67extern void
68extent_tree_remove_node (extent_tree_offset_t *offset_tree, extent_node_t * node);
69
70extern extent_node_t *
71extent_tree_off_first (extent_tree_offset_t *offset_tree);
72
73extern extent_node_t *
74extent_tree_off_search(extent_tree_offset_t *offset_tree, extent_node_t *node);
75
76extern extent_node_t *
77extent_tree_off_search_next(extent_tree_offset_t *offset_tree, extent_node_t *node);
78
79extern extent_node_t*
80extent_tree_off_search_nextWithSize (extent_tree_offset_t *offset_tree, extent_node_t *node);
81
82extern extent_node_t *
83extent_tree_off_search_prev(extent_tree_offset_t *offset_tree, extent_node_t *node);
84
85extern extent_node_t *
86extent_tree_off_next(extent_tree_offset_t *offset_tree, extent_node_t *node);
87
88extern extent_node_t *
89extent_tree_off_prev(extent_tree_offset_t *offset_tree, extent_node_t *node);
90
91extern void
92extent_tree_init(extent_tree_offset_t *offset_tree);
93
94extern void
95extent_tree_destroy(extent_tree_offset_t *offset_tree);
96
97extern int
98cmp_offset_node(extent_node_t *node_1, extent_node_t *node_2);
99
100
101#endif
102