当前位置: 首页 > 工具软件 > Tokyo Cabinet > 使用案例 >

tokyo cabinet源代码分析(2)

卫沈义
2023-12-01

2.4数据记录的查找

   在前面的部分对于记录的插入进行了阐述。本节对通过key查找value方法进行了分析。

2.4.1TCMAP数组查找

  先映射到MAP数组的一个元素,然后基于该元素对于hash buckets数组进行访问。

[c-sharp] view plain copy print ?
  1. 通过tcmdbget进行查找  
  2.     /* Retrieve a record in an on-memory hash database. */  
  3. void *tcmdbget(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){  
  4.   assert(mdb && kbuf && ksiz >= 0 && sp);  
  5.   unsigned int mi;  
  6.   /*将key映射到map数组的一个元素上*/  
  7.   TCMDBHASH(mi, kbuf, ksiz);  
  8.   /*通过mutex锁唯一访问*/  
  9.   if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;  
  10.   int vsiz;  
  11.   const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);  
  12.   char *rv;  
  13.   if(vbuf){  
  14.     TCMEMDUP(rv, vbuf, vsiz);  
  15.     *sp = vsiz;  
  16.   } else {  
  17.     rv = NULL;  
  18.   }  
  19.   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);  
  20.   return rv;  
  21. }  

2.4.2 hash buckets二叉树查找

  查找二叉树结构,获得value对象,返回的是分配好的内存地址,所以查找使用以后,

需要进行释放。

[c-sharp] view plain copy print ?
  1. /*通过tcmapget遍历二叉搜索树,查找value*/  
  2. /* Retrieve a record in a map object. */  
  3. const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp){  
  4.   assert(map && kbuf && ksiz >= 0 && sp);  
  5.   if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;  
  6.   uint32_t hash;  
  7.   TCMAPHASH1(hash, kbuf, ksiz);  
  8.   /*先定位到bucket一个元素上*/  
  9.   TCMAPREC *rec = map->buckets[hash%map->bnum];  
  10.   TCMAPHASH2(hash, kbuf, ksiz);  
  11.   hash &= ~TCMAPKMAXSIZ;  
  12.   /*遍历二叉树 
  13.    *hash值相同,然后比较key值 
  14.    */  
  15.   while(rec){  
  16.     uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;  
  17.     uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;  
  18.     if(hash > rhash){  
  19.       rec = rec->left;  
  20.     } else if(hash < rhash){  
  21.       rec = rec->right;  
  22.     } else {  
  23.     /*dbuf的结构是rec结构体之后存放了key 
  24.      *TCKEYCMP先比较了两个的keybuffer的大小, 
  25.      *然后再比较值*/  
  26.       char *dbuf = (char *)rec + sizeof(*rec);  
  27.       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);  
  28.       if(kcmp < 0){  
  29.         rec = rec->left;  
  30.       } else if(kcmp > 0){  
  31.         rec = rec->right;  
  32.       } else {  
  33.         *sp = rec->vsiz;  
  34.         /*找到之后,翻译value所在buffer的地址 
  35.          *通过TCMEMDUP复制内存, 
  36.          *所在在使用完了Value以后,应该释放*/  
  37.         return dbuf + rksiz + TCALIGNPAD(rksiz);  
  38.       }  
  39.     }  
  40.   }  

2.5数据记录的删除

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

[c-sharp] view plain copy print ?
  1. 二叉树中删除记录的过程:  
  2. /*记录在二叉树中的删除过程 
  3.  *通过HASH函数将key映射到TCMAP数组的一个元素, 
  4.  *然后通过tcmapout进行相应的删除工作*/  
  5. /* Remove a record of an on-memory hash database. */  
  6. bool tcmdbout(TCMDB *mdb, const void *kbuf, int ksiz){  
  7.   assert(mdb && kbuf && ksiz >= 0);  
  8.   unsigned int mi;  
  9.   TCMDBHASH(mi, kbuf, ksiz);  
  10.   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return false;  
  11.   bool rv = tcmapout(mdb->maps[mi], kbuf, ksiz);  
  12.   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);  
  13.   return rv;  
  14. }  

通过tcmapout进行删除。

[c-sharp] view plain copy print ?
  1. /* Remove a record of a map object. */  
  2. bool tcmapout(TCMAP *map, const void *kbuf, int ksiz){  
  3.   assert(map && kbuf && ksiz >= 0);  
  4.   if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;  
  5.   uint32_t hash;  
  6.   /*HASH映射到buckets数组的一个元素*/  
  7.   TCMAPHASH1(hash, kbuf, ksiz);  
  8.   int bidx = hash % map->bnum;  
  9.   TCMAPREC *rec = map->buckets[bidx];  
  10.   TCMAPREC **entp = map->buckets + bidx;  
  11.   TCMAPHASH2(hash, kbuf, ksiz);  
  12.   hash &= ~TCMAPKMAXSIZ;  
  13.   /*遍历二叉树,进行相应的删除*/  
  14.   while(rec){  
  15.     uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;  
  16.     uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;  
  17.     /*如果HASH不相同,循环遍历左子树或者右子树*/  
  18.     if(hash > rhash){  
  19.       entp = &(rec->left);  
  20.       rec = rec->left;  
  21.     } else if(hash < rhash){  
  22.       entp = &(rec->right);  
  23.       rec = rec->right;  
  24.     } else {  
  25.       /*如果相同,则比较KEY值 
  26.        *不相同继续遍历*/  
  27.       char *dbuf = (char *)rec + sizeof(*rec);  
  28.       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);  
  29.       if(kcmp < 0){  
  30.         entp = &(rec->left);  
  31.         rec = rec->left;  
  32.       } else if(kcmp > 0){  
  33.         entp = &(rec->right);  
  34.         rec = rec->right;  
  35.       } else {  
  36.         /*key相同,record记录减一*/  
  37.         map->rnum--;  
  38.         map->msiz -= rksiz + rec->vsiz;  
  39.         /*将删除的record节点的前续、后继节点进行重新连接*/  
  40.         if(rec->prev) rec->prev->next = rec->next;  
  41.         if(rec->next) rec->next->prev = rec->prev;  
  42.         if(rec == map->first) map->first = rec->next;  
  43.         if(rec == map->last) map->last = rec->prev;  
  44.         if(rec == map->cur) map->cur = rec->next;  
  45.         /*如果该删除节点只有左子树,则直接跳过该节点 
  46.          *指向它的左子树节点*/  
  47.         if(rec->left && !rec->right){  
  48.           *entp = rec->left;  
  49.         }  
  50.         /*如果只有右子树,则直接跳过该节点 
  51.          *指向它的右子树节点*/  
  52.          else if(!rec->left && rec->right){  
  53.           *entp = rec->right;  
  54.         /*如果没有子树,直接将节点删除*/  
  55.         } else if(!rec->left && !rec->left){  
  56.           *entp = NULL;  
  57.         } else {  
  58.          /*如果相同,即需要删除该节点 
  59.           *entp指向它的左子树,然后遍历左子树的 
  60.           右子树,到最右边的叶子节点(即:值最大的节点), 
  61.           将原先节点的右子树,作为最大节点的右子树*/  
  62.           *entp = rec->left;  
  63.           TCMAPREC *tmp = *entp;  
  64.           while(tmp->right){  
  65.             tmp = tmp->right;  
  66.           }  
  67.           tmp->right = rec->right;  
  68.         }  
  69.         TCFREE(rec);  
  70.         return true;  
  71.       }  
  72.     }  
  73.   }  
  74.   return false;  
  75. }  

在删除过程中,方法和通常介绍的方法有所不同。如果被删除节点A有左、右子树,那么左子树都小于它,
右子树大于它。而A节点的左子树的最右节点是它左子树中最大的节点,如果删除了A节点,那么它的右子树节点均大于左子树,所以可以直接将它右子树,连接到左子树中最大节点的右子树中。


 类似资料: