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