ee5e5e7014159c6e7441bee6e72b09859013824b
[monolithium.git] / kernel / include / avl_tree.h
1 /*
2  * avl_tree.h
3  *
4  * Copyright (C) 2013 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
5  *
6  * This program is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Affero General Public License as
8  * published by the Free Software Foundation, either version 3 of the
9  * License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Affero General Public License for more details.
15  *
16  * You should have received a copy of the GNU Affero General Public License
17  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
18  */
19
20 #ifndef _AVL_TREE_H_
21 #define _AVL_TREE_H_
22
23 #include <common.h>
24
25 typedef struct _avl_tree_t
26 {
27     struct _avl_tree_t *parent, *left, *right, *next_equal;
28     qword_t key;
29 } avl_tree_t;
30
31 void avl_tree_insert(avl_tree_t **tree, avl_tree_t *node);
32 avl_tree_t *avl_tree_lookup(avl_tree_t *tree, qword_t key);
33 bool_t avl_tree_remove(avl_tree_t **tree, avl_tree_t *node);
34 avl_tree_t *avl_tree_lower_bound(avl_tree_t *tree, qword_t key);
35 avl_tree_t *avl_tree_upper_bound(avl_tree_t *tree, qword_t key);
36 bool_t avl_tree_change_key(avl_tree_t **tree, avl_tree_t *node, qword_t new_key);
37 avl_tree_t *avl_get_next_node(avl_tree_t *node);
38 avl_tree_t *avl_get_previous_node(avl_tree_t *node);
39
40 #endif