çhsearch发现之前未输入值 [英] C hsearch finds values not entered before

问题描述

这是一个后续问题这个问题。

由于我解决了这部分，我有一种感觉，剩下的问题是毫无关系的第一个，我决定两个部分分离成两个问题。

Since I solved part of it and I have the feeling that the remaining problem is unrelated to the first one, I decided to separate the two parts into two questions.

我已经实现了使用POSIX关联数组 hcreate / hsearch 的建议的这里。

I have implemented an associated array using POSIX hcreate/hsearch as suggested here.

有关完整起见，这里是所有除了的main（）从previous问题函数code：

For the sake of completeness, here is all the code except for the main() function from the previous question:

#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（）功能：

and here is a slightly extended main() function:

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);
}

正如你所看到的，我把字符串栏，并将其与 0 相关联。
然后，我拿在只有一个字母不同，从栏的所有字并添加其关联到 1 ，如果他们没有添加之前，或 1 其它。
最后，我查找富，栏＆安培; 巴兹导致预期值：

As you can see, I take the string bar and associate it with 0. Then, I take all words that differ in exactly one letter from bar and add associate them to 1, if they were not added before, or -1 otherwise. Finally, I lookup foo, bar & baz resulting in the expected values:

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

现在我稍微修改函数替换富，栏＆安培; 巴兹按 CCCTTCTTATCG ＆安培; CCCTTCATTGCG ：

Now I slightly modify the function replacing foo, bar & baz by 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);
}

为了清楚起见这里是相应的差异：

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 已经从 CCCTTCTTATCG 3的编辑（如富从栏），因此不应该在哈希表中找到。

As you can see, CCCTTCATTGCG has 3 edits from CCCTTCTTATCG (like foo from bar) and thus should not be found in the hash table.

然而，这是相应的输出：

However, this is the corresponding output:

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 即使从未保存它。

As you can see, CCCTTCTTATCG is associated with -1 even though it was never stored.

这也是，进行了 1 分配的存储，因为它们中的散列已经当他们将要插入的所有字符串如此。

This is also true for all strings that got -1 assigned on storage since they were already in the hash when they were about to be inserted.

这也是在上面的小示例 BBR 真。

This is also true for bbr in the smaller example above.

为什么 hsearch 收益 1 这些键，即使他们从来没有被插入？的

How come hsearch returns 1 for these keys even though they have never been inserted?

推荐答案

手册页表明键应该是一个字符串分配的malloc 。下面是从该名男子页

The man page indicates that the key should be a string allocated with malloc. Here are a couple relevant quotes from the man page

的hdestroy（）函数调用的分类（3），用于在每次比较关键
  搜索表而不是数据项与密钥关联。

The hdestroy() function calls free(3) for each comparison key in the search table but not the data item associated with the key.

和

该密钥（传递给hsearch（）作为item.key）必须分配
  使用malloc（3）如果操作ENTER和hdestroy（）被调用。

The comparison key (passed to hsearch() as item.key) must be allocated using malloc(3) if action is ENTER and hdestroy() is called.

所以叫 hsearch 用行动 ENTER 存储在哈希一个指针，该指针有望指向可稍后被释放的字符串。在您的code，你有一个单一的字符串缓冲区，每次添加到哈希表中的条目时，传递相同的指针（指向您的字符串缓冲区）。这将会使哈希表的一个烂摊子。

So calling hsearch with action ENTER stores a pointer in the hash, and that pointer is expected to point to a string that can be later freed. In your code, you have one single string buffer, and every time you add an entry to the hash table, you pass the same pointer (which points to your string buffer). That's going to make a mess of the hash table.

解决这一问题，很简单。在商店功能，使键副本与的strdup 之前添加条目表。换句话说，替换

Fixing the problem is simple. In the store function, make a copy of the key with strdup before adding the entry to the table. In other words, replace

e.key=(char*)key;

与

e.key=strdup(key);

这篇关于çhsearch发现之前未输入值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！