jwl@sag4.ssl.berkeley.edu (Jim Lewis) (06/05/91)
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)); } } }
igb@fulcrum.bt.co.uk (Ian G Batten) (06/05/91)
In article <1991Jun4.210355.17290@agate.berkeley.edu> jwl@sag4.ssl.berkeley.edu (Jim Lewis) writes: > [ hsearch gets in trouble if you modify things you previously passed ] I experienced this. Reading the V.3 source confirms it. ian