.fp 5 CW

.TH RECSORT 3

.SH NAME

\fBRecsort\fR \- sorting records

.SH SYNOPSIS

.de Tp

.fl

.ne 2

.TP

..

.de Ss

.fl

.ne 2

.SS "\\$1"

..

.de Cs

.nf

.ft 5

..

.de Ce

.ft 1

.fi

..

.ta 1.0i 2.0i 3.0i 4.0i 5.0i

.Cs

#include <recsort.h>

#define uchar unsigned char

#define ulong unsigned long

.Ce

.Ss "RECSORT TYPES"

.Cs

Rs_t;

Rsdisc_t;

Rsmethod_t;

Rsobj_t;

.Ce

.Ss "OPENING/CLOSING SORT CONTEXTS"

.Cs

Rs_t* rsopen(Rsdisc_t* disc, Rsmethod_t* meth, ssize_t c_max, int type);

int rsclose(Rs_t* rs);

void rsclear(Rs_t* rs);

.Ce

.Ss "SORT METHODS"

.Cs

Rsmethod_t* Rsradix;

Rsmethod_t* Rssplay;

Rsmethod_t* Rsrasp;

Rsmethod_t* Rsverify;

Rsmethod_t* rsmethod(Rs_t* rs, Rsmethod_t* meth);

.Ce

.Ss "SORT DISCIPLINE"

.Cs

Rsdisc_t* rsdisc(Rs_t* rs, Rsdisc_t* disc);

typedef ssize_t (*Rsdefkey_f)(Rs_t* rs, Void_t* data, size_t s_data,

Void_t* key, size_t s_key, Rsdisc_t* disc);

typedef int (*Rsevent_f)(Rs_t* rs, int type, Void_t* data, Rsdisc_t* disc);

typedef struct

{ int type; /* RS_KSAMELEN|RS_DSAMELEN */

ssize_t data; /* data length or separator */

ssize_t key; /* key offset or expansion factor */

ssize_t keylen; /* key length or key end offset */

Rsdefdey_f defkeyf; /* function to define a key */

} Rsdisc_t;

.Ce

.Ss "OBJECT OPERATIONS"

.Cs

ssize_t rsprocess(Rs_t* rs, Void_t* data, ssize_t size);

ssize_t rscount(rs);

Rsobj_t* rslist(Rs_t* rs);

int rswrite(Rs_t* rs, Sfio_t* f, int type);

int rsmerge(Rs_t* rs, Sfio_t* f, Sfio_t** files, int n, int type);

.Ce

.SH DESCRIPTION

.PP

\fIRecsort\fP provides functions to sort strings in main memory and

to merge sorted data from different files.

These functions form a sort engine suitable for constructing

programs such as \fB/bin/sort\fP(1).

.PP

.Ss "RECSORT TYPES"

.PP

.Ss " Rs_t"

This defines the type of a sorting context handle.

.PP

.Ss " Rsdisc_t"

This defines the type of a discipline structure which describes

how keys are defined.

.PP

.Ss " Rsmethod_t"

This defines the type of a sorting method.

.PP

.Ss " Rsobj_t"

This is the type of a record to be sorted.

It contains the following fields:

.Cs

ulong order;

Rsobj_t* left;

Rsobj_t* right;

Rsobj_t* equal;

uchar* key;

ssize_t keylen;

uchar* data;

ssize_t datalen;

.Ce

.Tp

\f5order, left\fP:

These fields are only significant in calls to event functions

raised by method \f5Rsverify\fP.

.Tp

\f5right, equal\fP:

The \f5rslist()\fP call returns a linked list of sorted records.

\f5obj->right\fP defines the forward link for \f5obj\fP.

\f5obj->equal\fP, if not \f5NULL\fP,

points to a \f5NULL\fP-terminated linked list of records

compared equal to \f5obj\fP.

.Tp

\f5key, keylen, data, datalen\fP:

These fields define the key and data of the given record.

.PP

.Ss "OPENING/CLOSING SORT CONTEXTS"

.PP

.Ss " Rs_t* rsopen(Rsdisc_t* disc, Rsmethod_t* meth, ssize_t c_max, int type)"

This function creates a new sort context based on discipline \f5disc\fP

and sort method \f5meth\fP.

\f5rsopen()\fP returns the new sort context or \f5NULL\fP on error.

.Tp

\f5c_max\fP:

Due to memory cache behavior, it is sometimes worthwhile to limit

the amount of data sorted by a sort method at any given time.

Data across calls to \f5rsprocess()\fP accumulated for a sort method

is limited as follows.

If \f5c_max < 0\fP, there is no limit.

If \f5c_max = 0\fP, each \f5rsprocess()\fP call sorts data separately.

If \f5c_max > 0\fP, data will be accumulated up to \f5c_max\fP before sorted.

Thus, when \f5c_max >= 0\fP, many sorted list of records may result.

These lists will be merged together in a \f5rslist()\fP or \f5rswrite()\fP call.

.Tp

\f5type\fP:

This is a bit combination of:

(1) \f5RS_UNIQ\fP, keeping only one in a set of duplicated records,

(2) \f5RS_REVERSE\fP, sorting records in reverse order, and

(3) \f5RS_DATA\fP, comparing records by keys, then by data.

.PP

.Ss " int rsclose(Rs_t* rs)"

This deletes \f5rs\fP and associated memory.

If the discipline has an event function, the event \f5RS_CLOSE\fP will

be raised first. If the event funtion returns a negative value, \f5rsclose()\fP

will return the same value immediately.

\f5rsclose()\fP returns 0 on success.

.PP

.Ss " void rsclear(Rs_t* rs)"

This frees memory in \f5rs\fP without closing \f5rs\fP.

.PP

.Ss "SORT METHODS"

.PP

Sort methods are of type \f5Rsmethod_t*\fP.

The fields \f5int Rsmethod_t.type\fP and \f5char* Rsmethod_t.name\fP

contain the method type and name respectively.

.PP

.Ss " Rsradix"

This is radix sort.

Records are partitioned in phases by byte values.

.PP

.Ss " Rssplay"

Records are inserted into a top-down splay tree.

.PP

.Ss " Rsrasp"

This is a combination of radix sort and splay trees.

Records are partitioned by first bytes of their keys.

Then, groups with short keys are sorted using radix sort

while groups with long keys are sorted in splay trees.

A final merge phase collects everything together.

.PP

.Ss " Rsverify"

This method is used to verify if data is sorted.

When a record is out of order,

the event \f5RS_VERIFY\fP will be announced (see \f5Rsdisc_t.eventf\fP).

.PP

.Ss " Rsmethod_t* rsmethod(Rs_t* rs, Rsmethod_t* meth)"

If \f5meth\fP is not \f5NULL\fP,

\f5rsmethod()\fP changes the sort method of \f5rs\fP to \f5meth\fP.

This should be done only when there are no partially sorted records in \f5rs\fP,

i.e., before any \f5rsprocess()\fP call or immediately after a \f5rsclear()\fP call.

\f5rsmethod()\fP returns the old method on success and \f5NULL\fP on failure.

.PP

.Ss "SORT DISCIPLINE"

.PP

Object key management is defined in the type \f5Rsdisc_t\fP:

.Cs

typedef struct

{ int type;

ssize_t data;

ssize_t key;

ssize_t keylen;

Rsdefkey_f defkeyf;

Rsevent_f eventf;

} Rsdisc_t;

.Ce

.PP

.Ss " Rsdisc_t.type"

This should be a bit combination of \f5RS_KSAMELEN\fP and \f5RS_DSAMELEN\fP to

indicate respectively that keys and data have constant lengths.

.PP

.Ss " Rsdisc_t.data"

If \f5type&RS_DSAMELEN\fP, \f5Rsdisc_t.data\fP is the length of the data of a record.

Otherwise, \f5Rsdisc_t.data\fP defines the byte that

separates records in a byte stream (see \f5rsprocess()\fP.)

.PP

.Ss " Rsdisc_t.key, Rsdisc_t.keylen"

.Ss " Rsdisc_t.defkeyf(Rs_t* rs, Void_t* data, ssize_t s_data, Void_t* key, ssize_t s_key, Rsdisc_t* disc)"

Assume a record \fIdata\fP of length \fIs_data\fP.

If \f5Rsdisc_t.defkeyf\fP is \f5NULL\fP,

\f5Rsdisc_t.key\fP and \f5Rsdisc_t.keylen\fP together define a key.

\fIdata\fP+\f5Rsdisc_t.key\fP is the key's starting address.

If \f5Rsdisc_t.keylen\fP is positive, it is the length of the key.

Otherwise, the length of the key is the quantity

\fIs_data\fP+\f5Rsdisc_t.keylen-Rsdisc_t.key\fP.

If \f5Rsdisc_t.defkeyf\fP is not \f5NULL\fP, it is called to define a key.

The key should be constructed in the given area \f5key\fP whose size is \f5s_key\fP.

\f5s_key\fP is guaranteed to be at least \f5Rsdisc_t.key*s_data\fP.

\f5Rsdisc_t.defkeyf\fP should return the length of the key or a negative value on error.

.PP

.Ss " Rsdisc_t.eventf(Rs_t* rs, int type, Void_t* data, Rsdisc_t* disc)"

If \f5eventf\fP is not \f5NULL\fP, it is called to announce certain

events and associated data. If the return value of \f5eventf\fP is negative,

the operation causing the announcement will immediately return an error condition.

Following are supported events:

.Tp

\f5RS_CLOSE\fP:

This event is raised when \f5rs\fP is about to be closed.

The associated \f5data\fP is \f5NULL\fP.

.Tp

\f5RS_DISC\fP:

This event is raised when the discipline is about to be changed.

\f5(Sfdisc_t*)data\fP is the new discipline.

.Tp

\f5RS_METHOD\fP:

This event is raised when the method is about to be changed.

\f5(Sfmethod_t*)data\fP is the new method.

.Tp

\f5RS_VERIFY\fP:

This event is raised when method \f5Rsverify\fP detects

a record, \f5r=(Rsobj_t*)data\fP, out of order with respect to

a previous record \f5p\fP. There are three cases.

If \f5r\fP compares equal with \f5p\fP and \f5RS_UNIQ\fP is on,

then \f5r->equal\fP is \f5p\fP.

If \f5r\fP compares less than \f5p\fP and \f5RS_REVERSE\fP is off,

then \f5r->right\fP is \f5p\fP.

Finally, if \f5r\fP compares larger than \f5p\fP and \f5RS_REVERSE\fP is on,

then \f5r->left\fP is \f5p\fP.

\f5r->order\fP and \f5p->order\fP are the ordinal positions of \f5r\fP and \f5p\fP

in the stream of records.

The return value of \f5eventf\fP is significant as follows.

If it is negative, the verification process is aborted.

If it is zero, the verification process continues as if \f5r\fP did not exist.

If it is positive, the verification process continues as if \f5r\fP was in order.

.PP

.Ss " Rsdisc_t* rsdisc(Rs_t* rs, Rsdisc_t* disc)"

If \f5disc\fP is not \f5NULL\fP,

\f5rsdisc()\fP changes the discipline of \f5rs\fP to \f5disc\fP.

This should be done only when there are no partially sorted records in the context,

i.e., before any \f5rsprocess()\fP call or immediately after a \f5rsclear()\fP call.

\f5rsdisc()\fP returns the old discipline on success and \f5NULL\fP on failure.

.PP

.Ss "OBJECT OPERATIONS"

.PP

.Ss " ssize_t rsprocess(Rs_t* rs, Void_t* data, ssize_t s_data)"

.Ss " ssize_t rscount(Rs_t* rs)"

\f5rsprocess()\fP partitions \f5data\fP into records and inserts them into \f5rs\fP.

If \f5s_data\fP is non-positive,

\f5data\fP is a single record of size \f5-s_data\fP.

Otherwise, \f5data\fP is partitioned into records

according to the rules defined in the discipline of \f5rs\fP.

\f5rsprocess()\fP returns the number of bytes actually processed or \f5-1\fP on error.

After an \f5rsprocess()\fP call,

the number of processed records can be retrieved with \f5rscount()\fP.

.PP

.Ss " Rsobj_t* rslist(Rs_t* rs)"

This returns a sorted list of records previously inserted into \f5rs\fP.

After \f5rslist()\fP has been called, no new records can be inserted

until \f5rs\fP is cleared with \f5rsclear(rs)\fP.

.PP

.Ss " int rswrite(Rs_t* rs, Sfio_t* f, int type)"

This writes sorted records in \f5rs\fP to stream \f5f\fP then clears \f5rs\fP.

If \f5type\fP is any non-zero

combination of \f5RS_ITEXT\fP and \f5RS_OTEXT\fP, data is output in a plain format.

Otherwise, data is encoded for fast merging (see \f5rsmerge()\fP.)

\f5rswrite()\fP returns 0 on success and -1 on failure.

.PP

.Ss " int rsmerge(Rs_t* rs, Sfio_t* f, Sfio_t** files, int n, int type)"

This merges the given \f5n\fP \f5files\fP and writes the result to \f5f\fP.

If \f5type\fP contains \f5RS_ITEXT\fP,

the input data is assumed to be in a plain format.

Otherwise, data is assumed to be encoded for fast merging.

In addition, if \f5type\fP is any non-zero combination of

\f5RS_ITEXT\fP and \f5RS_OTEXT\fP, data is output in a plain format.

Otherwise, data is encoded for fast file merging.

\f5rsmerge()\fP returns 0 on success and -1 on failure.

.PP

.SH AUTHORS

Kiem-Phong Vo, kpv@research.att.com, and

Glenn S. Fowler, gsf@research.att.com