URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [uclinux/] [uC-libc/] [misc/] [qsort.c] - Blame information for rev 199

Go to most recent revision | Details | Compare with Previous | View Log


/*
 * This file lifted in toto from 'Dlibs' on the atari ST  (RdeBath)
 *
 *
 *    Dale Schumacher                         399 Beacon Ave.
 *    (alias: Dalnefre')                      St. Paul, MN  55104
 *    dal@syntel.UUCP                         United States of America
 *  "It's not reality that's important, but how you perceive things."
 */
#include <string.h>
 
char *_qbuf = 0;         /* pointer to storage for qsort() */
 
#define PIVOT                   ((i+j)>>1)
#define moveitem(dst,src,size)  if(dst != src) memcpy(dst, src, size)
 
static
_wqsort(base, lo, hi, cmp)
register int *base;
register int lo;
register int hi;
register int (*cmp) ();
{
   int   k;
   register int i, j, t;
   register int *p = &k;
 
   while (hi > lo)
   {
      i = lo;
      j = hi;
      t = PIVOT;
      *p = base[t];
      base[t] = base[i];
      base[i] = *p;
      while (i < j)
      {
         while (((*cmp) ((base + j), p)) > 0)
            --j;
         base[i] = base[j];
         while ((i < j) && (((*cmp) ((base + i), p)) <= 0))
            ++i;
         base[j] = base[i];
      }
      base[i] = *p;
      if ((i - lo) < (hi - i))
      {
         _wqsort(base, lo, (i - 1), cmp);
         lo = i + 1;
      }
      else
      {
         _wqsort(base, (i + 1), hi, cmp);
         hi = i - 1;
      }
   }
}
 
static
_lqsort(base, lo, hi, cmp)
register long *base;
register int lo;
register int hi;
register int (*cmp) ();
{
   long  k;
   register int i, j, t;
   register long *p = &k;
 
   while (hi > lo)
   {
      i = lo;
      j = hi;
      t = PIVOT;
      *p = base[t];
      base[t] = base[i];
      base[i] = *p;
      while (i < j)
      {
         while (((*cmp) ((base + j), p)) > 0)
            --j;
         base[i] = base[j];
         while ((i < j) && (((*cmp) ((base + i), p)) <= 0))
            ++i;
         base[j] = base[i];
      }
      base[i] = *p;
      if ((i - lo) < (hi - i))
      {
         _lqsort(base, lo, (i - 1), cmp);
         lo = i + 1;
      }
      else
      {
         _lqsort(base, (i + 1), hi, cmp);
         hi = i - 1;
      }
   }
}
 
static
_nqsort(base, lo, hi, size, cmp)
register char *base;
register int lo;
register int hi;
register int size;
register int (*cmp) ();
{
   register int i, j;
   register char *p = _qbuf;
 
   while (hi > lo)
   {
      i = lo;
      j = hi;
      p = (base + size * PIVOT);
      moveitem(_qbuf, p, size);
      moveitem(p, (base + size * i), size);
      moveitem((base + size * i), _qbuf, size);
      p = _qbuf;
      while (i < j)
      {
         while (((*cmp) ((base + size * j), p)) > 0)
            --j;
         moveitem((base + size * i), (base + size * j), size);
         while ((i < j) && (((*cmp) ((base + size * i), p)) <= 0))
            ++i;
         moveitem((base + size * j), (base + size * i), size);
      }
      moveitem((base + size * i), p, size);
      if ((i - lo) < (hi - i))
      {
         _nqsort(base, lo, (i - 1), size, cmp);
         lo = i + 1;
      }
      else
      {
         _nqsort(base, (i + 1), hi, size, cmp);
         hi = i - 1;
      }
   }
}
 
qsort(base, num, size, cmp)
char *base;
int   num;
int   size;
int   (*cmp) ();
{
   char  _qtemp[128];
 
   if (_qbuf == 0)
   {
      if (size > sizeof(_qtemp))/* records too large! */
         return;
      _qbuf = _qtemp;
   }
   if (size == 2)
      _wqsort(base, 0, num - 1, cmp);
   else if (size == 4)
      _lqsort(base, 0, num - 1, cmp);
   else
      _nqsort(base, 0, num - 1, size, cmp);
   if (_qbuf == _qtemp)
      _qbuf = 0;
}

Line No.	Rev	Author	Line
1	199	simons	`/*`
2			`* This file lifted in toto from 'Dlibs' on the atari ST (RdeBath)`
3			`*`
4			`*`
5			`* Dale Schumacher 399 Beacon Ave.`
6			`* (alias: Dalnefre') St. Paul, MN 55104`
7			`* dal@syntel.UUCP United States of America`
8			`* "It's not reality that's important, but how you perceive things."`
9			`*/`
10			`#include <string.h>`
11
12			`char _qbuf = 0; / pointer to storage for qsort() */`
13
14			`#define PIVOT ((i+j)>>1)`
15			`#define moveitem(dst,src,size) if(dst != src) memcpy(dst, src, size)`
16
17			`static`
18			`_wqsort(base, lo, hi, cmp)`
19			`register int *base;`
20			`register int lo;`
21			`register int hi;`
22			`register int (*cmp) ();`
23			`{`
24			`int k;`
25			`register int i, j, t;`
26			`register int *p = &k;`
27
28			`while (hi > lo)`
29			`{`
30			`i = lo;`
31			`j = hi;`
32			`t = PIVOT;`
33			`*p = base[t];`
34			`base[t] = base[i];`
35			`base[i] = *p;`
36			`while (i < j)`
37			`{`
38			`while (((*cmp) ((base + j), p)) > 0)`
39			`--j;`
40			`base[i] = base[j];`
41			`while ((i < j) && (((*cmp) ((base + i), p)) <= 0))`
42			`++i;`
43			`base[j] = base[i];`
44			`}`
45			`base[i] = *p;`
46			`if ((i - lo) < (hi - i))`
47			`{`
48			`_wqsort(base, lo, (i - 1), cmp);`
49			`lo = i + 1;`
50			`}`
51			`else`
52			`{`
53			`_wqsort(base, (i + 1), hi, cmp);`
54			`hi = i - 1;`
55			`}`
56			`}`
57			`}`
58
59			`static`
60			`_lqsort(base, lo, hi, cmp)`
61			`register long *base;`
62			`register int lo;`
63			`register int hi;`
64			`register int (*cmp) ();`
65			`{`
66			`long k;`
67			`register int i, j, t;`
68			`register long *p = &k;`
69
70			`while (hi > lo)`
71			`{`
72			`i = lo;`
73			`j = hi;`
74			`t = PIVOT;`
75			`*p = base[t];`
76			`base[t] = base[i];`
77			`base[i] = *p;`
78			`while (i < j)`
79			`{`
80			`while (((*cmp) ((base + j), p)) > 0)`
81			`--j;`
82			`base[i] = base[j];`
83			`while ((i < j) && (((*cmp) ((base + i), p)) <= 0))`
84			`++i;`
85			`base[j] = base[i];`
86			`}`
87			`base[i] = *p;`
88			`if ((i - lo) < (hi - i))`
89			`{`
90			`_lqsort(base, lo, (i - 1), cmp);`
91			`lo = i + 1;`
92			`}`
93			`else`
94			`{`
95			`_lqsort(base, (i + 1), hi, cmp);`
96			`hi = i - 1;`
97			`}`
98			`}`
99			`}`
100
101			`static`
102			`_nqsort(base, lo, hi, size, cmp)`
103			`register char *base;`
104			`register int lo;`
105			`register int hi;`
106			`register int size;`
107			`register int (*cmp) ();`
108			`{`
109			`register int i, j;`
110			`register char *p = _qbuf;`
111
112			`while (hi > lo)`
113			`{`
114			`i = lo;`
115			`j = hi;`
116			`p = (base + size * PIVOT);`
117			`moveitem(_qbuf, p, size);`
118			`moveitem(p, (base + size * i), size);`
119			`moveitem((base + size * i), _qbuf, size);`
120			`p = _qbuf;`
121			`while (i < j)`
122			`{`
123			`while (((cmp) ((base + size j), p)) > 0)`
124			`--j;`
125			`moveitem((base + size * i), (base + size * j), size);`
126			`while ((i < j) && (((cmp) ((base + size i), p)) <= 0))`
127			`++i;`
128			`moveitem((base + size * j), (base + size * i), size);`
129			`}`
130			`moveitem((base + size * i), p, size);`
131			`if ((i - lo) < (hi - i))`
132			`{`
133			`_nqsort(base, lo, (i - 1), size, cmp);`
134			`lo = i + 1;`
135			`}`
136			`else`
137			`{`
138			`_nqsort(base, (i + 1), hi, size, cmp);`
139			`hi = i - 1;`
140			`}`
141			`}`
142			`}`
143
144			`qsort(base, num, size, cmp)`
145			`char *base;`
146			`int num;`
147			`int size;`
148			`int (*cmp) ();`
149			`{`
150			`char _qtemp[128];`
151
152			`if (_qbuf == 0)`
153			`{`
154			`if (size > sizeof(_qtemp))/* records too large! */`
155			`return;`
156			`_qbuf = _qtemp;`
157			`}`
158			`if (size == 2)`
159			`_wqsort(base, 0, num - 1, cmp);`
160			`else if (size == 4)`
161			`_lqsort(base, 0, num - 1, cmp);`
162			`else`
163			`_nqsort(base, 0, num - 1, size, cmp);`
164			`if (_qbuf == _qtemp)`
165			`_qbuf = 0;`
166			`}`

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [uclinux/] [uC-libc/] [misc/] [qsort.c] - Blame information for rev 199