Thread: A General Shuffle Array Function

I wrote a general array shuffle function which has a signature:

Code:

void shuffle(void * ptr, unsigned int elem_size, size_t size)

and I want to know if its proper to cast the void * ptr to a character pointer inside the shuffle function when I shuffle the elements?

Here's a complete example of the shuffle function with two different arrays.

Code:

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

#define ARR_SIZE 10

void set_seed() {
  srand(time(NULL));
}

void shuffle(void * ptr, unsigned int elem_size, size_t size) {
  static bool set_seed_called = false;
  size_t counter = size - 1;
  char temp[elem_size];

  if (!set_seed_called) {
    set_seed();
    set_seed_called = true;
  }

  for (int i = 0; i < size; ++i) {
    int pos = rand() % (counter + 1);
    memcpy(temp, ((char*)ptr) + (elem_size * counter), elem_size);
    memcpy(((char*)ptr) + (elem_size * counter), ((char*)ptr) + (elem_size * pos), elem_size);
    memcpy(((char*)ptr) + (elem_size * pos), temp, elem_size);
    --counter;
  }
}

int main(int argc, char ** argv) {
  int i_arr[ARR_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  for (int i = 0; i < ARR_SIZE; ++i) {
    fprintf(stdout, "%d, ", i_arr[i]);
  }
  fputs("\n", stdout);
  
  shuffle(i_arr, sizeof(*i_arr), ARR_SIZE);
  
  for (int i = 0; i < ARR_SIZE; ++i) {
    fprintf(stdout, "%d, ", i_arr[i]);
  }
  fputs("\n", stdout);
  
  char* s_arr[ARR_SIZE] = {
    "aaaaa",
    "bbbbb",
    "ccccc",
    "ddddd",
    "eeeee",
    "fffff",
    "ggggg",
    "hhhhh",
    "iiiii",
    "jjjjj"
  };
  
  for (int i = 0; i < ARR_SIZE; ++i) {
    fprintf(stdout, "%s, ", s_arr[i]);
  }
  fputs("\n", stdout);
  
  shuffle(s_arr, sizeof(*s_arr), ARR_SIZE);
  
  for (int i = 0; i < ARR_SIZE; ++i) {
    fprintf(stdout, "%s, ", s_arr[i]);
  }
  fputs("\n", stdout);
 
  return 0;
}

Note: The shuffle functions works but I'd like to know if the casting is proper.

TBH, I'd use a few more locals to clean up the code.

Code:

void shuffle(void * ptr, unsigned int elem_size, size_t size) {
  char *cptr = ptr;
  static bool set_seed_called = false;
  size_t counter = size - 1;
  char temp[elem_size];
 
  if (!set_seed_called) {
    set_seed();
    set_seed_called = true;
  }
 
  for (int i = 0; i < size; ++i) {
    int pos = rand() % (counter + 1);
    char *from = cptr + (elem_size * counter);
    char *to = cptr + (elem_size * pos);
    memcpy(temp, from, elem_size);
    memcpy(from, to, elem_size);
    memcpy(to, temp, elem_size);
    --counter;
  }
}

> This means void * arithmetic is the same as char * (what is a UB is derreference a void *).
No it doesn't.

Just because the bits are the same in memory doesn't imply the rest of your statement.

Code:

#include <stdio.h>

int main()
{
    void *p = 0;
    char *q = p + 4;
    printf("%p %p\n", p, q );
}


$ gcc -Wall -Wextra -pedantic foo.c
foo.c: In function ‘main’:
foo.c:6:17: warning: pointer of type ‘void *’ used in arithmetic [-Wpointer-arith]
    6 |     char *q = p + 4;
      |                 ^

gcc lazily assumes sizeof(void*) is 1 when doing pointer arithmetic, but it's not standard.
Pointer Arith (Using the GNU Compiler Collection (GCC))

Originally Posted by Salem

> This means void * arithmetic is the same as char * (what is a UB is derreference a void *).
No it doesn't.

Yes it does, acoordingly to ISO 9899:

Code:

#include <stdio.h>

int main( void )
{
  char *p = 0;
  void *q = p + 4;

  printf( "%p %p\n", p, q );
}

Code:

$ cc -Wall -Wextra test.c -o test
$ ./test
0x0 0x04

No warnings...

ISO 9899:1999+ 6.2.5 § 26: "A pointer to void shall have the same representation and alignment requirements as a pointer to a character type..."

Code:

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

extern void set_seed ( void );

// Assuming ptr points to an array with less then or equal to UINT_MAX elements...
// Requires size > 0 and elem_size > 0.
// Simplier variant of Fisher-Yates routine (don't case about the previous swap).
void shuffle ( void *ptr, unsigned int elem_size, unsigned int size )
{
  static _Bool set_seed_called = 0;
  unsigned int counter = size;
  char temp[elem_size];

  if ( ! set_seed_called )
  {
    set_seed();
    set_seed_called = 1;
  }

  while ( size-- )
  {
    void *p, *q;

    // rand() will return 31 bits value (int). this way
    // pos will be in [0,counter) range.
    unsigned int pos = counter * ( rand() / ( RAND_MAX + 1.0 ) );

    // No problems here! ISO 9899 6.2.5 § 26!
    p = ptr + elem_size * --counter;
    q = ptr + elem_size * pos;

    // swap.
    memcpy ( temp, p, elem_size );
    memcpy ( p, q, elem_size );
    memcpy ( q, temp, elem_size );
  }
}

The representation has nothing to do with the operations you're allowed to do on it.

> ISO 9899:1999+ 6.2.5 § 26: "A pointer to void shall have the same representation and alignment requirements as a pointer to a character type..."
Posting it again in bold doesn't make you right.

Keep reading...
Also in section 6.2.5

18 The void type comprises an empty set of values; it is an incomplete type that cannot be completed.

Then read about sizeof

6.5.3.4 The sizeof operator
Constraints

The sizeof operator shall not be applied to an expression that has function type or an
incomplete type, to the parenthesized name of such a type, or to an expression that
designates a bit-field member.

When you do p+n for some pointer p (of type T), and some integer n, you're calculating the address of the n'th object, not the n'th byte.
In order to do this, the operation is p + n*sizeof(*p) to move the pointer by the required number of bytes to get to the n'th object.
But void is an incomplete type, you can't do a sizeof on it.

> No warnings...
You forgot to add pedantic.

Also, your code isn't the same as mine.

Code:

  char *p = 0;
  void *q = p + 4;

You do the math on a char*, then assign the result to void*.
Doing the math on the char* is perfectly defined.

Try doing the math on the void* itself, with -pedantic.

@venkatfor, I moved your post to it's own thread.
Array shuffle