Array access via double pointer, losing its body, pure C

Question

When I'm trying to sort array content, which I have referenced via double-pointer.

line 77

SortQuick(&(*data_resource)->data,
   &(*data_resource)->low,
   &(*data_resource)->length - 1);

The content hasn't been sorted, via the same method I'm printing values of this array very fine with the function ArrayPrint()

This code compiles well on MS C++ compiler, about GCC don't know. There are not any warning in the code or errors, MS compiler doesn't show it by standard configuration.

@LuchianGrigore yes, it Sorting function , it shows movement of values by QuickSort rules, but when Sorting function ends its work, the data which has been returned is the same as before sorting. — , Sep 11 '12 at 10:36
Fwiw, this compiles on GCC 4.6.1 (`-W -Wall -std=c99`) without warnings as well. And the array is not sorted too. — undur_gongor, Sep 11 '12 at 11:25

score 3 · Answer 1 · answered Sep 11 '12 at 10:50

It's not sorting because &(*data_resource)->length - 1 evaluates to &(*data_resource)->low.

&(*data_resource)->length is a pointer to an int. When you subtract 1 from it, it points to the int just before and that happens to be &(*data_resource)->low because you defined the structure members in precisely this order:

typedef struct Resource
{
        int low;
        int length;
        int *data;
} Resource;

So, your sorting code gets 2 identical indices to work with and rightly does not sort anything as there's nothing to sort in a subarray consisting of just one element.

Here's a slightly modified version that works:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Resource
{
        int low;
        int length;
        int *data;
} Resource;

void Swap(int *first, int *second)
{
        int tmp = *first;
        *first = *second;
        *second = tmp;
}

void SortQuick(int **data, int *low, int *high)
{
        int i = *low,
                j = *high,
                x = (*data)[(*low + *high) / 2];

        do
        {
                while((*data)[i] < x) i++;
                while((*data)[j] > x) j--;

                if(i <= j)
                {
                        Swap(&(*data)[i], &(*data)[j]);
                        i++;
                        j--;
                }

        } while(i <= j);

        if(i < *high) SortQuick(data, &i, high);
        if(*low < j) SortQuick(data, low, &j);
}

void ArrayPrint(int **data, int *array_length)
{
        for(int i = 0; i < *array_length; i++)
        {
                printf("[%i]: %20i\r\n", i, (*data)[i]);
        }
}

void ArrayInit(int **data, int *array_length)
{
        (*data) = (int*)malloc(sizeof(int) * *array_length);

        for(int i = 0; i < *array_length; i++)
        {
                (*data)[i] = rand();
        }
}

int GlobalInit(Resource **data_resource)
{
        srand((unsigned int)rand());

        *data_resource = (Resource*)malloc(sizeof(Resource));
        (*data_resource)->low = 0;
        (*data_resource)->length = 10;//rand();

        ArrayInit(&(*data_resource)->data, &(*data_resource)->length);

        return (*data_resource)->length;
}

void BenchmarkTest(Resource **data_resource)
{
        ArrayPrint(&(*data_resource)->data, &(*data_resource)->length);
        (*data_resource)->length--;
        SortQuick(&(*data_resource)->data, &(*data_resource)->low, &(*data_resource)->length);
        (*data_resource)->length++;
        ArrayPrint(&(*data_resource)->data, &(*data_resource)->length);
}

int main(void)
{
        Resource *data_resource = NULL;

        GlobalInit(&data_resource);
        BenchmarkTest(&data_resource);

        return 0;
}

Output (ideone):

[0]:           1362961854
[1]:              8891098
[2]:            392263175
[3]:            158428306
[4]:           2074436122
[5]:             47170999
[6]:            431826012
[7]:           1599373168
[8]:           1769073836
[9]:           1043058022
[0]:              8891098
[1]:             47170999
[2]:            158428306
[3]:            392263175
[4]:            431826012
[5]:           1043058022
[6]:           1362961854
[7]:           1599373168
[8]:           1769073836
[9]:           2074436122

I'm amazed at how you have managed to deal with so many indirections and run only in this one issue! Anyway, I strongly suggest removing unnecessary indirections. The code will be easier and more efficient. — Alexey Frunze, Sep 11 '12 at 10:52

score 1 · Answer 2 · answered Sep 11 '12 at 10:51

1

All of those references and dereferences of pointers are driving you mad, and in most cases they aren't necessary, try this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Resource
{
    int low;
    int length;
    int *data;
} Resource;

void Swap(int *first, int *second)
{
    int tmp = *first;
    *first = *second;
    *second = tmp;
}

void SortQuick(int *data, int low, int high)
{
    int i = low,
        j = high,
        x = data[(low + high) / 2];

    do
    {
        while(data[i] < x) i++;
        while(data[j] > x) j--;

        if(i <= j)
        {
            Swap(&(data[i]), &(data[j]));
            i++;
            j--;
        }

    } while(i <= j);

    if(i < high) SortQuick(data, i, high);
    if(low < j) SortQuick(data, low, j);
}

void ArrayPrint(int *data, int array_length)
{
    for(int i = 0; i < array_length; i++)
    {
        printf("[%i]: %i\r\n", i, data[i]);
    }
}

void ArrayInit(Resource *data_resource)
{
    data_resource->data = (int*)malloc(sizeof(int) * data_resource->length);

    for(int i = 0; i < data_resource->length; i++)
    {
        data_resource->data[i] = rand();
    }
}

Resource* GlobalInit()
{
    Resource *data_resource;
    srand((unsigned int)rand());

    data_resource = (Resource*)malloc(sizeof(Resource));
    data_resource->low = 0;
    data_resource->length = rand();

    ArrayInit(data_resource);

    return data_resource;
}

void BenchmarkTest(Resource *data_resource)
{
    ArrayPrint(data_resource->data, data_resource->length);
    SortQuick(data_resource->data, data_resource->low, data_resource->length - 1);
    ArrayPrint(data_resource->data, data_resource->length);
}

int main(void)
{
    Resource *data_resource = NULL;

    data_resource = GlobalInit();
    BenchmarkTest(data_resource);

    return 0;
}

answered Sep 11 '12 at 10:51

Chris Desjardins

2,631
1
23
25

of course I know it and the first version was the same, but if you are working with small and weak microcontroller? I used such way only because of optmization for memory issuses. – Sep 11 '12 at 11:05
OK, but this is still passing pointers everywhere, so the memory usage shouldn't be bad. – Chris Desjardins Sep 11 '12 at 11:16
int low, int high - making new copies if int value in body of the function then work with it and after } removes from memory the copy, no? – Sep 11 '12 at 11:27
2

In that case you either have to pass in the address of low and high, or the value, the difference in memory consumption is 0 bytes on most architectures where sizeof(int) == sizeof(int*), let me know what the sizeof(int) and sizeof(int*) is on your platform. – Chris Desjardins Sep 11 '12 at 11:31
It seems as if the real issue might be that you are recursing too deep and blowing your stack. So you are playing a bunch of games to reduce the amount of stack you use. Unfortunately all you have actually done is made the code more complex with out any reduction in stack consumption. Things to consider to reduce stack: 1: Use fewer arguments on recursive functions 2: Make sure arguments are reference types or primitives (Done) 3: Don't use recursion The third option will save the most stack, but sadly this algorithm does not lend itself to iterative approaches, other sorts may be better. – Chris Desjardins Sep 11 '12 at 15:41
but if to use tail-recursion for this algo? – Sep 11 '12 at 17:31
Well recursion is recursion when it comes to stack consumption. Every recursive call uses more stack. The alternative to recursion is of course iteration which does not use stack with every iteration. Here is a list of implementations of the QuickSort: http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#C Most of which are recursive, but some are iterative and there is even one C example that uses fewer recursive calls than the standard quick sort. Maybe you could look at one of the iterative approaches or the mixed recursive/iterative approach. – Chris Desjardins Sep 11 '12 at 17:41
Tail-recursion isn't the standart recursion as I remember and frees from additional computations ( which builds something like binary tree of repeated caclulations ), for example, the classic sample of factorial-counting ( tail recursion ): int fac_times (int n, int acc) { if (n == 0) return acc; else return fac_times(n - 1, acc * n); } int factorial (int n) { return fac_times (n, 1); } – Sep 11 '12 at 18:51
http://stackoverflow.com/questions/33923/what-is-tail-recursion It still eats stack with every recursive call. – Chris Desjardins Sep 11 '12 at 19:17

score 0 · Answer 3 · answered Sep 11 '12 at 10:55

0

This part doesn't make sense:

&(*data_resource)->length - 1);

You are taking the address of the length field and substracting 1. Removing the - 1 seems to make it work.

Besides, you are overusing pointers. E.g. ArrayPrint could simply be

void ArrayPrint(int *data, int array_length)
{
        for(int i = 0; i < array_length; i++)
        {
                printf("[%i]: %i\r\n", i, data[i]);
        }
}

answered Sep 11 '12 at 10:55

undur_gongor

15,657
5
63
75

why does it not make sence? I'm deferencing poitner with (*) then sending with unary & via double-pointer to function. And where does the sence not existing? You could send via pointer, double-pointer - it's access/transfer rule only, for example if you are working with microcontrollers - you need to work very optimized. "Besides, you are overusing pointers. E.g. ArrayPrint could simply be" - and could be in other way, and what? I used for optimizations only such way ( mine ) – Sep 11 '12 at 11:03
The "- 1" is obviously wrong. From C standard point of view and from your algorithm's function point of view. You are creating a pointer pointing to somewhere illegal (maybe the `low` field). Regarding all those pointers, I really doubt they help performancewise. Handing over a pointer to a function will hardly be more efficient than handing over an `int`. The same for pointer to pointer vs. just pointer. But o.k., I don't know your platform. – undur_gongor Sep 11 '12 at 11:08
Did you do measurements? It's hard to believe that `x(int)` is slower than `x(int*)`. – undur_gongor Sep 11 '12 at 11:20
Doesn't x(int) making new copy of int, then manipulate it in function body and then deletes its? with the pointer - you are managing the already allocated memory with not creating new copies, am I right or not? – Sep 11 '12 at 11:25
That copy is typically in a register. And with the pointer you are creating a copy of the pointer/address (in a register too) which is normally not less expensive than an int. It is a different story when you are dealing with big structs (and not with simple data types). – undur_gongor Sep 11 '12 at 11:27

Array access via double pointer, losing its body, pure C

3 Answers3