基于一致性hash算法 C++语言的实现详解（2） public, 接口

yuyang911220

CMD5HashFun 类继承CHashFun接口，实现获取hash值的getHashVal函数：
复制代码 代码如下:
/*用MD5算法计算结点的hash值，继承CHashFun父类*/
class CMD5HashFun : public CHashFun
{
public:
    virtual long getHashVal (const char * );
};
long CMD5HashFun::getHashVal(const char * instr)
{
    int i;
    long hash = 0;
    unsigned char digest[16];
    /*调用MD5相关函数，生成instr的MD5码，存入digest*/
    md5_state_t md5state;
    md5_init(&md5state);
    md5_append(&md5state, (const unsigned char *)instr, strlen(instr));
    md5_finish(&md5state, digest);
    /* 每四个字节构成一个32位整数，
    将四个32位整数相加得到instr的hash值（可能溢出） */
    for(i = 0; i < 4; i++)
    {
        hash += ((long)(digest[i*4 + 3]&0xFF) << 24)
            | ((long)(digest[i*4 + 2]&0xFF) << 16)
            | ((long)(digest[i*4 + 1]&0xFF) <<  8)
            | ((long)(digest[i*4 + 0]&0xFF));
    }
    return hash;
}
3、扩展红黑树结构中的查找函数，用于查找红黑树中大于key值中最小的结点。
复制代码 代码如下:
util_rbtree_node_t* util_rbtree_lookup(util_rbtree_t *rbtree, long key)
{
    if((rbtree != NULL) && !util_rbtree_isempty(rbtree))
    {
        util_rbtree_node_t *node = NULL;
        util_rbtree_node_t *temp = rbtree->root;
        util_rbtree_node_t *null = _NULL(rbtree);
        while(temp != null)
        {
            if(key <= temp->key)
            {
                node = temp; /* update node */
                temp = temp->left;
            }
            else if(key > temp->key)
            {
                temp = temp->right;
            }
        }
        /* if node==NULL return the minimum node */
        return ((node != NULL) ? node : util_rbtree_min(rbtree));
    }
    return NULL;
}
4、创建一致性hash类。使其具有插入、删除、查找实体结点的功能。
具体算法和操作过程已经在代码注释中说明。
复制代码 代码如下:
class CConHash
{
public:
    /*构造函数*/
    CConHash(CHashFun * pFunc);
    /*设置hash函数*/
    void setFunc(CHashFun * pFunc);
    /*增加实体结点 , 0代表成功 , -1代表失败*/
    int addNode_s(CNode_s * pNode);
    /*删除实体结点 , 0代表成功 , -1代表失败*/
    int delNode_s(CNode_s * pNode);
    /*查找实体结点*/
    CNode_s * lookupNode_s(const char * object);
    /*获取一致性hash结构的所有虚拟结点数量*/
    int getVNodes();
private:
    /*Hash函数*/
    CHashFun * func;
    /*虚拟结点总个数*/
    int vNodes;
    /*存储虚拟结点的红黑树*/
    util_rbtree_t * vnode_tree;
};
/*辅助函数，虚拟结点转化为红黑树结点*/
util_rbtree_node_t * vNode2RBNode(CVirtualNode_s * vnode);

CConHash::CConHash(CHashFun * pFunc)
{
    /*设置hash函数*/
    assert(pFunc!=NULL);
    this->func = pFunc;
    this->vNodes = 0;
    /*初始化红黑树*/
    vnode_tree = new util_rbtree_s();
    util_rbtree_init(vnode_tree);
}
int CConHash::addNode_s(CNode_s * pNode)
{
    if(pNode==NULL) return -1;
    int vCount = pNode->getVNodeCount();
    if(vCount<=0) return -1;
    CVirtualNode_s * virtualNode ;
    util_rbtree_node_t * rbNode;
    char str [100];
    char num[10];
    strcpy(str,pNode->getIden());
    long hash = 0;
    /*生成虚拟结点并插入到红黑树中*/
    for(int i=0;i<vCount;i++)
    {
        virtualNode = new CVirtualNode_s(pNode);
        /*采用str+“i”的方法产生不同的iden串，用于后面的hash值计算*/
        itoa(i,num,10);
        strcat(str,num);
        hash = func->getHashVal(str);
        virtualNode->setHash(hash);
        if(!util_rbtree_search(vnode_tree,hash))
        {
            /*生成红黑树结点*/
            rbNode = vNode2RBNode(virtualNode);
            if(rbNode!=NULL)
            {
                /*将该结点插入到红黑树中*/
                util_rbtree_insert(vnode_tree,rbNode);
                this->vNodes++;
            }
        }
    }
    return 0;
}
int CConHash::delNode_s(CNode_s * pNode)
{
    if(pNode==NULL) return -1;
    util_rbtree_node_t * rbNode;
    char str [100];
    char num [10];
    strcpy(str,pNode->getIden());
    int vCount = pNode->getVNodeCount();
    long hash = 0;
    CVirtualNode_s * node = NULL;
    /*将该实体结点产生的所有虚拟结点进行删除*/
    for(int i=0;i<vCount;i++)
    {
        itoa(i,num,10);
        strcat(str,num);/*采用该方法产生不同的iden串*/
        hash = func->getHashVal(str);
        rbNode = util_rbtree_search(vnode_tree,hash);
        if(rbNode!=NULL)
        {
            node = (CVirtualNode_s *) rbNode->data;
            if(node->getNode_s()==pNode && node->getHash()==hash)
            {
                this->vNodes--;
                /*将该结点从红黑树中删除*/
                util_rbtree_delete(vnode_tree,rbNode);
                delete rbNode;
                delete node;
            }
        }
    }
    return 0;
}
CNode_s * CConHash::lookupNode_s(const char * object)
{
    if(object==NULL||this->vNodes==0) return NULL;
    util_rbtree_node_t * rbNode;
    int key = this->func->getHashVal(object);
    /*在红黑树中查找key值比key大的最小的结点*/
    rbNode = util_rbtree_lookup(vnode_tree,key);
    if(rbNode!=NULL)
    {
        return ((CVirtualNode_s *) rbNode->data)->getNode_s();
    }
    return NULL;
}
int CConHash::getVNodes()
{
    return this->vNodes;
}

util_rbtree_node_t * vNode2RBNode(CVirtualNode_s * vnode)
{
    if(vnode==NULL) return NULL;
    util_rbtree_node_t *rbNode = new util_rbtree_node_t();
    rbNode->key = vnode->getHash();
    rbNode->data = vnode;
    return rbNode;
}