[deliverable/binutils-gdb.git] / gdb / testsuite / gdb.hp / quicksort.c

/* BeginSourceFile quicksort.c

  This file is take from the DDE test system.  It spawns six
  threads to do a sort of an array of random numbers.

  The locations marked "quick N" are used in the test "quicksort.exp".

  The locations marked "att N" are used in the test "attach.exp".

  To compile:

      cc -Ae +DA1.0 -g -o quicksort -lpthread quicksort.c

  To run:
  
     quicksort     --normal run
     quicksort 1   --waits before starting to allow attach
*/

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <pthread.h>

#define TRUE 1
#define FALSE 0
#define SORTSET 100000

/* Uncomment to turn on debugging output */
/* #define QUICK_DEBUG  */

/* Uncomment to turn on wait on each thread create */
/* #define THREAD_WAIT */

/* Fewer than SORT_DIRECT items are sorted with an insertion sort. */
#define SORT_DIRECT 20

/* Work at this depth or less generates a separate work item. */
#define DEFER_DEPTH 6

/* Workpile controller */
typedef void (*work_proc_t)(void *);

typedef struct workpile_struct {
	pthread_mutex_t lock;	       /* mutex for this structure */
	pthread_cond_t work_wait;      /* workers waiting for work */
	pthread_cond_t finish_wait;    /* to wait for workers to finish */
	int max_pile;		       /* length of workpile array */
	work_proc_t worker_proc;       /* work procedure */
	int n_working;		       /* number of workers working */
	int n_waiting;		       /* number of workers waiting for work */
	int n_pile;		       /* number of pointers in the workpile */
	int inp;		       /* FIFO input pointer */
	int outp;		       /* FIFO output pointer */
	void *pile[1];		       /* array of pointers - the workpile */
} *workpile_t;

typedef struct {
	float *data;		   /* Array to sort */
	int n;			   /* Number of elements in the array */
	int depth;		   /* Depth of recursion */
	workpile_t wp;		   /* Workpile to use */
} quick_sort_args;

/* True if waiting for attach.
 */
int wait_here = FALSE;

static workpile_t quick_sort_workpile = NULL;

void *worker(void * wptr);

/* Allocates and initializes a workpile that holds max_pile entries.
 * worker_proc is called to process each work item on the queue.
 */
workpile_t
work_init(int max_pile, work_proc_t worker_proc, int n_threads)
{
	int err;
	pthread_t t;
	workpile_t wp = (workpile_t)
		malloc(sizeof (struct workpile_struct) +
			(max_pile * sizeof (void *)));

	if (wp != NULL) {
		pthread_mutex_init(&wp->lock, NULL);
		pthread_cond_init(&wp->work_wait, NULL);
		pthread_cond_init(&wp->finish_wait, NULL);
		wp->max_pile = max_pile;
		wp->worker_proc = worker_proc;
		wp->n_working = wp->n_waiting = wp->n_pile = 0;
		wp->inp = wp->outp = 0;
		while (n_threads--) {
			err = pthread_create(&t, NULL,
			      worker, (void *)&wp);
#ifdef QUICK_DEBUG
                        printf( "== Quicksort: created new thread\n" );
#ifdef THREAD_WAIT
                        if( n_threads > 0 ) {
                            int i;
                        printf( "== Quicksort: waiting on user input of an integer\n" );
                            scanf( "%d", &i );
                            printf( "== Quicksort: continuing with quicksort\n" );
                        }
#endif
#endif

			assert(err == 0);    /* quick 1 */
		}
                /* All the threads have now been created.
                 */
                assert( n_threads == -1 );         /* att 1 */
                if( wait_here ) {
#ifdef QUICK_DEBUG
                    printf( "== Quicksort: waiting for attach\n" );
#endif
                    sleep( 25 );
                }
                wait_here = 99;              /* att 2, otherwise useless */
	}
	return (wp);                         /* quick 2 */
}

/*
 * Worker thread routine. Continuously looks for work, calls the
 * worker_proc associated with the workpile to do work.
 */
void *
worker(void * wptr)
{
        workpile_t wp;
	void *ptr;

        wp = * (workpile_t *) wptr;

	pthread_mutex_lock(&wp->lock);
	wp->n_working++;
	for (;;) {
		while (wp->n_pile == 0) {								/* wait for new work */
			if (--wp->n_working == 0)
				pthread_cond_signal(&wp->finish_wait);
			wp->n_waiting++;
			pthread_cond_wait(&wp->work_wait, &wp->lock);
			wp->n_waiting--;       /* quick 3 */
			wp->n_working++;
		}
		wp->n_pile--;
		ptr = wp->pile[wp->outp];
		wp->outp = (wp->outp + 1) % wp->max_pile;
		pthread_mutex_unlock(&wp->lock);
		/* Call application worker routine. */
		(*wp->worker_proc)(ptr);
		pthread_mutex_lock(&wp->lock);  /* quick 4 */
	}
	/* NOTREACHED */
}

/* Puts ptr in workpile. Called at the outset, or within a worker. */
void
work_put(workpile_t wp, void *ptr)
{
	pthread_mutex_lock(&wp->lock);
	if (wp->n_waiting) {
		/* idle workers to be awakened */
		pthread_cond_signal(&wp->work_wait);
	}
	assert(wp->n_pile != wp->max_pile);									/* check for room */
	wp->n_pile++;
	wp->pile[wp->inp] = ptr;
	wp->inp = (wp->inp + 1) % wp->max_pile;
	pthread_mutex_unlock(&wp->lock);
}


/* Wait until all work is done and workers quiesce. */
void
work_wait(workpile_t wp)
{
	pthread_mutex_lock(&wp->lock);
	while(wp->n_pile !=0 || wp->n_working != 0)
		pthread_cond_wait(&wp->finish_wait, &wp->lock);
	pthread_mutex_unlock(&wp->lock);
}

void
quick_sort_aux(float *data, int n, int depth, workpile_t wp, int deferrable)
{
	int i,j;

	/* If array small, use insertion sort */
	if (n <= SORT_DIRECT) {
		for (j = 1; j < n; j++) {
			/* data[0..j-1] in sort; find a spot for data[j] */
			float key = data[j];
			for (i = j - 1; i >= 0 && key < data[i]; i--)
				data[i+1] = data[i];
			data[i+1] = key;
		}
		return;
	}
	/* Defer this work to work queue if policy says so */
	if (deferrable && depth <= DEFER_DEPTH) {
		quick_sort_args *q = (quick_sort_args *)
								malloc(sizeof (quick_sort_args));
		assert(q != NULL);
		q->data = data; q->n = n; q->depth = depth; q->wp = wp;
		work_put(wp, (void *)q);
		return;
	}
	/* Otherwise, partition data based on a median estimate */
#define swap(i,j) {float t = data[i]; data[i] = data[j]; data[j] = t;}
	i = 0;
	j = n - 1;
	for (;;) {
		while (data[i] < data[j]) j--;
		if (i >= j) break;
		swap(i, j); i++;
		while (data[i] < data[j]) i++;
		if (i >= j) { i = j; break; }
		swap(i, j); j--;
	}
	/* Median value is now at data[i] */
	/* Partitioned so that data[0..i-1] <= median <= data[i+1..n-1] */
	quick_sort_aux(data,       i,     depth+1, wp, TRUE);
	quick_sort_aux(&data[i+1], n-i-1, depth+1, wp, TRUE);
}
/* Called from workpile controller with argument pointing to work. */
void
quick_sort_worker(void *a)
{
	quick_sort_args *q = (quick_sort_args *)a;
	quick_sort_aux(q->data, q->n, q->depth, q->wp, FALSE);
	free(q);
}
/* Main routine, called by client to do a sort. */
void
quick_sort(float *data, int n)
{
	if (quick_sort_workpile == NULL) {
		int n_threads = 6;
		quick_sort_workpile = work_init(2 << DEFER_DEPTH,
			quick_sort_worker, n_threads);
		assert(quick_sort_workpile != NULL);
	}
        
	quick_sort_aux(data, n, 0, quick_sort_workpile, FALSE);
        
	/* Wait for all work to finish */
	work_wait(quick_sort_workpile);
        
#ifdef QUICK_DEBUG
        printf( "== Quicksort: done sorting\n" );
#endif
}


main( argc, argv )
int    argc;
char **argv;
{
	float data[SORTSET];
	int i; int debugging = 0;

        if((argc > 1) && (0 != argv )) {
            if( 1 == atoi( argv[1] ) )
               wait_here = TRUE;
        }

	for(i = 0; i < SORTSET; i++)
		data[SORTSET -1 -i] = drand48();
                
	for(i = 0; i < SORTSET; i++)
		if (debugging)
                   printf("data[%d] = %f\n", i, data[i]);

	quick_sort(data, SORTSET);
	for(i = 0; i < SORTSET; i++)
		if (debugging)
		printf("data[%d] = %f\n", i, data[i]);

	return(0);
}
/* EndSourceFile */
Commit	Line	Data
c906108c SS	1	/* BeginSourceFile quicksort.c
	2
	3	This file is take from the DDE test system. It spawns six
	4	threads to do a sort of an array of random numbers.
	5
	6	The locations marked "quick N" are used in the test "quicksort.exp".
	7
	8	The locations marked "att N" are used in the test "attach.exp".
	9
	10	To compile:
	11
	12	cc -Ae +DA1.0 -g -o quicksort -lpthread quicksort.c
	13
	14	To run:
	15
	16	quicksort --normal run
	17	quicksort 1 --waits before starting to allow attach
	18	*/
	19
	20	#include <unistd.h>
	21	#include <stdlib.h>
	22	#include <stdio.h>
	23	#include <assert.h>
	24	#include <pthread.h>
	25
	26	#define TRUE 1
	27	#define FALSE 0
	28	#define SORTSET 100000
	29
	30	/* Uncomment to turn on debugging output */
	31	/* #define QUICK_DEBUG */
	32
	33	/* Uncomment to turn on wait on each thread create */
	34	/* #define THREAD_WAIT */
	35
	36	/* Fewer than SORT_DIRECT items are sorted with an insertion sort. */
	37	#define SORT_DIRECT 20
	38
	39	/* Work at this depth or less generates a separate work item. */
	40	#define DEFER_DEPTH 6
	41
	42	/* Workpile controller */
	43	typedef void (work_proc_t)(void );
	44
	45	typedef struct workpile_struct {
	46	pthread_mutex_t lock; /* mutex for this structure */
	47	pthread_cond_t work_wait; /* workers waiting for work */
	48	pthread_cond_t finish_wait; /* to wait for workers to finish */
	49	int max_pile; /* length of workpile array */
	50	work_proc_t worker_proc; /* work procedure */
	51	int n_working; /* number of workers working */
	52	int n_waiting; /* number of workers waiting for work */
	53	int n_pile; /* number of pointers in the workpile */
	54	int inp; /* FIFO input pointer */
	55	int outp; /* FIFO output pointer */
	56	void pile[1]; / array of pointers - the workpile */
	57	} *workpile_t;
	58
	59	typedef struct {
	60	float data; / Array to sort */
	61	int n; /* Number of elements in the array */
	62	int depth; /* Depth of recursion */
	63	workpile_t wp; /* Workpile to use */
	64	} quick_sort_args;
65
66	/* True if waiting for attach.
67	*/
68	int wait_here = FALSE;
69
70	static workpile_t quick_sort_workpile = NULL;
71
72	void worker(void wptr);
73
74	/* Allocates and initializes a workpile that holds max_pile entries.
75	* worker_proc is called to process each work item on the queue.
76	*/
77	workpile_t
78	work_init(int max_pile, work_proc_t worker_proc, int n_threads)
79	{
80	int err;
81	pthread_t t;
82	workpile_t wp = (workpile_t)
83	malloc(sizeof (struct workpile_struct) +
84	(max_pile * sizeof (void *)));
85
86	if (wp != NULL) {
87	pthread_mutex_init(&wp->lock, NULL);
88	pthread_cond_init(&wp->work_wait, NULL);
89	pthread_cond_init(&wp->finish_wait, NULL);
90	wp->max_pile = max_pile;
91	wp->worker_proc = worker_proc;
92	wp->n_working = wp->n_waiting = wp->n_pile = 0;
93	wp->inp = wp->outp = 0;
94	while (n_threads--) {
95	err = pthread_create(&t, NULL,
96	worker, (void *)&wp);
97	#ifdef QUICK_DEBUG
98	printf( "== Quicksort: created new thread\n" );
99	#ifdef THREAD_WAIT
100	if( n_threads > 0 ) {
101	int i;
102	printf( "== Quicksort: waiting on user input of an integer\n" );
103	scanf( "%d", &i );
104	printf( "== Quicksort: continuing with quicksort\n" );
105	}
106	#endif
107	#endif
108
109	assert(err == 0); /* quick 1 */
110	}
111	/* All the threads have now been created.
112	*/
113	assert( n_threads == -1 ); /* att 1 */
114	if( wait_here ) {
115	#ifdef QUICK_DEBUG
116	printf( "== Quicksort: waiting for attach\n" );
117	#endif
118	sleep( 25 );
119	}
120	wait_here = 99; /* att 2, otherwise useless */
121	}
122	return (wp); /* quick 2 */
123	}
124
125	/*
126	* Worker thread routine. Continuously looks for work, calls the
127	* worker_proc associated with the workpile to do work.
128	*/
129	void *
130	worker(void * wptr)
131	{
132	workpile_t wp;
133	void *ptr;
134
135	wp = * (workpile_t *) wptr;
136
137	pthread_mutex_lock(&wp->lock);
138	wp->n_working++;
139	for (;;) {
140	while (wp->n_pile == 0) { /* wait for new work */
141	if (--wp->n_working == 0)
142	pthread_cond_signal(&wp->finish_wait);
143	wp->n_waiting++;
144	pthread_cond_wait(&wp->work_wait, &wp->lock);
145	wp->n_waiting--; /* quick 3 */
146	wp->n_working++;
147	}
148	wp->n_pile--;
149	ptr = wp->pile[wp->outp];
150	wp->outp = (wp->outp + 1) % wp->max_pile;
151	pthread_mutex_unlock(&wp->lock);
152	/* Call application worker routine. */
153	(*wp->worker_proc)(ptr);
154	pthread_mutex_lock(&wp->lock); /* quick 4 */
155	}
156	/* NOTREACHED */
157	}
158
159	/* Puts ptr in workpile. Called at the outset, or within a worker. */
160	void
161	work_put(workpile_t wp, void *ptr)
162	{
163	pthread_mutex_lock(&wp->lock);
164	if (wp->n_waiting) {
165	/* idle workers to be awakened */
166	pthread_cond_signal(&wp->work_wait);
167	}
168	assert(wp->n_pile != wp->max_pile); /* check for room */
169	wp->n_pile++;
170	wp->pile[wp->inp] = ptr;
171	wp->inp = (wp->inp + 1) % wp->max_pile;
172	pthread_mutex_unlock(&wp->lock);
173	}
174
175
176	/* Wait until all work is done and workers quiesce. */
177	void
178	work_wait(workpile_t wp)
179	{
180	pthread_mutex_lock(&wp->lock);
181	while(wp->n_pile !=0 \|\| wp->n_working != 0)
182	pthread_cond_wait(&wp->finish_wait, &wp->lock);
183	pthread_mutex_unlock(&wp->lock);
184	}
185
186	void
187	quick_sort_aux(float *data, int n, int depth, workpile_t wp, int deferrable)
188	{
189	int i,j;
190
191	/* If array small, use insertion sort */
192	if (n <= SORT_DIRECT) {
193	for (j = 1; j < n; j++) {
194	/* data[0..j-1] in sort; find a spot for data[j] */
195	float key = data[j];
196	for (i = j - 1; i >= 0 && key < data[i]; i--)
197	data[i+1] = data[i];
198	data[i+1] = key;
199	}
200	return;
201	}
202	/* Defer this work to work queue if policy says so */
203	if (deferrable && depth <= DEFER_DEPTH) {
204	quick_sort_args q = (quick_sort_args )
205	malloc(sizeof (quick_sort_args));
206	assert(q != NULL);
207	q->data = data; q->n = n; q->depth = depth; q->wp = wp;
208	work_put(wp, (void *)q);
209	return;
210	}
211	/* Otherwise, partition data based on a median estimate */
212	#define swap(i,j) {float t = data[i]; data[i] = data[j]; data[j] = t;}
213	i = 0;
214	j = n - 1;
215	for (;;) {
216	while (data[i] < data[j]) j--;
217	if (i >= j) break;
218	swap(i, j); i++;
219	while (data[i] < data[j]) i++;
220	if (i >= j) { i = j; break; }
221	swap(i, j); j--;
222	}
223	/* Median value is now at data[i] */
224	/* Partitioned so that data[0..i-1] <= median <= data[i+1..n-1] */
225	quick_sort_aux(data, i, depth+1, wp, TRUE);
226	quick_sort_aux(&data[i+1], n-i-1, depth+1, wp, TRUE);
227	}
228	/* Called from workpile controller with argument pointing to work. */
229	void
230	quick_sort_worker(void *a)
231	{
232	quick_sort_args q = (quick_sort_args )a;
233	quick_sort_aux(q->data, q->n, q->depth, q->wp, FALSE);
234	free(q);
235	}
236	/* Main routine, called by client to do a sort. */
237	void
238	quick_sort(float *data, int n)
239	{
240	if (quick_sort_workpile == NULL) {
241	int n_threads = 6;
242	quick_sort_workpile = work_init(2 << DEFER_DEPTH,
243	quick_sort_worker, n_threads);
244	assert(quick_sort_workpile != NULL);
245	}
246
247	quick_sort_aux(data, n, 0, quick_sort_workpile, FALSE);
248
249	/* Wait for all work to finish */
250	work_wait(quick_sort_workpile);
251
252	#ifdef QUICK_DEBUG
253	printf( "== Quicksort: done sorting\n" );
254	#endif
255	}
256
257
258	main( argc, argv )
259	int argc;
260	char **argv;
261	{
262	float data[SORTSET];
263	int i; int debugging = 0;
264
265	if((argc > 1) && (0 != argv )) {
266	if( 1 == atoi( argv[1] ) )
267	wait_here = TRUE;
268	}
269
270	for(i = 0; i < SORTSET; i++)
271	data[SORTSET -1 -i] = drand48();
272
273	for(i = 0; i < SORTSET; i++)
274	if (debugging)
275	printf("data[%d] = %f\n", i, data[i]);
276
277	quick_sort(data, SORTSET);
278	for(i = 0; i < SORTSET; i++)
279	if (debugging)
280	printf("data[%d] = %f\n", i, data[i]);
281
282	return(0);
283	}
284	/* EndSourceFile */