본문 바로가기
보관용

[sHash] Simple Hash

by 크크다스 2014. 11. 10.
반응형

= [sHash] Simple Hash

간단하게 Hash를 처리하기에 좋다


= 사용법


    /* Hash */
    gHash.is_enabled = uFalse;
    if(! priv_sHash_init(&gHash)) {
        printk("priv_sHash_init() is failed.");
        return;
    }

= Header

/*=============================================================================
//                              _priv_simple_hash.h
//=============================================================================
// COMPANY        :
// AUTHOR        : firstpw
// DATE            :
// DESCRIPTION    :
//=============================================================================
*/
#ifndef    _PRIV_SIMPLE_HASH_H
#define    _PRIV_SIMPLE_HASH_H

/*=============================================================================
//        I N C L U D E   
//=============================================================================
*/

/*=============================================================================
//        External Definitions / Declaration
//=============================================================================
*/

/*=============================================================================
//        M A C R O
//=============================================================================
*/

/*=============================================================================
//        C O N S T A N T
//=============================================================================
*/
#ifndef    Boolean
    #define    Boolean        int
    #define    uFalse        0
    #define    uTrue        1
    #define    xu32        unsigned int
    #define    xu8            unsigned char
    #define    xc8            unsigned char
#endif

#ifndef IS_KERNEL

#define printk       printf

#endif

#ifndef    BCHK_NULL
    #define    XLOG(_format,...)    printk(_format "\n", ##__VA_ARGS__)
    #define    XSTART()
    #define    RETURN(_ret)        return(_ret)
    #define    BCHK_NULL(_val)        if(! (_val)) { XLOG(#_val " is (%p)", (xu8*)(_val)); RETURN(uFalse); }

    #define LOOPc(_condition)            for(idx=0; _condition; idx++)
    #define LOOPi(_idx, _max)            for(_idx=0; _idx < (_max); _idx++)
    #define LOOP(_max)                    LOOPi(idx, _max)

    #define XMEMSET                memset
    #define XMEMCPY                memcpy

#endif

#define    PRIV_IS_MAC_ADDR_EQ(_mac1, _mac2)    (!( ((_mac1)[5] != (_mac2)[5]) || \
                                            ((_mac1)[4] != (_mac2)[4]) || \
                                            ((_mac1)[3] != (_mac2)[3]) || \
                                            ((_mac1)[2] != (_mac2)[2]) || \
                                            ((_mac1)[1] != (_mac2)[1]) || \
                                            ((_mac1)[0] != (_mac2)[0])))
#define    PRIV_GET_ABS_BYTE_1(_val)            ((xu8)(_val) <= 0x7f ? (xu8)(_val) : 0x100 - (xu8)(_val))

/* Len */
#define    PRIV_MAC_ADDR_LEN                    6    /* size of 802.11 address */
/* Max */
#define    PRIV_MAX_HASH_ENTRY                    1024/* Total entry size */
#define    PRIV_MAX_HASH_BUCKET                256 /* Bucket size */

/* -------------------------- List ------------------------------ */
/* Cf>
 *        mHashNeighbor
 *        mHashKey
 *        mHashNeighbor
 *        mHashNeighbor
 * */
/* -------------------------- List ------------------------------ */
#define    PRIV_LIST_ENTRY(type)    \
    struct {    \
        struct type*    mNext;    /* next element */        \
        struct type*    mPrev;    /* previous element */    \
    }

#define    PRIV_NEXT_ENTRY(_entry)    ((_entry)->mHashNeighbor.mNext)
#define    PRIV_PREV_ENTRY(_entry)    ((_entry)->mHashNeighbor.mPrev)

/* -------------------------- Hash ------------------------------ */
#define    PRIV_HASH_BUCK_IDX_BY_MAC(pMacAddr)    \
    (((const xu8*)(pMacAddr))[PRIV_MAC_ADDR_LEN - 1] /* % PRIV_MAX_HASH_BUCKET */)

#define    PRIV_HASH_BUCK_IDX(pElem)    \
    PRIV_HASH_BUCK_IDX_BY_MAC((pElem)->mHashKey)

#define    HASH_LOOP_ENTRY(_idxPtr, _first)    \
    for ((_idxPtr) = (_first);    \
            (_idxPtr);                            \
            (_idxPtr) = PRIV_NEXT_ENTRY(_idxPtr))

#define    HASH_INSERT_ENTRY(_first, _entry) do { \
    PRIV_NEXT_ENTRY(_entry) = (_first); \
    if ( PRIV_NEXT_ENTRY(_entry) ) {    \
        PRIV_PREV_ENTRY(_first) = (_entry); \
    } \
    (_first) = (_entry);                    \
    PRIV_PREV_ENTRY(_entry) = NULL;    \
} while (0)

#define    HASH_DELETE_ENTRY(_first, _entry) do {    \
    if ((_first) == (_entry))    \
        (_first) = PRIV_NEXT_ENTRY(_entry); \
    if (PRIV_NEXT_ENTRY(_entry))    \
        PRIV_PREV_ENTRY(PRIV_NEXT_ENTRY(_entry)) = PRIV_PREV_ENTRY(_entry); \
    if (PRIV_PREV_ENTRY(_entry))    \
        PRIV_NEXT_ENTRY(PRIV_PREV_ENTRY(_entry)) = PRIV_NEXT_ENTRY(_entry); \
} while (0)


/*=============================================================================
//        S T R U C T U R E
//=============================================================================
*/
typedef struct Priv_sHash_Node {
    xc8                                    data[4];
    xu32                                valid_time;
    xu32                                update_ignored_time;
    /* Simple HASH */ /* ------------- Do NOT Change ------------- */
    xu8                                    mHashKey[PRIV_MAC_ADDR_LEN]; /* MacAddr */
    Boolean                                mHashUsed:16;
    PRIV_LIST_ENTRY(Priv_sHash_Node)    mHashNeighbor;
} Priv_sHash_Node;

typedef struct Priv_sHash_Entity {
    Boolean                                is_enabled;
    xu32                                key_width;
    /* Simple HASH */ /* ------------- Do NOT Change ------------- */
    Priv_sHash_Node                        mHashAllEntry[PRIV_MAX_HASH_ENTRY];
    Priv_sHash_Node*                    mHashBucketArr[PRIV_MAX_HASH_BUCKET];
} Priv_sHash_Entity;

typedef Boolean    (*Priv_sHash_Cb)(void* pUserPtr, Priv_sHash_Node* pElem);
/*=============================================================================
//        E x t e r n a l        F u n c t i o n s
//=============================================================================
*/
Boolean priv_sHash_init(Priv_sHash_Entity* pEnt);
Boolean priv_sHash_find(Priv_sHash_Entity* pEnt, xu8* pKey, Priv_sHash_Node** ppElem);
Boolean priv_sHash_get_elem(Priv_sHash_Entity* pEnt, Priv_sHash_Node** ppElem);
Boolean priv_sHash_insert(Priv_sHash_Entity* pEnt, xu8* pKey, Priv_sHash_Node** ppElem);
Boolean priv_sHash_find_insert(Priv_sHash_Entity* pEnt, xu8* pKey, Priv_sHash_Node** ppElem);
Boolean priv_sHash_delete(Priv_sHash_Entity* pEnt, xu8* pKey);
Boolean    priv_sHash_delete_with_node(Priv_sHash_Entity* pEnt, Priv_sHash_Node* pElem);
Boolean    priv_sHash_loop_cb(Priv_sHash_Entity* pEnt, Priv_sHash_Cb pCb, void* pUserPtr, Boolean isStopOnFail);

#endif    /* _PRIV_SIMPLE_HASH_H */

= Source

/*=============================================================================
//                              _priv_simple_hash.c
//=============================================================================
// COMPANY        :
// AUTHOR        : firstpw
// DATE            :
// DESCRIPTION    :
//=============================================================================
*/
#define    _PRIV_SIMPLE_HASH_C

/*=============================================================================
//        I N C L U D E   
//=============================================================================
*/
#include "_priv_simple_hash.h"

/*=============================================================================
//        M A C R O
//=============================================================================
*/

/*=============================================================================
//        C O N S T A N T
//=============================================================================
*/

/*=============================================================================
//        S T R U C T U R E
//=============================================================================
*/

/*=============================================================================
//        S T A T I C   V A R I A B L E
//=============================================================================
*/

/*=============================================================================
//        S T A T I C   F U N C T I O N
//=============================================================================
*/
/* ------------------------------ Start Of sHash --------------------------- */
/* Simple Hash */
Boolean    priv_sHash_init(Priv_sHash_Entity* pEnt)
{
    xu32    idx;

    BCHK_NULL(pEnt);
    XSTART()

    /* Bucket Init : Header Init */
    XMEMSET(pEnt->mHashBucketArr, 0x00, sizeof(pEnt->mHashBucketArr));
            
    LOOP(PRIV_MAX_HASH_ENTRY) {
        if(pEnt->mHashAllEntry[idx].mHashUsed) {
            pEnt->mHashAllEntry[idx].mHashUsed = uFalse;
        }
    }

    RETURN(uTrue);
}

Boolean    priv_sHash_find(Priv_sHash_Entity* pEnt, xu8* pKey, Priv_sHash_Node** ppElem)
{
    xu32    idx;
    Priv_sHash_Node* pElem;

    BCHK_NULL(pEnt);
    BCHK_NULL(pKey);
    /*    ppElem == NULL : is_exist
    BCHK_NULL(ppElem);
       */
    XSTART();

    /* Select Bucket Idx */
    idx = PRIV_HASH_BUCK_IDX_BY_MAC(pKey);
    HASH_LOOP_ENTRY(pElem, pEnt->mHashBucketArr[idx]) {
        if (PRIV_IS_MAC_ADDR_EQ(pElem->mHashKey, pKey)) {
            /* Found */
            if (ppElem) *ppElem = pElem;
            RETURN(uTrue);
        }
    }
    /* NOT Found */

    RETURN(uFalse);
}

Boolean    priv_sHash_get_elem(Priv_sHash_Entity* pEnt, Priv_sHash_Node** ppElem)
{
    xu32    idx;

    BCHK_NULL(pEnt);
    BCHK_NULL(ppElem);
    XSTART();

    LOOP(PRIV_MAX_HASH_ENTRY) {
        if(! pEnt->mHashAllEntry[idx].mHashUsed) {
            /* Select Bucket Idx */
            *ppElem = &pEnt->mHashAllEntry[idx];
            RETURN(uTrue);
        }
    }

    RETURN(uFalse);
}

Boolean    priv_sHash_insert(Priv_sHash_Entity* pEnt, xu8* pKey, Priv_sHash_Node** ppElem)
{
    xu32    idx;
    Priv_sHash_Node* pElem;

    BCHK_NULL(pEnt);
    BCHK_NULL(pKey);
    BCHK_NULL(ppElem);
    XSTART();

    if(! priv_sHash_get_elem(pEnt, &pElem)) {
        RETURN(uFalse);
    }
    pElem->mHashUsed = uTrue;
    XMEMCPY(pElem->mHashKey, pKey, PRIV_MAC_ADDR_LEN);
    /* Select Bucket Idx */
    idx = PRIV_HASH_BUCK_IDX(pElem);
    HASH_INSERT_ENTRY(pEnt->mHashBucketArr[idx], pElem);

    *ppElem = pElem;

    RETURN(uTrue);
}

/* Not found => insert */
Boolean    priv_sHash_find_insert(Priv_sHash_Entity* pEnt, xu8* pKey, Priv_sHash_Node** ppElem)
{
    BCHK_NULL(pEnt);
    BCHK_NULL(pKey);
    BCHK_NULL(ppElem);
    XSTART();

    if (priv_sHash_find(pEnt, pKey, ppElem)) {
        /* Found */
        RETURN(uTrue);
    }
    if (priv_sHash_insert(pEnt, pKey, ppElem)) {
        /* Found */
        RETURN(uTrue);
    }
    /* There is No Room : Full */
    RETURN(uFalse);
}

Boolean    priv_sHash_delete(Priv_sHash_Entity* pEnt, xu8* pKey)
{
    xu32    idx;
    Priv_sHash_Node* pElem;

    BCHK_NULL(pEnt);
    BCHK_NULL(pKey);
    XSTART();

    if (! priv_sHash_find(pEnt, pKey, &pElem)) {
        /* NOT Found */
        RETURN(uTrue);
    }
    idx = PRIV_HASH_BUCK_IDX(pElem);
    HASH_DELETE_ENTRY(pEnt->mHashBucketArr[idx], pElem);

    pElem->mHashUsed = uFalse;
    RETURN(uFalse);
}

Boolean    priv_sHash_delete_with_node(Priv_sHash_Entity* pEnt, Priv_sHash_Node* pElem)
{
    xu32    idx;

    BCHK_NULL(pEnt);
    BCHK_NULL(pElem);
    XSTART();

    idx = PRIV_HASH_BUCK_IDX(pElem);
    HASH_DELETE_ENTRY(pEnt->mHashBucketArr[idx], pElem);

    pElem->mHashUsed = uFalse;
    RETURN(uFalse);
}

Boolean    priv_sHash_loop_cb(Priv_sHash_Entity* pEnt, Priv_sHash_Cb pCb, void* pUserPtr, Boolean isStopOnFail)
{
    xu32    idx;
    Priv_sHash_Node* pElem;

    BCHK_NULL(pEnt);
    XSTART();

    LOOP(PRIV_MAX_HASH_ENTRY) {
        pElem = &pEnt->mHashAllEntry[idx];
        if(pElem->mHashUsed) {
            if(! pCb(pUserPtr, pElem) && isStopOnFail) {
                XLOG("UserCb(%u) is failed.", idx);
                RETURN(uFalse);
            }
        }
    }

    RETURN(uTrue);
}
/* ------------------------------ End Of sHash --------------------------- */


반응형

'보관용' 카테고리의 다른 글

[BusyBox] history 기능  (0) 2014.11.14
[jiffies] 값에 대한 단상  (0) 2014.11.14
[MySQL] Desc /Asc index => 지정 안된다 => 우회방법  (0) 2014.11.08
[HTTPs] POST form  (0) 2014.11.07
[전시회] 사물 인터넷 - 코엑스  (0) 2014.11.04

관련글

티스토리툴바