3
\$\begingroup\$

I wrote a function to reverse an array. The first argument is an iterable object, the second argument is the size of the array element in bytes, and the third argument is the length of the array.

void reverse(void *object, int size, int length) {
    int i;
    int j; 
    int k;

    for(i=0, j=length-1; i < j; i++, j--) {
        for(k=0; k<size; k++){
            *((char*)object+(i * size)+k) = *((char*)object+(i * size)+k) ^ *((char*)object+(j * size)+k);
            *((char*)object+(j * size)+k) = *((char*)object+(i * size)+k) ^ *((char*)object+(j * size)+k);
            *((char*)object+(i * size)+k) = *((char*)object+(j * size)+k) ^ *((char*)object+(i * size)+k);
        }
    }
}

Could this implementation cause errors? How can I improve it?

\$\endgroup\$
5
\$\begingroup\$

Your code works – as far as I can see – correctly. But I would rewrite it a bit to improve the readability (and with it the maintainability) of the code.

The function name reverse() is quite general. That could refer to reversing an array, string, or whatever. A better name might be reverseArray().

The repeated cast (char*)object can be avoided by defining a variable

char *ptr = objects;

once. Next, the address calculations can be simplified by separating the swapping of two objects into a helper function:

void reverseArray(void *objects, int size, int length) {
    char *ptr = objects;
    for (int i = 0, j = length - 1; i < j; i++, j--) {
        swapObjects(ptr + size * i, ptr + size * j, size);
    }
}

Note also how i and j are declared locally to the for-loop.

Using your method, swapObjects() would be:

static inline void swapObjects(char *o1, char *o2, int size) {
    for (int k = 0; k < size; k++) {
        o1[k] = o1[k] ^ o2[k];
        o2[k] = o1[k] ^ o2[k];
        o1[k] = o1[k] ^ o2[k];
    }
}

However, I can see no advantage in this "magically swap two bytes without temporary storage" and would rewrite it as

static inline void swapObjects(char *o1, char *o2, int size) {
    for (int k = 0; k < size; k++) {
        char tmp = o1[k];
        o1[k] = o2[k];
        o2[k] = tmp;
    }
}

which is much simpler (no XOR operations and less memory reads and writes). It is possible to make the swap operation faster by using int or long as temporary storage, but this requires a careful check of the sizes and memory alignments.

Here you can get rid of the subcripts by increasing the passed pointers

static inline void swapObjects(char *o1, char *o2, int size) {
    for (int k = 0; k < size; k++, o1++, o2++) {
        char tmp = *o1;
        *o1 = *o2;
        *o2 = tmp;
    }
}

but that is a matter of taste. I don't think that it makes a difference if you compile the code with optimizations switched on.

In addition, I would use size_t as type for the size and length parameters. size_t is what sizeof returns, and is the correct type to describe the size of an object in memory, see for example the declarations of malloc(), calloc() or strlen().

\$\endgroup\$
2
\$\begingroup\$

I have two concerns with your code:

  • Potential bug related to using XOR for swapping the values – According to Wikipedia's XOR swap algorithm, if the values to swap are the same and use the same storage location you might end up zeroing out the values and not actually swapping them.
  • Handle odd length or zero length arrays – I would possibly add some cases to verify that your size and length are legal values. I'm not sure if it's intentional or not, but you might be saved by your i < j condition avoiding to copying/swapping the center element of an array with an odd number of elements.

Another element not covered is what is typical values of the size and length of the arrays, and this might affect some of the other parameters. This could allow for temporary storage in an another container like an int or a long, or possibly given larger size to rather use memcpy or similar to swap the elements. Using memcpy would also reduce the chances of getting errors related to big or little endian issues, which could arise elsewise.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.