Title: Code Critique Competition 90

Author: Martin Moene

Date: 02 November 2014 21:04:36 +00:00 or Sun, 02 November 2014 21:04:36 +00:00

Summary: Set and collated by Roger Orr. A book prize is awarded for the best entry.

Body: 

Participation in this competition is open to all members, whether novice or expert. Readers are also encouraged to comment on published entries, and to supply their own possible code samples for the competition (in any common programming language) to scc@accu.org.

Note: we are investigating putting code critique articles online: if you would rather not have your critique visible please inform me. (We will remove email addresses!)

Last issue’s code

I'm trying to write a simple program to shuffle a deck of cards, but it crashes. What have I done wrong?

The code is in Listing 1.

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

enum
{
  black,
  red
};

enum
{
  Hearts,
  Diamonds
};

enum
{
  Clubs,
  Spades
};

typedef struct Card
{
  int color;
  int suit;
  int value;
} Card;

typedef Card Deck[52];

void LoadDeck(Deck * myDeck)
{
  int i = 0;
  for(; i < 51; i++)
  {
    myDeck[i]->color = i % 2;
    myDeck[i]->suit = i % 4;
    myDeck[i]->value = i % 13;
  }
}
// -- example11.cpp –- (C++11 example)
#include <cassert>
#include "wrapped_vector.hxx"

int main()
{
  wrapped_vector<int> iVec;
  iVec.push_back(1);
  iVec.push_back(0);
  iVec.push_back(2);

  int total(0);
  for (auto & p : iVec)
  {
     total += p;
  }
  assert(total == 3);

  wrapped_vector<int>::dump();
}

void PrintDeck(Deck * myDeck)
{
  int i = 0;
  for(;i < 52; i++)
  {
    char *colors[] = {"black", "red"};
    char *suits[][2] =
       {{"clubs", "spades"},
        {"hearts", "diamonds"}};    
    printf("Card %s %d of %s\n",
      colors[myDeck[i]->color],
      myDeck[i]->value,
      suits[myDeck[i]->color]
           [myDeck[i]->suit]);
  }
}

void Shuffle(Deck * myDeck)
{
  int i = 0;
  for (; i < 52; i++)
  {
    int n = sizeof(Card);
    int to = rand() % 52;
    Card tmp;
    memcpy(&tmp, myDeck[i], n);
    memcpy(myDeck[i], myDeck[to], n);
    memcpy(myDeck[to], &tmp, n);
  }
}
// -- example11.cpp –- (C++11 example)
#include <cassert>
#include "wrapped_vector.hxx"

int main()
{
  wrapped_vector<int> iVec;
  iVec.push_back(1);
  iVec.push_back(0);
  iVec.push_back(2);

  int total(0);
  for (auto & p : iVec)
  {
     total += p;
  }
  assert(total == 3);

  wrapped_vector<int>::dump();
}

void PrintDeck(Deck * myDeck)
{
  int i = 0;
  for(;i < 52; i++)
  {
    char *colors[] = {"black", "red"};
    char *suits[][2] =
       {{"clubs", "spades"},
        {"hearts", "diamonds"}};    
    printf("Card %s %d of %s\n",
      colors[myDeck[i]->color],
      myDeck[i]->value,
      suits[myDeck[i]->color]
           [myDeck[i]->suit]);
  }
}

void Shuffle(Deck * myDeck)
{
  int i = 0;
  for (; i < 52; i++)
  {
    int n = sizeof(Card);
    int to = rand() % 52;
    Card tmp;
    memcpy(&tmp, myDeck[i], n);
    memcpy(myDeck[i], myDeck[to], n);
    memcpy(myDeck[to], &tmp, n);
  }
}
			

Critiques

Paul Floyd

Well, there’s quite a lot not to like in this example. On first reading, I didn’t like the enums. There is redundancy – why two enums for the suits and why a separate enum for the colour? The colour of a suit is something that is ‘well known’. Also I didn’t like the inconsistent capitalization. In any case these enums aren’t used. I would remove the color field of Card, and infer the colour from the suit (see below for the corresponding change to PrintDeck).

The main issue is that there is confusion as to what a Card and what a Deck is. Specifically the LoadDeck, PrintDeck and ShuffleDeck take pointer to Deck arguments and treat them as arrays. They should be treated as pointers to arrays of Cards, not pointers to arrays of Decks. Simply removing the asterisks in these prototypes (and changing -> pointer dereferences to . member accesses) will fix this extra level of indirection.

Next, LoadDeck. This only iterates over 51 cards. I would recommend using a constant like CARDS_IN_DECK = 52. I don’t like the single loop, which works because 4 and 13 are relatively prime. If this code were used for a game like ‘belote’, which uses 32 cards, then LoadDeck would no longer work correctly. Two loops for suit and value would be a little more verbose but much clearer.

PrintDeck just prints values from 0 to 12. Again much clearer would be names and values offset by 1, e.g., using

  char *values[] = {"ace", "2", "3", "4", "5",
  "6", "7", "8", "9", "10",
  "jack", "queen", "king"};

The attempt to read the suit from the suits 2D array is wrong. This is a 2x2 array, but the ranges of the subscripts are 0..1 and 0..3. I would make suits a 1D array and index it with the 0..3 suit field. Also I would infer the colour from the suit, either directly in the code or by writing a little function.

I can only see one fault in Shuffle. There is no test to see if i equals to, in which case the second memcpy is undefined. This could be corrected by using memmove or adding a little check like

  if (i == to)
  {
    continue;
  }

One last point. It bothers me using common names like red and black. To avoid conflicts, I’d use some prefix like FooRed and FooBlack.

Silas S.Brown

I’m writing this reply on a Psion Revo PDA (made in 1999) while visiting my parents in rural West Dorset (with no Internet connection and not even a phone signal), and as I don’t have a proper keyboard I’ll be brief. (The reason why I say this at all is it might inspire other members, somehow or other. I do wish someone would come up with a decent modern version of the Revo though.)

Bug 1: there’s an inconsistency between LoadDeck, which says i<51 in the for loop, and PrintDeck, which says i<52. Maybe the writer was thinking <= instead of < when writing LoadDeck? Anyway it’s better to keep it consistent and write <52 in both cases (I wouldn’t advocate using a constant here, because anyone who knows about decks of cards in Western culture will be familiar with the number 52, but that’s an opinion that others are entitled to disagree with).

Bug 2: suit is set to i % 4 but there are only 2 suits of each colour. (Personally I’d have dropped colour and just listed the 4 suits, perhaps with a getColour function that effectively tests bit 2, but I won’t argue if you want to represent colour explicitly.)

Bug 3: the modulus operations in LoadDeck will not do what I think you meant. For example, all cards with odd value will also have colour set to red, whereas all cards with even value will also have colour set to black. Rather than trying to correct this using more complex assignments, I’d suggest simply writing three nested loops thus:

  int pointer=0, color=0, suit=0, value=0;
  for (; color < 2; color++) {
    for (; suit < 2; suit++) {
      for (; value < 13; value++) {
        myDeck[pointer]->color=color;
        myDeck[pointer]->suit=suit;
        myDeck[pointer]->value=value;
        pointer++;
      }
    }
  }
  assert(pointer==52);

Note the final assert as a sanity check. (You could also add items like MaxSuits and MaxValues to the ends of each enum, but it’s probably not worth doing so in this small example.) Registers are cheap these days, so it’s really no big deal to write multiple loops in this way, and it’s more readable than the corrected version of the one-loop approach which I won’t confuse you with.

The Shuffle function is OK (there are arguments about better approaches but let’s not worry about that for now); you might want to think about seeding the random number generator (if I had a copy of the standard with me right now, I’d look up whether or not it’s done for you by default).

James Holland

Having had a quick look at the code and given the fact that it crashes, I get the impression that the problem is all to do with pointers and structures. In fact it is reminiscent of some of the items in Alan Feuer’s The C Puzzle Book. I now wish I had paid more attention to what Alan was saying. Despite this, and not being an expert on C, I thought I would make an attempt to discover the defects in the code and get the program running.

The first thing to notice is that the three anonymous enumerated types at the start of the listing are not referenced in the code, so I shall ignore them for the time being. I now observe the main structure that represents the deck of cards. It is an array of 52 cards. Each card being a structure containing three integers representing the card colour, its suit and value respectively. The fact that the colour of the card as well as its suit is being stored is a bit of a worry. It is always possible to deduce the colour of the card from its suit. Clubs and spades are always black and hearts and diamonds are always red. Maintaining a variable to keep track of the card’s colour is redundant and runs the risk of becoming out of kilter with the colour of the suit. It is best removed.

The next thing to note is that the LoadDeck function initialises all but the last card in the deck. The loop variable should loop from 0 until it is not less than 52, not 51 as shown in the original listing.

The main problem lies in the way the loop variable, i, accesses the Deck array. The code incorrectly manipulates the myDeck pointer as if it were an array of pointers to a Deck. In fact, it is simply a single pointer to the Deck. To correctly access the suit, for example, of the card with index i, the following construction should be used.

  (*myDeck)[i].suit

This first dereferences the myDeck pointer to obtain the first card in the deck. The card with index i is then obtained by means of the [] operator. Finally, the suit of the card is obtained. With the variable to store the card colour removed, the LoadDeck function becomes as shown below.

  void LoadDeck(Deck * myDeck)
  {
    int i = 0;
    for (; i < 52; i++)
    {
      (*myDeck)[i].suit = i % 4;
      (*myDeck)[i].value = i % 13;
    }
  }

We now come to the PrintDeck function. Again, the incorrect method of referencing the cards in the deck has been used here and can be corrected in the same way as for the LoadDeck function. Also, now that the variable to store the suit colour has been removed, the way the suit colour is obtained has to be amended. Specifically, the suits array within PrintDeck has been simplified to become a one-dimensional array of suit names. The colour of the suit can now be obtained by taking the suit index of the card and determining if it is odd or even. If the suit index is odd, the suit colour is red. If the suit index is even, the suit colour is black. This is calculated by taking the suit index, dividing by 2 and using the remainder as in index into the colours array. This is achieved using the % operator. The revised PrintDeck function is shown below.

  void PrintDeck(Deck *myDeck)
  {
    int i = 0;
    for (; i < 52; i++)
    {
      const char *colours[] = {"black", "red"};
      const char *suits[] = {"clubs", "hearts",
        "spades", "diamonds"};
      printf("Card %s %d of %s\n",
             colours[(*myDeck)[i].suit % 2],
             (*myDeck)[i].value,
             suits[(*myDeck)[i].suit]);
    }
  }

The shuffle function, like the previous two, incorrectly references the cards in the deck and can be corrected in a similar way.

  void Shuffle(Deck * myDeck)
  {
    int i = 0;
    for (; i < 52; i++)
    {
      int n = sizeof (Card);
      int to = rand() % 52;
      Card temp;
      memcpy(&temp, &(*myDeck)[i], n);
      memcpy(&(*myDeck)[i], &(*myDeck)[to], n);
      memcpy(&(*myDeck)[to], &temp, n);
    }
  }

The program should now work as expected. Incidentally, there is no point in initialising the Deck array with all zeroes as is done in the second statement of main(). The Deck is correctly initialised by the (revised) LoadDeck function.

Marcel Marré

The code has several problems. The one actually leading to the crash is two different interpretations of the Card member suit. In LoadDeck, suit is initialised for each card with a value from 0 to 3. In PrintDeck, however, the strings for the suits are arranged in a two-dimensional array of two colours by two suits per colour. When these strings are used in the printf statement, the Card’s suit ranges from 0 to 3, and we read beyond the valid range of the array. We thus get an undefined char* for printf to output, which is liable to crash.

Let us fix LoadDeck. Apart from the inconsistent initialisation of suit, the function also initialises only a total of 51 cards. This does not lead to a crash, because the whole deck has been memset with 0s. This does mean, however, that one card is missing from the deck, and one card (value, suit and color all 0) is in the deck twice.

A more readable, logical version of LoadDeck would therefore be:

  void LoadDeck(Deck * myDeck)
  {
    int i = 0;
    for(; i < 52; i++)
    {
      myDeck[i]->color = i % 2;
      myDeck[i]->suit = (i / 2) % 2;
      myDeck[i]->value = i % 13;
    }
  }

The initialised deck is somewhat oddly sorted, so another change would be to initialise value thus:

    myDeck[i]->value = (i / 4) % 13; 

which is easier to follow.

Another point is that the enums were not actually used at all. Using them to initialise a card is possible, although the following card:

  Card myCard;
  myCard.color = black;
  myCard.suit = Hearts;
  myCard.value = 5;

will be displayed as "Card black 5 of Clubs".

Commentary

The code demonstrates confusion with pointers and arrays, not helped by the way that in C arrays will implicitly ‘decay’ to pointers to the first element in the array. (There are other problems, but I think those were more straightforward to understand and resolve.)

The code creates a single Deck object called myDeck and passes its address to LoadDeck. Inside LoadDeck this pointer treated as an array (myDeck[i]) of Deck objects. Unfortunately we’ve only passed in a single Deck and not an array of them, so every iteration round the loop after the first one accesses data beyond the end of myDeck and hence the crash.

Following the array subscript we have a pointer – what is this actually doing? Perhaps a simpler example will help:

  struct data { int field; } items[10];
  items->field;

The second line uses items which is of type ‘array of 10 struct data’ but this type decays to a pointer to the first item when used in this context. The second line is equivalent to:

  items[0].field

So returning to LoadDeck the first assignment to myDeck could be written as:

  myDeck[i][0].color = i % 2;

The pair of subscripts makes it a little more obvious what’s gone wrong, as a Deck is a simple array of one dimension.

It can be helpful, even when the data type is an array, to wrap it inside a struct for clarity.

  typedef struct Deck
  {
    Card card[52];
  } Deck;

With this restructuring the ‘broken’ LoadDeck function no longer compiles as the struct, unlike an array, is no longer interchangeable with a pointer type; it can now be fixed by changing it to, for example:

  void LoadDeck(Deck * myDeck)
  {
    int i = 0;
    for(; i < 52; i++)
    {
      myDeck->card[i].color = i % 2;
      myDeck->card[i].suit = i % 4;
      myDeck->card[i].value = i % 13;
    }
  }

While more verbose, it may be more understandable.

The winner of CC89

This critique contained several different problems as well as the ‘it crashes’ problem originally reported. The entrants did a pretty good job of identifying these problems. Paul pointed out that the code relies on 13 and 4 being mutually co-prime and Silas noted that populating suit and color separately was error-prone and the code as shown assigned the wrong color to some of the suits. James actually changed the code to remove the problematic field color. I thought Marcel’s explanation of why the 2-dimensional suits array was wrong was the clearest.

Silas also pointed out that it would be a good idea to seed the random number generator as otherwise the likelihood is that every run of the program will shuffle the deck exactly the same way!

Overall it was a hard call but I eventually decided to award Silas the prize for this code critique

Code Critique 90

(Submissions to scc@accu.org by December 1st)

I’m trying to instrument some code to find out how many iterator operations are done by some algorithms I use that operate on vectors. I’ve got some code that worked with C++03 and I’m trying to get it working with the new C++11 features. Mostly the C++11 code is just nicer but I can’t get my wrapper vector to work with the new style for loop. I’ve stripped out the instrumentation for other methods in this example code so it only counts the increment operations and when I run the two simple examples below I get this output:

    C: >example03.exe
    Increments: 3

	C: >example11.exe
	Increments: 0

I expected the same output from both examples as all I’ve done is re-write the for loop using the new style for syntax.’

Can you find out why it doesn’t work as expected and suggest some ways to improve (or replace) the mechanism being used?

The code is in Listing 2.

// -- wrapped_vector.hxx --
#include <vector>

template<typename T>
struct wrapped_vector : std::vector<T>
{
  typedef typename std::vector<T> vector;
  typedef typename vector::size_type
    size_type;
  // Sort the constructors
  #if __cplusplus >= 201103
    using vector::vector; // Nice :-)

  #else
    // legacy: need to spell them out ...
    wrapped_vector() {}

    explicit wrapped_vector(size_type n,
      const T& value = T())
    : vector(n, value) {}

    template <class InputIterator>
    wrapped_vector(InputIterator first,
      InputIterator last)
    : vector(first, last) {}
    // ...
  #endif // C++11

  // print the stats
  static void dump();

  // instrumented iterator
  struct iterator : vector::iterator
  {
    typedef typename vector::iterator base;
    iterator() {}
    iterator(base it) : base(it) {}
    iterator& operator ++();
    // (other instrumented methods removed)

    static int increments;
  };

  // const_iterator (unused so removed)
};

#include "wrapped_vector.inl"

// -- wrapped_vector.inl --
#include <iostream>

template <typename T>
void wrapped_vector<T>::dump()
{
  std::cout
    << "Increments: "
    << iterator::increments
    << std::endl;
}

template <typename T>

typename wrapped_vector<T>::iterator& wrapped_vector<T>::iterator::operator ++()
{
  base::operator ++();
  ++increments;
  return *this;
}

template <typename T>
int wrapped_vector<T>::iterator::increments;

// -- example03.cpp –
// (also works with C++11)
#include <cassert>
#include "wrapped_vector.hxx"

int main()
{
  wrapped_vector<int> iVec;
  iVec.push_back(1);
  iVec.push_back(0);
  iVec.push_back(2);

  int total(0);
  for (wrapped_vector<int>::iterator
    iter(iVec.begin()), past(iVec.end());
    iter != past; ++iter)
  {
    total += *iter;
  }
  assert(total == 3);

  wrapped_vector<int>::dump();
}

// -- example11.cpp –- (C++11 example)
#include <cassert>
#include "wrapped_vector.hxx"
int main()
{
  wrapped_vector<int> iVec;
  iVec.push_back(1);
  iVec.push_back(0);
  iVec.push_back(2);
  int total(0);
  for (auto & p : iVec)
  {
     total += p;
  }
  assert(total == 3);
  wrapped_vector<int>::dump();
}
			

You can also get the current problem from the accu-general mail list (next entry is posted around the last issue’s deadline) or from the ACCU website (http://www.accu.org/journals/). This particularly helps overseas members who typically get the magazine much later than members in the UK and Europe.

Notes: 

More fields may be available via dynamicdata ..