K&R hash table question

[merrittr]

Hi

in the code below in the main the hash table from K&R example replaces
a node when a collision occurs
What I am trying to do is set it up to "chain" another structure
beside the node that it collides with
can you spot what I am doing wrong? zork and 122 are to 2 that collide
so the "zork" node gets overwritten by
121.


#include <stdio.h>
#include <stdlib.h>
#define HASHSZ 10


struct nlist
{
struct nlist *next;
char *name;
char *defn;
};

static struct nlist *hashtab[HASHSZ] = {NULL};
char *strdup(char *);


int hash(char *str)
{
unsigned long h;
unsigned char *p;

p = (unsigned char*)str;
for(h = 0; *p != '\0'; p++)
h = 37 * h + *p;
printf("%s hash is > %d\n", str,h % HASHSZ);
return h % HASHSZ;
}


struct nlist *lookup(char *s)
{
struct nlist *np;

for (np = hashtab[hash(s)]; np != NULL; np = np->next)
{
printf("%s = %s\n",s,np->name);
if(strcmp(s, np->name) == 0)
{
return np;
}
}

return NULL;
}


struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;

if ((np = lookup(name)) == NULL)
{
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
}
else
free((void *) np->defn);
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}


void printhash()
{
int i;
struct nlist *np;
for(i = 0; i < HASHSZ; i++)
{
printf("\n%d- ",i);
if (hashtab != NULL)
{
np = hashtab;
printf ("name :%s defn :%s \n",np->name, np->defn);
if (np->next != NULL)
{
np = np->next;
}
}

}

}


main(int argc, char **argv)
{
printf(" %s hashes too > %d\n",argv[1],hash(argv[1]));
install("gleep","glorp");
install("zork","zero"); //this hashes to 0
install("glorp","gleep");
install("121", "ewewfgre1"); //this hashes to 0

printhash();
printf("\ndone\n");
}

 

[Eric Sosman]

merrittr wrote On 06/25/07 15:15,:

Hi

in the code below in the main the hash table from K&R example replaces
a node when a collision occurs
What I am trying to do is set it up to "chain" another structure
beside the node that it collides with
can you spot what I am doing wrong? zork and 122 are to 2 that collide
so the "zork" node gets overwritten by
121.
[... code snipped; see up-thread ...]

What evidence do you have that it gets overwritten?
Your printhash() function only prints the first node in
each non-empty chain it finds; how do you know anything
about possible successor nodes?

Start by fixing that bug, and then see where you stand.
There are a number of other improvements you could make,
but since you seem to be trying to learn by doing (a very
good way, with good guidance like K&R), you'll probably
learn more and better by discovering them for yourself.

 

[merrittr]

whoops sorry Eric,

I should have noted that my print hash is a stub.

here is what prints out now which led me to the
overwrite issue



gleep hash is > 5
gleep hash is > 5
------------------
zork hash is > 0
zork hash is > 0
------------------
glorp hash is > 6
glorp hash is > 6
------------------
121 hash is > 0
121 = zork
121 hash is > 0

0- name :121 defn :ewewfgre1
name :121 defn :ewewfgre1

1-
2-
3-
4-
5- name :gleep defn :gloop

6- name :glorp defn :gleep

7-
8-
9-
done

[... code snipped; see up-thread ...]

What evidence do you have that it gets overwritten?
Your printhash() function only prints the first node in
each non-empty chain it finds; how do you know anything
about possible successor nodes?

Start by fixing that bug, and then see where you stand.
There are a number of other improvements you could make,
but since you seem to be trying to learn by doing (a very
good way, with good guidance like K&R), you'll probably
learn more and better by discovering them for yourself.

 

[Eric Sosman]

merrittr wrote On 06/25/07 16:03,:

whoops sorry Eric,

I should have noted that my print hash is a stub.

here is what prints out now which led me to the
overwrite issue
[...]

Do you think we're a bunch of psychics? You'll
need to remove your tin foil helmet before we can read
your mind to discover what your actual code is so we
can study your actual bug.

Post a *complete* *exact* *short* *self-contained*
program that demonstrates your problem, and maybe someone
will be able to help you. For my part, I'm not going to
lift another finger on your behalf as long as you keep
feeding me half-truths. It's a waste of time -- both
mine and yours.

"Doctor, my knee hurts!"

"Which knee?"

"Whoops, sorry, I should have noted: it's not really
my knee, it's my head that hurts. Oh, and it's actually
my wife's head."

"I feel very sorry for her."

 

[Barry Schwarz]

Hi

in the code below in the main the hash table from K&R example replaces
a node when a collision occurs
What I am trying to do is set it up to "chain" another structure
beside the node that it collides with
can you spot what I am doing wrong? zork and 122 are to 2 that collide
so the "zork" node gets overwritten by
121.


#include <stdio.h>
#include <stdlib.h>
#define HASHSZ 10


struct nlist
{
struct nlist *next;
char *name;
char *defn;
};

static struct nlist *hashtab[HASHSZ] = {NULL};

The initialization is redundant but harmless.

char *strdup(char *);

This function invades the reserved namespace for the standard library.

int hash(char *str)
{
unsigned long h;
unsigned char *p;

p = (unsigned char*)str;
for(h = 0; *p != '\0'; p++)
h = 37 * h + *p;

If you want people to read your code, the least you could do is indent
consistently.

printf("%s hash is > %d\n", str,h % HASHSZ);

This invokes undefined behavior. h is an unsigned long. HASHSZ is a
sized int. The expression will evaluate to some flavor of long. %d
promises printf that the argument is an int. You cannot lie to printf
and expect predictable results.

return h % HASHSZ;
}


struct nlist *lookup(char *s)
{
struct nlist *np;

for (np = hashtab[hash(s)]; np != NULL; np = np->next)
{
printf("%s = %s\n",s,np->name);
if(strcmp(s, np->name) == 0)
{
return np;
}
}

return NULL;
}


struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;

if ((np = lookup(name)) == NULL)
{
np = (struct nlist *) malloc(sizeof(*np));

The cast serves no purpose other than to camouflage potential errors.

if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;

If np is not NULL but strdup returns NULL, you have created a memory
leak by failing to free np.

hashval = hash(name);

You keep oscillating between signed and unsigned values.

np->next = hashtab[hashval];
hashtab[hashval] = np;
}
else
free((void *) np->defn);

The cast serves no purpose.

if ((np->defn = strdup(defn)) == NULL)
return NULL;

If strdup returns NULL, np->defn becomes NULL. Later, you attempt to
print the string np->defn points to without checking if it is NULL or
not.

return np;
}


void printhash()
{
int i;
struct nlist *np;
for(i = 0; i < HASHSZ; i++)
{
printf("\n%d- ",i);
if (hashtab != NULL)
{
np = hashtab;
printf ("name :%s defn :%s \n",np->name, np->defn);
if (np->next != NULL)
{
np = np->next;
}
}

}

}


main(int argc, char **argv)
{
printf(" %s hashes too > %d\n",argv[1],hash(argv[1]));
install("gleep","glorp");
install("zork","zero"); //this hashes to 0
install("glorp","gleep");
install("121", "ewewfgre1"); //this hashes to 0

printhash();
printf("\ndone\n");

You never free your dynamically allocated memory.

}

Remove del for email

 

[merrittr]

Eric thats what I thought I did, the code in my first posting is
from the K&R book I added "main" and "printhash". I am sorry if you
think I somehow lied to you.

merrittr wrote On 06/25/07 16:03,:

whoops sorry Eric,

I should have noted that my print hash is a stub.

here is what prints out now which led me to the
overwrite issue
[...]

Do you think we're a bunch of psychics? You'll
need to remove your tin foil helmet before we can read
your mind to discover what your actual code is so we
can study your actual bug.

Post a *complete* *exact* *short* *self-contained*
program that demonstrates your problem, and maybe someone
will be able to help you. For my part, I'm not going to
lift another finger on your behalf as long as you keep
feeding me half-truths. It's a waste of time -- both
mine and yours.

"Doctor, my knee hurts!"

"Which knee?"

"Whoops, sorry, I should have noted: it's not really
my knee, it's my head that hurts. Oh, and it's actually
my wife's head."

"I feel very sorry for her."

 

[Eric Sosman]

A: Because it reverses the normal flow of discourse
and makes a conversation difficult to follow.
Q: Why?
A: Top-posting.
Q: Is there anything on Usenet that irritates you?

merrittr wrote On 06/26/07 14:58,:

Eric thats what I thought I did, the code in my first posting is
from the K&R book I added "main" and "printhash". I am sorry if you
think I somehow lied to you.

merrittr wrote On 06/25/07 16:03,:

whoops sorry Eric,

I should have noted that my print hash is a stub.

here is what prints out now which led me to the
overwrite issue
[...]

Do you think we're a bunch of psychics? You'll
need to remove your tin foil helmet before we can read
your mind to discover what your actual code is so we
can study your actual bug.

Post a *complete* *exact* *short* *self-contained*
program that demonstrates your problem, and maybe someone
will be able to help you. For my part, I'm not going to
lift another finger on your behalf as long as you keep
feeding me half-truths. It's a waste of time -- both
mine and yours.

"Doctor, my knee hurts!"

"Which knee?"

"Whoops, sorry, I should have noted: it's not really
my knee, it's my head that hurts. Oh, and it's actually
my wife's head."

"I feel very sorry for her."

You showed us *a* printhash(), but when I pointed out
that the function shown would print only the first node
in each chain you said you were actually using some other
printhash(). Which you didn't show. In short, you have
*not* shown us your program; you've shown us some bits
and pieces of things that may be like your program but
are actually not part of it.

 

[CBFalconer]

merrittr wrote: ** and top-posted - fixed ***

merrittr wrote On 06/25/07 16:03,:
.... snip ...

here is what prints out now which led me to the
overwrite issue
[...]

Do you think we're a bunch of psychics? You'll
need to remove your tin foil helmet before we can read
your mind to discover what your actual code is so we
can study your actual bug.

Post a *complete* *exact* *short* *self-contained*
program that demonstrates your problem, and maybe someone
will be able to help you. For my part, I'm not going to
lift another finger on your behalf as long as you keep
feeding me half-truths. It's a waste of time -- both
mine and yours.

Eric thats what I thought I did, the code in my first posting
is from the K&R book I added "main" and "printhash". I am sorry
if you think I somehow lied to you.

Please do not top-post. Your answer belongs after (or intermixed
with) the quoted material to which you reply, after snipping all
irrelevant material. I fixed this one. See the following links:

--
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/> (taming google)
<http://members.fortunecity.com/nnqweb/> (newusers)

 

[merrittr]

A: Because it reverses the normal flow of discourse
and makes a conversation difficult to follow.
Q: Why?
A: Top-posting.
Q: Is there anything on Usenet that irritates you?

merrittr wrote On 06/26/07 14:58,:

Eric thats what I thought I did, the code in my first posting is
from the K&R book I added "main" and "printhash". I am sorry if you
think I somehow lied to you.

merrittr wrote On 06/25/07 16:03,:
whoops sorry Eric,
I should have noted that my print hash is a stub.
here is what prints out now which led me to the
overwrite issue
[...]
Do you think we're a bunch of psychics? You'll
need to remove your tin foil helmet before we can read
your mind to discover what your actual code is so we
can study your actual bug.
Post a *complete* *exact* *short* *self-contained*
program that demonstrates your problem, and maybe someone
will be able to help you. For my part, I'm not going to
lift another finger on your behalf as long as you keep
feeding me half-truths. It's a waste of time -- both
mine and yours.
"Doctor, my knee hurts!"
"Which knee?"
"Whoops, sorry, I should have noted: it's not really
my knee, it's my head that hurts. Oh, and it's actually
my wife's head."
"I feel very sorry for her."

You showed us *a* printhash(), but when I pointed out
that the function shown would print only the first node
in each chain you said you were actually using some other
printhash(). Which you didn't show. In short, you have
*not* shown us your program; you've shown us some bits
and pieces of things that may be like your program but
are actually not part of it.

that is the printhash function I am using. It displays the fact that
the collide node gets overwritten

 

[¬a\\/b]

On Tue, 26 Jun 2007 16:36:58 -0400, Eric Sosman wrote:

Q: where is difficult to flow the "discourse"? (to consider apart i
don't well know english)
[answer to this:
top posting is better because i read first the last answer and
not have to scroll down all post that possibly i remember all
]

for doing this i have only to see lines of *each reply people*,
all in the reverse order [like here] and with exercise
this should be easy soon

A: Because it reverses the normal flow of discourse
and makes a conversation difficult to follow.

A: is only a conventional rule (and should be better);

Q: Why?

 

[Richard Heathfield]

¬a\/b said:

top posting is better

No, it isn't.

because i read first the last answer

Without checking the context?

and not have to scroll down all post

That's an argument in favour of judicious snipping. It is not an
argument in favour of top-posting.

for doing this i have only to see lines of *each reply people*,
all in the reverse order [like here] and with exercise
this should be easy soon

It isn't a question of what's easy for you. It's a question of what's
fast for your readers. In this newsgroup, we have long since discovered
that top-posted replies take longer to read and longer to reply to. So
we sometimes won't bother.

 

[Jean-Marc Bourguet]

[answer to this:
top posting is better because i read first the last answer and
not have to scroll down all post that possibly i remember all
]

If you follow one or two threads on one group, that's possible if these
threads are like a conversation between two people. When you follow most of
the threads of several subgroups, it doesn't scale. It doesn't scale even
for one typical thread which pretty quickly split up in more or less
related subthreads with the same people participating in several of the
branches.

Yours,

 

[¬a\\/b]

¬a\/b said:

Do you now see it is better?

<snip>

No, it isn't.

no the context is only in reverse order: more last is the post more
near is to the top; the first my line reply is below
someone have to begin to the first reply line

Without checking the context?

no it is (in favor of top post)

That's an argument in favour of judicious snipping. It is not an
argument in favour of top-posting.

<snip>

i try something new... possibly all you have not try this
____ [this indicate the first reply]

It isn't a question of what's easy for you. It's a question of what's
fast for your readers. In this newsgroup, we have long since discovered
that top-posted replies take longer to read and longer to reply to. So
we sometimes won't bother.

for doing this i have only to see lines of *each reply people*,
all in the reverse order [like here] and with exercise
this should be easy soon

 

[Richard Heathfield]

¬a\/b said:

Do you now see it is better?

Do I now see what is better?

<snip>

 

[Keith Thompson]

Do you now see it is better?

[...]

If you insist on top-posting, you will be ignored. (For the most
part, you already are.)

 

[Mark McIntyre]

Do you now see it is better?

What? You have no context for your comment.

Apparently you're a troll.

no the context is only in reverse order:

A stupid troll at that.
*plonk.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[CBFalconer]

.... snip ...


A stupid troll at that.

*plonk.

What took you so long?