43 #include "Ifpack_config.h"
52 void ifpack_multilist_sort (
int *
const pbase,
double *
const daux,
size_t total_elems);
61 for (i=0; i<QSORTLEN; i++)
64 d[i] = (double) -h[i];
67 printf(
"before sorting\n");
68 for (i=0; i<QSORTLEN; i++)
69 printf(
"%d %f\n", h[i], d[i]);
71 ifpack_multilist_sort(h, d, QSORTLEN);
73 printf(
"after sorting\n");
74 for (i=0; i<QSORTLEN; i++)
75 printf(
"%d %f\n", h[i], d[i]);
108 dtemp = daux[a-pbase]; \
109 daux[a-pbase] = daux[b-pbase]; \
110 daux[b-pbase] = dtemp; \
125 #define STACK_SIZE (8 * sizeof(unsigned long int))
126 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
127 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
128 #define STACK_NOT_EMPTY (stack < top)
154 void ifpack_multilist_sort (
int *
const pbase,
double *
const daux,
size_t total_elems)
158 const size_t size = 1;
159 register int *base_ptr = (
int *) pbase;
164 const size_t max_thresh = MAX_THRESH * size;
167 if (total_elems <= 0)
171 if (total_elems > MAX_THRESH)
174 int *hi = &lo[size * (total_elems - 1)];
179 while (STACK_NOT_EMPTY)
184 int *pivot = pivot_buffer;
191 int *mid = lo + size * ((hi - lo) / size >> 1);
203 pivot = pivot_buffer;
205 left_ptr = lo + size;
206 right_ptr = hi - size;
213 while (*left_ptr - *pivot < 0)
216 while (*pivot - *right_ptr < 0)
219 if (left_ptr < right_ptr)
221 SWAP (left_ptr, right_ptr);
225 else if (left_ptr == right_ptr)
232 while (left_ptr <= right_ptr);
239 if ((
size_t) (right_ptr - lo) <= max_thresh)
241 if ((
size_t) (hi - left_ptr) <= max_thresh)
248 else if ((
size_t) (hi - left_ptr) <= max_thresh)
251 else if ((right_ptr - lo) > (hi - left_ptr))
254 PUSH (lo, right_ptr);
272 #define min(x, y) ((x) < (y) ? (x) : (y))
275 int *
const end_ptr = &base_ptr[size * (total_elems - 1)];
276 int *tmp_ptr = base_ptr;
277 int *thresh = min(end_ptr, base_ptr + max_thresh);
278 register int *run_ptr;
284 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
285 if (*run_ptr - *tmp_ptr < 0)
288 if (tmp_ptr != base_ptr)
289 SWAP (tmp_ptr, base_ptr);
293 run_ptr = base_ptr + size;
294 while ((run_ptr += size) <= end_ptr)
296 tmp_ptr = run_ptr - size;
297 while (*run_ptr - *tmp_ptr < 0)
301 if (tmp_ptr != run_ptr)
305 trav = run_ptr + size;
306 while (--trav >= run_ptr)
309 double c2 = daux[trav-pbase];
313 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
316 daux[hi-pbase] = daux[lo-pbase];