Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/sort Delete more unwanted/unused cruft.
details: https://anonhg.NetBSD.org/src/rev/33ef84b53a91
branches: trunk
changeset: 746800:33ef84b53a91
user: dsl <dsl%NetBSD.org@localhost>
date: Thu Aug 20 06:36:25 2009 +0000
description:
Delete more unwanted/unused cruft.
Simplify logic for reading input records.
Do a merge sort whenever we have 16 partial sorted blocks.
The patient is breathing, but still carrying a lot of extra weight.
diffstat:
usr.bin/sort/append.c | 36 ++++------
usr.bin/sort/fields.c | 10 +-
usr.bin/sort/fsort.c | 164 +++++++++++++++++++------------------------------
usr.bin/sort/fsort.h | 12 +---
usr.bin/sort/msort.c | 21 ++----
usr.bin/sort/sort.c | 34 ++++++---
usr.bin/sort/sort.h | 10 +-
7 files changed, 121 insertions(+), 166 deletions(-)
diffs (truncated from 637 to 300 lines):
diff -r 0f27384bad2a -r 33ef84b53a91 usr.bin/sort/append.c
--- a/usr.bin/sort/append.c Thu Aug 20 03:49:34 2009 +0000
+++ b/usr.bin/sort/append.c Thu Aug 20 06:36:25 2009 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: append.c,v 1.18 2009/08/18 18:00:28 dsl Exp $ */
+/* $NetBSD: append.c,v 1.19 2009/08/20 06:36:25 dsl Exp $ */
/*-
* Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
@@ -64,7 +64,7 @@
#include "sort.h"
#ifndef lint
-__RCSID("$NetBSD: append.c,v 1.18 2009/08/18 18:00:28 dsl Exp $");
+__RCSID("$NetBSD: append.c,v 1.19 2009/08/20 06:36:25 dsl Exp $");
__SCCSID("@(#)append.c 8.1 (Berkeley) 6/6/93");
#endif /* not lint */
@@ -73,13 +73,8 @@
#define OUTPUT { \
if ((n = cpos - ppos) > 1) { \
- for (; ppos < cpos; ++ppos) \
- *ppos -= depth; \
ppos -= n; \
- if (stable_sort) \
- sradixsort(ppos, n, wts1, REC_D); \
- else \
- radixsort(ppos, n, wts1, REC_D); \
+ radix_sort(ppos, n, wts1, REC_D); \
for (; ppos < cpos; ppos++) { \
prec = (const RECHEADER *) (*ppos - REC_DATA_OFFSET);\
put(prec, fp); \
@@ -91,35 +86,36 @@
* copy sorted lines to output; check for uniqueness
*/
void
-append(const u_char **keylist, int nelem, int depth, FILE *fp, put_func_t put,
+append(const u_char **keylist, int nelem, FILE *fp, put_func_t put,
struct field *ftbl)
{
u_char *wts, *wts1;
int n;
- int hdr_off;
const u_char **cpos, **ppos, **lastkey;
const u_char *cend, *pend, *start;
const struct recheader *crec, *prec;
if (*keylist == '\0' && UNIQUE)
return;
+
wts1 = wts = ftbl[0].weights;
- if ((!UNIQUE) && SINGL_FLD) {
- if ((ftbl[0].flags & F) && (ftbl[0].flags & R))
+ if ((!UNIQUE) && SINGL_FLD && ftbl[0].flags & F) {
+ /* Folding case */
+ if (ftbl[0].flags & R)
wts1 = Rascii;
- else if (ftbl[0].flags & F)
+ else
wts1 = ascii;
}
+
lastkey = keylist + nelem;
- hdr_off = REC_DATA_OFFSET + depth;
if (SINGL_FLD && (UNIQUE || wts1 != wts)) {
ppos = keylist;
- prec = (const RECHEADER *) (*ppos - hdr_off);
+ prec = (const RECHEADER *) (*ppos - REC_DATA_OFFSET);
if (UNIQUE)
put(prec, fp);
for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
- crec = (const RECHEADER *) (*cpos - hdr_off);
- if (crec->length == prec->length) {
+ crec = (const RECHEADER *) (*cpos - REC_DATA_OFFSET);
+ if (crec->length == prec->length) {
/*
* Set pend and cend so that trailing NUL and
* record separator is ignored.
@@ -151,10 +147,10 @@
if (!UNIQUE) { OUTPUT; }
} else if (UNIQUE) {
ppos = keylist;
- prec = (const RECHEADER *) (*ppos - hdr_off);
+ prec = (const RECHEADER *) (*ppos - REC_DATA_OFFSET);
put(prec, fp);
for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
- crec = (const RECHEADER *) (*cpos - hdr_off);
+ crec = (const RECHEADER *) (*cpos - REC_DATA_OFFSET);
if (crec->offset == prec->offset) {
/*
* Set pend and cend so that trailing NUL and
@@ -179,7 +175,7 @@
}
}
} else for (cpos = keylist; cpos < lastkey; cpos++) {
- crec = (const RECHEADER *) (*cpos - hdr_off);
+ crec = (const RECHEADER *) (*cpos - REC_DATA_OFFSET);
put(crec, fp);
}
}
diff -r 0f27384bad2a -r 33ef84b53a91 usr.bin/sort/fields.c
--- a/usr.bin/sort/fields.c Thu Aug 20 03:49:34 2009 +0000
+++ b/usr.bin/sort/fields.c Thu Aug 20 06:36:25 2009 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: fields.c,v 1.23 2009/08/15 21:26:32 dsl Exp $ */
+/* $NetBSD: fields.c,v 1.24 2009/08/20 06:36:25 dsl Exp $ */
/*-
* Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
@@ -66,7 +66,7 @@
#include "sort.h"
#ifndef lint
-__RCSID("$NetBSD: fields.c,v 1.23 2009/08/15 21:26:32 dsl Exp $");
+__RCSID("$NetBSD: fields.c,v 1.24 2009/08/20 06:36:25 dsl Exp $");
__SCCSID("@(#)fields.c 8.1 (Berkeley) 6/6/93");
#endif /* not lint */
@@ -97,7 +97,8 @@
* followed by the original line.
*/
length_t
-enterkey(RECHEADER *keybuf, const u_char *keybuf_end, u_char *line_data, size_t line_size, struct field fieldtable[])
+enterkey(RECHEADER *keybuf, const u_char *keybuf_end, u_char *line_data,
+ size_t line_size, struct field fieldtable[])
/* keybuf: pointer to start of key */
{
int i;
@@ -169,7 +170,8 @@
* constructs a field (as defined by -k) within a key
*/
static u_char *
-enterfield(u_char *tablepos, const u_char *endkey, struct field *cur_fld, int gflags)
+enterfield(u_char *tablepos, const u_char *endkey, struct field *cur_fld,
+ int gflags)
{
u_char *start, *end, *lineend, *mask, *lweight;
struct column icol, tcol;
diff -r 0f27384bad2a -r 33ef84b53a91 usr.bin/sort/fsort.c
--- a/usr.bin/sort/fsort.c Thu Aug 20 03:49:34 2009 +0000
+++ b/usr.bin/sort/fsort.c Thu Aug 20 06:36:25 2009 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: fsort.c,v 1.37 2009/08/18 18:00:28 dsl Exp $ */
+/* $NetBSD: fsort.c,v 1.38 2009/08/20 06:36:25 dsl Exp $ */
/*-
* Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
@@ -72,7 +72,7 @@
#include "fsort.h"
#ifndef lint
-__RCSID("$NetBSD: fsort.c,v 1.37 2009/08/18 18:00:28 dsl Exp $");
+__RCSID("$NetBSD: fsort.c,v 1.38 2009/08/20 06:36:25 dsl Exp $");
__SCCSID("@(#)fsort.c 8.1 (Berkeley) 6/6/93");
#endif /* not lint */
@@ -82,149 +82,113 @@
static const u_char **keylist = 0;
u_char *buffer = 0;
size_t bufsize = DEFBUFSIZE;
-#define FSORTMAX 4
-int PANIC = FSORTMAX;
struct tempfile fstack[MAXFCT];
-#define MSTART (MAXFCT - MERGE_FNUM)
-#define CHECKFSTACK(n) \
- if (n >= MAXFCT) \
- errx(2, "fstack: too many temporary files; use -H or sort in pieces")
-
+
#define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1))
void
-fsort(int binno, int depth, int top, struct filelist *filelist, int nfiles,
- FILE *outfp, struct field *ftbl)
+fsort(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
{
- const u_char **keypos;
+ const u_char **keypos, **keyp;
u_char *bufend;
- u_char *weights;
- int ntfiles, mfct = 0;
+ int mfct = 0;
int c, nelem;
get_func_t get;
struct recheader *crec;
- struct field tfield[2];
u_char *nbuffer;
- memset(tfield, 0, sizeof(tfield));
- if (ftbl[0].flags & R)
- tfield[0].weights = Rascii;
- else
- tfield[0].weights = ascii;
- tfield[0].icol.num = 1;
- weights = ftbl[0].weights;
if (!buffer) {
buffer = malloc(bufsize);
keylist = malloc(MAXNUM * sizeof(u_char *));
memset(keylist, 0, MAXNUM * sizeof(u_char *));
}
bufend = buffer + bufsize;
+
if (SINGL_FLD)
+ /* Key and data are one! */
get = makeline;
else
+ /* Key (merged key fields) added before data */
get = makekey;
- c = nelem = ntfiles = 0; /* XXXGCC -Wuninitialized m68k */
- keypos = keylist; /* XXXGCC -Wuninitialized m68k */
- crec = (RECHEADER *) buffer; /* XXXGCC -Wuninitialized m68k */
- while (c != EOF) {
+ /* Loop through reads of chunk of input files that get sorted
+ * and then merged together. */
+ for (;;) {
keypos = keylist;
nelem = 0;
crec = (RECHEADER *) buffer;
- do_read:
- while ((c = get(-1, top, filelist, nfiles, crec,
- bufend, ftbl)) == 0) {
- *keypos++ = crec->data + depth;
- if (++nelem == MAXNUM) {
- c = BUFFEND;
+ /* Loop reading records */
+ for (;;) {
+ c = get(-1, 0, filelist, nfiles, crec, bufend, ftbl);
+ /* 'c' is 0, EOF or BUFFEND */
+ if (c == 0) {
+ /* Save start of key in input buffer */
+ *keypos++ = crec->data;
+ if (++nelem == MAXNUM) {
+ c = BUFFEND;
+ break;
+ }
+ crec = (RECHEADER *)((char *) crec +
+ SALIGN(crec->length) + REC_DATA_OFFSET);
+ continue;
+ }
+ if (c == EOF)
break;
- }
- crec =(RECHEADER *)((char *) crec +
- SALIGN(crec->length) + REC_DATA_OFFSET);
- }
+ if (nelem >= MAXNUM || bufsize >= MAXBUFSIZE)
+ /* Need to sort and save this lot of data */
+ break;
- if (c == BUFFEND && nelem < MAXNUM
- && bufsize < MAXBUFSIZE) {
- const u_char **keyp;
- u_char *oldb = buffer;
-
- /* buffer was too small for data, allocate
- * bigger buffer */
- nbuffer = realloc(buffer, bufsize * 2);
+ /* c == BUFFEND, and we can process more data */
+ /* Allocate a larger buffer for this lot of data */
+ bufsize *= 2;
+ nbuffer = realloc(buffer, bufsize);
if (!nbuffer) {
- err(2, "failed to realloc buffer to %lu bytes",
- (unsigned long) bufsize * 2);
+ err(2, "failed to realloc buffer to %zu bytes",
+ bufsize);
}
- buffer = nbuffer;
- bufsize *= 2;
- bufend = buffer + bufsize;
/* patch up keylist[] */
for (keyp = &keypos[-1]; keyp >= keylist; keyp--)
- *keyp = buffer + (*keyp - oldb);
+ *keyp = nbuffer + (*keyp - buffer);
- crec = (RECHEADER *) (buffer + ((u_char *)crec - oldb));
- goto do_read;
+ crec = (RECHEADER *) (nbuffer + ((u_char *)crec - buffer));
+ buffer = nbuffer;
+ bufend = buffer + bufsize;
}
- if (c != BUFFEND && !ntfiles && !mfct) {
- /* do not push */
- continue;
+ /* Sort this set of records */
+ if (radix_sort(keylist, nelem, ftbl[0].weights, REC_D))
+ err(2, NULL);
+
+ if (c == EOF && mfct == 0) {
+ /* all the data is (sorted) in the buffer */
+ append(keylist, nelem, outfp, putline, ftbl);
+ break;
}
Home |
Main Index |
Thread Index |
Old Index