p 145 K&R

[mdh]

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]

mdh wrote:

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;

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
es*****@ieee-dot-org.invalid

[Chris Torek]

[regarding free((void *)expr) in K&R2]

In article <oo******************************@comcast.com>
Eric Sosman <es*****@ieee-dot-org.invalidwrote:

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) [phone]
email: gmail (figure it out) http://web.torek.net/torek/index.html

[Ian Collins]

Chris Torek wrote:

[regarding free((void *)expr) in K&R2]

In article <oo******************************@comcast.com>
Eric Sosman <es*****@ieee-dot-org.invalidwrote:

> 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]

Chris Torek <[e-mail]:

...
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

[Peter Nilsson]

mdh <[e-mail]:

...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]

On Sep 1, 7:57*pm, Peter Nilsson <[e-mail]:

mdh <[e-mail]:

...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.

[Eric Sosman]

mdh wrote:

On Sep 1, 1:08 pm, Eric Sosman <[e-mail]:

>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
es*****@ieee-dot-org.invalid

[mdh]

On Sep 1, 8:33*pm, Eric Sosman <[e-mail]:

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.

[Bill Reid]

Chris Torek <no****@torek.netwrote in message
news:g9********@news4.newsguy.com...

[regarding free((void *)expr) in K&R2]

In article <oo******************************@comcast.com>
Eric Sosman <es*****@ieee-dot-org.invalidwrote:

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.)

And the great thing is, THIS is the book that typically recommended
here to "newbies" to learn "C". Aside from the fact that it contains
non-"standard" constructs, my opinion is it's a pretty bad book to try
to learn the language. I remember many years ago when I was TRYING
(I'm still TRYING) to learn "C", somebody at work gave me the K&R
book, and I struggled with it for about three minutes before throwing
it in the trash and going to a bookstore to buy a REAL book that
actually bothered to explain things rather than just present them in
a slap-dash manner starting at the middle and working sideways...

---
William Ernest Reid

[Richard]

"Bill Reid" <ho********@happyhealthy.netwrites:

Chris Torek <no****@torek.netwrote in message
news:g9********@news4.newsguy.com...

>[regarding free((void *)expr) in K&R2]

In article <oo******************************@comcast.com>
Eric Sosman <es*****@ieee-dot-org.invalidwrote:

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.)

And the great thing is, THIS is the book that typically recommended
here to "newbies" to learn "C". Aside from the fact that it contains
non-"standard" constructs, my opinion is it's a pretty bad book to try
to learn the language. I remember many years ago when I was TRYING
(I'm still TRYING) to learn "C", somebody at work gave me the K&R
book, and I struggled with it for about three minutes before throwing
it in the trash and going to a bookstore to buy a REAL book that
actually bothered to explain things rather than just present them in
a slap-dash manner starting at the middle and working sideways...

Admittedly you do have to have a programmers mind set and a modicum of
intelligence but when those criteria are met K&R is, in my mind, the
best language tutorial I have ever read.

[gw7rib]

On 2 Sep, 04:08, mdh <[e-mail]:

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.

That sounds a fair statement. Remember, however, that even with a
perfect hash function you have:

Number of items = size of hashtable * average length of list

so you may have to trade off the size of the hashtable (which takes
memory to strore) against how long you want the lists to be (takes
time to look up items).

[Eric Sosman]

Bill Reid wrote:

>
And the great thing is, [K&R] is the book that typically recommended
here to "newbies" to learn "C". Aside from the fact that it contains
non-"standard" constructs, my opinion is it's a pretty bad book to try
to learn the language. I remember many years ago when I was TRYING
(I'm still TRYING) to learn "C", somebody at work gave me the K&R
book, and I struggled with it for about three minutes [...]

Bill calls K&R a "pretty bad book" because it failed to
teach him C in three minutes. Righty-ho.

--
Eric Sosman
es*****@ieee-dot-org.invalid

[Nick Keighley]

On 2 Sep, 15:21, Richard<[e-mail]:

"Bill Reid" <[e-mail]:

<snip>

And the great thing is, THIS [K&R] is the book that typically recommended
here to "newbies" to learn "C". *Aside from the fact that it contains
non-"standard" constructs, my opinion is it's a pretty bad book to try
to learn the language. *I remember many years ago when I was TRYING
(I'm still TRYING) to learn "C", somebody at work gave me the K&R
book, and I struggled with it for about three minutes before throwing
it in the trash and going to a bookstore to buy a REAL book that
actually bothered to explain things rather than just present them in
a slap-dash manner starting at the middle and working sideways...

Admittedly you do have to have a programmers mind set and a modicum of
intelligence but when those criteria are met K&R is, in my mind, the
best language tutorial I have ever read.- Hide quoted text -

It seems not to suit complete beginners (or some of them). I know
someone who became a very competant programmer who couldn't get on
with K&R. A bit too information dense I think. And a lack of
answers to the exercises.

I thought K&R was great, but C was my Nth language

--
Nick Keighley

[pete]

Nick Keighley wrote:

It seems not to suit complete beginners (or some of them).

The book says as much in the preface.

"The book is not an introductory programming manual;
it assumes some familiarity with basic programming concepts
like variables, assignement statements, loops, and functions."

I know
someone who became a very competant programmer who couldn't get on
with K&R. A bit too information dense I think. And a lack of
answers to the exercises.

I thought K&R was great, but C was my Nth language

I had to put it down and pick up Schildt.
Three weeks later after I had learned C,
I picked up K&R and started reading clc.
It took me about two years to unlearn Schildt.

My K&R2 is page worn now.
I think most of the regulars here could tell you
what's on page 53, without looking.

--
pete

[Richard Heathfield]

pete said:

Nick Keighley wrote:

<snip>

>I thought K&R was great, but C was my Nth language

I had to put it down and pick up Schildt.
Three weeks later after I had learned C,
I picked up K&R and started reading clc.
It took me about two years to unlearn Schildt.

<grin>

My K&R2 is page worn now.
I think most of the regulars here could tell you
what's on page 53, without looking.

Right (and I know I certainly could). More scarily, I think a good number
of them could tell you (again without looking) what's on the page turn of
pp99-100, AND why it's such an unfortunate place to break the page, AND
who was (probably) the first person to notice this and point it out.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[lawrence.jones]

Nick Keighley <ni******************@hotmail.comwrote:

>
It seems not to suit complete beginners (or some of them). I know
someone who became a very competant programmer who couldn't get on
with K&R. A bit too information dense I think. And a lack of
answers to the exercises.

My favorite book for complete beginners is Tom Plum's Learning to
Program in C, but I have no idea whether it's still available or not.
--
Larry Jones

That's the problem with nature. Something's always stinging you
or oozing mucus on you. -- Calvin