p 145 K&R

M

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

Chris Torek

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

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

Ian Collins

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

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

Peter Nilsson

Chris Torek said:
...
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.
 
M

mdh

mdh said:
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.
 
P

Peter Nilsson

mdh said:
...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.
 
M

mdh

Since there's only a head node, it's the simplest way.


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

mdh

mdh wrote:

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

Bill Reid

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

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

Richard

Bill Reid said:
[regarding free((void *)expr) in K&R2]

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

gw7rib

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

gw7rib

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
*/

I think you're worrying unduly about whether the code happens in
sequential order here. Each of the semicolons gives you a sequence
point. The usual problems with sequence points (or rather, the lack of
them) tend to happen when you use ++ or --.

Hope that helps.
Paul.
 
D

Dan Henry

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.

A reasonable reading order could be:

1. K&R as a decent tutorial.
2. H&S as a decent reference.
3. The Standard (year of your interest) as the definitive
reference.
 
N

Nick Keighley

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
 
L

lawrence.jones

Nick Keighley said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

K&R hash table question 16
hash table variable question 4
Question on free() ing a hash table 13
Queue in C 25
Fibonacci 0
One last question on hashes 2
First Fit Memory Allocation -- review 0
K&R p 130 29

Members online

Forum statistics

Threads
473,744
Messages
2,569,480
Members
44,900
Latest member
Nell636132

Latest Threads

Top