Thread: Hash table code question

Hi,

I'm having difficulty understanding part of a hash table code example from my textbook. I don't understand why the pointer to a pointer to an Element "ptrUpdate" is strictly necessary when the pointer to an Element "ptrCurr" transverses the linked list of Elements in exactly the same way as ptrUpdate except for one less level of indirection.

My best current guess is that, since this example is supposed to be part of a case study on aspects of Instruction Level Parallelism and run-time hardware scheduling, the apparent redundancy is really just for exposing additional instruction level parallelism in the loops, or at least smoothing it out.

I don't trust that guess, which is why I'm asking you (it has been awhile since I coded in C).

Code:

/*I've copied this manually out of my textbook, so any typographical
errors are most likely mine */

typedef struct _Element {

int value;
struct _Element *next;

} Element;

Element element[N_ELEMENTS], *bucket[1024];

for(i=0;i< N_ELEMENTS; i++)
{
Element *ptrCurr, **ptrUpdate;
int hash_index;

hash_index =element[i].value & 1023;
ptrUpdate=&bucket[hash_index];
ptrCurr=bucket[hash_index];

while(ptrCurr && ptrCurr->value <= element[i].value)
{

ptrUpdate=&ptrCurr->next;
ptrCurr=ptrCurr->next;
}

element[i].next= *ptrUpdate;
*ptrUpdate = &element[i];

}

Couldn't the last two statements be replaced with

Code:

element[i].next=ptrCurr;
*ptrCurr=element[i];

and all the previous uses of ptrUpdate omitted?

That would be assinging struct to struct which isn't allowed in C.

Who said that? I'm doing it all the time

Originally Posted by vart

Who said that? I'm doing it all the time

Please explain, is that possible from day 0, or is it added as some extension? 'Cause all this years i've been memcpy()-ing....

Originally Posted by rasta_freak

Please explain, is that possible from day 0, or is it added as some extension? 'Cause all this years i've been memcpy()-ing....

It's been part of ANSI since the first ANSI standard, that's for sure. I don't know if it was there before that.

Looking at the original code, it doesn't look entirely complete [some lines appear to be missing] - so it would be a little bit difficult to say exactly what is meant to happen and where.

--
Mats

Please explain, is that possible from day 0

I think so because it is the same as passing struct by value which was possible from the very beginning

Originally Posted by rasta_freak

Will assigning ('=') copy padded bytes too (of aligned members) like memcpy() or not?

I believe that is technically not specified, but in the implementations I've seen it either calls memcpy() or implements the same functionality inline for larger structures. Small structures may be copied with simpler constructions, but generally copying all bytes of the struct in 32-bit chunks. What difference does it make? You can't "use" those padding bytes for anything, so whether they are copied or not wouldn't make much meaningful difference.

--
Mats

Originally Posted by rasta_freak

When you do data/integrity checking and have CRC32 of whole struct, it could make difference...

Yes, I suppose so. But then I would try to ensure that I knew where and how much the padding was too - by adding my own filler bytes and then verifying that sizeof(mystruct) == expected size somewhere in the early stages of the code. That way, there would be no "surprise holes".

Edit: Seeing as you probably need the CRC checks because the data passes from one application to another [probably via some network or similar], you would have to know that the size matches at both ends some way or another.

But I think you can ALMOST 100% trust the compiler to copy the entire struct, padding included.

--
Mats