summaryrefslogtreecommitdiff
path: root/gdb/testsuite/gdb.hp/quicksort.c
diff options
context:
space:
mode:
Diffstat (limited to 'gdb/testsuite/gdb.hp/quicksort.c')
-rw-r--r--gdb/testsuite/gdb.hp/quicksort.c284
1 files changed, 284 insertions, 0 deletions
diff --git a/gdb/testsuite/gdb.hp/quicksort.c b/gdb/testsuite/gdb.hp/quicksort.c
new file mode 100644
index 00000000000..b44b828a8d5
--- /dev/null
+++ b/gdb/testsuite/gdb.hp/quicksort.c
@@ -0,0 +1,284 @@
+/* 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 */
View Lorry Controller Status