yc_bbstree.h

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software for any
 * purpose is hereby granted without fee, provided that the above copyright
 * notice appear in all copies and that both that copyright notice and this
 * permission notice appear in supporting documentation.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

/******************************************************************************/
/******************************************************************************/
#ifndef __MACRO_C_YOUNG_LIBRARY_BALANCED_BINARY_SEARCH_TREE_HEADER_FILE__
#define __MACRO_C_YOUNG_LIBRARY_BALANCED_BINARY_SEARCH_TREE_HEADER_FILE__
/******************************************************************************/
#include "yc_definition.h"

#ifdef __cplusplus
    namespace youngc {  extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/

typedef  enum { RED = 0, BLACK = 1 }  rbtree_color_t;

typedef  struct balanced_binary_search_tree_node
{
    struct balanced_binary_search_tree_node*  left;
    struct balanced_binary_search_tree_node*  right;
    struct balanced_binary_search_tree_node*  parent;
    rbtree_color_t  color;
}  bbstree_node;

typedef  struct balanced_binary_search_tree_object
{
    bbstree_node       m_header;
    size_t             m_node_count;
    size_t             m_element_size;
    ylib_fp_copy_t     m_elmt_init_copy; /* safe function */
    ylib_fp_oper_t     m_elmt_destroy;   /* safe function */
    ylib_fp_get_t      m_get_key;        /* safe function */
    ylib_fp_cmp_t      m_cmp_key;        /* safe function */
    ylib_fp_alloc_t    m_alloc;          /* safe function */
    ylib_fp_dealloc_t  m_dealloc;        /* safe function */
}  bbstree;

typedef  bbstree_node*  bbstree_iterator;

typedef  struct bbstree_pair_iterator
{
    bbstree_iterator  first;
    bbstree_iterator  second;
}  bbstree_pair_iterator;

/******************************************************************************/

#define BBSTREE_ITR_DEREF( ITR, TYPE ) \
        ( *( (TYPE*)( ((ylib_byte_t*)(ITR)) + sizeof(bbstree_node) ) ) )

#define BBSTREE_BEGIN( TREE )   ( (TREE).m_header.left )

#define BBSTREE_END( TREE )     ( &((TREE).m_header) )

#define BBSTREE_SIZE( TREE )    ( (TREE).m_node_count )

/******************************************************************************/

/* *iterator */
#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void* bbstree_itr_deref( bbstree_iterator itr );
#else
    inline void* bbstree_itr_deref( bbstree_iterator itr )
    {
        return ((ylib_byte_t*)itr) + sizeof(bbstree_node);
    }
#endif

/* ++iterator */
void bbstree_itr_inc( bbstree_iterator* pitr );

/* --iterator */
void bbstree_itr_dec( bbstree_iterator* pitr );

/******************************************************************************/

void bbstree_init( bbstree* uninit_self,
                   size_t element_size,
                   ylib_fp_copy_t elmt_init_copy,
                   ylib_fp_oper_t elmt_destroy,
                   ylib_fp_get_t get_key,
                   ylib_fp_cmp_t cmp_key,
                   ylib_fp_alloc_t alloc,
                   ylib_fp_dealloc_t dealloc );

void bbstree_destroy( bbstree* self );

/* (1) < 0: uninit_self = src;  (2) = 0: fail;  (3) > 0: succeed */
int bbstree_init_copy( bbstree* uninit_self,
                       const bbstree* src );

/* (1) < 0: self = src or can't matching;  (2) = 0: fail;  (3) > 0: succeed */
int bbstree_assign_copy( bbstree* self,
                         const bbstree* src );

void bbstree_init_move( bbstree* uninit_self,
                        bbstree* src );

void bbstree_assign_move( bbstree* self,
                          bbstree* src );

void bbstree_swap( bbstree* self,
                   bbstree* other );

/* returns an iterator that designates the earliest element in the tree whose
 * sort key equals key. If no such element exists, the iterator equals
 * bbstree_end() */
bbstree_iterator bbstree_find( bbstree* self,
                               const void* key );

/* returns an iterator that designates the earliest element key in the
 * tree for which m_cmp_key( element, key ) < 0. If no such element exists,
 * the function returns bbstree_end() */
bbstree_iterator bbstree_lower_bound( bbstree* self,
                                      const void* key );

/* returns an iterator that designates the earliest element key in the
 * tree for which m_cmp_key( key, element ) < 0. If no such element exists,
 * the function returns bbstree_end() */
bbstree_iterator bbstree_upper_bound( bbstree* self,
                                      const void* key );

/* returns a pair of iterators x such that x.first == bbstree_lower_bound(key)
 * and x.second == bbstree_upper_bound(key) */
bbstree_pair_iterator bbstree_equal_range( bbstree* self,
                                           const void* key );

/* returns the number of elements x in the range
 * [ bbstree_lower_bound(key), bbstree_upper_bound(key) ) */
size_t bbstree_count( bbstree* self,
                      const void* key );

/* removes the element of the tree pointed to by pos */
void bbstree_erase_pos( bbstree* self,
                        bbstree_iterator pos );

/* removes the elements in the range [first, last) */
void bbstree_erase_range( bbstree* self,
                          bbstree_iterator first,
                          bbstree_iterator last );

/* removes the elements with sort keys in the range
 * [ bbstree_lower_bound(key), bbstree_upper_bound(key) ),
 * it returns the number of elements it removes */
size_t bbstree_erase_key( bbstree* self,
                          const void* key );

/* if value exists returns a iterator pointer to value; if not, it creates
 * such an element x and initializes it with value, if succeeded returns
 * the iterator that designates the inserted element, otherwise returns NULL */
bbstree_iterator bbstree_insert_unique_value( bbstree* self,
                                              const void* value );

/* equivalent to bbstree_insert_unique_value(value), return value is an
 * iterator pointing to the element with the key equivalent to that of value,
 * the iterator pos is a hint pointing to where the search should start */
bbstree_iterator bbstree_insert_unique_pos( bbstree* self,
                                            bbstree_iterator pos,
                                            const void* value );

/* inserts the value in the tree, if succeeded returns the iterator that
 * designates the inserted element, otherwise returns NULL */
bbstree_iterator bbstree_insert_equal_value( bbstree* self,
                                             const void* value );

/* equivalent to bbstree_insert_equal_value(value), return value is an
 * iterator pointing to the element with the key equivalent to that of value,
 * the iterator pos is a hint pointing to where the search should start */
bbstree_iterator bbstree_insert_equal_pos( bbstree* self,
                                           bbstree_iterator pos,
                                           const void* value );

/* if new_key exists returns false, otherwise replaces key of pos to new_key
 * and returns true */
bool bbstree_replace_key_unique_pos( bbstree* self,
                                     bbstree_iterator pos,
                                     const void* new_key,
                                     ylib_fp_copy_t copy_key );

/* if new_key exists returns a iterator pointer to new_key, otherwise replaces
 * old_key to new_key and returns a iterator pointer to new_key */
bbstree_iterator bbstree_replace_key_unique( bbstree* self,
                                             const void* old_key,
                                             const void* new_key,
                                             ylib_fp_copy_t copy_key );

/* replaces key of pos to new_key */
void bbstree_replace_key_equal_pos( bbstree* self,
                                    bbstree_iterator pos,
                                    const void* new_key,
                                    ylib_fp_copy_t copy_key );

/* replaces key of elements to new_key in the range
 * [ bbstree_lower_bound(old_key), bbstree_upper_bound(old_key) ) */
void bbstree_replace_key_equal( bbstree* self,
                                const void* old_key,
                                const void* new_key,
                                ylib_fp_copy_t copy_key );

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    size_t bbstree_max_size( void );

    size_t bbstree_size( bbstree* self );

    bbstree_iterator bbstree_begin( bbstree* self );

    bbstree_iterator bbstree_end( bbstree* self );
#else
    inline size_t bbstree_max_size( void )
    {
        return SIZE_MAX;
    }

    inline size_t bbstree_size( bbstree* self )
    {
        return self->m_node_count;
    }

    inline bbstree_iterator bbstree_begin( bbstree* self )
    {
        return self->m_header.left;
    }

    inline bbstree_iterator bbstree_end( bbstree* self )
    {
        return &(self->m_header);
    }
#endif

/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
    }  }
#endif
#endif
/******************************************************************************/
/******************************************************************************/