2.4数据记录的查找
在前面的部分对于记录的插入进行了阐述。本节对通过key查找value方法进行了分析。
2.4.1TCMAP数组查找
先映射到MAP数组的一个元素,然后基于该元素对于hash buckets数组进行访问。
- 通过tcmdbget进行查找
-
- void *tcmdbget(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){
- assert(mdb && kbuf && ksiz >= 0 && sp);
- unsigned int mi;
-
- TCMDBHASH(mi, kbuf, ksiz);
-
- if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;
- int vsiz;
- const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);
- char *rv;
- if(vbuf){
- TCMEMDUP(rv, vbuf, vsiz);
- *sp = vsiz;
- } else {
- rv = NULL;
- }
- pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
- return rv;
- }
2.4.2 hash buckets二叉树查找
查找二叉树结构,获得value对象,返回的是分配好的内存地址,所以查找使用以后,
需要进行释放。
-
-
- const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp){
- assert(map && kbuf && ksiz >= 0 && sp);
- if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
- uint32_t hash;
- TCMAPHASH1(hash, kbuf, ksiz);
-
- TCMAPREC *rec = map->buckets[hash%map->bnum];
- TCMAPHASH2(hash, kbuf, ksiz);
- hash &= ~TCMAPKMAXSIZ;
-
-
-
- while(rec){
- uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
- uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
- if(hash > rhash){
- rec = rec->left;
- } else if(hash < rhash){
- rec = rec->right;
- } else {
-
-
-
- char *dbuf = (char *)rec + sizeof(*rec);
- int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
- if(kcmp < 0){
- rec = rec->left;
- } else if(kcmp > 0){
- rec = rec->right;
- } else {
- *sp = rec->vsiz;
-
-
-
- return dbuf + rksiz + TCALIGNPAD(rksiz);
- }
- }
- }
2.5数据记录的删除
主要流程为二叉树节点删除。
- 二叉树中删除记录的过程:
-
-
-
-
- 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进行删除。
-
- bool tcmapout(TCMAP *map, const void *kbuf, int ksiz){
- assert(map && kbuf && ksiz >= 0);
- if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
- uint32_t hash;
-
- 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;
-
- if(hash > rhash){
- entp = &(rec->left);
- rec = rec->left;
- } else if(hash < rhash){
- entp = &(rec->right);
- rec = rec->right;
- } else {
-
-
- 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 {
-
- map->rnum--;
- map->msiz -= rksiz + rec->vsiz;
-
- 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 = rec->left;
- TCMAPREC *tmp = *entp;
- while(tmp->right){
- tmp = tmp->right;
- }
- tmp->right = rec->right;
- }
- TCFREE(rec);
- return true;
- }
- }
- }
- return false;
- }
在删除过程中,方法和通常介绍的方法有所不同。如果被删除节点A有左、右子树,那么左子树都小于它,
右子树大于它。而A节点的左子树的最右节点是它左子树中最大的节点,如果删除了A节点,那么它的右子树节点均大于左子树,所以可以直接将它右子树,连接到左子树中最大节点的右子树中。