1
2 #include <sys/types.h>
3
4 #if defined INTEGERTIME || defined CLOCKTIME || defined PosixTime
5 # include <time.h>
6 #elif defined EnhTime
7 # include <windows.h>
8 #else
9 # include <sys/time.h>
10 #endif
11
12 #include <stdlib.h>
13 #include <stdio.h>
14 #ifdef WIN32
15 # include <io.h> /* Used in file search functions */
16 #endif
17 #include <ctype.h>
18 #include <string.h>
19 #include <float.h>
20 #include <math.h>
21 #include "commonlib.h"
22
23 #ifdef FORTIFY
24 # include "lp_fortify.h"
25 #endif
26
27 #if defined FPUexception
28 /* FPU exception masks */
clearFPU()29 unsigned int clearFPU()
30 {
31 return( _clearfp() );
32 }
resetFPU(unsigned int mask)33 unsigned int resetFPU(unsigned int mask)
34 {
35 _clearfp();
36 mask = _controlfp( mask, 0xfffff);
37 return( mask );
38 }
catchFPU(unsigned int mask)39 unsigned int catchFPU(unsigned int mask)
40 {
41 /* Always call _clearfp before enabling/unmasking a FPU exception */
42 unsigned int u = _clearfp();
43
44 /* Set the new mask by not-and'ing it with the previous settings */
45 u = _controlfp(0, 0);
46 mask = u & ~mask;
47 mask = _controlfp(mask, _MCW_EM);
48
49 /* Return the previous mask */
50 return( u );
51 }
52 #endif
53
54 /* Math operator equivalence function */
intpow(int base,int exponent)55 int intpow(int base, int exponent)
56 {
57 int result = 1;
58 while(exponent > 0) {
59 result *= base;
60 exponent--;
61 }
62 while(exponent < 0) {
63 result /= base;
64 exponent++;
65 }
66 return( result );
67 }
mod(int n,int d)68 int mod(int n, int d)
69 {
70 return(n % d);
71 }
72
73 /* Some string functions */
strtoup(char * s)74 void strtoup(char *s)
75 {
76 if(s != NULL)
77 while (*s) {
78 *s = toupper(*s);
79 s++;
80 }
81 }
strtolo(char * s)82 void strtolo(char *s)
83 {
84 if(s != NULL)
85 while (*s) {
86 *s = tolower(*s);
87 s++;
88 }
89 }
strcpyup(char * t,char * s)90 void strcpyup(char *t, char *s)
91 {
92 if((s != NULL) && (t != NULL)) {
93 while (*s) {
94 *t = toupper(*s);
95 t++;
96 s++;
97 }
98 *t = '\0';
99 }
100 }
strcpylo(char * t,char * s)101 void strcpylo(char *t, char *s)
102 {
103 if((s != NULL) && (t != NULL)) {
104 while (*s) {
105 *t = tolower(*s);
106 t++;
107 s++;
108 }
109 *t = '\0';
110 }
111 }
112
113 /* Unix library naming utility function */
so_stdname(char * stdname,char * descname,int buflen)114 MYBOOL so_stdname(char *stdname, char *descname, int buflen)
115 {
116 char *ptr;
117
118 if((descname == NULL) || (stdname == NULL) || (((int) strlen(descname)) >= buflen - 6))
119 return( FALSE );
120
121 strcpy(stdname, descname);
122 if((ptr = strrchr(descname, '/')) == NULL)
123 ptr = descname;
124 else
125 ptr++;
126 stdname[(int) (ptr - descname)] = 0;
127 if(strncmp(ptr, "lib", 3))
128 strcat(stdname, "lib");
129 strcat(stdname, ptr);
130 if(strcmp(stdname + strlen(stdname) - 3, ".so"))
131 strcat(stdname, ".so");
132 return( TRUE );
133 }
134
135 /* Return the greatest common divisor of a and b, or -1 if it is
136 not defined. Return through the pointer arguments the integers
137 such that gcd(a,b) = c*a + b*d. */
gcd(LLONG a,LLONG b,int * c,int * d)138 int gcd(LLONG a, LLONG b, int *c, int *d)
139 {
140 LLONG q,r,t;
141 int cret,dret,C,D,rval, sgn_a = 1,sgn_b = 1, swap = 0;
142
143 if((a == 0) || (b == 0))
144 return( -1 );
145
146 /* Use local multiplier instances, if necessary */
147 if(c == NULL)
148 c = &cret;
149 if(d == NULL)
150 d = &dret;
151
152 /* Normalize so that 0 < a <= b */
153 if(a < 0){
154 a = -a;
155 sgn_a = -1;
156 }
157 if(b < 0){
158 b = -b;
159 sgn_b = -1;
160 }
161 if(b < a){
162 t = b;
163 b = a;
164 a = t;
165 swap = 1;
166 }
167
168 /* Now a <= b and both >= 1. */
169 q = b/a;
170 r = b - a*q;
171 if(r == 0) {
172 if(swap){
173 *d = 1;
174 *c = 0;
175 }
176 else {
177 *c = 1;
178 *d = 0;
179 }
180 *c = sgn_a*(*c);
181 *d = sgn_b*(*d);
182 return( (int) a );
183 }
184
185 rval = gcd(a,r,&C,&D);
186 if(swap){
187 *d = (int) (C-D*q);
188 *c = D;
189 }
190 else {
191 *d = D;
192 *c = (int) (C-D*q);
193 }
194 *c = sgn_a*(*c);
195 *d = sgn_b*(*d);
196 return( rval );
197 }
198
199 /* Array search functions */
findIndex(int target,int * attributes,int count,int offset)200 int findIndex(int target, int *attributes, int count, int offset)
201 {
202 int focusPos, beginPos, endPos;
203 int focusAttrib, beginAttrib, endAttrib;
204
205 /* Set starting and ending index offsets */
206 beginPos = offset;
207 endPos = beginPos + count - 1;
208 if(endPos < beginPos)
209 return(-1);
210
211 /* Do binary search logic based on a sorted (decending) attribute vector */
212 focusPos = (beginPos + endPos) / 2;
213 beginAttrib = attributes[beginPos];
214 focusAttrib = attributes[focusPos];
215 endAttrib = attributes[endPos];
216
217 while(endPos - beginPos > LINEARSEARCH) {
218 if(beginAttrib == target) {
219 focusAttrib = beginAttrib;
220 endPos = beginPos;
221 }
222 else if(endAttrib == target) {
223 focusAttrib = endAttrib;
224 beginPos = endPos;
225 }
226 else if(focusAttrib < target) {
227 beginPos = focusPos + 1;
228 beginAttrib = attributes[beginPos];
229 focusPos = (beginPos + endPos) / 2;
230 focusAttrib = attributes[focusPos];
231 }
232 else if(focusAttrib > target) {
233 endPos = focusPos - 1;
234 endAttrib = attributes[endPos];
235 focusPos = (beginPos + endPos) / 2;
236 focusAttrib = attributes[focusPos];
237 }
238 else {
239 beginPos = focusPos;
240 endPos = focusPos;
241 }
242 }
243
244 /* Do linear (unsorted) search logic */
245 if(endPos - beginPos <= LINEARSEARCH) {
246
247 /* CPU intensive loop; provide alternative evaluation models */
248 #if defined DOFASTMATH
249 /* Do fast pointer arithmetic */
250 int *attptr = attributes + beginPos;
251 while((beginPos < endPos) && ((*attptr) < target)) {
252 beginPos++;
253 attptr++;
254 }
255 focusAttrib = (*attptr);
256 #else
257 /* Do traditional indexed access */
258 focusAttrib = attributes[beginPos];
259 while((beginPos < endPos) && (focusAttrib < target)) {
260 beginPos++;
261 focusAttrib = attributes[beginPos];
262 }
263 #endif
264 }
265
266 /* Return the index if a match was found, or signal failure with a -1 */
267 if(focusAttrib == target) /* Found; return retrieval index */
268 return(beginPos);
269 else if(focusAttrib > target) /* Not found; last item */
270 return(-beginPos);
271 else if(beginPos > offset+count-1)
272 return(-(endPos+1)); /* Not found; end of list */
273 else
274 return(-(beginPos+1)); /* Not found; intermediate point */
275
276 }
findIndexEx(void * target,void * attributes,int count,int offset,int recsize,findCompare_func findCompare,MYBOOL ascending)277 int findIndexEx(void *target, void *attributes, int count, int offset, int recsize, findCompare_func findCompare, MYBOOL ascending)
278 {
279 int focusPos, beginPos, endPos, compare, order;
280 void *focusAttrib, *beginAttrib, *endAttrib;
281
282 /* Set starting and ending index offsets */
283 beginPos = offset;
284 endPos = beginPos + count - 1;
285 if(endPos < beginPos)
286 return(-1);
287 order = (ascending ? -1 : 1);
288
289 /* Do binary search logic based on a sorted attribute vector */
290 focusPos = (beginPos + endPos) / 2;
291 beginAttrib = CMP_ATTRIBUTES(beginPos);
292 focusAttrib = CMP_ATTRIBUTES(focusPos);
293 endAttrib = CMP_ATTRIBUTES(endPos);
294
295 compare = 0;
296 while(endPos - beginPos > LINEARSEARCH) {
297 if(findCompare(target, beginAttrib) == 0) {
298 focusAttrib = beginAttrib;
299 endPos = beginPos;
300 }
301 else if(findCompare(target, endAttrib) == 0) {
302 focusAttrib = endAttrib;
303 beginPos = endPos;
304 }
305 else {
306 compare = findCompare(target, focusAttrib)*order;
307 if(compare < 0) {
308 beginPos = focusPos + 1;
309 beginAttrib = CMP_ATTRIBUTES(beginPos);
310 focusPos = (beginPos + endPos) / 2;
311 focusAttrib = CMP_ATTRIBUTES(focusPos);
312 }
313 else if(compare > 0) {
314 endPos = focusPos - 1;
315 endAttrib = CMP_ATTRIBUTES(endPos);
316 focusPos = (beginPos + endPos) / 2;
317 focusAttrib = CMP_ATTRIBUTES(focusPos);
318 }
319 else {
320 beginPos = focusPos;
321 endPos = focusPos;
322 }
323 }
324 }
325
326 /* Do linear (unsorted) search logic */
327 if(endPos - beginPos <= LINEARSEARCH) {
328
329 /* Do traditional indexed access */
330 focusAttrib = CMP_ATTRIBUTES(beginPos);
331 if(beginPos == endPos)
332 compare = findCompare(target, focusAttrib)*order;
333 else
334 while((beginPos < endPos) &&
335 ((compare = findCompare(target, focusAttrib)*order) < 0)) {
336 beginPos++;
337 focusAttrib = CMP_ATTRIBUTES(beginPos);
338 }
339 }
340
341 /* Return the index if a match was found, or signal failure with a -1 */
342 if(compare == 0) /* Found; return retrieval index */
343 return(beginPos);
344 else if(compare > 0) /* Not found; last item */
345 return(-beginPos);
346 else if(beginPos > offset+count-1)
347 return(-(endPos+1)); /* Not found; end of list */
348 else
349 return(-(beginPos+1)); /* Not found; intermediate point */
350
351 }
352
353 /* Simple sorting and searching comparison "operators" */
compareCHAR(const void * current,const void * candidate)354 int CMP_CALLMODEL compareCHAR(const void *current, const void *candidate)
355 {
356 return( CMP_COMPARE( *(char *) current, *(char *) candidate ) );
357 }
compareINT(const void * current,const void * candidate)358 int CMP_CALLMODEL compareINT(const void *current, const void *candidate)
359 {
360 return( CMP_COMPARE( *(int *) current, *(int *) candidate ) );
361 }
compareREAL(const void * current,const void * candidate)362 int CMP_CALLMODEL compareREAL(const void *current, const void *candidate)
363 {
364 return( CMP_COMPARE( *(REAL *) current, *(REAL *) candidate ) );
365 }
366
367 /* Heap sort function (procedurally based on the Numerical Recipes version,
368 but expanded and generalized to hande any object with the use of
369 qsort-style comparison operator). An expanded version is also implemented,
370 where interchanges are reflected in a caller-initialized integer "tags" list. */
hpsort(void * attributes,int count,int offset,int recsize,MYBOOL descending,findCompare_func findCompare)371 void hpsort(void *attributes, int count, int offset, int recsize, MYBOOL descending, findCompare_func findCompare)
372 {
373 register int i, j, k, ir, order;
374 register char *hold, *base;
375 char *save;
376
377 if(count < 2)
378 return;
379 offset -= 1;
380 attributes = CMP_ATTRIBUTES(offset);
381 base = CMP_ATTRIBUTES(1);
382 save = (char *) malloc(recsize);
383 if(descending)
384 order = -1;
385 else
386 order = 1;
387
388 k = (count >> 1) + 1;
389 ir = count;
390
391 for(;;) {
392 if(k > 1) {
393 MEMCOPY(save, CMP_ATTRIBUTES(--k), recsize);
394 }
395 else {
396 hold = CMP_ATTRIBUTES(ir);
397 MEMCOPY(save, hold, recsize);
398 MEMCOPY(hold, base, recsize);
399 if(--ir == 1) {
400 MEMCOPY(base, save, recsize);
401 break;
402 }
403 }
404
405 i = k;
406 j = k << 1;
407 while(j <= ir) {
408 hold = CMP_ATTRIBUTES(j);
409 if( (j < ir) && (findCompare(hold, CMP_ATTRIBUTES(j+1))*order < 0) ) {
410 hold += recsize;
411 j++;
412 }
413 if(findCompare(save, hold)*order < 0) {
414 MEMCOPY(CMP_ATTRIBUTES(i), hold, recsize);
415 i = j;
416 j <<= 1;
417 }
418 else
419 break;
420 }
421 MEMCOPY(CMP_ATTRIBUTES(i), save, recsize);
422 }
423
424 FREE(save);
425 }
hpsortex(void * attributes,int count,int offset,int recsize,MYBOOL descending,findCompare_func findCompare,int * tags)426 void hpsortex(void *attributes, int count, int offset, int recsize, MYBOOL descending, findCompare_func findCompare, int *tags)
427 {
428 if(count < 2)
429 return;
430 if(tags == NULL) {
431 hpsort(attributes, count, offset, recsize, descending, findCompare);
432 return;
433 }
434 else {
435 register int i, j, k, ir, order;
436 register char *hold, *base;
437 char *save;
438 int savetag;
439
440 offset -= 1;
441 attributes = CMP_ATTRIBUTES(offset);
442 tags += offset;
443 base = CMP_ATTRIBUTES(1);
444 save = (char *) malloc(recsize);
445 if(descending)
446 order = -1;
447 else
448 order = 1;
449
450 k = (count >> 1) + 1;
451 ir = count;
452
453 for(;;) {
454 if(k > 1) {
455 MEMCOPY(save, CMP_ATTRIBUTES(--k), recsize);
456 savetag = tags[k];
457 }
458 else {
459 hold = CMP_ATTRIBUTES(ir);
460 MEMCOPY(save, hold, recsize);
461 MEMCOPY(hold, base, recsize);
462 savetag = tags[ir];
463 tags[ir] = tags[1];
464 if(--ir == 1) {
465 MEMCOPY(base, save, recsize);
466 tags[1] = savetag;
467 break;
468 }
469 }
470
471 i = k;
472 j = k << 1;
473 while(j <= ir) {
474 hold = CMP_ATTRIBUTES(j);
475 if( (j < ir) && (findCompare(hold, CMP_ATTRIBUTES(j+1))*order < 0) ) {
476 hold += recsize;
477 j++;
478 }
479 if(findCompare(save, hold)*order < 0) {
480 MEMCOPY(CMP_ATTRIBUTES(i), hold, recsize);
481 tags[i] = tags[j];
482 i = j;
483 j <<= 1;
484 }
485 else
486 break;
487 }
488 MEMCOPY(CMP_ATTRIBUTES(i), save, recsize);
489 tags[i] = savetag;
490 }
491
492 FREE(save);
493 }
494 }
495
496 /* This is a "specialized generic" version of C.A.R Hoare's Quick Sort algorithm.
497 It will handle arrays that are already sorted, and arrays with duplicate keys.
498 There are two versions here; one extended conventional with optional tag data
499 for each sortable value, and a version for the QSORTrec format. The QSORTrec
500 format i.a. includes the ability for to do linked list sorting. If the passed
501 comparison operator is NULL, the comparison is assumed to be for integers. */
502 #define QS_IS_switch LINEARSEARCH /* Threshold for switching to insertion sort */
503
qsortex_swap(void * attributes,int l,int r,int recsize,void * tags,int tagsize,char * save,char * savetag)504 void qsortex_swap(void *attributes, int l, int r, int recsize,
505 void *tags, int tagsize, char *save, char *savetag)
506 {
507 MEMCOPY(save, CMP_ATTRIBUTES(l), recsize);
508 MEMCOPY(CMP_ATTRIBUTES(l), CMP_ATTRIBUTES(r), recsize);
509 MEMCOPY(CMP_ATTRIBUTES(r), save, recsize);
510 if(tags != NULL) {
511 MEMCOPY(savetag, CMP_TAGS(l), tagsize);
512 MEMCOPY(CMP_TAGS(l), CMP_TAGS(r), tagsize);
513 MEMCOPY(CMP_TAGS(r), savetag, tagsize);
514 }
515 }
516
qsortex_sort(void * attributes,int l,int r,int recsize,int sortorder,findCompare_func findCompare,void * tags,int tagsize,char * save,char * savetag)517 int qsortex_sort(void *attributes, int l, int r, int recsize, int sortorder, findCompare_func findCompare,
518 void *tags, int tagsize, char *save, char *savetag)
519 {
520 register int i, j, nmove = 0;
521 char *v;
522
523 /* Perform the a fast QuickSort */
524 if((r-l) > QS_IS_switch) {
525 i = (r+l)/2;
526
527 /* Tri-Median Method */
528 if(sortorder*findCompare(CMP_ATTRIBUTES(l), CMP_ATTRIBUTES(i)) > 0)
529 { nmove++; qsortex_swap(attributes, l,i, recsize, tags, tagsize, save, savetag); }
530 if(sortorder*findCompare(CMP_ATTRIBUTES(l), CMP_ATTRIBUTES(r)) > 0)
531 { nmove++; qsortex_swap(attributes, l,r, recsize, tags, tagsize, save, savetag); }
532 if(sortorder*findCompare(CMP_ATTRIBUTES(i), CMP_ATTRIBUTES(r)) > 0)
533 { nmove++; qsortex_swap(attributes, i,r, recsize, tags, tagsize, save, savetag); }
534
535 j = r-1;
536 qsortex_swap(attributes, i,j, recsize, tags, tagsize, save, savetag);
537 i = l;
538 v = CMP_ATTRIBUTES(j);
539 for(;;) {
540 while(sortorder*findCompare(CMP_ATTRIBUTES(++i), v) < 0);
541 while(sortorder*findCompare(CMP_ATTRIBUTES(--j), v) > 0);
542 if(j < i) break;
543 nmove++; qsortex_swap(attributes, i,j, recsize, tags, tagsize, save, savetag);
544 }
545 nmove++; qsortex_swap(attributes, i,r-1, recsize, tags, tagsize, save, savetag);
546 nmove += qsortex_sort(attributes, l,j, recsize, sortorder, findCompare, tags, tagsize, save, savetag);
547 nmove += qsortex_sort(attributes, i+1,r, recsize, sortorder, findCompare, tags, tagsize, save, savetag);
548 }
549 return( nmove );
550 }
551
qsortex_finish(void * attributes,int lo0,int hi0,int recsize,int sortorder,findCompare_func findCompare,void * tags,int tagsize,char * save,char * savetag)552 int qsortex_finish(void *attributes, int lo0, int hi0, int recsize, int sortorder, findCompare_func findCompare,
553 void *tags, int tagsize, char *save, char *savetag)
554 {
555 int i, j, nmove = 0;
556
557 /* This is actually InsertionSort, which is faster for local sorts */
558 for(i = lo0+1; i <= hi0; i++) {
559
560 /* Save bottom-most item */
561 MEMCOPY(save, CMP_ATTRIBUTES(i), recsize);
562 if(tags != NULL)
563 MEMCOPY(savetag, CMP_TAGS(i), tagsize);
564
565 /* Shift down! */
566 j = i;
567 while ((j > lo0) && (sortorder*findCompare(CMP_ATTRIBUTES(j-1), save) > 0)) {
568 MEMCOPY(CMP_ATTRIBUTES(j), CMP_ATTRIBUTES(j-1), recsize);
569 if(tags != NULL)
570 MEMCOPY(CMP_TAGS(j), CMP_TAGS(j-1), tagsize);
571 j--;
572 nmove++;
573 }
574
575 /* Store bottom-most item at the top */
576 MEMCOPY(CMP_ATTRIBUTES(j), save, recsize);
577 if(tags != NULL)
578 MEMCOPY(CMP_TAGS(j), savetag, tagsize);
579 }
580 return( nmove );
581 }
582
qsortex(void * attributes,int count,int offset,int recsize,MYBOOL descending,findCompare_func findCompare,void * tags,int tagsize)583 int qsortex(void *attributes, int count, int offset, int recsize, MYBOOL descending, findCompare_func findCompare, void *tags, int tagsize)
584 {
585 int iswaps = 0, sortorder = (descending ? -1 : 1);
586 char *save = NULL, *savetag = NULL;
587
588 /* Check and initialize to zero-based arrays */
589 if(count <= 1)
590 goto Finish;
591 attributes = (void *) CMP_ATTRIBUTES(offset);
592 save = (char *) malloc(recsize);
593 if((tagsize <= 0) && (tags != NULL))
594 tags = NULL;
595 else if(tags != NULL) {
596 tags = (void *) CMP_TAGS(offset);
597 savetag = (char *) malloc(tagsize);
598 }
599 count--;
600
601 /* Perform sort */
602 iswaps = qsortex_sort(attributes, 0, count, recsize, sortorder, findCompare, tags, tagsize, save, savetag);
603 #if QS_IS_switch > 0
604 iswaps += qsortex_finish(attributes, 0, count, recsize, sortorder, findCompare, tags, tagsize, save, savetag);
605 #endif
606
607 Finish:
608 FREE(save);
609 FREE(savetag);
610 return( iswaps );
611 }
612
613 #undef QS_IS_switch
614
615 /* This is a "specialized generic" version of C.A.R Hoare's Quick Sort algorithm.
616 It will handle arrays that are already sorted, and arrays with duplicate keys.
617 The implementation here requires the user to pass a comparison operator and
618 assumes that the array passed has the QSORTrec format, which i.a. includes
619 the ability for to do linked list sorting. If the passed comparison operator
620 is NULL, the comparison is assumed to be for integers. */
621 #define QS_IS_switch 4 /* Threshold for switching to insertion sort */
622
QS_swap(UNIONTYPE QSORTrec a[],int i,int j)623 void QS_swap(UNIONTYPE QSORTrec a[], int i, int j)
624 {
625 UNIONTYPE QSORTrec T = a[i];
626 a[i] = a[j];
627 a[j] = T;
628 }
QS_addfirst(UNIONTYPE QSORTrec a[],void * mydata)629 int QS_addfirst(UNIONTYPE QSORTrec a[], void *mydata)
630 {
631 a[0].pvoid2.ptr = mydata;
632 return( 0 );
633 }
QS_append(UNIONTYPE QSORTrec a[],int ipos,void * mydata)634 int QS_append(UNIONTYPE QSORTrec a[], int ipos, void *mydata)
635 {
636 if(ipos <= 0)
637 ipos = QS_addfirst(a, mydata);
638 else
639 a[ipos].pvoid2.ptr = mydata;
640 return( ipos );
641 }
QS_replace(UNIONTYPE QSORTrec a[],int ipos,void * mydata)642 void QS_replace(UNIONTYPE QSORTrec a[], int ipos, void *mydata)
643 {
644 a[ipos].pvoid2.ptr = mydata;
645 }
QS_insert(UNIONTYPE QSORTrec a[],int ipos,void * mydata,int epos)646 void QS_insert(UNIONTYPE QSORTrec a[], int ipos, void *mydata, int epos)
647 {
648 for(; epos > ipos; epos--)
649 a[epos] = a[epos-1];
650 a[ipos].pvoid2.ptr = mydata;
651 }
QS_delete(UNIONTYPE QSORTrec a[],int ipos,int epos)652 void QS_delete(UNIONTYPE QSORTrec a[], int ipos, int epos)
653 {
654 for(; epos > ipos; epos--)
655 a[epos] = a[epos-1];
656 }
QS_sort(UNIONTYPE QSORTrec a[],int l,int r,findCompare_func findCompare)657 int QS_sort(UNIONTYPE QSORTrec a[], int l, int r, findCompare_func findCompare)
658 {
659 register int i, j, nmove = 0;
660 UNIONTYPE QSORTrec v;
661
662 /* Perform the a fast QuickSort */
663 if((r-l) > QS_IS_switch) {
664 i = (r+l)/2;
665
666 /* Tri-Median Method */
667 if(findCompare((char *) &a[l], (char *) &a[i]) > 0)
668 { nmove++; QS_swap(a,l,i); }
669 if(findCompare((char *) &a[l], (char *) &a[r]) > 0)
670 { nmove++; QS_swap(a,l,r); }
671 if(findCompare((char *) &a[i], (char *) &a[r]) > 0)
672 { nmove++; QS_swap(a,i,r); }
673
674 j = r-1;
675 QS_swap(a,i,j);
676 i = l;
677 v = a[j];
678 for(;;) {
679 while(findCompare((char *) &a[++i], (char *) &v) < 0);
680 while(findCompare((char *) &a[--j], (char *) &v) > 0);
681 if(j < i) break;
682 nmove++; QS_swap (a,i,j);
683 }
684 nmove++; QS_swap(a,i,r-1);
685 nmove += QS_sort(a,l,j,findCompare);
686 nmove += QS_sort(a,i+1,r,findCompare);
687 }
688 return( nmove );
689 }
QS_finish(UNIONTYPE QSORTrec a[],int lo0,int hi0,findCompare_func findCompare)690 int QS_finish(UNIONTYPE QSORTrec a[], int lo0, int hi0, findCompare_func findCompare)
691 {
692 int i, j, nmove = 0;
693 UNIONTYPE QSORTrec v;
694
695 /* This is actually InsertionSort, which is faster for local sorts */
696 for(i = lo0+1; i <= hi0; i++) {
697
698 /* Save bottom-most item */
699 v = a[i];
700
701 /* Shift down! */
702 j = i;
703 while ((j > lo0) && (findCompare((char *) &a[j-1], (char *) &v) > 0)) {
704 a[j] = a[j-1];
705 j--;
706 nmove++;
707 }
708
709 /* Store bottom-most item at the top */
710 a[j] = v;
711 }
712 return( nmove );
713 }
QS_execute(UNIONTYPE QSORTrec a[],int count,findCompare_func findCompare,int * nswaps)714 MYBOOL QS_execute(UNIONTYPE QSORTrec a[], int count, findCompare_func findCompare, int *nswaps)
715 {
716 int iswaps = 0;
717
718 /* Check and initialize */
719 if(count <= 1)
720 goto Finish;
721 count--;
722
723 /* Perform sort */
724 iswaps = QS_sort(a, 0, count, findCompare);
725 #if QS_IS_switch > 0
726 iswaps += QS_finish(a, 0, count, findCompare);
727 #endif
728
729 Finish:
730 if(nswaps != NULL)
731 *nswaps = iswaps;
732 return( TRUE );
733 }
734
735
736
737 /* Simple specialized bubble/insertion sort functions */
sortByREAL(int * item,REAL * weight,int size,int offset,MYBOOL unique)738 int sortByREAL(int *item, REAL *weight, int size, int offset, MYBOOL unique)
739 {
740 int i, ii, saveI;
741 REAL saveW;
742
743 for(i = 1; i < size; i++) {
744 ii = i+offset-1;
745 while ((ii >= offset) && (weight[ii] >= weight[ii+1])) {
746 if(weight[ii] == weight[ii+1]) {
747 if(unique)
748 return(item[ii]);
749 }
750 else {
751 saveI = item[ii];
752 saveW = weight[ii];
753 item[ii] = item[ii+1];
754 weight[ii] = weight[ii+1];
755 item[ii+1] = saveI;
756 weight[ii+1] = saveW;
757 }
758 ii--;
759 }
760 }
761 return(0);
762 }
sortByINT(int * item,int * weight,int size,int offset,MYBOOL unique)763 int sortByINT(int *item, int *weight, int size, int offset, MYBOOL unique)
764 {
765 int i, ii, saveI;
766 int saveW;
767
768 for(i = 1; i < size; i++) {
769 ii = i+offset-1;
770 while ((ii >= offset) && (weight[ii] >= weight[ii+1])) {
771 if(weight[ii] == weight[ii+1]) {
772 if(unique)
773 return(item[ii]);
774 }
775 else {
776 saveI = item[ii];
777 saveW = weight[ii];
778 item[ii] = item[ii+1];
779 weight[ii] = weight[ii+1];
780 item[ii+1] = saveI;
781 weight[ii+1] = saveW;
782 }
783 ii--;
784 }
785 }
786 return(0);
787 }
sortREALByINT(REAL * item,int * weight,int size,int offset,MYBOOL unique)788 REAL sortREALByINT(REAL *item, int *weight, int size, int offset, MYBOOL unique)
789 {
790 int i, ii, saveW;
791 REAL saveI;
792
793 for(i = 1; i < size; i++) {
794 ii = i+offset-1;
795 while ((ii >= offset) && (weight[ii] >= weight[ii+1])) {
796 if(weight[ii] == weight[ii+1]) {
797 if(unique)
798 return(item[ii]);
799 }
800 else {
801 saveI = item[ii];
802 saveW = weight[ii];
803 item[ii] = item[ii+1];
804 weight[ii] = weight[ii+1];
805 item[ii+1] = saveI;
806 weight[ii+1] = saveW;
807 }
808 ii--;
809 }
810 }
811 return(0);
812 }
813
814
815 /* Time and message functions */
timeNow(void)816 double timeNow(void)
817 {
818 #ifdef INTEGERTIME
819 return((double)time(NULL));
820 #elif defined CLOCKTIME
821 return((double)clock()/CLOCKS_PER_SEC /* CLK_TCK */);
822 #elif defined PosixTime
823 struct timespec t;
824 # if 0
825 clock_gettime(CLOCK_REALTIME, &t);
826 return( (double) t.tv_sec + (double) t.tv_nsec/1.0e9 );
827 # else
828 static double timeBase;
829
830 clock_gettime(CLOCK_MONOTONIC, &t);
831 if(timeBase == 0)
832 timeBase = clockNow() - ((double) t.tv_sec + (double) t.tv_nsec/1.0e9);
833 return( timeBase + (double) t.tv_sec + (double) t.tv_nsec/1.0e9 );
834 # endif
835 #elif defined EnhTime
836 static LARGE_INTEGER freq;
837 static double timeBase;
838 LARGE_INTEGER now;
839
840 QueryPerformanceCounter(&now);
841 if(timeBase == 0) {
842 QueryPerformanceFrequency(&freq);
843 timeBase = clockNow() - (double) now.QuadPart/(double) freq.QuadPart;
844 }
845 return( timeBase + (double) now.QuadPart/(double) freq.QuadPart );
846 #else
847 struct timeval tv;
848 struct timezone tz;
849
850 gettimeofday(&tv, &tz);
851 return((double)tv.tv_sec+((double)tv.tv_usec)/1000000.0);
852
853 #endif
854 }
855
856
857 /* Miscellaneous reporting functions */
858
859 /* List a vector of INT values for the given index range */
blockWriteINT(FILE * output,char * label,int * myvector,int first,int last)860 void blockWriteINT(FILE *output, char *label, int *myvector, int first, int last)
861 {
862 int i, k = 0;
863
864 fprintf(output, "%s", label);
865 fprintf(output, "\n");
866 for(i = first; i <= last; i++) {
867 fprintf(output, " %5d", myvector[i]);
868 k++;
869 if(k % 12 == 0) {
870 fprintf(output, "\n");
871 k = 0;
872 }
873 }
874 if(k % 12 != 0)
875 fprintf(output, "\n");
876 }
877
878 /* List a vector of MYBOOL values for the given index range */
blockWriteBOOL(FILE * output,char * label,MYBOOL * myvector,int first,int last,MYBOOL asRaw)879 void blockWriteBOOL(FILE *output, char *label, MYBOOL *myvector, int first, int last, MYBOOL asRaw)
880 {
881 int i, k = 0;
882
883 fprintf(output, "%s", label);
884 fprintf(output, "\n");
885 for(i = first; i <= last; i++) {
886 if(asRaw)
887 fprintf(output, " %1d", myvector[i]);
888 else
889 fprintf(output, " %5s", my_boolstr(myvector[i]));
890 k++;
891 if(k % 36 == 0) {
892 fprintf(output, "\n");
893 k = 0;
894 }
895 }
896 if(k % 36 != 0)
897 fprintf(output, "\n");
898 }
899
900 /* List a vector of REAL values for the given index range */
blockWriteREAL(FILE * output,char * label,REAL * myvector,int first,int last)901 void blockWriteREAL(FILE *output, char *label, REAL *myvector, int first, int last)
902 {
903 int i, k = 0;
904
905 fprintf(output, "%s", label);
906 fprintf(output, "\n");
907 for(i = first; i <= last; i++) {
908 fprintf(output, " %18g", myvector[i]);
909 k++;
910 if(k % 4 == 0) {
911 fprintf(output, "\n");
912 k = 0;
913 }
914 }
915 if(k % 4 != 0)
916 fprintf(output, "\n");
917 }
918
919
920 /* CONSOLE vector and matrix printing routines */
printvec(int n,REAL * x,int modulo)921 void printvec( int n, REAL *x, int modulo )
922 {
923 int i;
924
925 if (modulo <= 0) modulo = 5;
926 for (i = 1; i<=n; i++) {
927 if(mod(i, modulo) == 1)
928 printf("\n%2d:%12g", i, x[i]);
929 else
930 printf(" %2d:%12g", i, x[i]);
931 }
932 if(i % modulo != 0) printf("\n");
933 }
934
935
printmatUT(int size,int n,REAL * U,int modulo)936 void printmatUT( int size, int n, REAL *U, int modulo)
937 {
938 int i, ll;
939 ll = 0;
940 for(i = 1; i<=n; i++) {
941 printvec(n-i+1, &U[ll], modulo);
942 ll += size-i+1;
943 }
944 }
945
946
printmatSQ(int size,int n,REAL * X,int modulo)947 void printmatSQ( int size, int n, REAL *X, int modulo)
948 {
949 int i, ll;
950 ll = 0;
951 for(i = 1; i<=n; i++) {
952 printvec(n, &X[ll], modulo);
953 ll += size;
954 }
955 }
956
957 /* Miscellaneous file functions */
958 #if defined _MSC_VER
959 /* Check MS versions before 7 */
960 #if _MSC_VER < 1300
961 # define intptr_t long
962 #endif
963
fileCount(char * filemask)964 int fileCount( char *filemask )
965 {
966 struct _finddata_t c_file;
967 intptr_t hFile;
968 int count = 0;
969
970 /* Find first .c file in current directory */
971 if( (hFile = _findfirst( filemask, &c_file )) == -1L )
972 ;
973 /* Iterate over all matching names */
974 else {
975 while( _findnext( hFile, &c_file ) == 0 )
976 count++;
977 _findclose( hFile );
978 }
979 return( count );
980 }
fileSearchPath(char * envvar,char * searchfile,char * foundpath)981 MYBOOL fileSearchPath( char *envvar, char *searchfile, char *foundpath )
982 {
983 char pathbuffer[_MAX_PATH];
984
985 _searchenv( searchfile, envvar, pathbuffer );
986 if(pathbuffer[0] == '\0')
987 return( FALSE );
988 else {
989 if(foundpath != NULL)
990 strcpy(foundpath, pathbuffer);
991 return( TRUE );
992 }
993 }
994 #endif
995