|  | p 145 K&R | | |
| | | mdh |  |
|  Posted: Mon Sep 01, 2008 7:39 pm Post subject: p 145 K&R |  |
| |  | |
Hi all,
I have a question about an aspect of the hash table implementation
from p 145.
The code, stripped as far as possble, is as follows.
/*******/
#define HASHSIZE 101
struct nlist{
struct nlist *next;
char *defn;
char *name;
};
struct nlist *hashtable[HASHSIZE];
struct nlist *install( char *name, char *defn);
int main (int argc, const char * argv[]) {
struct nlist *np;
np = install("test", "12");
}
struct nlist *install( char *name, char *defn){
struct nlist *np;
unsigned hashval;
if ( (np=lookup(name) )== NULL) {
np= malloc(sizeof(*np));
if ( np == NULL || (np->name = str_dup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtable[hashval]; /******** Question 1*******/
hashtable[hashval]=np;
}
else
free((void *) np->defn); /********* Question 2 **********/
if ( ( np->defn = str_dup(defn)) == NULL)
return NULL;
return np;
}
Question 1;
What exactly does this line do? It seems to be assigning a pointer at
element "hasval" to the member nlist.next, but my question is
why?  I assume to create the linked list...but the logic escapes
me.
Question 2:
free casts np-> defn to a void pointer. K&R do not go into great
detail about free here, but seeing that free and malloc seem tied
close together, does the admonition of not using a cast in malloc
apply to free to. Of note, the errata pages do not make mention of
this.
Thanks as always. |
| |
| | | Eric Sosman | |
| | Posted: Mon Sep 01, 2008 7:39 pm Post subject: Re: p 145 K&R | |
| | | |
mdh wrote:
| Quote: | Hi all,
I have a question about an aspect of the hash table implementation
from p 145.
The code, stripped as far as possble, is as follows.
/*******/
#define HASHSIZE 101
struct nlist{
struct nlist *next;
char *defn;
char *name;
};
struct nlist *hashtable[HASHSIZE];
struct nlist *install( char *name, char *defn);
int main (int argc, const char * argv[]) {
struct nlist *np;
np = install("test", "12");
}
struct nlist *install( char *name, char *defn){
struct nlist *np;
unsigned hashval;
if ( (np=lookup(name) )== NULL) {
np= malloc(sizeof(*np));
if ( np == NULL || (np->name = str_dup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtable[hashval]; /******** Question 1*******/
hashtable[hashval]=np;
}
else
free((void *) np->defn); /********* Question 2 **********/
if ( ( np->defn = str_dup(defn)) == NULL)
return NULL;
return np;
}
Question 1;
What exactly does this line do? It seems to be assigning a pointer at
element "hasval" to the member nlist.next, but my question is
why? I assume to create the linked list...but the logic escapes
me.
|
Yes, the code adds the new `struct nlist' -- the one `np'
points to -- to the beginning of a linked list. If you pretend
for a moment that `hashtable[hashval]' is spelled `firstnode',
the pattern should resemble something you've seen before:
np->next = firstnode;
firstnode = np;
| Quote: | Question 2:
free casts np-> defn to a void pointer. K&R do not go into great
detail about free here, but seeing that free and malloc seem tied
close together, does the admonition of not using a cast in malloc
apply to free to. Of note, the errata pages do not make mention of
this.
|
The cast is unnecessary. I can't think of any good reason
to write it, but I can guess (this is only a guess) that since
Messrs K and R formed their C coding habits long before C was
standardized, some pre-Standard quirks still show through. In
particular, pre-Standard C had no `void*', so the argument to
free() was taken as `char*'. Pre-Standard C also lacked function
prototypes, so there was no way to declare that free() required
a `char*' argument, and a cast to `char*' was necessary just in
case `char*' and `struct nlist*' had different representations.
(The cast was often omitted by ill-informed people who "knew"
that all pointers looked alike; their code often came to grief
when ported to machines that didn't fit such a narrow view.)
Anyhow, my guess is that K and R were so accustomed to writing
`free( (char*) some_pointer )' -- which was safe and correct in
pre-Standard C -- that they just plugged in Standard C's `(void*)'
cast without quite thinking the matter through. But that's just my
guess, not an authoritative version of the factoids. (And I'm not
inclined to sneer at them over this slip-up, either: IIRC, the
second edition went to press a little while before the Standard
was officially adopted, so they could not have had a lot of practical
experience in coding for the newer-than-new Standard environment.)
--
Eric Sosman
esosman@ieee-dot-org.invalid |
| |
| | | Chris Torek | |
| | Posted: Mon Sep 01, 2008 7:39 pm Post subject: Re: p 145 K&R | |
| | | |
[regarding free((void *)expr) in K&R2]
In article <oo2dna88w_9e1iHVnZ2dnUVZ_oPinZ2d@comcast.com>
Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
| Quote: | The cast is unnecessary. I can't think of any good reason
to write it, but I can guess (this is only a guess) that since
Messrs K and R formed their C coding habits long before C was
standardized, some pre-Standard quirks still show through. ...
that's just my guess, not an authoritative version of the factoids.
(And I'm not inclined to sneer at them over this slip-up, either:
IIRC, the second edition went to press a little while before the
Standard was officially adopted, so they could not have had a lot
of practical experience in coding for the newer-than-new Standard
environment.)
|
K&R2 was indeed published pre- (or at least co-) Standard, and
there were no "ANSI C" compilers available at the time. They have
mentioned, here and/or in the front of the book (my K&R is missing
and/or in a box so I cannot check) that the code was compiled with
a then-C++ compiler, rather than either a K&R-1 C compiler or an
ANSI C compiler, and C++ (both then and now) had and has different
rules for type conversions, particularly with regard to "void *".
(The C++ language that existed in 1987/88 was quite different from
today's C++ language. I would say it was more different from
today's C++ than today's C99 is from K&R-1 C. But it -- then-C++,
I mean -- was the only way to work with function prototypes, back
then.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) LINK |
| |
| | | Ian Collins | |
| | Posted: Mon Sep 01, 2008 8:15 pm Post subject: Re: p 145 K&R | |
| | | |
Chris Torek wrote:
| Quote: | [regarding free((void *)expr) in K&R2]
In article <oo2dna88w_9e1iHVnZ2dnUVZ_oPinZ2d@comcast.com
Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
The cast is unnecessary. I can't think of any good reason
to write it, but I can guess (this is only a guess) that since
Messrs K and R formed their C coding habits long before C was
standardized, some pre-Standard quirks still show through. ...
that's just my guess, not an authoritative version of the factoids.
(And I'm not inclined to sneer at them over this slip-up, either:
IIRC, the second edition went to press a little while before the
Standard was officially adopted, so they could not have had a lot
of practical experience in coding for the newer-than-new Standard
environment.)
K&R2 was indeed published pre- (or at least co-) Standard, and
there were no "ANSI C" compilers available at the time. They have
mentioned, here and/or in the front of the book (my K&R is missing
and/or in a box so I cannot check) that the code was compiled with
a then-C++ compiler, rather than either a K&R-1 C compiler or an
ANSI C compiler, and C++ (both then and now) had and has different
rules for type conversions, particularly with regard to "void *".
|
You remember well, it's the second from last sentence in the preface.
--
Ian Collins. |
| |
| | | Peter Nilsson | |
| | Posted: Mon Sep 01, 2008 10:47 pm Post subject: Re: p 145 K&R | |
Chris Torek <nos...@torek.net> wrote:
| Quote: | ...
K&R2 was indeed published pre- (or at least co-)
Standard, and there were no "ANSI C" compilers available
at the time.
...
(The C++ language that existed in 1987/88 was quite
different from today's C++ language. I would say it was
more different from today's C++ than today's C99 is from
K&R-1 C. But it -- then-C++, I mean -- was the only way
to work with function prototypes, back then.)
|
According to the Preface "We used Bjarne Stroustrup's C++
translator extensively for local testing of our programs,
and Dave Kristol provided us with an ANSI C compiler for
final testing."
Depending on what you mean by 'work', it's worth noting
that C99 still doesn't _require_ function prototypes.
--
Peter |
| |
| | | Eric Sosman | |
| | Posted: Tue Sep 02, 2008 1:33 am Post subject: Re: p 145 K&R | |
| | | |
mdh wrote:
| Quote: | On Sep 1, 1:08 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
mdh wrote:
Hi all,
I have a question about an aspect of the hash table implementation
np->next = hashtable[hashval]; /******** Question 1*******/
hashtable[hashval]=np;
Yes, the code adds the new `struct nlist' -- the one `np'
points to -- to the beginning of a linked list. If you pretend
for a moment that `hashtable[hashval]' is spelled `firstnode',
the pattern should resemble something you've seen before:
np->next = firstnode;
firstnode = np;
I think I may be making this more complicated than it should be...and
I keep thinking the list is broken at some point...but ..
|
The list *is* "broken at some point," because adding the
new node involves changing two pointers, and you can only
assign to one at a time.
While linked structures are still new and strange to you
(as they were to me, back in the Bronze Age), you may find it
helpful to draw before-and-after diagrams. Show the variables
and structs as boxes, and connect them with arrows representing
the values of the pointers. Draw the "before" and "after" arrows
in different colors or styles, so you can see which arrows have
to change and which remain the same. Then walk through the code,
seeing how it changes first one arrow and then the other. Once
you've got the idea, try to discover why the program would *not*
work if the two assignments were interchanged: What is wrong with
firstnode = np;
np->next = firstnode;
? (If you have trouble seeing the difficulty, draw three
diagrams showing the initial situation, the situation after
the first assignment, and the final outcome.)
Eventually, this stuff will become familiar -- trust me.
--
Eric Sosman
esosman@ieee-dot-org.invalid |
| |
| | | mdh | |
| | Posted: Tue Sep 02, 2008 1:59 am Post subject: Re: p 145 K&R | |
| | | |
On Sep 1, 1:08 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
| Quote: | mdh wrote:
Hi all,
I have a question about an aspect of the hash table implementation
np->next = hashtable[hashval]; /******** Question 1*******/
hashtable[hashval]=np;
Yes, the code adds the new `struct nlist' -- the one `np'
points to -- to the beginning of a linked list. If you pretend
for a moment that `hashtable[hashval]' is spelled `firstnode',
the pattern should resemble something you've seen before:
np->next = firstnode;
firstnode = np;
|
I think I may be making this more complicated than it should be...and
I keep thinking the list is broken at some point...but ..
let me see if this makes sense to you.
if "name does not exist" {
np = malloc(sizeof(*np));
/* malloc returns a pointer to a struct of type nplist.*/
/* this pointer 'np' points to some memory somewhere that I
need not be concerned with */
if ("errors found")
return NULL;
hashval = "create a hash vauel from name";
np->next = hashtable[hashval];
/* whatever is currently pointed to ( be it a single struct
or a list) by the nth element of the hashtable, is now assigned to be
pointed to by the "next" pointer of the current struct ie np.ie the
single struct/list is attached to the "end" of the current struct.
At this point, and I tread carefully, knowing that events do not
happen in sequential order between sequence points...I think ,
there **could** be no connection at all between the "new" struct
linked list and the hashtable, but np still exists? as it still points
to the original "space" assigned by malloc ( and presumably all the
other structs to which it is linked do the same ).
hashtable[hashval]=np;
/* the entire new linked list is once again assigned to the hashtable
*/
**if** this is vaguely correct, is this the usual way a new struct is
"lined" to the chain ie last is placed first in a list?
thank you as always. |
| |
| | | Peter Nilsson | |
| | Posted: Tue Sep 02, 2008 2:57 am Post subject: Re: p 145 K&R | |
mdh <m...@comcast.net> wrote:
| Quote: | ...is this the usual way a new struct is "lined" to the
chain ie last is placed first in a list?
|
Since there's only a head node, it's the simplest way.
e.g. you could traverse to the end of the list and
attach it to the last node, but why bother? If the
number of clashes increases to the point where a linear
search of a small unordered list becomes too costly, then
it's time to review the hash algorithm and/or the size of
the hash table. Incorporating a more elaborate mechanism
to manage clashes tends to defeat the purposes of using
a hash table in the first place. Of course that's not
to say it never happens.
--
Peter |
| |
| | | mdh | |
| | Posted: Tue Sep 02, 2008 3:08 am Post subject: Re: p 145 K&R | |
On Sep 1, 7:57 pm, Peter Nilsson <ai...@acay.com.au> wrote:
| Quote: | mdh <m...@comcast.net> wrote:
...is this the usual way a new struct is "lined" to the
chain ie last is placed first in a list?
Since there's only a head node, it's the simplest way.
snip
If the
number of clashes increases to the point where a linear
search of a small unordered list becomes too costly,
|
Having not worked with Hash tables extensively, it seems from what you
say, that the essence is to distribute the input evenly across as many
"buckets" as possible, and keep the actual linked list reasonably
small? Is that a fair statement ?. Thank you. |
| |
| | | mdh | |
| | Posted: Tue Sep 02, 2008 3:44 am Post subject: Re: p 145 K&R | |
On Sep 1, 8:33 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
| Quote: | mdh wrote:
I think I may be making this more complicated than it should be...and
I keep thinking the list is broken at some point...but ..
The list *is* "broken at some point," because adding the
new node involves changing two pointers, and you can only
assign to one at a time.
While linked structures are still new and strange to you
(as they were to me, back in the Bronze Age),
|
Eric...thank you. Actually, I do draw things and certainly try to
mentally visualize things as you say. In fact, in writing the reply to
you, it did become clearer as well.
As far as progress goes, I finally do feel some. As per another
frequent replier to my endless questions ( ) where I had referred
to something in the "cretaceous" period, the "bronze age" is a
significant step forward!!!! :-)
As always, thank you for your answer. |
| |
| Page 1 of 2 .:. Goto page 1, 2 Next | |
|
|
