Debian Codegraph @

lib/database/src/so/nodes/nurbs/libnurbs/sorter.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 /*
38 * sorter.c++ - $Revision: 1.1.1.1 $
39 * Derrick Burns - 1991
40 */
41
42 #include "glimports.h"
43 #include "sorter.h"
44 #include "mystdio.h"
45
46 Sorter::Sorter( int _es )
47 {
48 es = _es;
49 }
50
51 void
52 Sorter::qsort( void *a, int n )
53 {
54 qs1( (char *)a, ((char *)a)+n*es);
55 }
56
57 int
58 Sorter::qscmp( char *, char * )
59 {
60 dprintf( "Sorter::qscmp: pure virtual called\n" );
61 return 0;
62 }
63
64
65 void
66 Sorter::qsexc( char *, char * )
67 {
68 dprintf( "Sorter::qsexc: pure virtual called\n" );
69 }
70
71
72 void
73 Sorter::qstexc( char *, char *, char * )
74 {
75 dprintf( "Sorter::qstexc: pure virtual called\n" );
76 }
77
78 void
79 Sorter::qs1( char *a, char *l )
80 {
81 char *i, *j;
82 char *lp, *hp;
83 int c;
84 unsigned int n;
85
86 start:
87 if((n=l-a) <= es)
88 return;
89 n = es * (n / (2*es));
90 hp = lp = a+n;
91 i = a;
92 j = l-es;
93 while(1) {
94 if(i < lp) {
95 if((c = qscmp(i, lp)) == 0) {
96 qsexc(i, lp -= es);
97 continue;
98 }
99 if(c < 0) {
100 i += es;
101 continue;
102 }
103 }
104
105 loop:
106 if(j > hp) {
107 if((c = qscmp(hp, j)) == 0) {
108 qsexc(hp += es, j);
109 goto loop;
110 }
111 if(c > 0) {
112 if(i == lp) {
113 qstexc(i, hp += es, j);
114 i = lp += es;
115 goto loop;
116 }
117 qsexc(i, j);
118 j -= es;
119 i += es;
120 continue;
121 }
122 j -= es;
123 goto loop;
124 }
125
126 if(i == lp) {
127 if(lp-a >= l-hp) {
128 qs1(hp+es, l);
129 l = lp;
130 } else {
131 qs1(a, lp);
132 a = hp+es;
133 }
134 goto start;
135 }
136
137 qstexc(j, lp -= es, i);
138 j = hp -= es;
139 }
140 }
141