ltctests/pth_str/pth_str03.c - platform/external/ltp - Gitiles

 /*
  *
  *   Copyright (c) International Business Machines  Corp., 2001
  *
  *   This program is free software;  you can redistribute it and/or modify
  *   it under the terms of the GNU General Public License as published by
  *   the Free Software Foundation; either version 2 of the License, or
  *   (at your option) any later version.
  *
  *   This program is distributed in the hope that it will be useful,
  *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
  *   the GNU General Public License for more details.
  *
  *   You should have received a copy of the GNU General Public License
  *   along with this program;  if not, write to the Free Software
  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  */

 /*
  *  FILE        : pth_str01.c
  *  DESCRIPTION : create a tree of threads does calculations, and
  *                returns result to parent
  *  HISTORY:
  *    05/l6/2001 Paul Larson (plars@us.ibm.com)
  *      -Ported
  *
  */

 #include <pthread.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <sys/types.h>

 #define MAXTHREADS 1000

 /* Type definition */
 struct kid_info {
 	long		   sum;            /* sum of childrens indexes plus our own */
 	int     	   index;          /* our index into the array */
 	int                status;         /* return status of this thread */
 	int                child_count;    /* Count of children created */
 	int                talk_count;     /* Count of siblings that we talked to */
 	pthread_t          *threads;       /* dynamic array of thread id of kids */
 	pthread_mutex_t    talk_mutex;     /* mutex for the talk_count */
 	pthread_mutex_t    child_mutex;    /* mutex for the child_count */
 	pthread_cond_t     talk_condvar;   /* condition variable for talk_count */
 	pthread_cond_t     child_condvar;  /* condition variable for child_count */
 	struct kid_info    **child_ptrs;   /* dynamic array of ptrs to kids */
 } ;
 typedef struct kid_info c_info;


 /* Global variables */
 int	depth = 3;
 int	breadth = 4;
 int	timeout = 30;			/* minutes */
 int	cdepth;				/* current depth */
 int	debug = 0;

 c_info		*child_info;		/* pointer to info array */
 int		node_count;		/* number of nodes created so far */
 pthread_mutex_t	node_mutex;		/* mutex for the node_count */
 pthread_cond_t	node_condvar;		/* condition variable for node_count */
 pthread_attr_t	attr;			/* attributes for created threads */


 /*--------------------------------------------------------------------------------*
  * parse_args
  *
  * Parse command line arguments.  Any errors cause the program to exit
  * at this point.
  *--------------------------------------------------------------------------------*/
 static void parse_args( int argc, char *argv[] )
 {
 	int		opt, errflag = 0;
 	int		bflag = 0, dflag = 0, tflag = 0;
 	extern char	*optarg;

 	while ( (opt = getopt( argc, argv, "b:d:t:D?" )) != EOF ) {
 	    switch ( opt ) {
 		case 'b':
 		    if ( bflag )
 			errflag++;
 		    else {
 			bflag++;
 			breadth = atoi( optarg );
 			if ( breadth <= 0 )
 			    errflag++;
 		    }
 		    break;
 		case 'd':
 		    if ( dflag )
 			errflag++;
 		    else {
 			dflag++;
 			depth = atoi( optarg );
 			if ( depth <= 0 )
 			    errflag++;
 		    }
 		    break;
 		case 't':
 		    if ( tflag )
 			errflag++;
 		    else {
 			tflag++;
 			timeout = atoi( optarg );
 			if ( timeout <= 0 )
 			    errflag++;
 		    }
 		    break;
 		case 'D':
 		    debug = 1;
 		    break;
 		case '?':
 		default:
 		    errflag++;
 		    break;
 	    }
 	}

 	if ( errflag ) {
 		fprintf( stderr, "usage: %s [-b <num>] [-d <num>] [-t <num>] [-D]", argv[0] );
 		fprintf( stderr, "where:\n" );
 		fprintf( stderr, "\t-b <num>\tbreadth of child nodes\n" );
 		fprintf( stderr, "\t-d <num>\tdepth of child nodes\n" );
 		fprintf( stderr, "\t-t <num>\ttimeout for child communication (in minutes)\n" );
 		fprintf( stderr, "\t-D\tdebug mode\n" );
 		exit( 1 );
 	}

 }


 /*--------------------------------------------------------------------------------*
  * num_nodes
  *
  * Caculate the number of child nodes for a given breadth and depth tree.
  *--------------------------------------------------------------------------------*/
 int num_nodes( int b, int d )
 {
 	int	n, sum = 1, partial_exp = 1;

 	/*
 	 * The total number of children = sum ( b ** n )
 	 *                                n=0->d
 	 * Since b ** 0 == 1, and it's hard to compute that kind of value
 	 * in this simplistic loop, we start sum at 1 (above) to compensate
 	 * and do the computations from 1->d below.
 	 */
 	for ( n = 1; n <= d; n++ ) {
 		partial_exp *= b;
 		sum += partial_exp;
 	}

 	return( sum );
 }


 /*--------------------------------------------------------------------------------*
  * synchronize_children
  *
  * Register the child with the parent and then wait for all of the children
  * at the same level to register also.  Return when everything is synched up.
  *--------------------------------------------------------------------------------*/
 int synchronize_children( c_info *parent )
 {
 	int		  my_index, rc;
 	c_info		  *info_p;
 	struct timespec	  timer;

 	if ( debug ) {
 	    printf( "trying to lock node_mutex\n" );
 	    fflush( stdout );
 	}

 	/* Lock the node_count mutex to we can safely increment it.  We
 	 * will unlock it when we broadcast that all of our siblings have
 	 * been created or when we block waiting for that broadcast.  */
 	pthread_mutex_lock( &node_mutex );
 	my_index = node_count++;

 	printf( "thread %d started\n", my_index );
 	fflush( stdout );

 	/* Get a pointer into the array of thread structures which will be "me". */
 	info_p = &child_info[my_index];
 	info_p->index = my_index;
 	info_p->sum = (long) my_index;

 	if ( debug ) {
 	    printf( "thread %d info_p=%x\n", my_index, info_p );
 	    fflush( stdout );
 	}

 	/* Register with parent bumping the parent's child_count variable.
 	 * Make sure we have exclusive access to that variable before we
 	 * do the increment.  */
 	if ( debug ) {
 	    printf( "thread %d locking child_mutex %x\n", my_index, &parent->child_mutex );
 	    fflush( stdout );
 	}
 	pthread_mutex_lock( &parent->child_mutex );
 	if ( debug ) {
 	    printf( "thread %d bumping child_count (currently %d)\n",
 	      my_index, parent->child_count );
 	    fflush( stdout );
 	}
 	parent->child_ptrs[parent->child_count++] = info_p;
 	if ( debug ) {
 	    printf( "thread %d unlocking child_mutex %x\n", my_index,
 	      &parent->child_mutex );
 	    fflush( stdout );
 	}
 	pthread_mutex_unlock( &parent->child_mutex );

 	if ( debug ) {
 	    printf( "thread %d node_count = %d\n", my_index, node_count );
 	    printf( "expecting %d nodes\n", num_nodes(breadth, cdepth) );
 	    fflush( stdout );
 	}

 	/* Have all the nodes at our level in the tree been created yet?
 	 * If so, then send out a broadcast to wake everyone else up (to let
 	 * them know they can now create their children (if they are not
 	 * leaf nodes)).  Otherwise, go to sleep waiting for the broadcast.  */
 	if ( node_count == num_nodes(breadth, cdepth) ) {

 	    /* Increase the current depth variable, as the tree is now
 	     * fully one level taller.  */
 	    if ( debug ) {
 		printf( "thread %d doing cdepth++ (%d)\n", my_index, cdepth );
 		fflush( stdout );
 	    }
 	    cdepth++;

 	    if ( debug ) {
 		printf( "thread %d sending child_mutex broadcast\n", my_index );
 		fflush( stdout );
 	    }

 	    /* Since all of our siblings have been created, this level of
 	     * the tree is now allowed to continue its work, so wake up the
 	     * rest of the siblings.  */
 	    pthread_cond_broadcast( &node_condvar );

 	} else {

 	    /* In this case, not all of our siblings at this level of the
 	     * tree have been created, so go to sleep and wait for the
 	     * broadcast on node_condvar.  */
 	    if ( debug ) {
 		printf( "thread %d waiting for siblings to register\n",
 		  my_index );
 		fflush( stdout );
 	    }
 	    time( &timer.tv_sec );
 	    timer.tv_sec += (unsigned long)timeout * 60;
             timer.tv_nsec = (unsigned long)0;
 	    if ( rc = pthread_cond_timedwait(&node_condvar, &node_mutex,
 	      &timer) ) {
 		fprintf( stderr, "pthread_cond_timedwait (sync) %d: %s\n",
 		    my_index, sys_errlist[rc] );
 		exit( 2 );
 	    }

 	    if ( debug ) {
 		printf( "thread %d is now unblocked\n", my_index );
 		fflush( stdout );
 	    }

 	}

 	/* Unlock the node_mutex lock, as this thread is finished initializing.  */
 	if ( debug ) {
 	    printf( "thread %d unlocking node_mutex\n", my_index );
 	    fflush( stdout );
 	}
 	pthread_mutex_unlock( &node_mutex );
 	if ( debug ) {
 	    printf( "thread %d unlocked node_mutex\n", my_index );
 	    fflush( stdout );
 	}

 	if ( debug ) {
 	    printf( "synchronize_children returning %d\n", my_index );
 	    fflush( stdout );
 	}

 	return( my_index );
 }


 /*--------------------------------------------------------------------------------*
  * doit
  *
  * Do it.
  *--------------------------------------------------------------------------------*/
 void *doit( void *param )
 {
         c_info *parent  = (c_info *) param;
 	int		rc, child, my_index;
 	void		*status;
 	c_info 		*info_p;
 	struct timespec	timer;

 	if ( debug ) {
 	    printf( "parent=%#010x\n", parent );
 	    fflush( stdout );
 	}

 	if ( parent != NULL ) {
 	    /* Synchronize with our siblings so that all the children at
 	     * a given level have been created before we allow those children
 	     * to spawn new ones (or do anything else for that matter).  */
 	    if ( debug ) {
 		printf( "non-root child calling synchronize_children\n" );
 		fflush( stdout );
 	    }
 	    my_index = synchronize_children( parent );
 	    if ( debug ) {
 		printf( "non-root child has been assigned index %d\n",
 		  my_index );
 		fflush( stdout );
 	    }
 	} else {
 	    /* The first thread has no one with which to synchronize, so
 	     * set some initial values for things.  */
 	    if ( debug ) {
 		printf( "root child\n" );
 		fflush( stdout );
 	    }
 	    cdepth = 1;
 	    my_index = 0;
 	    node_count = 1;
 	}

 	/* Figure out our place in the pthread array.  */
 	info_p = &child_info[my_index];

 	if ( debug ) {
 	    printf( "thread %d getting to heart of doit.\n", my_index );
 	    printf( "info_p=%x, cdepth=%d, depth=%d\n", info_p, cdepth, depth );
 	    fflush( stdout );
 	}

 	if ( cdepth <= depth )
 	{
 	    /* Since the tree is not yet complete (it is not yet tall enough),
 	     * we need to create another level of children.  */

 	    printf( "thread %d creating kids, cdepth=%d\n", my_index, cdepth );
 	    fflush( stdout );

 	    /* Create breadth children.  */
 	    for ( child = 0; child < breadth; child++ ) {
 		if ( debug ) {
 		    printf( "thread %d making child %d, ptr=%x\n", my_index,
 		      child, &(info_p->threads[child]) );
 		    fflush( stdout );
 		}
 		if ( rc = pthread_create(&(info_p->threads[child]), &attr, doit, (void *) info_p) ) {
 		    fprintf( stderr, "pthread_create (doit): %s\n",
 		      sys_errlist[rc] );
 		    exit( 3 );
 		} else {
 		    if ( debug ) {
 			printf( "pthread_create made thread %x\n",
 			  &(info_p->threads[child]) );
 			fflush( stdout );
 		    }
 		}
 	    }

 	    if ( debug ) {
 		printf( "thread %d waits on kids, cdepth=%d\n", my_index,
 		    cdepth );
 		fflush( stdout );
 	    }

 	    /* Wait for our children to finish before we exit ourselves.  */
 	    for ( child = 0; child < breadth; child++ ) {
 		if ( debug ) {
 		    printf( "attempting join on thread %x\n",
 		      &(info_p->threads[child]) );
 		    fflush( stdout );
 		}
 		if ( rc = pthread_join((info_p->threads[child]), &status) ) {
 		    if ( debug ) {
 			fprintf( stderr,
 			  "join failed on thread %d, status addr=%x: %s\n",
 			  my_index, status, sys_errlist[rc] );
 			fflush( stderr );
 		    }
 		    exit( 4 );
 		} else {
 		    if ( debug ) {
 			printf( "thread %d joined child %d ok\n", my_index, child );
 			fflush( stdout );
 		    }

 		    /* Add all childrens indexes to your index value */
 		    info_p->sum += info_p->child_ptrs[child]->sum;
 		    printf("thread %d adding child thread %ld to sum = %ld\n",
 			   my_index, info_p->child_ptrs[child]->index, info_p->sum);
 		}
 	    }

 	} else {

 	    /* This is the leaf node case.  These children don't create
 	     * any kids; they just talk amongst themselves.  */
 	    printf( "thread %d is a leaf node, depth=%d\n", my_index, cdepth );
 	    fflush( stdout );

 	    /* Talk to siblings (children of the same parent node).  */
 	    if ( breadth > 1 ) {

 		for ( child = 0; child < breadth; child++ ) {
 		    /* Don't talk to yourself.  */
 		    if ( parent->child_ptrs[child] != info_p ) {
 			if ( debug ) {
 			    printf( "thread %d locking talk_mutex\n",
 			      my_index );
 			    fflush( stdout );
 			}
 			pthread_mutex_lock(
 			  &(parent->child_ptrs[child]->talk_mutex) );
 			if ( ++parent->child_ptrs[child]->talk_count == (breadth - 1) ) {
 			    if ( debug ) {
 				printf( "thread %d talk siblings\n", my_index );
 				fflush( stdout );
 			    }
 			    if ( rc = pthread_cond_broadcast(
 			      &parent->child_ptrs[child]->talk_condvar) ) {
 				fprintf( stderr, "pthread_cond_broadcast: %s\n",
 				  sys_errlist[rc] );
 				exit( 5 );
 			    }
 			}
 			if ( debug ) {
 			    printf( "thread %d unlocking talk_mutex\n",
 			      my_index );
 			    fflush( stdout );
 			}
 			pthread_mutex_unlock(
 			  &(parent->child_ptrs[child]->talk_mutex) );
 		    }
 		}

 		/* Wait until the breadth - 1 siblings have contacted us.  */
 		if ( debug ) {
 		    printf( "thread %d waiting for talk siblings\n", my_index );
 		    fflush( stdout );
 		}

 		pthread_mutex_lock( &info_p->talk_mutex );
 		if ( info_p->talk_count < (breadth - 1) ) {
 		    time( &timer.tv_sec );
 		    timer.tv_sec += (unsigned long)timeout * 60;
 		    timer.tv_nsec = (unsigned long)0;
 		    if ( rc = pthread_cond_timedwait(&info_p->talk_condvar,
 		      &info_p->talk_mutex, &timer) ) {
 			fprintf( stderr,
 			  "pthread_cond_timedwait (leaf) %d: %s\n",
 			  my_index, sys_errlist[rc] );
 			exit( 6 );
 		    }
 		}
 		pthread_mutex_unlock( &info_p->talk_mutex );

 	    }

 	}

 	/* Our work is done.  We're outta here. */
 	printf( "thread %d exiting, depth=%d, status=%d, addr=%x\n", my_index,
 	  cdepth, info_p->status, info_p);
 	fflush( stdout );

 	pthread_exit( 0 );
 }


 /*--------------------------------------------------------------------------------*
  * main
  *--------------------------------------------------------------------------------*/
 int main( int argc, char *argv[] )
 {
 	int		rc, index, total;
 	pthread_t	root_thread;

 	parse_args( argc, argv );

 	/* Initialize node mutex.  */
 	if ( rc = pthread_mutex_init(&node_mutex, NULL) ) {
 		fprintf( stderr, "pthread_mutex_init(node_mutex): %s\n",
 		    sys_errlist[rc] );
 		exit( 7 );
 	}

 	/* Initialize node condition variable.  */
 	if ( rc = pthread_cond_init(&node_condvar, NULL) ) {
 		fprintf( stderr, "pthread_cond_init(node_condvar): %s\n",
 		    sys_errlist[rc] );
 		exit( 8 );
 	}

 	/* Allocate pthread info structure array.  */
 	if ( (total = num_nodes( breadth, depth )) > MAXTHREADS ) {
 		fprintf( stderr, "Can't create %d threads; max is %d.\n",
 		    total, MAXTHREADS );
 		exit( 9 );
 	}
 	printf( "Allocating %d nodes.\n", total );
 	fflush( stdout );
 	if ( (child_info = (c_info *)malloc( total * sizeof(c_info) )) == NULL ) {
 		perror( "malloc child_info" );
 		exit( 10 );
 	}
 	bzero( child_info, total * sizeof(c_info) );

 	if ( debug ) {
 		printf( "Initializing array for %d children\n", total );
 		fflush( stdout );
 	}

 	/* Allocate array of pthreads descriptors and initialize variables.  */
 	for ( index = 0; index < total; index++ ) {

 		if ( (child_info[index].threads =
 		    (pthread_t *)malloc( breadth * sizeof(pthread_t) )) == NULL ) {
 			perror( "malloc threads" );
 			exit( 11 );
 		}
 		bzero( child_info[index].threads, breadth * sizeof(pthread_t) );

 		if ( (child_info[index].child_ptrs =
 		    (c_info **)malloc( breadth * sizeof(c_info *) )) == NULL ) {
 			perror( "malloc child_ptrs" );
 			exit( 12 );
 		}
 		bzero( child_info[index].child_ptrs,
 		    breadth * sizeof(c_info *) );

 		if ( rc = pthread_mutex_init(&child_info[index].child_mutex, NULL) ) {
 			fprintf( stderr, "pthread_mutex_init child_mutex: %s\n",
 			    sys_errlist[rc] );
 			exit( 13 );
 		}

 		if ( rc = pthread_mutex_init(&child_info[index].talk_mutex, NULL) ) {
 			fprintf( stderr, "pthread_mutex_init talk_mutex: %s\n",
 			    sys_errlist[rc] );
 			exit( 14 );
 		}

 		if ( rc = pthread_cond_init(&child_info[index].child_condvar, NULL) ) {
 			fprintf( stderr,
 			    "pthread_cond_init child_condvar: %s\n",
 			    sys_errlist[rc] );
 			exit( 15 );
 		}

 		if ( rc = pthread_cond_init(&child_info[index].talk_condvar, NULL) ) {
 			fprintf( stderr, "pthread_cond_init talk_condvar: %s\n",
 			    sys_errlist[rc] );
 			exit( 16 );
 		}

 		if ( debug ) {
 			printf( "Successfully initialized child %d.\n", index );
 			fflush( stdout );
 		}

 	}

 	printf( "Creating root thread attributes via pthread_attr_init.\n" );
 	fflush( stdout );

 	if ( rc = pthread_attr_init(&attr) ) {
 		fprintf( stderr, "pthread_attr_init: %s\n", sys_errlist[rc] );
 		exit( 17 );
 	}

 	/* Make sure that all the thread children we create have the
 	 * PTHREAD_CREATE_JOINABLE attribute.  If they don't, then the
 	 * pthread_join call will sometimes fail and cause mass confusion.  */
 	if ( rc = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE)) {
 		fprintf( stderr, "pthread_attr_setdetachstate: %s\n",
 		    sys_errlist[rc] );
 		exit( 18 );
 	}

 	printf( "Creating root thread via pthread_create.\n" );
 	fflush( stdout );

 	if ( rc = pthread_create(&root_thread, &attr, doit, NULL) ) {
 		fprintf( stderr, "pthread_create: %s\n", sys_errlist[rc] );
 		exit( 19 );
 	}

 	if ( debug ) {
 		printf( "Doing pthread_join.\n" );
 		fflush( stdout );
 	}

 	/* Wait for the root child to exit.  */
 	if ( rc = pthread_join(root_thread, NULL) ) {
 		fprintf( stderr, "pthread_join: %s\n", sys_errlist[rc] );
 		exit( 20 );
 	}

 	if ( debug ) {
 		printf( "About to pthread_exit.\n" );
 		fflush( stdout );
 	}

 	printf("\n\nThe sum of tree (breadth %d, depth %d) is %ld\n",
 		breadth, depth, child_info[0].sum);
 	exit( 0 );
 }
	/*
	*
	* Copyright (c) International Business Machines Corp., 2001
	*
	* This program is free software; you can redistribute it and/or modify
	* it under the terms of the GNU General Public License as published by
	* the Free Software Foundation; either version 2 of the License, or
	* (at your option) any later version.
	*
	* This program is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
	* the GNU General Public License for more details.
	*
	* You should have received a copy of the GNU General Public License
	* along with this program; if not, write to the Free Software
	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	*/

	/*
	* FILE : pth_str01.c
	* DESCRIPTION : create a tree of threads does calculations, and
	* returns result to parent
	* HISTORY:
	* 05/l6/2001 Paul Larson (plars@us.ibm.com)
	* -Ported
	*
	*/

	#include <pthread.h>
	#include <stdio.h>
	#include <stdlib.h>
	#include <errno.h>
	#include <sys/types.h>

	#define MAXTHREADS 1000

	/* Type definition */
	struct kid_info {
	long sum; /* sum of childrens indexes plus our own */
	int index; /* our index into the array */
	int status; /* return status of this thread */
	int child_count; /* Count of children created */
	int talk_count; /* Count of siblings that we talked to */
	pthread_t threads; / dynamic array of thread id of kids */
	pthread_mutex_t talk_mutex; /* mutex for the talk_count */
	pthread_mutex_t child_mutex; /* mutex for the child_count */
	pthread_cond_t talk_condvar; /* condition variable for talk_count */
	pthread_cond_t child_condvar; /* condition variable for child_count */
	struct kid_info *child_ptrs; / dynamic array of ptrs to kids */
	} ;
	typedef struct kid_info c_info;


	/* Global variables */
	int depth = 3;
	int breadth = 4;
	int timeout = 30; /* minutes */
	int cdepth; /* current depth */
	int debug = 0;

	c_info child_info; / pointer to info array */
	int node_count; /* number of nodes created so far */
	pthread_mutex_t node_mutex; /* mutex for the node_count */
	pthread_cond_t node_condvar; /* condition variable for node_count */
	pthread_attr_t attr; /* attributes for created threads */


	/--------------------------------------------------------------------------------
	* parse_args
	*
	* Parse command line arguments. Any errors cause the program to exit
	* at this point.
	--------------------------------------------------------------------------------/
	static void parse_args( int argc, char *argv[] )
	{
	int opt, errflag = 0;
	int bflag = 0, dflag = 0, tflag = 0;
	extern char *optarg;

	while ( (opt = getopt( argc, argv, "b:d:t:D?" )) != EOF ) {
	switch ( opt ) {
	case 'b':
	if ( bflag )
	errflag++;
	else {
	bflag++;
	breadth = atoi( optarg );
	if ( breadth <= 0 )
	errflag++;
	}
	break;
	case 'd':
	if ( dflag )
	errflag++;
	else {
	dflag++;
	depth = atoi( optarg );
	if ( depth <= 0 )
	errflag++;
	}
	break;
	case 't':
	if ( tflag )
	errflag++;
	else {
	tflag++;
	timeout = atoi( optarg );
	if ( timeout <= 0 )
	errflag++;
	}
	break;
	case 'D':
	debug = 1;
	break;
	case '?':
	default:
	errflag++;
	break;
	}
	}

	if ( errflag ) {
	fprintf( stderr, "usage: %s [-b <num>] [-d <num>] [-t <num>] [-D]", argv[0] );
	fprintf( stderr, "where:\n" );
	fprintf( stderr, "\t-b <num>\tbreadth of child nodes\n" );
	fprintf( stderr, "\t-d <num>\tdepth of child nodes\n" );
	fprintf( stderr, "\t-t <num>\ttimeout for child communication (in minutes)\n" );
	fprintf( stderr, "\t-D\tdebug mode\n" );
	exit( 1 );
	}

	}


	/--------------------------------------------------------------------------------
	* num_nodes
	*
	* Caculate the number of child nodes for a given breadth and depth tree.
	--------------------------------------------------------------------------------/
	int num_nodes( int b, int d )
	{
	int n, sum = 1, partial_exp = 1;

	/*
	* The total number of children = sum ( b ** n )
	* n=0->d
	* Since b ** 0 == 1, and it's hard to compute that kind of value
	* in this simplistic loop, we start sum at 1 (above) to compensate
	* and do the computations from 1->d below.
	*/
	for ( n = 1; n <= d; n++ ) {
	partial_exp *= b;
	sum += partial_exp;
	}

	return( sum );
	}


	/--------------------------------------------------------------------------------
	* synchronize_children
	*
	* Register the child with the parent and then wait for all of the children
	* at the same level to register also. Return when everything is synched up.
	--------------------------------------------------------------------------------/
	int synchronize_children( c_info *parent )
	{
	int my_index, rc;
	c_info *info_p;
	struct timespec timer;

	if ( debug ) {
	printf( "trying to lock node_mutex\n" );
	fflush( stdout );
	}

	/* Lock the node_count mutex to we can safely increment it. We
	* will unlock it when we broadcast that all of our siblings have
	* been created or when we block waiting for that broadcast. */
	pthread_mutex_lock( &node_mutex );
	my_index = node_count++;

	printf( "thread %d started\n", my_index );
	fflush( stdout );

	/* Get a pointer into the array of thread structures which will be "me". */
	info_p = &child_info[my_index];
	info_p->index = my_index;
	info_p->sum = (long) my_index;

	if ( debug ) {
	printf( "thread %d info_p=%x\n", my_index, info_p );
	fflush( stdout );
	}

	/* Register with parent bumping the parent's child_count variable.
	* Make sure we have exclusive access to that variable before we
	* do the increment. */
	if ( debug ) {
	printf( "thread %d locking child_mutex %x\n", my_index, &parent->child_mutex );
	fflush( stdout );
	}
	pthread_mutex_lock( &parent->child_mutex );
	if ( debug ) {
	printf( "thread %d bumping child_count (currently %d)\n",
	my_index, parent->child_count );
	fflush( stdout );
	}
	parent->child_ptrs[parent->child_count++] = info_p;
	if ( debug ) {
	printf( "thread %d unlocking child_mutex %x\n", my_index,
	&parent->child_mutex );
	fflush( stdout );
	}
	pthread_mutex_unlock( &parent->child_mutex );

	if ( debug ) {
	printf( "thread %d node_count = %d\n", my_index, node_count );
	printf( "expecting %d nodes\n", num_nodes(breadth, cdepth) );
	fflush( stdout );
	}

	/* Have all the nodes at our level in the tree been created yet?
	* If so, then send out a broadcast to wake everyone else up (to let
	* them know they can now create their children (if they are not
	* leaf nodes)). Otherwise, go to sleep waiting for the broadcast. */
	if ( node_count == num_nodes(breadth, cdepth) ) {

	/* Increase the current depth variable, as the tree is now
	* fully one level taller. */
	if ( debug ) {
	printf( "thread %d doing cdepth++ (%d)\n", my_index, cdepth );
	fflush( stdout );
	}
	cdepth++;

	if ( debug ) {
	printf( "thread %d sending child_mutex broadcast\n", my_index );
	fflush( stdout );
	}

	/* Since all of our siblings have been created, this level of
	* the tree is now allowed to continue its work, so wake up the
	* rest of the siblings. */
	pthread_cond_broadcast( &node_condvar );

	} else {

	/* In this case, not all of our siblings at this level of the
	* tree have been created, so go to sleep and wait for the
	* broadcast on node_condvar. */
	if ( debug ) {
	printf( "thread %d waiting for siblings to register\n",
	my_index );
	fflush( stdout );
	}
	time( &timer.tv_sec );
	timer.tv_sec += (unsigned long)timeout * 60;
	timer.tv_nsec = (unsigned long)0;
	if ( rc = pthread_cond_timedwait(&node_condvar, &node_mutex,
	&timer) ) {
	fprintf( stderr, "pthread_cond_timedwait (sync) %d: %s\n",
	my_index, sys_errlist[rc] );
	exit( 2 );
	}

	if ( debug ) {
	printf( "thread %d is now unblocked\n", my_index );
	fflush( stdout );
	}

	}

	/* Unlock the node_mutex lock, as this thread is finished initializing. */
	if ( debug ) {
	printf( "thread %d unlocking node_mutex\n", my_index );
	fflush( stdout );
	}
	pthread_mutex_unlock( &node_mutex );
	if ( debug ) {
	printf( "thread %d unlocked node_mutex\n", my_index );
	fflush( stdout );
	}

	if ( debug ) {
	printf( "synchronize_children returning %d\n", my_index );
	fflush( stdout );
	}

	return( my_index );
	}


	/--------------------------------------------------------------------------------
	* doit
	*
	* Do it.
	--------------------------------------------------------------------------------/
	void doit( void param )
	{
	c_info parent = (c_info ) param;
	int rc, child, my_index;
	void *status;
	c_info *info_p;
	struct timespec timer;

	if ( debug ) {
	printf( "parent=%#010x\n", parent );
	fflush( stdout );
	}

	if ( parent != NULL ) {
	/* Synchronize with our siblings so that all the children at
	* a given level have been created before we allow those children
	* to spawn new ones (or do anything else for that matter). */
	if ( debug ) {
	printf( "non-root child calling synchronize_children\n" );
	fflush( stdout );
	}
	my_index = synchronize_children( parent );
	if ( debug ) {
	printf( "non-root child has been assigned index %d\n",
	my_index );
	fflush( stdout );
	}
	} else {
	/* The first thread has no one with which to synchronize, so
	* set some initial values for things. */
	if ( debug ) {
	printf( "root child\n" );
	fflush( stdout );
	}
	cdepth = 1;
	my_index = 0;
	node_count = 1;
	}

	/* Figure out our place in the pthread array. */
	info_p = &child_info[my_index];

	if ( debug ) {
	printf( "thread %d getting to heart of doit.\n", my_index );
	printf( "info_p=%x, cdepth=%d, depth=%d\n", info_p, cdepth, depth );
	fflush( stdout );
	}

	if ( cdepth <= depth )
	{
	/* Since the tree is not yet complete (it is not yet tall enough),
	* we need to create another level of children. */

	printf( "thread %d creating kids, cdepth=%d\n", my_index, cdepth );
	fflush( stdout );

	/* Create breadth children. */
	for ( child = 0; child < breadth; child++ ) {
	if ( debug ) {
	printf( "thread %d making child %d, ptr=%x\n", my_index,
	child, &(info_p->threads[child]) );
	fflush( stdout );
	}
	if ( rc = pthread_create(&(info_p->threads[child]), &attr, doit, (void *) info_p) ) {
	fprintf( stderr, "pthread_create (doit): %s\n",
	sys_errlist[rc] );
	exit( 3 );
	} else {
	if ( debug ) {
	printf( "pthread_create made thread %x\n",
	&(info_p->threads[child]) );
	fflush( stdout );
	}
	}
	}

	if ( debug ) {
	printf( "thread %d waits on kids, cdepth=%d\n", my_index,
	cdepth );
	fflush( stdout );
	}

	/* Wait for our children to finish before we exit ourselves. */
	for ( child = 0; child < breadth; child++ ) {
	if ( debug ) {
	printf( "attempting join on thread %x\n",
	&(info_p->threads[child]) );
	fflush( stdout );
	}
	if ( rc = pthread_join((info_p->threads[child]), &status) ) {
	if ( debug ) {
	fprintf( stderr,
	"join failed on thread %d, status addr=%x: %s\n",
	my_index, status, sys_errlist[rc] );
	fflush( stderr );
	}
	exit( 4 );
	} else {
	if ( debug ) {
	printf( "thread %d joined child %d ok\n", my_index, child );
	fflush( stdout );
	}

	/* Add all childrens indexes to your index value */
	info_p->sum += info_p->child_ptrs[child]->sum;
	printf("thread %d adding child thread %ld to sum = %ld\n",
	my_index, info_p->child_ptrs[child]->index, info_p->sum);
	}
	}

	} else {

	/* This is the leaf node case. These children don't create
	* any kids; they just talk amongst themselves. */
	printf( "thread %d is a leaf node, depth=%d\n", my_index, cdepth );
	fflush( stdout );

	/* Talk to siblings (children of the same parent node). */
	if ( breadth > 1 ) {

	for ( child = 0; child < breadth; child++ ) {
	/* Don't talk to yourself. */
	if ( parent->child_ptrs[child] != info_p ) {
	if ( debug ) {
	printf( "thread %d locking talk_mutex\n",
	my_index );
	fflush( stdout );
	}
	pthread_mutex_lock(
	&(parent->child_ptrs[child]->talk_mutex) );
	if ( ++parent->child_ptrs[child]->talk_count == (breadth - 1) ) {
	if ( debug ) {
	printf( "thread %d talk siblings\n", my_index );
	fflush( stdout );
	}
	if ( rc = pthread_cond_broadcast(
	&parent->child_ptrs[child]->talk_condvar) ) {
	fprintf( stderr, "pthread_cond_broadcast: %s\n",
	sys_errlist[rc] );
	exit( 5 );
	}
	}
	if ( debug ) {
	printf( "thread %d unlocking talk_mutex\n",
	my_index );
	fflush( stdout );
	}
	pthread_mutex_unlock(
	&(parent->child_ptrs[child]->talk_mutex) );
	}
	}

	/* Wait until the breadth - 1 siblings have contacted us. */
	if ( debug ) {
	printf( "thread %d waiting for talk siblings\n", my_index );
	fflush( stdout );
	}

	pthread_mutex_lock( &info_p->talk_mutex );
	if ( info_p->talk_count < (breadth - 1) ) {
	time( &timer.tv_sec );
	timer.tv_sec += (unsigned long)timeout * 60;
	timer.tv_nsec = (unsigned long)0;
	if ( rc = pthread_cond_timedwait(&info_p->talk_condvar,
	&info_p->talk_mutex, &timer) ) {
	fprintf( stderr,
	"pthread_cond_timedwait (leaf) %d: %s\n",
	my_index, sys_errlist[rc] );
	exit( 6 );
	}
	}
	pthread_mutex_unlock( &info_p->talk_mutex );

	}

	}

	/* Our work is done. We're outta here. */
	printf( "thread %d exiting, depth=%d, status=%d, addr=%x\n", my_index,
	cdepth, info_p->status, info_p);
	fflush( stdout );

	pthread_exit( 0 );
	}



	/--------------------------------------------------------------------------------
	* main
	--------------------------------------------------------------------------------/
	int main( int argc, char *argv[] )
	{
	int rc, index, total;
	pthread_t root_thread;

	parse_args( argc, argv );

	/* Initialize node mutex. */
	if ( rc = pthread_mutex_init(&node_mutex, NULL) ) {
	fprintf( stderr, "pthread_mutex_init(node_mutex): %s\n",
	sys_errlist[rc] );
	exit( 7 );
	}

	/* Initialize node condition variable. */
	if ( rc = pthread_cond_init(&node_condvar, NULL) ) {
	fprintf( stderr, "pthread_cond_init(node_condvar): %s\n",
	sys_errlist[rc] );
	exit( 8 );
	}

	/* Allocate pthread info structure array. */
	if ( (total = num_nodes( breadth, depth )) > MAXTHREADS ) {
	fprintf( stderr, "Can't create %d threads; max is %d.\n",
	total, MAXTHREADS );
	exit( 9 );
	}
	printf( "Allocating %d nodes.\n", total );
	fflush( stdout );
	if ( (child_info = (c_info )malloc( total sizeof(c_info) )) == NULL ) {
	perror( "malloc child_info" );
	exit( 10 );
	}
	bzero( child_info, total * sizeof(c_info) );

	if ( debug ) {
	printf( "Initializing array for %d children\n", total );
	fflush( stdout );
	}

	/* Allocate array of pthreads descriptors and initialize variables. */
	for ( index = 0; index < total; index++ ) {

	if ( (child_info[index].threads =
	(pthread_t )malloc( breadth sizeof(pthread_t) )) == NULL ) {
	perror( "malloc threads" );
	exit( 11 );
	}
	bzero( child_info[index].threads, breadth * sizeof(pthread_t) );

	if ( (child_info[index].child_ptrs =
	(c_info *)malloc( breadth sizeof(c_info *) )) == NULL ) {
	perror( "malloc child_ptrs" );
	exit( 12 );
	}
	bzero( child_info[index].child_ptrs,
	breadth * sizeof(c_info *) );

	if ( rc = pthread_mutex_init(&child_info[index].child_mutex, NULL) ) {
	fprintf( stderr, "pthread_mutex_init child_mutex: %s\n",
	sys_errlist[rc] );
	exit( 13 );
	}

	if ( rc = pthread_mutex_init(&child_info[index].talk_mutex, NULL) ) {
	fprintf( stderr, "pthread_mutex_init talk_mutex: %s\n",
	sys_errlist[rc] );
	exit( 14 );
	}

	if ( rc = pthread_cond_init(&child_info[index].child_condvar, NULL) ) {
	fprintf( stderr,
	"pthread_cond_init child_condvar: %s\n",
	sys_errlist[rc] );
	exit( 15 );
	}

	if ( rc = pthread_cond_init(&child_info[index].talk_condvar, NULL) ) {
	fprintf( stderr, "pthread_cond_init talk_condvar: %s\n",
	sys_errlist[rc] );
	exit( 16 );
	}

	if ( debug ) {
	printf( "Successfully initialized child %d.\n", index );
	fflush( stdout );
	}

	}

	printf( "Creating root thread attributes via pthread_attr_init.\n" );
	fflush( stdout );

	if ( rc = pthread_attr_init(&attr) ) {
	fprintf( stderr, "pthread_attr_init: %s\n", sys_errlist[rc] );
	exit( 17 );
	}

	/* Make sure that all the thread children we create have the
	* PTHREAD_CREATE_JOINABLE attribute. If they don't, then the
	* pthread_join call will sometimes fail and cause mass confusion. */
	if ( rc = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE)) {
	fprintf( stderr, "pthread_attr_setdetachstate: %s\n",
	sys_errlist[rc] );
	exit( 18 );
	}

	printf( "Creating root thread via pthread_create.\n" );
	fflush( stdout );

	if ( rc = pthread_create(&root_thread, &attr, doit, NULL) ) {
	fprintf( stderr, "pthread_create: %s\n", sys_errlist[rc] );
	exit( 19 );
	}

	if ( debug ) {
	printf( "Doing pthread_join.\n" );
	fflush( stdout );
	}

	/* Wait for the root child to exit. */
	if ( rc = pthread_join(root_thread, NULL) ) {
	fprintf( stderr, "pthread_join: %s\n", sys_errlist[rc] );
	exit( 20 );
	}

	if ( debug ) {
	printf( "About to pthread_exit.\n" );
	fflush( stdout );
	}

	printf("\n\nThe sum of tree (breadth %d, depth %d) is %ld\n",
	breadth, depth, child_info[0].sum);
	exit( 0 );
	}