Thread: A General Shuffle Array Function

  1. #1
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    102

    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.
    Last edited by G4143; 12-05-2022 at 06:37 AM.

  2. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    1,069
    Why do you need to cast void * to char * there?

    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..."

    This means void * arithmetic is the same as char * (what is a UB is try to 'derreference' a void *).

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,570
    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;
      }
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,570
    > 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))
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    102
    Quote Originally Posted by Salem View Post
    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;
      }
    }
    Yeah that really cleans up the casting clutter.

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    1,069
    Quote Originally Posted by Salem View Post
    > 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..."
    Last edited by flp1969; 12-05-2022 at 08:12 AM.

  7. #7
    Registered User
    Join Date
    Feb 2019
    Posts
    1,069
    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 );
      }
    }
    Last edited by flp1969; 12-05-2022 at 08:46 AM.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,570
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,570
    @venkatfor, I moved your post to it's own thread.
    Array shuffle
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shuffle rows in an array
    By Justin Time in forum C Programming
    Replies: 2
    Last Post: 04-23-2015, 07:39 PM
  2. What wrong with this shuffle function?
    By defjamvan in forum C Programming
    Replies: 6
    Last Post: 09-09-2013, 07:33 AM
  3. String Array Shuffle
    By omGeeK in forum C Programming
    Replies: 3
    Last Post: 02-14-2011, 07:48 PM
  4. shuffle 2-dimensional array
    By patkhor in forum C Programming
    Replies: 5
    Last Post: 11-26-2008, 03:51 PM
  5. Array Shuffle
    By ypramesh in forum C Programming
    Replies: 2
    Last Post: 04-08-2006, 11:01 AM

Tags for this Thread