You need to separate in your mind two things (1) in what memory is the thing I want to store stored?; and (2) what variable (pointer) holds the address to where it is stored so I can find it again.
You first declare two pointers to struct hashrec
:
HASHREC *htmp, *hprv;
A pointer is nothing but a variable that holds the address to something else as its value. When you first declare the two pointers, they are uninitialized and hold no address. You then, in a rather awkward manner, initialize both pointers within a for
loop declaration, e.g. hprv = NULL, htmp = ht[hval]
and later hprv = htmp, htmp = htmp->next
so presumably both pointers now hold an address and point somewhere.
Following the loop (with an empty body), you test if (htmp == NULL)
, meaning that htmp
does not point to an address (which can be the case if you have found the hash-index of interest empty).
Then in order to provide storage for one HASHREC
(e.g. a struct hashrec
) you need to allocate storage so you have a block of memory in which to store the thing you want to store. So you allocate a block to hold one struct. (See: Do I cast the result of malloc?)
Now, look at what you have allocated memory for:
typedef struct hashrec {
char *word;
long long id;
struct hashrec *next;
} HASHREC;
You have allocated storage for a struct that contains (1) a char *word;
(a pointer to char - 8-bytes (4-bytes on x86)); (2) a long long id;
(8-bytes on both) and (3) a pointer to hold the address of the next HASHREC
in the sequence.
There is no question that id
can hold a long long
value, but what about word
and next
? They are both pointers. What do pointers hold? The address to where the thing they point to can be found. Where can word
be found? The thing you want is currently pointed to by w
, but there is no guarantee that w
will continue to hold the word you want, so you are going to make a copy and store it as part of the HASHREC
. So you see:
htmp->word = malloc(strlen(w) + 1); /* useless cast removed */
Now what does malloc
return? It returns the address to the beginning of a new block of memory, strlen(w) + 1
bytes long. Since a pointer holds the value of something else as its value, htmp->word
now stores the address to the beginning of the new block of memory as its value. So htmp->word
"points" to the new block of memory and you can use htmp->word
as a reference to refer to that block of memory.
What happens next is important:
strcpy(htmp->word, w); #
htmp->id = id; # why not allocate memory for htmp->id ?
htmp->next = NULL; # why nor allocate memory for htmp->next?
strcpy(htmp->word, w);
copies w
into that new block of memory. htmp->id = id;
assigns the value of id
to htmp->id
and no allocation is required because when you allocate:
htmp = malloc(sizeof(HASHREC)); /* useless cast removed */
You allocate storage for a (1) char *
pointer, (2) a long long id;
and (3) a struct hashrec*
pointer -- you have already allocated for a long long
so htmp->id
can store the value of id
in the memory for the long long
.
htmp->next = NULL; # why nor allocate memory for htmp->next?
What is it that you are attempting to store that would require new allocation for htmp->next
? (hint: nothing currently) It will point to the next struct hashrec
. Currently it is initialize to NULL
so that the next time you iterate to the end of all the struct hashrec next
pointers, you know you are at the end when you reach NULL
.
Another way to think of it is that the previous struct hashrec next
can now point to this node you just allocated. Again no additional allocation is required, the previous node ->next
pointer simply points to the next node in sequence, not requiring any specific new memory to be allocated. It is just used as a reference to refer (or point to) the next node in the chain.
There is a lot of information here, but when you go through the thought process of determining (1) in what memory is the thing I want to store stored?; and (2) what variable (pointer) holds the address to where it is stored so I can find it again... -- things start to fall into place. Hope this helps.