C program fails after multiple runs

Discussion in 'Mac Programming' started by moonman239, Dec 16, 2015.

  1. moonman239, Dec 16, 2015
    Last edited: Dec 18, 2015

    moonman239 macrumors 68000

    Joined:
    Mar 27, 2009
    #1
    I'm building a program that creates one hash for each string, then associates that hash with a char * value. I've found, though, that if I run the code posted below enough times, eventually I trigger one of my custom "exceptions", shall we say. The only way to get the program to function is to change my printf, run it, then change it back. Here's my code:

    Code:
    #include <stdio.h>
    
    
    
    #include <string.h>
    
    #include "stdlib.h"
    
    #include "math.h"
    
    struct hashvaluepair {
    
        int hash;
    
        char *value;
    
    };
    
    
    
    typedefstructhashvaluepair hvp;
    
    struct table {
    
        int length;
    
        hvp *backingArray;
    
    };
    
    typedefstructtable htable;
    
    int hash(char *key)
    
    {
    
        int _hash = 0;
    
        unsigned long keyLength = strlen(key);
    
        int partSum = 0;
    
        int elementsPerPart = 2;
    
        for (int i=0; i <= keyLength; i++) {
    
            if (i % elementsPerPart == 0) {
    
                _hash = 10 * _hash + (partSum % 1000);
    
                partSum = 0;
    
            }
    
            char literal = key[i];
    
            int asciiStringRep = literal;
    
            partSum += asciiStringRep;
    
        }
    
        return _hash;
    
    }
    
    htable * createHashTable()
    
    {
    
        htable *newHashTable = malloc(sizeof(htable));
    
        newHashTable->backingArray = malloc(0);
    
        newHashTable->length = 0;
    
        return newHashTable;
    
    }
    
    int insertHVP(htable *table, hvp *pair)
    
    {
    // Create a new backing array to accommodate the new "hvp" variable.
        int hvpSize = sizeof(pair);
    
        table->backingArray = realloc(table->backingArray,sizeof(table->backingArray) + hvpSize);
    
        hvp *array = table->backingArray;
    
        int hvpIndex = 0;
    // All elements in the array should be sorted according to their hashes. The struct with hash 800 should have a lower index than the struct with hash 912.
        for (int i=0; ((pair->hash > array[i - 1].hash) && (i <= table->length)) || i==0; i++) {
    
            hvpIndex = i;
    
        }
    
        for (int i=hvpIndex; i <= table->length; i++) {
    
            array[i + 1] = array[i];
    
        }
    
        if (array[hvpIndex].hash == pair->hash) {
    
            return 1 + (array[hvpIndex].value == pair->value);
    
        }
    
        array[hvpIndex] = *pair;
    
        table->length += 1;
    
        return 0;
    
    }
    
    int addKeyValuePair(char *key, char *value, htable *table)
    
    {
    
        hvp *hashValuePair = malloc(sizeof(hvp));
    
        int _hash = hash(key);
    
        hashValuePair->hash = _hash;
    
        hashValuePair->value = value;
    
        int returnVal = insertHVP(table, hashValuePair);
    
        free(hashValuePair);
    
        return returnVal;
    
    }
    
    char *valueForKey(char *key,htable *table)
    
    {
    
        int _hash = hash(key);
    
        int minIndex = 0;
    
        int maxIndex = table->length - 1;
    
        int middleIndex = -1;
    
        hvp *array = table->backingArray;
    
        char *value = NULL;
        // Here, I look for the hash-value pair by checking the first and last hashes in the array. If they are not there, my "while" loop will search for the hash-value pair by calculating ranges that get smaller until only one hash-value pair remains.
        if (array[minIndex].hash == _hash)
    
        {
    
            value = array[minIndex].value;
    
        }
    
        else if (array[maxIndex].hash == _hash)
    
        {
    
            value = array[maxIndex].value;
    
        }
    
        else
    
        {
    
        while (array[middleIndex].hash != _hash) {
    
            middleIndex = floor((minIndex + maxIndex) / 2);
    
            hvp middle = array[middleIndex];
    
            // printf("middle hash: %d", middle.hash);
    
            int middleHash = middle.hash;
    
            if (middleHash < _hash) {
    
                minIndex = middleIndex;
    
            }
    
            else if (middleHash > _hash)
    
            {
    
                maxIndex = middleIndex;
    
            }
    
            else
    
            {
    
                value = middle.value;
    
            }
    
        }
    
        }
    
        return value;
    
    }
    
    
    
    int main(int argc, const char * argv[]) {
    
        htable *table = createHashTable();
    
        char *allison = "Allison";
    
        char *andy = "Andy";
    
    
    
        addKeyValuePair(allison, "1234 Whatever Way", table);
    
        int errorCode = addKeyValuePair(andy, "1514 Anytown Dr", table);
    
        if (errorCode > 0)
    
        {
    
            printf("Error code %d \n", errorCode);
    
            abort();
    
        }
    
        printf("%s",valueForKey(andy, table));
    
        free(table->backingArray);
    
        free(table);
    
        return 0;
    
    }
    
     
  2. --R0B-- macrumors newbie

    Joined:
    Sep 2, 2010
    Location:
    Bury St Edmunds, UK
    #2
    I haven't tried to look too deeply into this but a few things look unfamiliar to me.

    I'm not sure that malloc(0) is valid.

    The use of sizeof () in both cases will return the sizeof the pointer (8 bytes) not the sizeof the malloc()'d buffer.

    int hvpSize = sizeof(pair);
    table->backingArray = realloc(table->backingArray,sizeof(table->backingArray) + hvpSize);
     
  3. moonman239 thread starter macrumors 68000

    Joined:
    Mar 27, 2009
    #3
    Great Scott, you're right. Thank you for pointing that out. C is a rather strange language. I suppose I can appreciate somewhat that, as someone else said, C is more of a building-blocks language, but one would expect to be able to easily get sizeof() to work with anything.
     
  4. cqexbesd macrumors regular

    Joined:
    Jun 4, 2009
    #4
    sizeof works fine. You asked for the sizeof a pointer and it told you...
     
  5. moonman239 thread starter macrumors 68000

    Joined:
    Mar 27, 2009
    #5
    That darn C language...
    But this untested code should work, right?
    For the struct:
    Code:
    sizeof(*pair) //dereferencing the pointer, so sizeof gets the hvp instead of the pointer.
    
    For the array:
    Code:
    int i=0;
    int arraySize = 0;
    while (sizeof(table->backingArray[i]) > 0)
    {
    arraySize += sizeof(table->backingArray[i]);
    i += 1;
    }
    
     
  6. --R0B-- macrumors newbie

    Joined:
    Sep 2, 2010
    Location:
    Bury St Edmunds, UK
    #6
    sizeof() is a computed at compile time not runtime.

    You already know how big your table is in table->length which is the number of elements in your array, the number of bytes would be table->length * sizeof (hvp);
     
  7. --R0B--, Dec 18, 2015
    Last edited: Dec 18, 2015

    --R0B-- macrumors newbie

    Joined:
    Sep 2, 2010
    Location:
    Bury St Edmunds, UK
    #7
    There is possibly another issue here in that for (i=0; ; ) causes array to point at the start of table->backingArray but the test array[i - 1].hash means that you are now pointing to the bytes before the malloc()'d memory which ought to crash.

    It would help if there were some comments to describe what you are expecting each block of code to do then it would make it easier to see if the code does what you want it to.

    Let me know if you want help with this.
     
  8. moonman239 thread starter macrumors 68000

    Joined:
    Mar 27, 2009
    #8
    I've included some commentary in my OP.
     
  9. --R0B--, Dec 18, 2015
    Last edited: Dec 18, 2015

    --R0B-- macrumors newbie

    Joined:
    Sep 2, 2010
    Location:
    Bury St Edmunds, UK
    #9
    Code:
    int insertHVP (htable *table, hvp *pair)
    {
        hvp *array = table->backingArray;
        int hvpIndex = 0;    /* Insertion point - default to first slot. */
    
       /* Find insertion point. */
       for (int i = 0; i < table->length; i ++)
          {
          hvpIndex = i;
    
          /* This would appear to be an error. */
          if (pair->hash == array [i].hash)
             return (1);
          else if (pair->hash < array [i].hash)
             break;
          }
    
       /* If we end up here we need to make room for another entry. */
       table->backingArray = realloc (table->backingArray, (++ table->length) * sizeof (hvp));
       array = table->backingArray;
    
       /* Shuffle everything past insertion point up one. */
       for (int i = table->length - 1; i > hvpIndex; i --)
          array [i] = array [i - 1];
    
       /* Put data into insertion point. */
       array [hvpIndex] = *pair;
    
       return (0);
    }
    
    This might do the trick, not sure what you wanted if the key already exists, you were doing:

    Code:
    return 1 + (array[hvpIndex].value == pair->value);
    
    the == with evaluate to True (or 1), if both sizes are equal so 1 + True will return 2 but your test is for errorCode > 0. If you wanted 2 just change the return in my code.

    Take care with the array[].value's, they will be pointing to the strings from main(), if you end up reading values in from a file the value's may well end up all pointing to the same buffer, you might want to use strdup() to keep a copy.
     
  10. moonman239 thread starter macrumors 68000

    Joined:
    Mar 27, 2009
    #10
    If there's already a value for the given hash, I want to return an error code to let main() know.
     
  11. Toutou macrumors 6502a

    Toutou

    Joined:
    Jan 6, 2015
    Location:
    Prague, Czech Republic
    #11
    If you compiled your original code with
    Code:
    gcc -g main.c
    and then run it with
    Code:
    valgrind --tool=memcheck --leak-check=full --show-leak-kinds=all ./a.out
    you would see this:
    Code:
    ==5429== Memcheck, a memory error detector
    ==5429== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
    ==5429== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
    ==5429== Command: ./a.out
    ==5429==
    ==5429== Invalid read of size 4
    ==5429==    at 0x100000B06: insertHVP (main.c:93)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==  Address 0x100a78670 is 16 bytes before a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==
    ==5429== Conditional jump or move depends on uninitialised value(s)
    ==5429==    at 0x100000B08: insertHVP (main.c:93)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==
    ==5429== Invalid write of size 8
    ==5429==    at 0x100000B8C: insertHVP (main.c:101)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==  Address 0x100a78690 is 0 bytes after a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==
    ==5429== Invalid write of size 8
    ==5429==    at 0x100000B93: insertHVP (main.c:101)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==  Address 0x100a78698 is 8 bytes after a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==
    ==5429== Conditional jump or move depends on uninitialised value(s)
    ==5429==    at 0x100000BBB: insertHVP (main.c:105)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E58: main (main.c:227)
    ==5429==
    ==5429== Invalid read of size 4
    ==5429==    at 0x100000B06: insertHVP (main.c:93)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==  Address 0x100a78710 is 16 bytes before a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==
    ==5429== Invalid write of size 8
    ==5429==    at 0x100000B8C: insertHVP (main.c:101)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==  Address 0x100a78730 is 0 bytes after a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==
    ==5429== Invalid write of size 8
    ==5429==    at 0x100000B93: insertHVP (main.c:101)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==  Address 0x100a78738 is 8 bytes after a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==
    ==5429== Invalid read of size 8
    ==5429==    at 0x100000B89: insertHVP (main.c:101)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==  Address 0x100a78730 is 0 bytes after a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==
    ==5429== Invalid read of size 8
    ==5429==    at 0x100000B8F: insertHVP (main.c:101)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==  Address 0x100a78738 is 8 bytes after a block of size 16 alloc'd
    ==5429==    at 0x100009920: realloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x100000AC9: insertHVP (main.c:87)
    ==5429==    by 0x100000C84: addKeyValuePair (main.c:131)
    ==5429==    by 0x100000E6F: main (main.c:229)
    ==5429==
    1514 Anytown Dr==5429==
    ==5429== HEAP SUMMARY:
    ==5429==     in use at exit: 26,244 bytes in 188 blocks
    ==5429==   total heap usage: 278 allocs, 90 frees, 32,564 bytes allocated
    ==5429==
    ==5429== 2,064 bytes in 1 blocks are possibly lost in loss record 57 of 63
    ==5429==    at 0x10000917C: malloc_zone_malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==5429==    by 0x1004F4EFD: _objc_copyClassNamesForImage (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E8182: protocols() (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E8093: readClass(objc_class*, bool, bool) (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E5C13: gc_init (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004ED24E: objc_initializeClassPair_internal(objc_class*, char const*, objc_class*, objc_class*) (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004FA132: layout_string_create (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E883C: realizeClass(objc_class*) (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E8300: copySwiftV1MangledName(char const*, bool) (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E82E9: copySwiftV1MangledName(char const*, bool) (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E82E9: copySwiftV1MangledName(char const*, bool) (in /usr/lib/libobjc.A.dylib)
    ==5429==    by 0x1004E82E9: copySwiftV1MangledName(char const*, bool) (in /usr/lib/libobjc.A.dylib)
    ==5429==
    ==5429== LEAK SUMMARY:
    ==5429==    definitely lost: 0 bytes in 0 blocks
    ==5429==    indirectly lost: 0 bytes in 0 blocks
    ==5429==      possibly lost: 2,064 bytes in 1 blocks
    ==5429==    still reachable: 0 bytes in 0 blocks
    ==5429==         suppressed: 24,180 bytes in 187 blocks
    ==5429==
    ==5429== For counts of detected and suppressed errors, rerun with: -v
    ==5429== Use --track-origins=yes to see where uninitialised values come from
    ==5429== ERROR SUMMARY: 13 errors from 11 contexts (suppressed: 17 from 17)
    That thing is a mess (which is kinda ok, since you're apparently new to plain C).
     

Share This Page