Thread: Hash Help

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    Hash Help

    Hi,
    I seem to get a seg fault when i implement this hash function from 'Algorithms in C -Sedgewick' ....
    I'm think it's more of my structuring, and pointer problems..

    Code:
    typedef struct {
            char *key;
            char *value;
    } TableEntry;
    
    typedef struct {
            int table_size;
            int num_items;
            TableEntry *table;
    } HashTable;
    
    static HashTable *
    hashtable_init(size_t size)
    {
        int i;
    
        HashTable *newtable = safe_malloc(sizeof(HashTable));
        newtable->table = safe_malloc(sizeof(TableEntry)*size);
        newtable->table_size = size;
        newtable->num_items = (int)size;
    
        if(newtable == NULL)
        {
                fprintf(stderr, "hashtable_init() - NYI\n");
                exit(EXIT_FAILURE);
        }
    
        /*allocate memory for word and key for each TableEntry*/
        for(i=0; i<(int)size; i++){
            newtable->table[i].key = safe_malloc(sizeof(char)*WORD_LEN);
            newtable->table[i].value = safe_malloc(sizeof(char)*WORD_LEN);
        }
    
        /*Initialise all keys and values to be null character*/
        for(i=0; i<(int)size; i++)
        {
            newtable->table[i].key = '\0';
            newtable->table[i].value = '\0';
        }
    
        return newtable;
    }
    
    static void
    hashtable_insert(HashTable *ht, char *key, char *value)
    {
        int hashval = hash_func(value, ht);
        int M = ht->num_items;
    
    
        while(ht->table[hashval].key != '\0')
            hashval = (hashval+1) % M;
    
            strcpy(ht->table[hashval].key, key);
            strcpy(ht->table[hashval].value, value);
    
    }
    
    int hash_func(char *v, HashTable *ht)
    {
            int h = 0, a = 31415, b = 27183;
            int M = ht->num_items;
    
            /*Segmentation Fault happens in this loop*/
            for(h=0; *v != '\0'; v++, a = a*b % (M-1))
                    h = (a*h + *v) % M;
    
    
            return h;
    }
    
    static void
    read_records(FILE *fp, HashTable *ht, char chomp(char*))
    {
            char key_buffer[MAX_STRING_SIZE];
            char value_buffer[MAX_STRING_SIZE];
    
            while (fgets(key_buffer, MAX_STRING_SIZE, fp) != NULL)
            {
                    if (fgets(value_buffer, MAX_STRING_SIZE, fp) == NULL)
                    {
                            fprintf(stderr, "Badly formed input file");
                            exit(EXIT_FAILURE);
                    }
                    hashtable_insert(ht, chomp(key_buffer), chomp(value_buffer));
            }
    }
    The chomp() function just replaces '\n' with '\0' from the input file

    Thx!!!!

  2. #2
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    are u getting the right key values here
    Code:
    int M = ht->num_items;
    try putting some printfs and find out. The loop itself looks to me ike right.

    ssharish2005
    Last edited by ssharish2005; 04-26-2007 at 08:46 AM.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Why do people never say what LINE it crashes in?

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Quote Originally Posted by brewbuck View Post
    Why do people never say what LINE it crashes in?
    How can they possibly know what is causing it? I mean it's not like they can scatter printf() statements throughout their code.... Oh, wait.

  5. #5
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    Code:
    /*Segmentation Fault happens in this loop*/
            for(h=0; *v != '\0'; v++, a = a*b &#37; (M-1))
                    h = (a*h + *v) % M;
    Perhaps he has already mentioned it.

    ssharish2005

  6. #6
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Ah, good point, although I would have recommended that he put that in bold if he dropped it in the code. Either way, I admit I missed it.

    Then again, since I didn't get any sleep for the past 22 hours or so, I suppose that could be the reason why.

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MacGyver View Post
    Ah, good point, although I would have recommended that he put that in bold if he dropped it in the code. Either way, I admit I missed it.
    If I'd had a hint that such a comment was in the code somewhere, I would have bothered trying to find it

    As it stands, there is far too much code missing to isolate the problem.

  8. #8
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Agreed.

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    What on earth is safe_malloc ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Salem View Post
    What on earth is safe_malloc ?
    There's no need to feign ignorance. It most likely calls malloc() and exits if it fails, or longjmps somewhere. So, "safe" in the sense that it never returns NULL.

  11. #11
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    Quote Originally Posted by Salem View Post
    What on earth is safe_malloc ?
    May be a user defined function, but there is no need one. And more over he is sending a paramtere. May be depending on the size the function allocates blocks and return address may be. Wired

    ssharish2005

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by brewbuck View Post
    There's no need to feign ignorance. It most likely calls
    If you have to add "most likely", then you are ignorant on how it works.


    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >char chomp(char*)
    So chomp returns a single char, not a string?

    > hashtable_insert(ht, chomp(key_buffer), chomp(value_buffer));
    Then you're passing those single chars to hashtable_insert, which is expecting strings.

    chomp should be returning a string, and declared as:
    Code:
    char *chomp(char*)

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    Seg fault at hash func fixed

    Oh yep!...u're right, shouldn't be returning single character from chomp().... thanks
    i'ved fixed that, and now segfault, happens in the hashtable_insert() function at the strcpy part....

    but i'll try to see wat i can do to fix that first before disturbing ...

    anyway, here's chomp() and safe_malloc()
    Code:
    static char *
    chomp(char *str)
    {
            size_t i;
    
            assert(str != NULL);
    
            for (i = strlen(str) - 1; str[i] == '\n'; i--)
            {
                    str[i] = '\0';
            }
    
            return str;
    }
    
    
    static void *
    safe_malloc(size_t size)
    {
            void *mem;
    
            if ((mem = malloc(size)) == NULL)
            {
                    fprintf(stderr, "Cannot allocate memory.\n");
                    exit(EXIT_FAILURE);
            }
    
            return mem;
    }
    thx!

  15. #15
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by quzah View Post
    If you have to add "most likely", then you are ignorant on how it works.
    The rest of the code looks rather sane. I ask myself, "what would a sane individual do in a function called safe_malloc?" Having written and seen this a thousand times, I'm pretty sure what it is.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with unaligned intrinsics
    By The Wazaa in forum C++ Programming
    Replies: 4
    Last Post: 02-18-2009, 12:36 PM
  2. need help with hash tables with direct chaining
    By agentsmith in forum C Programming
    Replies: 4
    Last Post: 01-05-2008, 04:19 AM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 07:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 09:00 PM