source: svn/newcon3bcm2_21bu/BSEAV/lib/utils/bhash.h @ 46

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

 *     Copyright (c) 2007 Broadcom Corporation

 *     All Rights Reserved

 *     Confidential Property of Broadcom Corporation

 *

 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE

 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR

 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.

 *

 * $brcm_Workfile: bhash.h $

 * $brcm_Revision: 4 $

 * $brcm_Date: 8/17/07 3:37p $

 *

 * Module Description:

 *

 * Hash table associative container

 * 

 * Revision History:

 *

 * $brcm_Log: /BSEAV/lib/utils/bhash.h $

 * 

 * 4   8/17/07 3:37p vsilyaev

 * PR 33812: Improved use of arguments in macro

 * 

 * 3   7/21/07 9:34p vsilyaev

 * PR 32813: Improved BHEAD_FOREACH_BEGIN

 * 

 * 2   7/18/07 7:02p vsilyaev

 * PR 32813: Improved itterator

 * 

 * 1   7/18/07 3:01p vsilyaev

 * PR 32813: Hash table data container

 * 

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

#ifndef __BHASH_H__

#define __BHASH_H__



#include "blst_slist.h"



/*================== Module Overview =====================================

This modules defines macros to control hash table associative container.

This container allows to associate any user defined data type with the user

defined key. Single data type could be simultaneously member of many associative

tables.



All operations are typesafe (doesn't require typecasting) and run in a constant space.



This module implements hash table with chaining type of collision resolution.

And conainer supports the following operations:



  o Insert a new entry - time complexity O(1)

  o Removal of entry by key - time complexity O(1) .. O(n) (*)

  o Lookup by key - time complexity O(1) .. O(n) (*)

  o Each element requires single pointer in order to be addded in to the container

  o Code size and execution time is about twice that for singly-linked list



Note *:

Performance of hash table is strongly corellated with quality of hash function.

With good quality hash function removal and lookup are O(1) (constant time), with poor

hash function there are meny collisions ans peformance degraded to O(n) (e.g. proportional

to number of elements stored in the container).

  

========================================================================*/



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

Summary:

    Creates new data type for the heash head

        

Description:

    Creates new data type for the hash head, this type used to create variable for the hash head.

    User should create new the hash head data type for every different element datatype.

        

Input:

        name - name for the new data type (structure)

    type - existing user data type(structure) used for element of the container



Example:    

     BHASH_HEAD(block_hash, block);

     struct block_hash container;



Returns:

    <none>

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

#define BHASH_HEAD(name, type, size) struct name { \

        BLST_S_HEAD(name##_index, type) hash_bucket[size]; }  



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

Summary:

    Defines hash entry

        

Description:

    Defines entrys for the hash inside the user data type.

        

Input:

    type - the datatype for element



Example:

     struct block {

        BHASH_ENTRY(block) hash_link;

                int key;

        char string[256];

     };  



Returns:

    <none>

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

#define BHASH_ENTRY(type) BLST_S_ENTRY(type) 



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

Summary:

    Defines internal functions to operate with a container

        

Description:

     This macro shall be used in the C file and it defines static function

         that are needed for internal working of the hash container.

        

Input:

    name - user selected name for the hash

        type_key - datatype of key

    type - the datatype(structure) of the element

        field - name of the hash link field in the element

        hash - hash function that takes key and returns it's hash (unsigned int)

        compare - compare function that takes key and pointer to the element and returns true 

                  if and only if key is exactly matches user element



Example:

        static unsigned block_key_hash(int key) {return key;}

        static bool block_key_compare(const struct block *block, int key) {return block->key == key;}

        BHASH_GENERATE(block_container, int, block, hash_link, block_key_hash, block_key_compare)



Returns:

    <none>

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

#define BHASH_GENERATE(name, type_key, type, field, hash, compare) \

static void name##_hash_init(struct name *h) { \

        unsigned i; \

        for(i=0;i<sizeof(h->hash_bucket)/sizeof(h->hash_bucket[0]);i++) { BLST_S_INIT(&h->hash_bucket[i]); } \

        return; } \

static void \

name##_hash_add(struct name *h, type_key key, struct type *t) { \

        unsigned key_hash = hash(key); \

        BDBG_ASSERT(h); \

        key_hash = key_hash % (sizeof(h->hash_bucket)/sizeof(h->hash_bucket[0])); \

        BLST_S_INSERT_HEAD(&h->hash_bucket[key_hash], t, field); return; } \

static struct type * \

name##_hash_find(struct name *h, type_key key) { \

        struct type *t; unsigned key_hash = hash(key); \

        BDBG_ASSERT(h); \

        key_hash = key_hash % (sizeof(h->hash_bucket)/sizeof(h->hash_bucket[0])); \

        for(t = BLST_S_FIRST(&h->hash_bucket[key_hash]); t ; t = BLST_S_NEXT(t, field)) { \

                if(compare(key, t)) { return t;} } \

        return NULL; } \

static bool \

name##_hash_remove(struct name *h, type_key key) { \

        struct type *t, *prev_t; \

        unsigned key_hash = hash(key); \

        BDBG_ASSERT(h); \

        key_hash = key_hash % (sizeof(h->hash_bucket)/sizeof(h->hash_bucket[0])); \

        for(prev_t = NULL, t = BLST_S_FIRST(&h->hash_bucket[key_hash]); t; t = BLST_S_NEXT(t, field)) { \

                if(compare(key, t)) { \

                        if(prev_t==NULL) { BLST_S_REMOVE_HEAD(&h->hash_bucket[key_hash], field); } \

                        else { BLST_S_REMOVE_NEXT(&h->hash_bucket[key_hash], prev_t, field); }\

                        return true; \

                } prev_t = t; \

        }return false; } 





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

Summary:

    Initializes conteiner

        

Description:

    Initializes container, e.g. wipes out all it's content.

        

Input:

    name - name of the hash container

        hash - pointer to the container



See also:

    BHASH_GENERATE



Example:

     struct block_hash container;

         BHASH_INIT(block_container, &container);



Returns:

    <none>

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

#define BHASH_INIT(name, hash) name##_hash_init(hash)



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

Summary:

    Adds element into the container

        

Description:

    This macro is used to associate a key with the data element. Note only 

        one key could be associated with the given data element (e.g. data element

        could be added only once in the container).

        

Input:

    name - name of the hash container

        hash - pointer to the container

        key - key for association

        elem - pointer to the data element



See also:

    BHASH_REMOVE

        BHASH_FIND



Returns:

    <none>



Example:

        struct block b;

    BHASH_ADD(block_container, &container, 0, &b );

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

#define BHASH_ADD(name, hash, key, elm) name##_hash_add((hash), (key), (elm))



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

Summary:

    Removes element into the container

        

Description:

    This macro is used to remove association between key and data element;

        

Input:

    name - name of the hash container

        hash - pointer to the container

        key - key for removal from the container



See also:

    BHASH_ADD



Returns:

    true - if element was in the container

        false - if element wasn't in the container



Example:

    if(!BHASH_REMOVE(block_container, &container, 0)) {

                printf("key 0 wasn't in the table!!!");

        }

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

#define BHASH_REMOVE(name, hash, key) name##_hash_remove((hash), (key))



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

Summary:

    Removes element into the container

        

Description:

    This macro is used to remove association between key and data element;

        

Input:

    name - name of the hash container

        hash - pointer to the container

        key - key to search in the container



See also:

    BHASH_ADD



Returns:

    pointer to data element - if element was in the container

        NULL - if element wasn't in the container



Example:

        struct block *b = BHASH_FIND(block_container, &container, 0)) {

    if(b) {

                printf("key 0 associated with %s", b->string);

        }

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

#define BHASH_FIND(name, hash, key) name##_hash_find((hash), (key))



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

Summary:

    Open itterator for the container 

        

Description:

    The BHASH_FOREACH_BEGIN and BHASH_FOREACH_END are used to itterate over 

        all elements in the container.

        Please note that 'break' can't be used to escape from the itterator,

        however goto could safely used if it points outside of itterator.



        User shall not add or remove elements from the container, the only

        exception is that user could remove currently itterated element, e.g.

        itterator is widely useful for controlled removal of all elements

        from the container

        

Input:

    name - name of the hash container

        hash - pointer to the container

    type - the datatype(structure) of the element

        elm - element to be itterated

        field - name of the hash link field in the element



See also:

    BHASH_REMOVE

        BHASH_FOREACH_END



Returns:

    <none>



Example:

        struct block *b;

        BHASH_FOREACH_BEGIN(block_container, &container, block, b, hash_link)

                printf("key %d associated with %s", b->key, b->string);

        BHASH_FOREACH_END()

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

#define BHASH_FOREACH_BEGIN(name,hash,type,elm,field) { unsigned _hash_i; for(_hash_i=0;_hash_i<sizeof((hash)->hash_bucket)/sizeof((hash)->hash_bucket[0]);_hash_i++) { \

                                                                                struct type *_hash_next;for(_hash_next=elm=BLST_S_FIRST(&(hash)->hash_bucket[_hash_i]);elm;elm=_hash_next) { _hash_next = BLST_S_NEXT(elm, field);



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

Summary:

    Open itterator for the container 



See also:

        BHASH_FOREACH_BEGIN



Returns:

    <none>

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

#define BHASH_FOREACH_END()     }}}



#endif  /* __BHASH_H__ */