yc_hashtable.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_HASH_TABLE_HEADER_FILE__
#define __MACRO_C_YOUNG_LIBRARY_HASH_TABLE_HEADER_FILE__
/******************************************************************************/
#include "yc_definition.h"

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

typedef  size_t (*ylib_fp_hash_t)( const void* key );

typedef  struct hash_table_node
{
    struct hash_table_node*  next;
}  hashtable_node;

typedef  struct hash_table_object
{
    hashtable_node**   m_chain_table;
    size_t             m_node_count;
    size_t             m_table_len;
    float              m_factor;
    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_equal_key;      /* safe function */
    ylib_fp_hash_t     m_hash_key;       /* safe function */
    ylib_fp_alloc_t    m_alloc;          /* safe function */
    ylib_fp_dealloc_t  m_dealloc;        /* safe function */
}  hashtable;

typedef  struct hash_table_iterator
{
    hashtable_node*  node;
    hashtable*       table;
}  hstb_iterator;

typedef  struct hash_table_pair_iterator
{
    hstb_iterator  first;
    hstb_iterator  second;
}  hstb_pair_iterator;

typedef  hashtable_node*  hstb_local_iterator;

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

#define HASHTABLE_LC_ITR_INC( LCITR )  ( (LCITR) = (LCITR).next )

#define HASHTABLE_LC_ITR_DEREF( LCITR, TYPE ) \
        ( *( (TYPE*)( ((ylib_byte_t*)(LCITR)) + sizeof(hashtable_node) ) ) )

#define HASHTABLE_ITR_DEREF( ITR, TYPE ) \
        ( *( (TYPE*)( ((ylib_byte_t*)((ITR).node)) + sizeof(hashtable_node) ) ) )

#define HASHTABLE_SIZE( HT )  ( (HT).m_node_count )

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

/* ++iterator */
void hstb_itr_inc( hstb_iterator* pitr );

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    /* left == right */
    bool hstb_itr_equal( const hstb_iterator left,
                         const hstb_iterator right );

    /* *iterator */
    void* hstb_itr_deref( hstb_iterator itr );

    /* ++local_iterator */
    void hstb_lc_itr_inc( hstb_local_iterator* plcitr );

    /* *local_iterator */
    void* hstb_lc_itr_deref( hstb_local_iterator itr );
#else
    inline bool hstb_itr_equal( const hstb_iterator left,
                                const hstb_iterator right )
    {
        return left.node == right.node ? true : false;
    }

    inline void* hstb_itr_deref( hstb_iterator itr )
    {
        return ((ylib_byte_t*)(itr.node)) + sizeof(hashtable_node);
    }

    inline void hstb_lc_itr_inc( hstb_local_iterator* plcitr )
    {
        *plcitr = (*plcitr)->next;
    }

    inline void* hstb_lc_itr_deref( hstb_local_iterator lcitr )
    {
        return ((ylib_byte_t*)lcitr) + sizeof(hashtable_node);
    }
#endif

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

void hstb_init( hashtable* uninit_self,
                float max_load_factor,
                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 equal_key,
                ylib_fp_hash_t hash_key,
                ylib_fp_alloc_t alloc,
                ylib_fp_dealloc_t dealloc );

void hstb_destroy( hashtable* self );

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

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

void hstb_init_move( hashtable* uninit_self,
                     hashtable* src );

void hstb_assign_move( hashtable* self,
                       hashtable* src );

hstb_iterator hstb_begin( hashtable* self );

/* rehashes the hash table, ensuring that it contains at least n chains,
 * if succeeded returns true, otherwise returns false */
bool hstb_rehash( hashtable* self,
                  size_t new_capacity );

/* returns the number of elements in the hash table that equivalent to key */
size_t hstb_count( hashtable* self,
                   const void* key );

/* returns an iterator that designates the earliest element in the hash table
 * whose sort key equals key. If no such element exists, the iterator equals
 * hstb_end() */
hstb_iterator hstb_find( hashtable* self,
                         const void* key );

/* returns a range that contains all of the elements with the specified key,
 * it returns ( first = hstb_end(), second = hstb_end() ) if no such elements
 * exist */
hstb_pair_iterator hstb_equal_range( hashtable* self,
                                     const void* key );

/* removes the element of the hash table pointed to by pos */
void hstb_erase_pos( hashtable* self,
                     hstb_iterator pos );

/* removes the elements in the range [first, last) */
void hstb_erase_range( hashtable* self,
                       hstb_iterator first,
                       hstb_iterator last );

/* erases all elements with key equivalent to key, returns the number of
 * elements erased */
size_t hstb_erase_key( hashtable* 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, insert succeeded returns
 * the iterator that designates the inserted element, otherwise returns
 * hstb_end() */
hstb_iterator hstb_insert_unique( hashtable* self,
                                  const void* value );

/* equivalent to hstb_insert_unique(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 */
hstb_iterator hstb_insert_unique_pos( hashtable* self,
                                      hstb_iterator pos,
                                      const void* value );

/* inserts the value in the hash table, if succeeded returns the iterator that
 * designates the inserted element, otherwise returns hstb_end() */
hstb_iterator hstb_insert_equal( hashtable* self,
                                 const void* value );

/* equivalent to hstb_insert_equal(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 */
hstb_iterator hstb_insert_equal_pos( hashtable* self,
                                     hstb_iterator pos,
                                     const void* value );

/* if new_key exists returns false, otherwise replaces key of pos to new_key
 * and returns true */
bool hstb_replace_key_unique_pos( hashtable* self,
                                  hstb_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 */
hstb_iterator hstb_replace_key_unique( hashtable* self,
                                       const void* old_key,
                                       const void* new_key,
                                       ylib_fp_copy_t copy_key );

/* replaces key of pos to new_key */
void hstb_replace_key_equal_pos( hashtable* self,
                                 hstb_iterator pos,
                                 const void* new_key,
                                 ylib_fp_copy_t copy_key );

/* replaces key of elements to new_key in the range
 * [ hstb_equal_range(old_key).first, hstb_equal_range(old_key).second ) */
void hstb_replace_key_equal( hashtable* self,
                             const void* old_key,
                             const void* new_key,
                             ylib_fp_copy_t copy_key );

/* max_load_factor is positive, changes the container's maximum load factor,
 * using max_load_factor as a hint */
void hstb_set_max_load_factor( hashtable* self,
                               float max_load_factor );

/* returns an upper bound on the number of chains that hash table
 * might ever contain */
size_t hstb_max_chain_count( void );

/* returns the number of chains that hash table contains */
size_t hstb_chain_count( hashtable* self );

/* index is in the range [ 0, hstb_chain_count() ), returns the number of
 * elements in m_chain_table[index] */
size_t hstb_chain_size( hashtable* self,
                        size_t index );

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    hstb_iterator hstb_end( hashtable* self );

    hstb_local_iterator hstb_local_begin( hashtable* self,
                                          size_t index );

    hstb_local_iterator hstb_local_end( void );

    size_t hstb_max_size( void );

    size_t hstb_size( hashtable* self );

    size_t hstb_table_size( hashtable* self );

    /* returns the index of the chain in which elements with keys equivalent
     * to key would be found, if any such element existed */
    size_t hstb_key_chain( hashtable* self,
                           const void* key );

    /* returns the average number of elements per chain */
    float hstb_load_factor( hashtable* self );

    /* returns a number that the container attempts to keep the load factor
     * less than or equal to, the container automatically increases the number
     * of chains as necessary to keep the load factor below this number, return
     * value is positive */
    float hstb_get_max_load_factor( hashtable* self );
#else
    inline hstb_iterator hstb_end( hashtable* self )
    {
        hstb_iterator end;
        end.node = NULL;
        end.table = self;
        return end;
    }

    inline hstb_local_iterator hstb_local_begin( hashtable* self,
                                                 size_t index )
    {
        return self->m_chain_table[index];
    }

    inline hstb_local_iterator hstb_local_end( void )
    {
        return NULL;
    }

    inline size_t hstb_max_size( void )
    {
        return SIZE_MAX;
    }

    inline size_t hstb_size( hashtable* self )
    {
        return self->m_node_count;
    }

    inline size_t hstb_table_size( hashtable* self )
    {
        return self->m_table_len;
    }

    inline size_t hstb_key_chain( hashtable* self,
                                  const void* key )
    {
        return self->m_table_len == 0
               ? 0 : self->m_hash_key( key ) % self->m_table_len;
    }

    inline float hstb_load_factor( hashtable* self )
    {
        return self->m_table_len == 0
               ? (float)0.0
               : (float)(self->m_node_count) / (float)(self->m_table_len);
    }

    inline float hstb_get_max_load_factor( hashtable* self )
    {
        return self->m_factor;
    }
#endif

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