EXC_BAD_ACCESS on pointer in linked list for radix sort

Question

I'm trying to come up with a rudimentary radix sort (I've never actually seen one, so I'm sorry if mine is awful), but I am getting an EXC_BAD_ACCESS error on the line link = *(link.pointer);. My C skills aren't great, so hopefully someone can teach me what I'm doing wrong.

I'm using XCode and ARC is enabled.

Here is the code:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

#define ARRAY_COUNT 10
#define MAX_VALUE   1000000
#define MODULO 10.0f

typedef enum
{
    false,
    true
} bool;

typedef struct linkedListStruct
{
    int value;
    struct linkedListStruct *pointer;
} LinkedList;

void radixSort(int *array);
bool arraySorted(int *array);
int * intArray(int minValue, int maxValue);

int main(int argc, const char * argv[])
{
    int *sortingArray = intArray(0, MAX_VALUE);

    radixSort(sortingArray);

    printf("Array %s sorted", arraySorted(sortingArray) ? "" : "not");

    return 0;
}

void radixSort(int *array)
{
    int numberOfIterations = (int)ceilf(log(MAX_VALUE)/log(MODULO));
    for(int n = 0; n < numberOfIterations; n++)
    {
        LinkedList *linkedListPointers[(int)MODULO] = {0};
        int i = ARRAY_COUNT;
        while(i--)
        {
            int location = (int)floor((array[i] % (int)powf(MODULO, n + 1))/powf(MODULO, n));
            LinkedList link = { array[i], NULL };
            link.pointer = linkedListPointers[location];
            linkedListPointers[location] = &link;
        }
        int location = 0;
        for(int pointerSelection = 0; pointerSelection < MODULO; pointerSelection++)
        {
            if(linkedListPointers[pointerSelection])
            {
                LinkedList link = { 0, linkedListPointers[pointerSelection] };
                linkedListPointers[pointerSelection] = NULL;
                while(link.pointer)
                {
                    link = *(link.pointer);
                    array[location++] = link.value;
                }
            }
        }
    }
}

bool arraySorted(int *array)
{
    int i = ARRAY_COUNT;
    while(--i)if(array[i - 1] > array[i])break;
    return !i;
}

int * intArray(int minValue, int maxValue)
{
    int difference = maxValue - minValue;
    int *array = (int *)malloc(sizeof(int) * ARRAY_COUNT);
    int i;
    for(i = 0; i < ARRAY_COUNT; i++)
    {
        array[i] = rand()%difference + minValue;
    }
    return array;
}

Also, if someone wants to suggest improvements to my sort, that would also be appreciated.

umm why do you have an enum with bool, bool is already a defined type and part of the language just like int, short etc. — AndersK, Aug 01 '13 at 20:52
@claptrap I didn't always compile with `C99`, so it's more of a habit than anything. And even now I'm using GNU99. — RileyE, Aug 01 '13 at 20:53
Regarding @claptrap's comment, you can `#include ` to get the `bool` type (I believe it is a typedef of `_Bool`). — jxh, Aug 01 '13 at 20:59
@jxh I thought that was `C99` exclusive as per [this answer](http://stackoverflow.com/a/1921557/1292230). — RileyE, Aug 01 '13 at 20:59
@RileyE: I think GNU99 is supposed to be a superset of C99. But, if it doesn't work for you, *c'est la vie*. — jxh, Aug 01 '13 at 21:02

RileyE · Answer 1 · 2013-08-02T14:33:14.020

0

The problem came from how I was allocating the linked list. I changed

LinkedList link = { array[i], NULL };
link.pointer = linkedListPointers[location];

to

LinkedList *link = malloc(sizeof(LinkedList));
link->value = array[i];
link->pointer = linkedListPointers[location];

In the first example, the pointer to link remained the same through each loop iteration (I wasn't aware it would do that), so I needed to make the pointer point to a newly allocated memory chunk.

EDIT:

Changing that also had me change from

while(link.pointer)
{
    link = *(link.pointer);
    array[location++] = link.value;
}

to

while(linkPointer)
{
    link = *linkPointer;
    array[location++] = link.value;
    linkPointer = link.pointer;
}

edited Aug 02 '13 at 14:33

answered Aug 01 '13 at 21:51

RileyE

10,874
13
63
106

need initialize `LinkedList *linkedListPointers[(int)MODULO]={0};` – BLUEPIXY Aug 02 '13 at 10:26
@BLUEPIXY Good catch. I had that in my code but I forgot to mention that I changed that as well. Thank you! – RileyE Aug 02 '13 at 14:22

EXC_BAD_ACCESS on pointer in linked list for radix sort

1 Answers1