FreeBSD/Linux Kernel Cross Reference
sys/sys/rpst.h
1 /* $NetBSD: rpst.h,v 1.3 2011/04/14 15:31:20 yamt Exp $ */
2
3 /*-
4 * Copyright (c)2009 YAMAMOTO Takashi,
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 #if !defined(_SYS_RPST_H_)
30 #define _SYS_RPST_H_
31
32 #if defined(_KERNEL) || defined(_STANDALONE)
33 #include <sys/types.h>
34 #else /* defined(_KERNEL) || defined(_STANDALONE) */
35 #include <stdint.h>
36 #endif /* defined(_KERNEL) || defined(_STANDALONE) */
37
38 struct rpst_tree {
39 struct rpst_node *t_root;
40 unsigned int t_height;
41 };
42
43 struct rpst_node {
44 struct rpst_node *n_parent;
45 struct rpst_node *n_children[2];
46 uint64_t n_y;
47 uint64_t n_x;
48 };
49
50 struct rpst_iterator {
51 struct rpst_tree *it_tree;
52 struct rpst_node *it_cur;
53 unsigned int it_idx;
54 unsigned int it_level;
55 uint64_t it_max_y;
56 uint64_t it_min_x;
57 uint64_t it_max_x;
58 };
59
60 void rpst_init_tree(struct rpst_tree *);
61 struct rpst_node *rpst_insert_node(struct rpst_tree *, struct rpst_node *);
62 void rpst_remove_node(struct rpst_tree *, struct rpst_node *);
63 struct rpst_node *rpst_iterate_first(struct rpst_tree *, uint64_t, uint64_t,
64 uint64_t, struct rpst_iterator *);
65 struct rpst_node *rpst_iterate_next(struct rpst_iterator *);
66
67 #endif /* !defined(_SYS_RPST_H_) */
Cache object: a36588831eb30f3d99d434e19ae66f69
|