lib/include/tree.h

Go to the documentation of this file.

//  This file is part of MOS, the MANTIS Operating System
//  See http://mantis.cs.colorado.edu/
//
//  Copyright (c) 2002 - 2007 University of Colorado, Boulder
//
//   All rights reserved.
//
//   Redistribution and use in source and binary forms, with or without
//   modification, are permitted provided that the following conditions are
//   met:
//
//       * Redistributions of source code must retain the above copyright
//         notice, this list of conditions and the following disclaimer.
//       * Redistributions in binary form must reproduce the above
//         copyright notice, this list of conditions and the following
//         disclaimer in the documentation and/or other materials provided
//         with the distribution. 
//       * Neither the name of the MANTIS Project nor the names of its
//         contributors may be used to endorse or promote products derived
//         from this software without specific prior written permission.
//
//   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
//   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
//   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
//   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
//   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
//   INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
//   BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
//   LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
//   CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
//   LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
//   ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
//   POSSIBILITY OF SUCH DAMAGE.

#include <inttypes.h>

enum {
   TREE_OK,
   TREE_NODE_EXISTS,
   TREE_NODE_NOT_FOUND,
   TREE_OUT_OF_MEM,
   TREE_INVALID_ROTATION
};

typedef struct node_t{
   uint16_t key;
   //uint16_t aux; //user data
   struct node_t *left,*right, *p;
}tree_node;

typedef tree_node* node_ptr;

void print_tree(node_ptr starting_point);

void clear_tree();

node_ptr get_root();

uint8_t insert(uint16_t key);

node_ptr find(uint16_t key);

node_ptr find_node(uint16_t key);

uint8_t delete(uint16_t key);

uint8_t left_rotate_node(uint16_t key);

uint8_t right_rotate_node(uint16_t key);

uint8_t left_rotate(node_ptr x);

uint8_t right_rotate(node_ptr x);

void splay(node_ptr x);

void splay_node(uint16_t key);

node_ptr get_min();

node_ptr get_max();

uint16_t count_nodes(node_ptr starting_point);

uint16_t get_total(node_ptr starting_point);

---