Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!agate!root
From: jwl@sag4.ssl.berkeley.edu (Jim Lewis)
Newsgroups: comp.lang.c
Subject: hash table library routines
Message-ID: <1991Jun4.210355.17290@agate.berkeley.edu>
Date: 4 Jun 91 21:03:55 GMT
Sender: root@agate.berkeley.edu (Charlie Root)
Organization: Space Science Labs
Lines: 71

I wonder if anyone else has been bitten by a problem I had with the
hsearch() function under SunOS 4.0.3.   I wrote a simple program which
created a hash table, entered a single item under a known key, and
then walked through part of the key space, attempting to find each key.
Instead of finding just the one item I put there,  many other keys would
result in successful retrievals!  (See the code below...)

After reading TFM and talking to a local expert, we decided that the
problem was *probably* that I was using the same char array as my key for 
entry and retrieval.  If hsearch() only stored the pointer to the key, 
we'd get the behavior I was seeing.

Can someone in the know verify that Sun's runtime library is actually doing
it this way?  That strikes me as a spectacularly lame design, especially
considering the complete lack of any warnings in the documentation about using
automatic storage for keys!  (Imagine inserting an item from function
foo(), using an automatic variable for the key, then trying to retrieve it 
from function bar(), after the stack has been scribbled on for a while...)

BTW, the man page *does* warn the hsearch() calls malloc()!  What the hell
for, if it's not making private copies of keys?  It's supposed to be
using an open addressing scheme (Knuth's algorithm D, section 6.4) which
uses a fixed size hash table and a secondary hash function to resolve 
collisions without resorting to linked lists or the like.

-- Jim Lewis
   U.C. Berkeley
   Space Science Labs

/* test program to illustrate hsearch() problem */

#include <stdio.h>
#include <search.h>

ENTRY *hsearch();
ENTRY item,*result;
char key[10];
char *malloc();

main()
{
   hcreate(2000);
   hash_enter(9);
   hash_dump();
}

hash_enter(int_key)
int int_key;
{
   sprintf(key,"%05x",int_key);
   item.key = key;
   item.data = malloc(100);
   printf("Entering item:  key = %s  data = %x\n",item.key, (int) item.data);
   result = hsearch(item,ENTER);
}

hash_dump()
{
   int int_key;

   for(int_key = 0; int_key < 0xff; ++int_key)
   {
      sprintf(key,"%05x",int_key);
      item.key = key;
      result = hsearch(item,FIND);
      if (result != NULL)
      {
         printf("Key: %s  Data: %x\n",result->key,(int) (result->data));
      }
   } 
}