C hsearch发现之前未输入的值

Question

这是这个问题的后续问题.

由于我解决了部分内容并且我觉得剩下的问题与第一个问题无关,所以我决定将这两个部分分成两个问题.

我已经使用POSIX hcreate/ 实现了一个关联数组hsearch,如此处所示.

为了完整起见,以下是除main()上一个问题的函数之外的所有代码:

#include <inttypes.h> /* intptr_t             */
#include <search.h>   /* hcreate(), hsearch() */
#include <stdio.h>    /* perror()             */
#include <stdlib.h>   /* exit()               */
#include <string.h>   /* strcpy()             */

void exit_with_error(const char* error_message){
  perror(error_message);
  exit(EXIT_FAILURE);
}
int fetch(const char* key, intptr_t* value){
  ENTRY e,*p;
  e.key=(char*)key;
  p=hsearch(e, FIND);
  if(!p) return 0;
  *value=(intptr_t)p->data;
  return 1;
}

void store(const char *key, intptr_t value){
  ENTRY e,*p;
  e.key=(char*)key;
  p = hsearch(e, ENTER);
  if(!p) exit_with_error("hash full");
  p->data = (void *)value;
}

这是一个稍微扩展的main()功能:

int main(){
  char a[4]="foo";
  char b[4]="bar";
  char c[4]="baz";
  char t[4]="";
  char y='\0';
  const char l[6]={'a','b','f','o','r','z'};
  intptr_t x=NULL;
  size_t i=0,j=0;

  if(!hcreate(50)) exit_with_error("no hash");

  strcpy(t,b);
  store(t,0);
  if(fetch(t,&x)) printf("stored %s-->%d\n",t,(int)x);
  else printf("%s not stored\n",t);

  for(i=0;i<3;++i){
    y=t[i];
    for(j=0;j<6;++j){
      if(l[j]==y) continue;
      t[i]=l[j];
      if(fetch(t,&x)) store(t,-1);
      else store(t,1);
      if(fetch(t,&x)) printf("stored %s-->%d\n",t,(int)x);
      else printf("%s not stored\n",t);
    }   
    t[i]=y;
  }

  strcpy(t,a); if(fetch(t,&x)) printf("read %s-->%d\n",t,(int)x); else printf("%s not found\n",t);
  strcpy(t,b); if(fetch(t,&x)) printf("read %s-->%d\n",t,(int)x); else printf("%s not found\n",t);
  strcpy(t,c); if(fetch(t,&x)) printf("read %s-->%d\n",t,(int)x); else printf("%s not found\n",t);

  exit(EXIT_SUCCESS);
}

如您所见,我将字符串bar与之关联起来0.然后,我将所有与一个字母完全不同的单词bar并将它们关联起来1,如果之前没有添加它们,或者-1以其他方式添加它们.最后,我查找foo,bar并baz得出预期的值:

stored bar-->0
stored aar-->1
stored far-->1
stored oar-->1
stored rar-->1
stored zar-->1
stored bbr-->-1
stored bfr-->1
stored bor-->1
stored brr-->1
stored bzr-->1
stored baa-->1
stored bab-->1
stored baf-->1
stored bao-->1
stored baz-->1
foo not found
read bar-->0
read baz-->1

现在我稍微修改函数替换foo,bar&baz由CCCTTCTTATCG&CCCTTCATTGCG:

int main(){
  char a[13]="CCCTTCTTATCG"
            /*|||||| |  ||*/
  char b[13]="CCCTTCATTGCG";
  char t[13]="";
  char y='\0';
  const char l[4]={'A','C','G','T'};
  intptr_t x=NULL;
  size_t i=0,j=0;

  if(!hcreate(150)) exit_with_error("no hash");

  strcpy(t,a);
  store(t,0); 
  if(fetch(t,&x)) printf("stored %s-->%d\n",t,(int)x);
  else printf("%s not stored\n",t);

  for(i=0;i<12;++i){
    y=t[i];
    for(j=0;j<4;++j){
      if(l[j]==y) continue;
      t[i]=l[j];
      if(fetch(t,&x)) store(t,-1);
      else store(t,1);
      if(fetch(t,&x)) printf("stored %s-->%d\n",t,(int)x);
      else printf("%s not stored\n",t);
    }   
    t[i]=y;
  }

  strcpy(t,a); if(fetch(t,&x)) printf("read %s-->%d\n",t,(int)x); else printf("%s not found\n",t);
  strcpy(t,b); if(fetch(t,&x)) printf("read %s-->%d\n",t,(int)x); else printf("%s not found\n",t);

  exit(EXIT_SUCCESS);
}

为清楚起见,这里是相应的diff:

29,32c29,32
<   char a[4]="foo";
<   char b[4]="bar";
<   char c[4]="baz";
<   char t[4]="";
---
>   char a[13]="CCCTTCTTATCG";
>             /*|||||| |  ||*/
>   char b[13]="CCCTTCATTGCG";
>   char t[13]="";
34c34
<   const char l[6]={'a','b','f','o','r','z'};
---
>   const char l[4]={'A','C','G','T'};
38c38
<   if(!hcreate(50)) exit_with_error("no hash");
---
>   if(!hcreate(150)) exit_with_error("no hash");
40c40
<   strcpy(t,b);
---
>   strcpy(t,a);
45c45
<   for(i=0;i<3;++i){
---
>   for(i=0;i<12;++i){
47c47
<     for(j=0;j<6;++j){
---
>     for(j=0;j<4;++j){
60d59
<   strcpy(t,c); if(fetch(t,&x)) printf("read %s-->%d\n",t,(int)x); else printf("%s not found\n",t);

如您所见,CCCTTCATTGCG有3个编辑CCCTTCTTATCG(foo从中bar),因此不应在哈希表中找到.

但是,这是相应的输出:

stored CCCTTCTTATCG-->0
stored ACCTTCTTATCG-->1
stored GCCTTCTTATCG-->1
stored TCCTTCTTATCG-->1
stored CACTTCTTATCG-->1
stored CGCTTCTTATCG-->1
stored CTCTTCTTATCG-->1
stored CCATTCTTATCG-->1
stored CCGTTCTTATCG-->1
stored CCTTTCTTATCG-->1
stored CCCATCTTATCG-->1
stored CCCCTCTTATCG-->1
stored CCCGTCTTATCG-->1
stored CCCTACTTATCG-->1
stored CCCTCCTTATCG-->1
stored CCCTGCTTATCG-->1
stored CCCTTATTATCG-->1
stored CCCTTGTTATCG-->1
stored CCCTTTTTATCG-->1
stored CCCTTCATATCG-->1
stored CCCTTCCTATCG-->1
stored CCCTTCGTATCG-->1
stored CCCTTCTAATCG-->1
stored CCCTTCTCATCG-->1
stored CCCTTCTGATCG-->1
stored CCCTTCTTCTCG-->-1
stored CCCTTCTTGTCG-->-1
stored CCCTTCTTTTCG-->-1
stored CCCTTCTTAACG-->-1
stored CCCTTCTTACCG-->-1
stored CCCTTCTTAGCG-->-1
stored CCCTTCTTATAG-->-1
stored CCCTTCTTATGG-->-1
stored CCCTTCTTATTG-->-1
stored CCCTTCTTATCA-->-1
stored CCCTTCTTATCC-->-1
stored CCCTTCTTATCT-->-1
read CCCTTCTTATCG-->-1
read CCCTTCATTGCG-->1

正如您所看到的,即使它从未存储过,CCCTTCTTATCG也会与之相关联-1.

对于-1在存储上分配的所有字符串也是如此,因为它们在即将插入时已经在哈希中.

bbr在上面的较小例子中也是如此.

如果从未插入这些键,为什么会hsearch返回1？

Answer 1

手册页指示key应该是分配的字符串malloc.以下是手册页中的几个相关引用

hdestroy()函数为搜索表中的每个比较键调用free(3),但不调用与键关联的数据项.

和

如果action为ENTER并且调用了hdestroy(),则必须使用malloc(3)分配比较键(作为item.key传递给hsearch()).

因此,hsearch使用action 调用会ENTER在散列中存储指针,并且该指针应指向稍后可以释放的字符串.在您的代码中,您有一个单独的字符串缓冲区,每次向哈希表添加一个条目时,都会传递相同的指针(指向您的字符串缓冲区).这将使哈希表变得混乱.

解决问题很简单.在store函数中,在将条目添加到表之前复制keywith strdup.换句话说,替换

e.key=(char*)key;

同

e.key=strdup(key);