* The Regents of the University of California. All rights reserved.
* This code is derived from software contributed to Berkeley by
* %sccs.include.redist.c%
static char sccsid
[] = "@(#)msort.c 8.1 (Berkeley) %G%";
/* Subroutines using comparisons: merge sort and check order */
#define LALIGN(n) ((n+3) & ~3)
struct trecheader rec
[1];
static int cmp
__P((struct recheader
*, struct recheader
*));
static int insert
__P((struct mfile
**, struct mfile
**, int, int));
fmerge(binno
, files
, nfiles
, get
, outfd
, fput
, ftbl
)
void (*put
)(struct recheader
*, FILE *);
struct tempfile
*l_fstack
;
if (!UNIQUE
&& SINGL_FLD
&& ftbl
->flags
& F
)
wts1
= (ftbl
->flags
& R
) ? Rascii
: ascii
;
cfilebuf
= malloc(MAXLLEN
+ sizeof(TMFILE
));
i
= min(16, nfiles
) * LALIGN(MAXLLEN
+sizeof(TMFILE
));
if (!buffer
|| i
> BUFSIZE
) {
buffer
= buffer
? realloc(buffer
, i
) : malloc(i
);
linebuf
= malloc(MAXLLEN
);
l_fstack
= fstack
+ files
.top
;
for (j
= 0; j
< nfiles
; j
+= 16) {
last
= min(16, nfiles
- j
);
for (i
= 0; i
< last
; i
++)
if (!(l_fstack
[i
+MAXFCT
-1-16].fd
=
fopen(files
.names
[j
+ i
], "r")))
err(2, "%s", files
.names
[j
+i
]);
merge(MAXFCT
-1-16, last
, get
, tout
, put
, ftbl
);
for (i
= 0; i
< last
; i
++)
rewind(l_fstack
[i
+j
].fd
);
merge(files
.top
+j
, last
, get
, tout
, put
, ftbl
);
if (nfiles
> 16) l_fstack
[j
/16].fd
= tout
;
nfiles
= (nfiles
+ 15) / 16;
merge(infl0
, nfiles
, get
, outfd
, put
, ftbl
)
void (*put
)(struct recheader
*, FILE *);
union f_handle dummy
= {0};
struct mfile
*flist
[16], *cfile
;
for (i
= j
= 0; i
< nfiles
; i
++) {
cfile
= (MFILE
*) (buffer
+
i
* LALIGN(MAXLLEN
+ sizeof(TMFILE
)));
cfile
->end
= cfile
->rec
->data
+ MAXLLEN
;
if (EOF
== (c
= get(j
+infl0
, dummy
, nfiles
,
cfile
->rec
, cfile
->end
, ftbl
))) {
c
= insert(flist
, &cfile
, i
, !DELETE
);
cfile
->flno
= flist
[0]->flno
;
cfile
->end
= cfile
->rec
->data
+ MAXLLEN
;
if (EOF
== (c
= get(cfile
->flno
, dummy
, nfiles
,
cfile
->rec
, cfile
->end
, ftbl
))) {
put(flist
[0]->rec
, outfd
);
memmove(flist
, flist
+ 1,
sizeof(MFILE
*) * (--nfiles
));
cfile
->flno
= flist
[0]->flno
;
if (!(c
= insert(flist
, &cfile
, nfiles
, DELETE
)))
* if delete: inserts *rec in flist, deletes flist[0], and leaves it in *rec;
* otherwise just inserts *rec in flist.
insert(flist
, rec
, ttop
, delete)
struct mfile
**flist
, **rec
;
int delete, ttop
; /* delete = 0 or 1 */
register struct mfile
*tmprec
;
register int top
, mid
, bot
= 0, cmpv
= 1;
for (mid
= top
/2; bot
+1 != top
; mid
= (bot
+top
)/2) {
cmpv
= cmp(tmprec
->rec
, flist
[mid
]->rec
);
cmpv
= cmp(tmprec
->rec
, flist
[0]->rec
);
memmove(flist
, flist
+1, bot
* sizeof(MFILE
**));
(*rec
)->flno
= (*flist
)->flno
;
if (!bot
&& !(UNIQUE
&& !cmpv
)) {
cmpv
= cmp(tmprec
->rec
, flist
[0]->rec
);
memmove(flist
+ bot
+1, flist
+ bot
,
(ttop
- bot
) * sizeof(MFILE
**));
* check order on one file
struct recheader
*crec
, *prec
, *trec
;
linebuf
= malloc(MAXLLEN
);
buffer
= malloc(2 * (MAXLLEN
+ sizeof(TRECHEADER
)));
end
= buffer
+ 2 * (MAXLLEN
+ sizeof(TRECHEADER
));
crec
= (RECHEADER
*) buffer
;
prec
= (RECHEADER
*) (buffer
+ MAXLLEN
+ sizeof(TRECHEADER
));
if (SINGL_FLD
&& ftbl
->flags
& F
)
wts1
= ftbl
->flags
& R
? Rascii
: ascii
;
if (0 == get(-1, infile
, 1, prec
, end
, ftbl
))
while (0 == get(-1, infile
, 1, crec
, end
, ftbl
)) {
if (0 < (c
= cmp(prec
, crec
))) {
crec
->data
[crec
->length
-1] = 0;
errx(1, "found disorder: %s", crec
->data
+crec
->offset
);
crec
->data
[crec
->length
-1] = 0;
errx(1, "found non-uniqueness: %s",
crec
->data
+crec
->offset
);
struct recheader
*rec1
, *rec2
;
register u_char
*pos1
, *pos2
, *end
;
for (cwts
= wts
; cwts
; cwts
= (cwts
== wts1
? 0 : wts1
)) {
if (!SINGL_FLD
&& UNIQUE
)
end
= pos1
+ min(rec1
->offset
, rec2
->offset
);
end
= pos1
+ min(rec1
->length
, rec2
->length
);
if (r
= cwts
[*pos1
++] - cwts
[*pos2
++])