monolithium/kernel/include/avl_tree.h

/*
 * avl_tree.h
 * 
 * Copyright (C) 2013 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_

#include <common.h>

typedef struct _avl_tree_t
{
    struct _avl_tree_t *parent, *left, *right, *next_equal;
    qword_t key;
} avl_tree_t;

void avl_tree_insert(avl_tree_t **tree, avl_tree_t *node);
avl_tree_t *avl_tree_lookup(avl_tree_t *tree, qword_t key);
bool_t avl_tree_remove(avl_tree_t **tree, avl_tree_t *node);
avl_tree_t *avl_tree_lower_bound(avl_tree_t *tree, qword_t key);
avl_tree_t *avl_tree_upper_bound(avl_tree_t *tree, qword_t key);
bool_t avl_tree_change_key(avl_tree_t **tree, avl_tree_t *node, qword_t new_key);
avl_tree_t *avl_get_next_node(avl_tree_t *node);
avl_tree_t *avl_get_previous_node(avl_tree_t *node);

#endif