Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit33b3c95

Browse files
committed
Complete TODO item:
* -Add BSD-licensed qsort() for Solaris
1 parentd7d741a commit33b3c95

File tree

6 files changed

+239
-11
lines changed

6 files changed

+239
-11
lines changed

‎configure

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11902,6 +11902,13 @@ case $host_os in
1190211902
esac
1190311903
1190411904
11905+
# Set path of qsort for solaris, which has a very slow qsort in certain cases.
11906+
QSORT=""
11907+
case$host_osin
11908+
solaris*) DLLINIT='$(top_builddir)/src/backend/port/qsort.o' ;;
11909+
esac
11910+
11911+
1190511912
# On HPUX 9, rint() is not in regular libm.a but in /lib/pa1.1/libm.a;
1190611913
# this hackery with HPUXMATHLIB allows us to cope.
1190711914
HPUXMATHLIB=""
@@ -17584,6 +17591,7 @@ s,@STRTOL@,$STRTOL,;t t
1758417591
s,@STRTOUL@,$STRTOUL,;t t
1758517592
s,@STRCASECMP@,$STRCASECMP,;t t
1758617593
s,@DLLINIT@,$DLLINIT,;t t
17594+
s,@QSORT@,$QSORT,;t t
1758717595
s,@HPUXMATHLIB@,$HPUXMATHLIB,;t t
1758817596
s,@HAVE_POSIX_SIGNALS@,$HAVE_POSIX_SIGNALS,;t t
1758917597
s,@MSGFMT@,$MSGFMT,;t t

‎configure.in

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
dnl Process this file with autoconf to produce a configure script.
2-
dnl $Header: /cvsroot/pgsql/configure.in,v 1.192 2002/07/18 04:13:59 momjian Exp $
2+
dnl $Header: /cvsroot/pgsql/configure.in,v 1.193 2002/07/19 17:35:09 momjian Exp $
33
dnl
44
dnl Developers, please strive to achieve this order:
55
dnl
@@ -932,6 +932,13 @@ case $host_os in
932932
esac
933933
AC_SUBST(DLLINIT)
934934

935+
# Set path of qsort for solaris, which has a very slow qsort in certain cases.
936+
QSORT=""
937+
case $host_os in
938+
solaris*) DLLINIT='$(top_builddir)/src/backend/port/qsort.o' ;;
939+
esac
940+
AC_SUBST(QSORT)
941+
935942
# On HPUX 9, rint() is not in regular libm.a but in /lib/pa1.1/libm.a;
936943
# this hackery with HPUXMATHLIB allows us to cope.
937944
HPUXMATHLIB=""

‎src/Makefile.global.in

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
# -*-makefile-*-
2-
# $Header: /cvsroot/pgsql/src/Makefile.global.in,v 1.150 2002/07/18 04:30:36 momjian Exp $
2+
# $Header: /cvsroot/pgsql/src/Makefile.global.in,v 1.151 2002/07/19 17:35:10 momjian Exp $
33

44
#------------------------------------------------------------------------------
55
# All PostgreSQL makefiles include this file and use the variables it sets,
@@ -352,6 +352,7 @@ INET_ATON = @INET_ATON@
352352
ISINF = @ISINF@
353353
MEMCMP = @MEMCMP@
354354
MISSING_RANDOM = @MISSING_RANDOM@
355+
QSORT = @QSORT@
355356
SNPRINTF = @SNPRINTF@
356357
SRANDOM = @SRANDOM@
357358
STRCASECMP = @STRCASECMP@
@@ -360,7 +361,7 @@ STRERROR = @STRERROR@
360361
STRTOL = @STRTOL@
361362
STRTOUL = @STRTOUL@
362363

363-
#Usedby the backend
364+
#Not really standard libc functions, usedby the backend.
364365
DLLINIT = @DLLINIT@
365366
TAS = @TAS@
366367

‎src/backend/port/Makefile

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,15 +13,19 @@
1313
# be converted to Method 2.
1414
#
1515
# IDENTIFICATION
16-
# $Header: /cvsroot/pgsql/src/backend/port/Makefile,v 1.16 2002/07/18 04:13:59 momjian Exp $
16+
# $Header: /cvsroot/pgsql/src/backend/port/Makefile,v 1.17 2002/07/19 17:35:11 momjian Exp $
1717
#
1818
#-------------------------------------------------------------------------
1919

2020
subdir = src/backend/port
2121
top_builddir = ../../..
2222
include$(top_builddir)/src/Makefile.global
2323

24-
OBJS=dynloader.o pg_sema.o pg_shmem.o
24+
OBJS=$(GETHOSTNAME)$(GETRUSAGE)$(INET_ATON)$(ISINF)$(MEMCMP)\
25+
$(MISSING_RANDOM)$(QSORT)$(SNPRINTF)$(SRANDOM)$(STRCASECMP)\
26+
$(STRDUP)$(STRERROR)$(STRTOL)$(STRTOUL)
27+
28+
OBJS+=dynloader.o pg_sema.o pg_shmem.o
2529

2630
OBJS+=$(DLLINIT)
2731

‎src/port/Makefile

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -7,17 +7,17 @@
77
# with broken/missing library files.
88

99
# IDENTIFICATION
10-
# $Header: /cvsroot/pgsql/src/port/Makefile,v 1.1 2002/07/18 04:13:59 momjian Exp $
10+
# $Header: /cvsroot/pgsql/src/port/Makefile,v 1.2 2002/07/19 17:35:11 momjian Exp $
1111
#
1212
#-------------------------------------------------------------------------
1313

1414
subdir = src/port
1515
top_builddir = ../..
1616
include$(top_builddir)/src/Makefile.global
1717

18-
OBJS=$(GETHOSTNAME)$(GETRUSAGE)$(INET_ATON)$(ISINF)$(MEMCMP)\
19-
$(MISSING_RANDOM)$(SNPRINTF)$(SRANDOM)$(STRCASECMP)$(STRDUP)\
20-
$(STRERROR)$(STRTOL)$(STRTOUL)
2118

22-
distcleanclean:
23-
rm -f$(OBJS)
19+
#
20+
# The backend/port directory removes these files.
21+
#
22+
#distclean clean:
23+
#rm -f $(OBJS)

‎src/port/qsort.c

Lines changed: 208 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,208 @@
1+
/*
2+
* Copied from NetBSD CVS, 2002-07-19, bjm
3+
* Add do ... while() macro fix
4+
* Remove __inline, _DIAGASSERTs
5+
*/
6+
7+
/*$NetBSD: qsort.c,v 1.12 1999/09/20 04:39:40 lukem Exp $ */
8+
9+
/*-
10+
* Copyright (c) 1992, 1993
11+
*The Regents of the University of California. All rights reserved.
12+
*
13+
* Redistribution and use in source and binary forms, with or without
14+
* modification, are permitted provided that the following conditions
15+
* are met:
16+
* 1. Redistributions of source code must retain the above copyright
17+
* notice, this list of conditions and the following disclaimer.
18+
* 2. Redistributions in binary form must reproduce the above copyright
19+
* notice, this list of conditions and the following disclaimer in the
20+
* documentation and/or other materials provided with the distribution.
21+
* 3. All advertising materials mentioning features or use of this software
22+
* must display the following acknowledgement:
23+
*This product includes software developed by the University of
24+
*California, Berkeley and its contributors.
25+
* 4. Neither the name of the University nor the names of its contributors
26+
* may be used to endorse or promote products derived from this software
27+
* without specific prior written permission.
28+
*
29+
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30+
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31+
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32+
* ARE DISCLAIMED.IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33+
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34+
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35+
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36+
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37+
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38+
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39+
* SUCH DAMAGE.
40+
*/
41+
42+
#include<sys/cdefs.h>
43+
#include<sys/types.h>
44+
45+
#include<assert.h>
46+
#include<errno.h>
47+
#include<stdlib.h>
48+
49+
staticchar*med3__P((char*,char*,char*,
50+
int (*) (constvoid*,constvoid*)));
51+
staticvoidswapfunc__P((char*,char*,size_t,int));
52+
53+
#definemin(a,b)(a) < (b) ? a : b
54+
55+
/*
56+
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
57+
*/
58+
#defineswapcode(TYPE,parmi,parmj,n) \
59+
do {\
60+
size_t i = (n) / sizeof (TYPE);\
61+
TYPE *pi = (TYPE *)(void *)(parmi);\
62+
TYPE *pj = (TYPE *)(void *)(parmj);\
63+
do {\
64+
TYPEt = *pi;\
65+
*pi++ = *pj;\
66+
*pj++ = t;\
67+
} while (--i > 0);\
68+
} while (0)
69+
70+
#defineSWAPINIT(a,es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
71+
es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
72+
73+
staticvoid
74+
swapfunc(a,b,n,swaptype)
75+
char*a,
76+
*b;
77+
size_tn;
78+
intswaptype;
79+
{
80+
if (swaptype <=1)
81+
swapcode(long,a,b,n);
82+
else
83+
swapcode(char,a,b,n);
84+
}
85+
86+
#defineswap(a,b)\
87+
if (swaptype == 0) {\
88+
long t = *(long *)(void *)(a);\
89+
*(long *)(void *)(a) = *(long *)(void *)(b);\
90+
*(long *)(void *)(b) = t;\
91+
} else\
92+
swapfunc(a, b, es, swaptype)
93+
94+
#definevecswap(a,b,n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
95+
96+
staticchar*
97+
med3(a,b,c,cmp)
98+
char*a,
99+
*b,
100+
*c;
101+
int(*cmp)__P((constvoid*,constvoid*));
102+
{
103+
returncmp(a,b)<0 ?
104+
(cmp(b,c)<0 ?b : (cmp(a,c)<0 ?c :a))
105+
: (cmp(b,c)>0 ?b : (cmp(a,c)<0 ?a :c));
106+
}
107+
108+
void
109+
qsort(a,n,es,cmp)
110+
void*a;
111+
size_tn,
112+
es;
113+
int(*cmp)__P((constvoid*,constvoid*));
114+
{
115+
char*pa,
116+
*pb,
117+
*pc,
118+
*pd,
119+
*pl,
120+
*pm,
121+
*pn;
122+
intd,
123+
r,
124+
swaptype,
125+
swap_cnt;
126+
127+
loop:SWAPINIT(a,es);
128+
swap_cnt=0;
129+
if (n<7)
130+
{
131+
for (pm= (char*)a+es;pm< (char*)a+n*es;pm+=es)
132+
for (pl=pm;pl> (char*)a&&cmp(pl-es,pl)>0;
133+
pl-=es)
134+
swap(pl,pl-es);
135+
return;
136+
}
137+
pm= (char*)a+ (n /2)*es;
138+
if (n>7)
139+
{
140+
pl= (char*)a;
141+
pn= (char*)a+ (n-1)*es;
142+
if (n>40)
143+
{
144+
d= (n /8)*es;
145+
pl=med3(pl,pl+d,pl+2*d,cmp);
146+
pm=med3(pm-d,pm,pm+d,cmp);
147+
pn=med3(pn-2*d,pn-d,pn,cmp);
148+
}
149+
pm=med3(pl,pm,pn,cmp);
150+
}
151+
swap(a,pm);
152+
pa=pb= (char*)a+es;
153+
154+
pc=pd= (char*)a+ (n-1)*es;
155+
for (;;)
156+
{
157+
while (pb <=pc&& (r=cmp(pb,a)) <=0)
158+
{
159+
if (r==0)
160+
{
161+
swap_cnt=1;
162+
swap(pa,pb);
163+
pa+=es;
164+
}
165+
pb+=es;
166+
}
167+
while (pb <=pc&& (r=cmp(pc,a)) >=0)
168+
{
169+
if (r==0)
170+
{
171+
swap_cnt=1;
172+
swap(pc,pd);
173+
pd-=es;
174+
}
175+
pc-=es;
176+
}
177+
if (pb>pc)
178+
break;
179+
swap(pb,pc);
180+
swap_cnt=1;
181+
pb+=es;
182+
pc-=es;
183+
}
184+
if (swap_cnt==0)
185+
{/* Switch to insertion sort */
186+
for (pm= (char*)a+es;pm< (char*)a+n*es;pm+=es)
187+
for (pl=pm;pl> (char*)a&&cmp(pl-es,pl)>0;
188+
pl-=es)
189+
swap(pl,pl-es);
190+
return;
191+
}
192+
193+
pn= (char*)a+n*es;
194+
r=min(pa- (char*)a,pb-pa);
195+
vecswap(a,pb-r,r);
196+
r=min(pd-pc,pn-pd-es);
197+
vecswap(pb,pn-r,r);
198+
if ((r=pb-pa)>es)
199+
qsort(a,r /es,es,cmp);
200+
if ((r=pd-pc)>es)
201+
{
202+
/* Iterate rather than recurse to save stack space */
203+
a=pn-r;
204+
n=r /es;
205+
gotoloop;
206+
}
207+
/*qsort(pn - r, r / es, es, cmp);*/
208+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp