/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 2; tab-width: 2 -*- */
/*
 * tree.h
 *
 * libtdata is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation, either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * libtdata 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.";
 */

#ifndef __TREE_H__
#define __TREE_H__

#include <tdata/usrtc.h>

#define tree_root_priv(T) ((T)->sentinel.left)
#define tree_null_priv(L) (&(L)->sentinel)
#define TREE_DEPTH_MAX 64

/*tree functions*/
void usrtc_tree_init(usrtc_t *us);
void usrtc_tree_insert(usrtc_t *us, usrtc_node_t *node, const void *key);
void usrtc_tree_delete(usrtc_t *us, usrtc_node_t *node, usrtc_node_t **pswap,
											 usrtc_node_t **pchild);
usrtc_node_t *usrtc_tree_lookup(usrtc_t *us, const void *key);
usrtc_node_t *usrtc_tree_lower_bound(usrtc_t *us, const void *key);
usrtc_node_t *usrtc_tree_upper_bound(usrtc_t *us, const void *key);
usrtc_node_t *usrtc_tree_first(usrtc_t *us);
usrtc_node_t *usrtc_tree_last(usrtc_t *us);
usrtc_node_t *usrtc_tree_next(usrtc_t *us, usrtc_node_t *curr);
usrtc_node_t *usrtc_tree_prev(usrtc_t *us, usrtc_node_t *curr);
void usrtc_tree_convert_to_list(usrtc_t *us);
void usrtc_tree_convert_from_list(usrtc_t *us);
void usrtc_tree_rotate_left(usrtc_node_t *child, usrtc_node_t *parent);
void usrtc_tree_rotate_right(usrtc_node_t *child, usrtc_node_t *parent);


#endif /*__TREE_H__*/