address boundary error while sorting struct with qsort in c

Question

I've got a struct, which I want to sort by the ID and afterwards remove the entries with a NULL ID. But I get an Adress Boundary Error. Not really sure what the problem is.

typedef struct data_id
{
char* id;
int marker;
int key;
} data_id;

My compare function:

int cmp(const void *p1, const void *p2)
{
const data_id *v1 = (data_id *)p1;
const data_id *v2 = (data_id *)p2;
if (v1->id < v2->id)
    return -1;
else if (v1->id > v2->id)
    return +1;
else
    return 0;
}

and I'm calling qsort in the main function with:

qsort(nodeList, num_id, sizeof(nodeList),cmp);

num_id is the number of entries.

But anyway you need to show a minimal reproducible example

I'm reading data from stdin and create the list.

void create_list(input){
nodeList  = realloc(nodeList, sizeof *nodeList * 10000);
if (input == 65) // A
{
    stop_flag = true;
    s_flag = true;
}
else if (input == 73) // I
{
    moves_flag = true;
}
else if (s_flag == true && (islower(input) || isdigit(input)))
{
    start_node = input;
    s_flag = false;
}
else if (moves_flag == true && isdigit(input))
{
    num_moves = (char)input - '0';
    moves_flag = false;
}
else if ((islower(input) || isdigit(input)) && !stop_flag )
{
    if (m_flag == true && isdigit(input))
    {
        nodeList[tmp_id].marker = digitconcat(nodeList[tmp_id].marker,input);
    }
    else if (m_flag == false && (isdigit(input)||islower(input)))
    {
        buffer[0] = (char)input;
        if (buffer_size == 0)
        {
            nodeList[num_id].id = strconcat(1, buffer);
            buffer_size++;
        }
        else
            nodeList[num_id].id = strconcat(2, nodeList[num_id].id, buffer);
        m_flag = false;
    }
}
else if (input == '-' && !stop_flag)
{
    m_flag = true;
}
else if (input == '\n' && !stop_flag)
{
    tmp_id++;
    num_id++;
    buffer_size = 0;
    nodeList[tmp_id].marker = 0;
    nodeList[num_id].key = num_id;
    m_flag = false;
}
else if ((input == ',' || input == ':') && !stop_flag)
{
    buffer_size = 0;
    num_id++;
    nodeList[tmp_id].marker = 0;
    nodeList[num_id].key = num_id;
    m_flag = false;
} 
}

The concatenation function for strings and digits are:

unsigned digitconcat(unsigned x, unsigned y)
{
y = (char)y - '0';
unsigned pow = 10;
while (y >= pow)
    pow *= 10; 
return x * pow + y;
}

char *strconcat(int count, ...)
{
va_list ap;
int i;

// Find required length to store merged string
int len = 1; // room for NULL
va_start(ap, count);
for (i = 0; i < count; i++)
    len += strlen(va_arg(ap, char *));
va_end(ap);

// Allocate memory to concat strings
char *merged = calloc(sizeof(char), len);
int null_pos = 0;

// Actually concatenate strings
va_start(ap, count);
for (i = 0; i < count; i++)
{
    char *s = va_arg(ap, char*);
    strcpy(merged + null_pos, s);
    null_pos += strlen(s);
}
va_end(ap);
return merged;
}

An example Input could be:

aqwe:b66,g
b66:g,l-23452
asfag:l
l:-2424
A:g
I:5

The strings seperated by a :, , or LF are the IDs. After the - follows the marker. The last two rows don't need to be saved in the list.

I also didn't figure out yet why the last entry of my list gets added to it, because I specifically set stop_flag, to stop adding ID, Key or Marker after it reaches the A in the second to last line.

What is nodeList?

The data is supposed to represent a graph. Tho nodes are seperated by a :, , or LF. The weight(marker) is the number after the dash, which belongs to the first node of the line it is in. Furthermore I give every node a specific 'key'. Ohh and every node that is on the same line is connected. So nodeList is the array that stores information about every node in the graph.

But I just thought that maybe an array isn't the best data structure to store the data in, because it's harder to get rid of duplicates.

How can you sort by ID, if some of them are `NULL` ? You also can't compare them with `<` or `>` as you do, because these are pointers. — Eugene Sh., Jun 09 '21 at 14:40
You're sorting on the addresses - not the (presumably) null terminated stirngs that `id` points at. — Ted Lyngmo, Jun 09 '21 at 14:42
@Cina Neither the definition of the function cmp nor the function call qsort(nodeList, num_id, sizeof(nodeList),cmp); makes a sense.:) — Vlad from Moscow, Jun 09 '21 at 14:43
`v1->id < v2->id` -> `strcmp(v1->id, v2->id) < 0` and `v1->id > v2->id` -> `strcmp(v1->id, v2->id) > 0` (read this for more information: https://stackoverflow.com/questions/8004237/how-do-i-properly-compare-strings-in-c). But anyway you need to show a [mcve], your call to `qsort` might be wrong, bit it's hard to tell without more information. — Jabberwocky, Jun 09 '21 at 14:45
@Jabberwocky : I extended my Question with a bit more detail. Maybe that will help. — Cina, Jun 09 '21 at 15:30
@Cina it's better but we need a [MCVE]. This means some work for you, but doing so you might even find the bug yourself. — Jabberwocky, Jun 09 '21 at 16:02
With a proper debugger you should be able to determine where in your code the fault occurs. (But note that the place where the fault occurs is not necessarily where the bug is.) Do read carefully what [mcve] means; it should be something that a person could copy/paste into a file, compile and run, and see the same failure. That means all the necessary includes, auxiliary functions, etc - but reduced to the bare minimum that still reproduces the problem. — Nate Eldredge, Jun 09 '21 at 16:14
What is stored in `nodeList`? At first I thought you stored `data_id`:s and then I suspected you stored `data_id*`s but then I noticed: `realloc(nodeList, sizeof *nodeList * 10000);` in your edited question. So, what is `nodeList` defined as really? — Ted Lyngmo, Jun 10 '21 at 06:24
@Cina I don't see that you've added an answer? I see that you've tried to describe what `nodeList` is. it's much better if you include the actual definition in a [mre]. — Ted Lyngmo, Jun 14 '21 at 06:11

score 0 · Accepted Answer · answered Jun 17 '21 at 18:31

So I ended up not using qsort, instead wrote one myself with some help:

void sort()
{
    data_id tmp;
    for (int i = 0; i < num_id; ++i)
    {
        for (int j = i + 1; j < num_id; ++j)
        {
            // swapping strings if they are not in the lexicographical order
            if (strcmp(nodeList[i].id, nodeList[j].id) > 0)
            {
                tmp = nodeList[i];
                nodeList[i] = nodeList[j];
                nodeList[j] = tmp;
            }
        }
    }
}

And call the function after everthing is read.

address boundary error while sorting struct with qsort in c

1 Answers1