Hash table code question

This is a discussion on Hash table code question within the C Programming forums, part of the General Programming Boards category; Hi, I'm having difficulty understanding part of a hash table code example from my textbook. I don't understand why the ...

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    54

    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?
    Last edited by Boxknife; 08-12-2008 at 05:22 PM.

  2. #2
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    ptrCurr is local pointer, but ptrUpdate is it's address (of current item), so it modifies original...

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    54
    Okay, so *ptrUpdate=&element[i] modifies the contents of the "next pointer" of the actual element, while ptrCurr=element[i] would just place an address into the ptrCurr variable?

  4. #4
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by Boxknife View Post
    Okay, so *ptrUpdate=&element[i] modifies the contents of the "next pointer" of the actual element, while ptrCurr=element[i] would just place an address into the ptrCurr variable?
    Yes, and that ptrCurr will be overwritten in loop and lost when block ends ("}"), so "result of whole operation" is void/incomplete.

  5. #5
    Registered User
    Join Date
    Jun 2008
    Posts
    54
    Is there absolutely no way to store element[i] to the original object through ptrCurr? Like, say, *ptrCurr = element[i] ?

  6. #6
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by Boxknife View Post
    Is there absolutely no way to store element[i] to the original object through ptrCurr? Like, say, *ptrCurr = element[i] ?
    That would be assinging struct to struct which isn't allowed in C. But you don't want to copy elements, you want to update their pointers (->next), so you must use pointer to pointer to modify pointer "in-place".

  7. #7
    Registered User
    Join Date
    Jun 2008
    Posts
    54
    Ahhhhhhhhhhhhhh, thanks.

  8. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    That would be assinging struct to struct which isn't allowed in C.
    Who said that? I'm doing it all the time
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by vart View Post
    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....
    Last edited by rasta_freak; 08-13-2008 at 02:31 AM. Reason: syntax errors

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by rasta_freak View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  12. #12
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Will assigning ('=') copy padded bytes too (of aligned members) like memcpy() or not?

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by rasta_freak View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by matsp View Post
    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
    When you do data/integrity checking and have CRC32 of whole struct, it could make difference...

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by rasta_freak View Post
    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&#37; trust the compiler to copy the entire struct, padding included.

    --
    Mats
    Last edited by matsp; 08-13-2008 at 04:29 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. trying to make a hash table......trouble w/ memory?
    By cuizy in forum C Programming
    Replies: 3
    Last Post: 05-11-2009, 04:47 PM
  2. hash table *clueless* help :)
    By willc0de4food in forum C Programming
    Replies: 2
    Last Post: 10-15-2005, 03:54 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Hash Table implementation
    By supaben34 in forum C++ Programming
    Replies: 6
    Last Post: 09-26-2003, 12:48 PM
  5. Very simple question, problem in my Code.
    By Vber in forum C Programming
    Replies: 7
    Last Post: 11-16-2002, 02:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21