gdb/testsuite/gdb.hp/quicksort.c

   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 */