2

Using associative arrays implented via the POSIX hcreate/hsearch functions (as described here, I struggled some unexpected behaviour finding keys I've never entered or the other way around. I tracked it down to some instance of store-by-reference-instead-of-value. This was surprising to me, since in the example uses string literals as keys:

store("red",    0xff0000);
store("orange", 0x123456);  /* Insert wrong value! */
store("green",  0x008000);
store("blue",   0x0000ff);
store("white",  0xffffff);
store("black",  0x000000);
store("orange", 0xffa500);  /* Replace with correct value. */

Here is an MWE that shows my problem:

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

void main(){
  char a[4]="foo";
  char b[4]="bar";
  char c[4]="";
  intptr_t x=NULL;

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

  store(a,1);  /* a -->  1   */
  strcpy(c,a); /* remember a */
  strcpy(a,b); /* set a to b */
  store(a,-1); /* b --> -1   */
  strcpy(a,c); /* reset a    */

  if(fetch(a,&x)&&x==1) puts("a is here.");
  if(!fetch(b,&x)) puts("b is not.");
  strcpy(a,b); printf("But if we adjust a to match b");
  if(fetch(a,&x)&&x==-1&&fetch(b,&x)&&x==-1) puts(", we find both.");
  exit(EXIT_SUCCESS);
 }

Compiling and executing above C code results in the following output:

a is here.
b is not.
But if we adjust a to match b, we find both.

I will need to read a file and store a a large number of string:int pairs and then I will need to read a second file to check an even larger number of strings for previously stored values.

I don't see how this would be possible if keys are compared by reference.

How can I change my associative array implementation to store keys by value?

And if that's not possible, how can I work around that problem given the above use case?

edit:

This question just deals with keys entered but not found. The opposite problem also appears and is described in detail in this question.

Community
  • 1
  • 1
mschilli
  • 1,884
  • 1
  • 26
  • 56
  • Possible duplicate of [C hsearch finds values not entered before](http://stackoverflow.com/questions/34752934/c-hsearch-finds-values-not-entered-before) – mschilli Jan 13 '16 at 10:10

1 Answers1

1

edit:

It turned out that store() needs to strdup() key to fix this and another problem.

I found out that by using the same variable for storage & lookup, I can actually retrieve all the values in the array:

void main(){
 char a[4]="foo";
  char b[4]="bar";
  char c[4]="baz";
  char t[4]="";
  intptr_t x=NULL;

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

  strcpy(t,a); store(t, 1); /* a -->  1 */
  strcpy(t,b); store(t,-1); /* b --> -1 */
  strcpy(t,c); store(t, 0); /* c -->  0 */

  if(!fetch(a,&x)) puts("a is not here.");
  if(!fetch(b,&x)) puts("Neither is b.");
  if( fetch(c,&x)) puts("c is in (and equal to t).");

  strcpy(t,a); if(fetch(t,&x)&&x== 1) puts("t can retrieve a.");
  strcpy(t,b); if(fetch(t,&x)&&x==-1) puts("It also finds b.");
  strcpy(t,c); if(fetch(t,&x)&&x== 0) puts("And as expected c.");

  exit(EXIT_SUCCESS);
}

This results in the following output:

a is not here.
Neither is b.
c is in (and equal to t).
t can retrieve a.
It also finds b.
And as expected c.

However, I still don't understand why this is happening.

Somehow it seems the key needs to be at the same location (reference) and contain the same content (value) to be found.

Community
  • 1
  • 1
mschilli
  • 1,884
  • 1
  • 26
  • 56