Welcome to MDGSF's Blog!

This is my github blog

[C/C++] hashtable

2016-07-01

C/C++

C++ Hashtable

冲突解决技术可以分为两类：开散列方法( open hashing，也称为拉链法，separate chaining )和闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。

这里使用的是开散列。

A simple hashtabl.

#ifndef HASHTABLE_HJ
#define HASHTABLE_HJ

#include <stdio.h>
#include <string.h>

#define DEFAULT_BUCKET_SIZE 12000

namespace JCL
{
    namespace pub
    {

        enum EHashType {
            EDJBHASH,
            EAPHASH
        };

        typedef struct _SNode {
            struct _SNode * m_pNext;
            char m_acKey[BUFSIZ];
            void * m_pvVal;
            _SNode(): m_pNext(NULL), m_pvVal(NULL)
            {
                memset(m_acKey, 0, sizeof(m_acKey));
            }
            ~_SNode()
            {
            }
        }SNode;

        class CHashTable
        {
            public:
                CHashTable(
                        EHashType iHashType = EDJBHASH,
                        int iMaxBucketSize = DEFAULT_BUCKET_SIZE);

                virtual ~CHashTable();

                /*
                 * @param pcKey[IN]: the string key
                 * @return the value, failed: NULL.
                 */
                void * m_pvFind(const char * pcKey);

                /*
                 * @param pcKey[IN]: use string as key
                 * @param pvVal[IN]: use to store the value.
                 * @return 0:success, -1:failed.
                 */
                int m_iInsert(const char * pcKey, void * pvVal);


                /*
                 * @param pcKey[IN]: the string key
                 * @return 0:success, -1:failed.
                 */
                int m_iDelete(const char * pcKey);

                /*
                 * get the current size of hashtable.
                 */
                int m_iGetSize();

                void m_vShowStatus();

            private:
                CHashTable(const CHashTable&);
                CHashTable& operator = (const CHashTable&);

                SNode * m_pstFindNode(const char * pcKey);

                unsigned int m_iHashFunction(const char * pcKey);
                unsigned int DJBHash(const char * str);
                unsigned int APHash(const char* str);
                EHashType m_iHashType;

                int m_iSize;
                int m_iMaxBucketSize;
                SNode ** m_bucket;
        };
    }
}

#endif

#include "hashtable.h"
#include <stdlib.h>

#define MAX_BUCKET_SIZE 120000

using namespace JCL::pub;

CHashTable::CHashTable(
    EHashType iHashType,
    int iMaxBucketSize) :
    m_iHashType(iHashType),
    m_iSize(0),
    m_iMaxBucketSize(iMaxBucketSize)
{
    m_iMaxBucketSize = m_iMaxBucketSize > MAX_BUCKET_SIZE ? MAX_BUCKET_SIZE : m_iMaxBucketSize;
    m_bucket = new SNode*[m_iMaxBucketSize];
    for (int i = 0; i < m_iMaxBucketSize; i++) {
        m_bucket[i] = NULL;
    }
}

CHashTable::~CHashTable()
{
    SNode * pNode = NULL;
    for (int i = 0; i < m_iMaxBucketSize; i++)
    {
        pNode = m_bucket[ i ];
        if(NULL != pNode) {
            delete pNode;
        }
    }
    delete m_bucket;
}

void
CHashTable::m_vShowStatus()
{
    printf("\n******************************\n");
    printf("m_iMaxBucketSize: %d\n", m_iMaxBucketSize);
    printf("m_iSize: %d\n", m_iSize);
    int iEmpty = 0;
    int iOne = 0;
    int iTwo = 0;
    int iOthers = 0;
    for (int i = 0; i < m_iMaxBucketSize; i++)
    {
        SNode * pNode = m_bucket[i];
        if(NULL == pNode)
        {
            iEmpty++;
        }
        else
        {
            int iCurNum = 0;
            SNode * pCurNode = pNode;
            while (pCurNode != NULL) {
                iCurNum++;
                pCurNode = pCurNode->m_pNext;
            }

            switch(iCurNum)
            {
            case 1:
                iOne++;
                break;
            case 2:
                iTwo++;
                break;
            default:
                iOthers++;
                break;
            }
        }
    }
    printf("iOne: %d\n", iOne);
    printf("iTwo: %d\n", iTwo);
    printf("iOthers: %d\n", iOthers);
    printf("******************************\n");
}

int
CHashTable::m_iGetSize()
{
    return m_iSize;
}

int
CHashTable::m_iInsert(const char * pcKey, void * pvVal)
{
    if(NULL == pcKey || strlen(pcKey) == 0) {
        printf("m_iInsert() invalid parameters\n");
        return -1;
    }

    unsigned int uiKey = m_iHashFunction(pcKey);
    SNode * pNode = m_bucket[ uiKey % m_iMaxBucketSize ];
    if(NULL == pNode) {
        pNode = new SNode();
        pNode->m_pNext = NULL;
        strcpy(pNode->m_acKey, pcKey);
        pNode->m_pvVal = pvVal;

        m_bucket[ uiKey % m_iMaxBucketSize ] = pNode;
        m_iSize++;
        return 0;
    }

    SNode * pCurNode = pNode;
    while (pCurNode != NULL)
    {
        if(strcmp(pCurNode->m_acKey, pcKey) == 0)
        {
            printf("already exists pcKey=%s\n", pcKey);
            return -1;
        }
        pCurNode = pCurNode->m_pNext;
    }

    SNode * pNewNode = new SNode();
    strcpy(pNewNode->m_acKey, pcKey);
    pNewNode->m_pvVal = pvVal;

    pNewNode->m_pNext = pNode->m_pNext;
    pNode->m_pNext = pNewNode;
    m_iSize++;
    return 0;
}

int
CHashTable::m_iDelete(const char * pcKey)
{
    if(NULL == pcKey || strlen(pcKey) == 0) {
        printf("m_iDelete invalid parameters\n");
        return -1;
    }

    unsigned int uiKey = m_iHashFunction(pcKey);

    SNode * pNode = m_bucket[ uiKey % m_iMaxBucketSize ];
    if(NULL == pNode){
        printf("Not exist in hashtable\n");
        return -1;
    }

    if(strcmp(pNode->m_acKey, pcKey) == 0) {
        m_bucket[ uiKey % m_iMaxBucketSize ] = pNode->m_pNext;
        delete pNode;
        m_iSize--;
        return 0;
    }

    SNode * p1 = pNode->m_pNext;
    SNode * p2 = pNode;
    while (p1 != NULL)
    {
        if(strcmp(p1->m_acKey, pcKey) == 0)
        {
            p2->m_pNext = p1->m_pNext;
            delete p1;
            m_iSize--;
            return 0;
        }

        p1 = p1->m_pNext;
        p2 = p2->m_pNext;
    }

    return -1;
}

void *
CHashTable::m_pvFind(const char * pcKey)
{
    if(NULL == pcKey) {
        return NULL;
    }

    SNode * pNode = m_pstFindNode(pcKey);
    if(NULL == pNode) {
        return NULL;
    }

    return pNode->m_pvVal;
}

SNode *
CHashTable::m_pstFindNode(const char * pcKey)
{
    unsigned int uiKey = m_iHashFunction(pcKey);
    SNode * pNode = m_bucket[ uiKey % m_iMaxBucketSize ];
    if(NULL == pNode) {
        return NULL;
    }

    while (pNode != NULL)
    {
        if(strcmp(pNode->m_acKey, pcKey) == 0) {
            return pNode;
        }
        pNode = pNode->m_pNext;
    }

    return NULL;
}

unsigned int
CHashTable::m_iHashFunction(const char * pcKey)
{
    switch(m_iHashType)
    {
    case EDJBHASH:
        return DJBHash(pcKey);
        break;
    case EAPHASH:
        return APHash(pcKey);
        break;
    default:
        printf("m_iHashFunction() unknown hash type\n");
        break;
    }
    return 0;
}

unsigned int
CHashTable::DJBHash(const char * str)
{
    char * pcKey = const_cast<char*>(str);
    unsigned int hash = 5381;
    while (*pcKey)
    {
        hash = ((hash << 5) + hash) + (*pcKey);
        pcKey++;
    }
    return hash;
}

unsigned int
CHashTable::APHash(const char* str)
{
    char * pcKey = const_cast<char*>(str);

    unsigned int hash = 0xAAAAAAAA;
    unsigned int i    = 0;

    while (*pcKey)
    {
        hash ^= ((i & 1) == 0) ? (  (hash <<  7) ^ (*pcKey) * (hash >> 3)) :
            (~((hash << 11) + ((*pcKey) ^ (hash >> 5))));
        pcKey++;
        i++;
    }

    return hash;
}

hash 算法是从下面这个链接复制来的。

http://www.partow.net/programming/hashfunctions/

Read All

[C/C++] 指针的引用作为参数

2016-06-24

C/C++

C++

#include <stdio.h>

int a = 1;
int b = 2;
int c = 3;

void vTest1(int * pi)
{
    pi = &b;
    printf("vTest1() *pi = %d\n", *pi);
}

void vTest2(int * & rpi)
{
    rpi = &c;
    printf("vTest2() *rpi = %d\n", *rpi);
}

int main()
{
    int * pi = &a;
    printf("*pi = %d\n", *pi);

    vTest1(pi);
    printf("main() vTest1 *pi = %d\n", *pi);

    vTest2(pi);
    printf("main() vTest2 *pi = %d\n", *pi);

    return 0;
}

输出：

*pi = 1
vTest1() *pi = 2
main() vTest1 *pi = 1
vTest2() *rpi = 3
main() vTest2 *pi = 3

在 vTest1() 中, 当我们把一个指针做为参数传一个方法时，其实是把指针的复本传递给了 vTest1()，

也就是说 是对指针进行了值传递。

在方法里做修改只是修改的指针的copy而不是指针本身，原来的指针还保留着原来的值。

vText2() 则是对指针的引用。

Read All

[Linux][常用命令] tail 查看log文件的实时变化

2016-06-23

mdgsf

Linux

Linux Command
```
tail -f test.log
```
Read All
[Network] socket linger usage

2016-06-15

mdgsf

Network

Network Linger
```
#include <arpa/inet.h>

struct linger {
    int l_onoff;
    int l_linger;
};
```
三种断开方式：

1. l_onoff = 0; l_linger忽略;

close()立刻返回，底层会将未发送完的数据发送完成后再释放资源，即优雅退出。

2. l_onoff != 0; l_linger = 0;

close()立刻返回，但不会发送未发送完成的数据，而是通过一个REST包强制的关闭socket描述符，即强制退出。

3. l_onoff != 0; l_linger > 0;

close()不会立刻返回，内核会延迟一段时间，这个时间就由l_linger的值来决定。如果超时时间到达之前，发送完未发送的数据(包括FIN包)并得到另一端的确认，close()会返回正确，socket描述符优雅性退出。否则，close()会直接返回错误值，未发送数据丢失，socket描述符被强制性退出。需要注意的时，如果socket描述符被设置为非堵塞型，则close()会直接返回值。

具体用法：
```
struct linger ling = {0, 0};
setsockopt(socketfd, SOL_SOCKET, SO_LINGER, (void*)&ling, sizeof(ling));
```
Read All
[Network] Frame in data link layer

2016-06-15

mdgsf

Network

Network Frame
Black list: 只要Source Mac在list中，就不转发。

White list: 只有Source Mac在list中，才转发。

Frame 的格式：
```
|       6字节     |      6字节       |  2字节    |        46-->1500字节           |  4字节  |
|     目的地址     |      源地址      | 长度/类型 |            数据或填充           |  CRC   |

|<------------------min:64字节(512bit), max=1518字节(12144bit) --------------------------->|
```
Mac 地址格式：

源地址始终是单播地址，因为任何帧都只可能来自一个站。

而目的地址则有可能是单播，多播或者广播地址。
1. 单播地址：目的地址的第一个字节的最低位是0 。(例如： 4A:30:10:21:10:1A)
2. 多播地址：目的地址的第一个字节的最低位不是0 。(例如： 47:20:1B:2E:08:EE)
3. 广播地址：目的地址的 6 个字节全都是1 。(例如： FF:FF:FF:FF:FF:FF)
Read All

[算法学习][LintCode] A + B

2016-06-15

Art

C A+b

要求：不用加减乘除实现A+B。

int aplusb(int a, int b) {
    while(b != 0){
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

x^y //执行加法，不考虑进位。

(x&y)«1 //进位操作

Read All

81/97

Welcome to MDGSF's Blog!

[C/C++] hashtable

[C/C++] 指针的引用作为参数

[Linux][常用命令] tail 查看log文件的实时变化

[Network] socket linger usage

三种断开方式：

[Network] Frame in data link layer

[算法学习][LintCode] A + B