tokyo cabinet源代码分析（6）

2.5数据记录的删除

主要流程为二叉树节点删除。

二叉树中删除记录的过程:

/*记录在二叉树中的删除过程

*通过HASH函数将key映射到TCMAP数组的一个元素，

*然后通过tcmapout进行相应的删除工作*/

/* Remove a record of an on-memory hash database. */

bool tcmdbout(TCMDB *mdb, const void *kbuf, int ksiz){

assert(mdb && kbuf && ksiz >= 0);

unsigned int mi;

TCMDBHASH(mi, kbuf, ksiz);

if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return false;

bool rv = tcmapout(mdb->maps[mi], kbuf, ksiz);

pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);

return rv;

}

通过tcmapout进行删除。

/* Remove a record of a map object. */

bool tcmapout(TCMAP *map, const void *kbuf, int ksiz){

assert(map && kbuf && ksiz >= 0);

if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;

uint32_t hash;

/*HASH映射到buckets数组的一个元素*/

TCMAPHASH1(hash, kbuf, ksiz);

int bidx = hash % map->bnum;

TCMAPREC *rec = map->buckets[bidx];

TCMAPREC **entp = map->buckets + bidx;

TCMAPHASH2(hash, kbuf, ksiz);

hash &= ~TCMAPKMAXSIZ;

/*遍历二叉树，进行相应的删除*/

while(rec){

uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;

uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;

/*如果HASH不相同，循环遍历左子树或者右子树*/

if(hash > rhash){

entp = &(rec->left);

rec = rec->left;

} else if(hash < rhash){

entp = &(rec->right);

rec = rec->right;

} else {

/*如果相同，则比较KEY值

*不相同继续遍历*/

char *dbuf = (char *)rec + sizeof(*rec);

int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);

if(kcmp < 0){

entp = &(rec->left);

rec = rec->left;

} else if(kcmp > 0){

entp = &(rec->right);

rec = rec->right;

} else {

/*key相同，record记录减一*/

map->rnum--;

map->msiz -= rksiz + rec->vsiz;

/*将删除的record节点的前续、后继节点进行重新连接*/

if(rec->prev) rec->prev->next = rec->next;

if(rec->next) rec->next->prev = rec->prev;

if(rec == map->first) map->first = rec->next;

if(rec == map->last) map->last = rec->prev;

if(rec == map->cur) map->cur = rec->next;

/*如果该删除节点只有左子树，则直接跳过该节点

*指向它的左子树节点*/

if(rec->left && !rec->right){

*entp = rec->left;

}

/*如果只有右子树，则直接跳过该节点

*指向它的右子树节点*/

else if(!rec->left && rec->right){

*entp = rec->right;

/*如果没有子树，直接将节点删除*/

} else if(!rec->left && !rec->left){

*entp = NULL;

} else {

/*如果相同，即需要删除该节点

*entp指向它的左子树，然后遍历左子树的

右子树，到最右边的叶子节点（即：值最大的节点），

将原先节点的右子树，作为最大节点的右子树*/

*entp = rec->left;

TCMAPREC *tmp = *entp;

while(tmp->right){

tmp = tmp->right;

}

tmp->right = rec->right;

}

TCFREE(rec);

return true;

}

}

}

return false;

}

在删除过程中，方法和通常介绍的方法有所不同。如果被删除节点A有左、右子树，那么左子树都小于它，

右子树大于它。而A节点的左子树的最右节点是它左子树中最大的节点，如果删除了A节点，那么它的右子树节点均大于左子树，所以可以直接将它右子树，连接到左子树中最大节点的右子树中。