begin quoting Gabriel Sechan as of Tue, Jan 08, 2008 at 04:16:46PM -0600: > > Comments inline. For fun, I'm running this like I would a work code > review- things I would want to see at least defended before allowing > checkin. I'm not looking for better algorithms and I'm not looking > for minor bugs, I'm just doing a style review.
Excellent! > ---------------------------------------- > > Date: Tue, 8 Jan 2008 02:02:44 -0800 > > From: [EMAIL PROTECTED] > > To: [email protected] > > Subject: Code Criticism > > > > > > #ifndef FALSE > > #define FALSE 0 > > #define TRUE 1 > > #endif > > C99 introduced a bool type, as well as false and true keywords. We > shouldn't be using #defined true false anymore. Even without that, > this should be an enum, not defines. Assumed language is C89. Not entirely sure I have a C99 compiler on all of my machines. > > #define ERROR_EMPTY_ARG "Programmer error. Empty argument in %s at %d\n" > > #define ERROR_MALLOC_FAIL "Failed to allocate memory. In %s at %d\n" > > #define ERROR_BAD_BOARD "Bad board configuration: '%s' in %s at %d\n" > > #define ERROR_SWITCH_BROKE "Unknown value in switch: %d in %s at %d\n" > > > > /* change BLANK to use a different 'empty' character. '_' might be good. */ > > #define BLANK ' ' > > C99 also introduced const variables, just like C++. These have type > checking, #defines do not. Use them instead. BLANK should be a variable, but not const. I may want to let the user change it. I'm not a fan of 'const' anyway. It generally causes more problems than it solves for me -- and it's sticky, like statics in Java -- it gets everywhere. PITA. Besides, improvements to the error code should involve an error subsystem, using an array (okay, maybe that can be const) to store the messages. Plus, that would allow for transparent localization. > > /* The fundamental board structure. We have nine puzzle slots, but > > * we want to treat it as a string, so we need space for the terminating > > * null. We want to eliminate repeats, so we keep track of the parent, > > * which also offers a simple way to print out the final pieces in order. > > */ > > typedef struct { > > char board[10]; > > void *moves[4]; > > void *prev; > > } configuration; > > > > Bad mistake in using strncmp and strings. This isn't string data. > Use the memcmp, memcpy, etc functions instead. That also means you > only need char[9]. Unless you really only want to check up til the > first null char, which seems a bit... odd It lets me print out the current state when coding by dropping in fprintfs. > General comment- couldn't you have found a queue library prewritten? Maybe. It's doubtful I would have found a *small* library. I might have been able to grab some "general purpose source code" from somewhere, but then I'd need to worry about licensing issues, as I don't have the right to release anyone else's code into the public domain. I *could* have extended my own general-purpose library and used that. Arguably, I should do so anyway. > > /* We need a simple queue of arbitrary size, so we use a singly linked list. > > */ > > typedef struct { > > configuration *data; > > void *next; > > } dequenode; > > > > /* We push new items to the tail and pull them from the head for fast > > * O(1) access. > > * TODO - also keep a count of the # of elements in the queue? > > */ > > typedef struct { > > dequenode *head; > > dequenode *tail; > > } deque; > > > > /* ----------------------------------------------------------------- */ > > > > /* make_dequeue > > * creates a new queue. > > * exits on malloc failure. > > */ > > deque *make_deque() { > > deque *p; > > p = malloc( sizeof( deque ) ); > > if ( p == NULL ) { > > fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ ); > > exit( EXIT_FAILURE ); > > } > > > > p->head = NULL; > > p->tail = NULL; > > } > > > > exiting like that is ok for such a minor program, but its a bad idea > in anything bigger. If you wanted to reuse this code, return NULL on > error instead and let the calling code exit. Valid point. This data structure is not reusable, however. Had I done the _right_ thing and added to my generic-data-structure library, then having support code exit the program would be very bad style indeed. > > /* deque_insert > > * inserts the current node into the queue. > > * exits on malloc failure. > > */ > > void deque_insert( deque *d, configuration *current ) { > > dequenode *n, *t; > > n = malloc( sizeof( dequenode ) ); > > if ( n == NULL ) { > > fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ ); > > exit( EXIT_FAILURE ); > > } > > > > n->data = current; > > > > if ( d->head == NULL ) { > > d->head = n; > > } else { > > t = d->tail; > > t->next = (struct dequenode *)n; > > /*d->tail->next = n;*/ > > } > > d->tail = n; > > } > > > > Really bad variable names. Heh. Yup. > > /* deque_remove > > * removes the oldest node from the queue. > > * do not call if queue is empty. > > */ > > configuration *deque_remove( deque *d ) { > > configuration *p; > > dequenode *q; > > > > q = d->head; > > p = q->data; > > > > if ( d->head == d->tail ) { > > d->head = NULL; > > d->tail = NULL; > > } else { > > d->head = (dequenode *)d->head->next; > > } > > > > free( q ); > > > > return p; > > } > > > > /* deque_empty > > * answers if the queue is empty. > > */ > > int deque_empty( deque *d ) { > > return d->head == NULL; > > } > > > > /* deque_size > > * answers the number of items in the queue. > > * warning - very slow. Walks the linked list. See TODO for struct. > > */ > > int deque_size( deque *d ) { > > int count = 0; > > dequenode *p = d->head; > > dequenode *end = d->tail; > > while ( p != end ) { count++; p = p->next; } > > return count; > > } > > If you expect to call size frequently, add a size member to the > structure and increment/decrement it on insert/remove. Walking is > expensive. Yup. Noted in the TODOs. Calling size _at all_ towards the middle and end of the run was very slow. > > /* ----------------------------------------------------------------- */ > > > > /* got_match > > * Answers if the two configurations are equivalent. > > * Exits on programmer error. > > */ > > int got_match( configuration *current, configuration *final ) { > > if ( current == NULL ) { > > return FALSE; > > } > > if ( final == NULL ) { > > fprintf( stderr, ERROR_EMPTY_ARG, __FILE__, __LINE__ ); > > /*return FALSE;*/ > > exit( EXIT_FAILURE ); > > } > > > > return ! (strncmp( current->board, final->board, 10 )); > > } > > > > As previously said- use memcmp. That adds another parameter to screw up. On the other hand, memcmp and memcpy would let me use character sequences instead of just characters, allowing for mnemonic tile names. > > /* got_repeat > > * Walks the ancestor list looking for a configuration that is equivalent > > * to the current node. This is an optimization step. > > */ > > int got_repeat( configuration *current ) { > > configuration *p; > > p = (configuration *)current->prev; > > while ( p != NULL ) { > > if ( got_match( p, current ) ) return TRUE; > > p = (configuration *)p->prev; > > } > > return FALSE; > > } > > > > Why do you have two list mechanisms? Why not use a dequeue inside the > configuration? Because a dequeue holds a configuration. And this list -- a chain of parent nodes -- cannot and should not change. We walk it repeatedly, and it encodes our final solution. > > /* new > > * Answers a clone of the the provided configuration. A NULL configuration > > * will cause an uninitialized configuration to be created. > > * TODO - how much of the brute-force initialization can we remove? > > */ > > configuration *new( configuration *current ) { > > configuration *p; > > > > p = malloc( sizeof( configuration ) ); > > if ( p == NULL ) { > > fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__); > > exit( EXIT_FAILURE ); > > } > > p->board[0] = '\0'; > > p->board[1] = '\0'; > > p->board[2] = '\0'; > > p->board[3] = '\0'; > > p->board[4] = '\0'; > > p->board[5] = '\0'; > > p->board[6] = '\0'; > > p->board[7] = '\0'; > > p->board[8] = '\0'; > > p->board[9] = '\0'; > > p->board[10] = '\0'; > > p->prev = NULL; > > p->moves[0] = NULL; > > p->moves[1] = NULL; > > p->moves[2] = NULL; > > p->moves[3] = NULL; > > > > if ( current != NULL ) { > > char *a, *b; > > p->prev = (struct configuration *)current; > > strncpy( p->board, current->board, 10 ); > > } > > > > return p; > > } > > Loops to initialize arrays. Don't initialize the board to nulls if > you're just going to overwrite it if current!=NULL (in otherwise, put > it in an else). Yes, this is cruft leftover from tracking down a bug. It seriously needs to be yanked out. > > /* swap_tile > > * Swaps the board elements at the specified location. > > * Assumes arguments are valid and sensible. > > */ > > void swap_tile( configuration *current, int source, int dest ) { > > char temp; > > temp = current->board[dest]; > > current->board[dest] = current->board[source]; > > current->board[source] = temp; > > } > > > > /* make_child > > * Creates a unique new child of the current configuration using the > > * specified swap of tiles and adding to the specified move slot. > > * If the child repeats an ancestor state, it is discarded. > > */ > > void make_child( configuration *current, int move, int dest, int source ) { > > configuration *p; > > p = new( current ); > > swap_tile( p, source, dest ); > > if ( ! got_repeat( p ) ) { > > current->moves[move] = (struct configuration *)p; > > } else { > > free( p ); > > } > > } > > > > /* fill_children > > * Creates all the possible children of the current configuration and > > * adds them to the current configuration. > > */ > > void fill_children( configuration *current ) { > > configuration *p; > > char temp; > > int i; > > int blank = -1; > > > > for ( i = 0; i < 9; i++ ) { > > if ( current->board[i] == BLANK ) { > > blank = i; > > break; > > } > > } > > > > if ( blank < 0 ) { > > fprintf( stderr, ERROR_BAD_BOARD, current->board, __FILE__, __LINE__); > > return; > > } > > > > /* > > * 0 | 1 | 2 > > * -----+-----+----- > > * 3 | 4 | 5 > > * -----+-----+----- > > * 6 | 7 | 8 > > * > > */ > > > > switch ( blank ) { > > case 0: /* 1->0, 3->0 */ > > make_child( current, 0, 0, 1 ); > > make_child( current, 1, 0, 3 ); > > break; > > case 1: /* 0->1, 2->1, 4->1 */ > > make_child( current, 0, 1, 0 ); > > make_child( current, 1, 1, 2 ); > > make_child( current, 2, 1, 4 ); > > break; > > case 2: /* 1->2, 5->2 */ > > make_child( current, 0, 2, 1 ); > > make_child( current, 1, 2, 5 ); > > break; > > case 3: /* 0->3, 4->3, 6-> 3 */ > > make_child( current, 0, 3, 0 ); > > make_child( current, 1, 3, 4 ); > > make_child( current, 2, 3, 6 ); > > break; > > case 4: /* 1->4, 3->4, 5->4, 7->4 */ > > make_child( current, 0, 4, 1 ); > > make_child( current, 1, 4, 3 ); > > make_child( current, 2, 4, 5 ); > > make_child( current, 3, 4, 7 ); > > break; > > case 5: /* 2->5, 4->5, 8->5 */ > > make_child( current, 0, 5, 2 ); > > make_child( current, 1, 5, 4 ); > > make_child( current, 2, 5, 8 ); > > break; > > case 6: /* 3->6, 7->6 */ > > make_child( current, 0, 6, 3 ); > > make_child( current, 1, 6, 7 ); > > break; > > case 7: /* 6->7, 4->7, 8->7 */ > > make_child( current, 0, 7, 4 ); > > make_child( current, 1, 7, 6 ); > > make_child( current, 2, 7, 8 ); > > break; > > case 8: /* 5->8, 7->8 */ > > make_child( current, 0, 8, 5 ); > > make_child( current, 1, 8, 7 ); > > break; > > default: > > fprintf( stderr, ERROR_SWITCH_BROKE, blank, __FILE__, __LINE__ ); > > } > > } > > > There has got to be a better solution than a giant switch. Plus if > you can do it programatically, it expands to more than 3x3 There are always nine cases, even for more than a 3x3 grid. Each corner (top left, top right, bottom left, bottom right), the edges (top, left, right, bottom), and the middle. The problem with the switch is that it's hard-coded to the 3x3 grid, but not using a hard-coded lookup table. Worst of both worlds. > > /* walk_solutions > > * Breadth-first walk of the solution tree and find the first solution. > > */ > > configuration *walk_solutions( configuration *initial, configuration *final > > ) { > > configuration *current; > > deque *queue; > > int i; > > > > queue = make_deque(); > > deque_insert( queue, initial ); > > > > while ( TRUE ) { > > current = deque_remove( queue ); > > if ( got_match( current, final ) ) { > > return current; /* leak memory like mad */ > > } > > > > #ifdef MONITOR_PROGRESS > > i = deque_size( queue ); > > if ( i % 100 == 0 ) { > > if ( i < 1000 ) fprintf(stderr, "."); > > else if ( i < 10000 ) fprintf(stderr, ":"); > > else if ( i < 100000 ) fprintf(stderr, "!"); > > else fprintf(stderr, "#"); > > } > > #endif > > > > fill_children( current ); > > for ( i = 0; i < 4; i++ ) { > > if ( current->moves[i] != NULL ) { > > deque_insert( queue, (configuration *)current->moves[i] ); > > } > > }/* for */ > > > > }/* while */ > > } > > > > /* print_solution_size > > * Outputs the number of moves it took to solve the problem. > > */ > > void print_solution_size( configuration *end ) { > > configuration *p; > > int count; > > > > count = 0; > > p = end; > > while ( p != NULL ) { > > p = (configuration *)p->prev; > > count++; > > } > > > > fprintf( stdout, "There are %d steps in the solution.\n", count); > > } > > > > /* print_solutions > > * Print the solution-stack, in reasonable order. > > * Recursive. > > */ > > void print_solutions( configuration *end ) { > > if ( end->prev != NULL ) { > > print_solutions( (configuration *)end->prev ); > > } > > int row, col; > > for ( row = 0; row < 3; row++ ) { > > for ( col = 0; col < 3; col++ ) { > > fprintf( stdout, " [%c] ", end->board[row * 3 + col] ); > > } > > fprintf( stdout, "\n" ); > > } > > fprintf( stdout, "\n" ); > > } > > > > /* ----------------------------------------------------------------- */ > > > > /* usage > > * Outputs how to use the program. > > */ > > void usage( char **argv ) { > > fprintf( stderr, "Usage: %s start end\n", argv[0]); > > fprintf( stderr, "\tstart = 9 character board configuration\n"); > > fprintf( stderr, "\tend = 9 character board configuration\n"); > > fprintf( stderr, "\t(Note that a blank is REQUIRED!)\n"); > > /* change this if change definition of BLANK define */ > > } > > > > /* main > > * program entry-point > > */ > > int main( int argc, char **argv ) { > > configuration *start; > > configuration *end; > > configuration *solution; > > > > if ( argc != 3 ) { usage( argv ); return EXIT_FAILURE; } > > > > start = new( NULL ); > > end = new( NULL ); > > > > if ( strlen( argv[1] ) != 9 ) { usage( argv ); return EXIT_FAILURE; } > > if ( strlen( argv[2] ) != 9 ) { usage( argv ); return EXIT_FAILURE; } > > > > strncpy( start->board, argv[1], 10 ); > > strncpy( end->board, argv[2], 10 ); > > > > fprintf( stdout, "Starting with '%s' and trying for '%s'\n", > > start->board, end->board ); > > fprintf( stdout, "start: %p \t end: %p\n", start, end ); > > > > solution = walk_solutions( start, end ); > > > > print_solution_size( solution ); > > > > print_solutions( solution ); > > > > return EXIT_SUCCESS; > > } > > --------------------------------------------------------------------------- There are two memory leaks. Only one of 'em is called out. I didn't notice the second until I reviewed the code the first time. -- I need a good C99 book Then I could really cook! Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
