1 /* $NetBSD: fields.c,v 1.31 2009/11/06 18:34:22 joerg Exp $ */
4 * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Ben Harris and Jaromir Dolecek.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
34 * The Regents of the University of California. All rights reserved.
36 * This code is derived from software contributed to Berkeley by
39 * Redistribution and use in source and binary forms, with or without
40 * modification, are permitted provided that the following conditions
42 * 1. Redistributions of source code must retain the above copyright
43 * notice, this list of conditions and the following disclaimer.
44 * 2. Redistributions in binary form must reproduce the above copyright
45 * notice, this list of conditions and the following disclaimer in the
46 * documentation and/or other materials provided with the distribution.
47 * 3. Neither the name of the University nor the names of its contributors
48 * may be used to endorse or promote products derived from this software
49 * without specific prior written permission.
51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
52 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
53 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
54 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
55 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
56 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
57 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
59 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
60 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
64 /* Subroutines to generate sort keys. */
68 #define SKIP_BLANKS(ptr) { \
69 if (BLANK & d_mask[*(ptr)]) \
70 while (BLANK & d_mask[*(++(ptr))]); \
73 #define NEXTCOL(pos) { \
75 while (BLANK & l_d_mask[*(++pos)]); \
76 while ((*(pos+1) != '\0') && !((FLD_D | REC_D_F) & l_d_mask[*++pos]));\
79 static u_char
*enterfield(u_char
*, const u_char
*, struct field
*, int);
80 static u_char
*number(u_char
*, const u_char
*, u_char
*, u_char
*, int);
81 static u_char
*length(u_char
*, const u_char
*, u_char
*, u_char
*, int);
83 #define DECIMAL_POINT '.'
86 * constructs sort key with leading recheader, followed by the key,
87 * followed by the original line.
90 enterkey(RECHEADER
*keybuf
, const u_char
*keybuf_end
, u_char
*line_data
,
91 size_t line_size
, struct field fieldtable
[])
92 /* keybuf: pointer to start of key */
96 u_char
*lineend
, *pos
;
99 struct coldesc
*clpos
;
105 lineend
= line_data
+ line_size
-1;
106 /* don't include rec_delimiter */
108 for (i
= 0; i
< ncols
; i
++) {
110 for (; (col
< clpos
->num
) && (pos
< lineend
); col
++) {
115 clpos
->start
= SEP_FLAG
? pos
+ 1 : pos
;
119 if (pos
>= lineend
) {
120 clpos
->end
= lineend
;
125 for (; i
<= ncols
; i
++)
126 clist
[i
].start
= clist
[i
].end
= lineend
;
127 if (clist
[0].start
< line_data
)
131 * We write the sort keys (concatenated) followed by the
132 * original line data (for output) as the 'keybuf' data.
133 * keybuf->length is the number of key bytes + data bytes.
134 * keybuf->offset is the number of key bytes.
135 * We add a record separator weight after the key in case
136 * (as is usual) we need to preserve the order of equal lines,
138 * The key itself will have had the correct weight applied.
140 keypos
= keybuf
->data
;
141 endkey
= keybuf_end
- line_size
- 1;
142 if (endkey
<= keypos
)
143 /* No room for any key bytes */
146 for (ftpos
= fieldtable
+ 1; ftpos
->icol
.num
; ftpos
++) {
147 if ((keypos
= enterfield(keypos
, endkey
, ftpos
,
148 fieldtable
->flags
)) == NULL
)
152 keybuf
->offset
= keypos
- keybuf
->data
;
153 keybuf
->length
= keybuf
->offset
+ line_size
;
156 * Posix requires that equal keys be further sorted by the
157 * entire original record.
158 * NetBSD has (at least for some time) kept equal keys in
159 * their original order.
160 * For 'sort -u' posix_sort is unset.
162 keybuf
->keylen
= posix_sort
? keybuf
->length
: keybuf
->offset
;
164 memcpy(keypos
, line_data
, line_size
);
169 * constructs a field (as defined by -k) within a key
172 enterfield(u_char
*tablepos
, const u_char
*endkey
, struct field
*cur_fld
,
173 int __attribute__ ((unused
)) gflags
)
175 u_char
*start
, *end
, *lineend
, *mask
, *lweight
;
176 struct column icol
, tcol
;
179 icol
= cur_fld
->icol
;
180 tcol
= cur_fld
->tcol
;
181 flags
= cur_fld
->flags
;
182 start
= icol
.p
->start
;
183 lineend
= clist
[ncols
].end
;
186 start
+= icol
.indent
;
187 start
= min(start
, lineend
);
197 end
= min(end
, lineend
);
203 return length(tablepos
, endkey
, start
, end
, flags
);
205 return number(tablepos
, endkey
, start
, end
, flags
);
207 /* Bound check space - assuming nothing is skipped */
208 if (tablepos
+ (end
- start
) + 1 >= endkey
)
211 mask
= cur_fld
->mask
;
212 lweight
= cur_fld
->weights
;
213 for (; start
< end
; start
++) {
214 if (!mask
|| mask
[*start
]) {
215 *tablepos
++ = lweight
[*start
];
218 /* Add extra byte (absent from lweight) to sort short keys correctly */
219 *tablepos
++ = lweight
[REC_D
];
224 * Numbers are converted to a floating point format (exponent & mantissa)
225 * so that they compare correctly as sequence of unsigned bytes.
226 * Bytes 0x00 and 0xff are used to terminate positive and negative numbers
227 * to ensure that 0.123 sorts after 0.12 and -0.123 sorts before -0.12.
229 * The first byte contain the overall sign, exponent sign and some of the
230 * exponent. These have to be ordered (-ve value, decreasing exponent),
231 * zero, (+ve value, increasing exponent).
233 * The first byte is 0x80 for zero, 0xc0 for +ve with exponent 0.
234 * -ve values are the 1's compliments (so 0x7f isn't used!).
236 * This only leaves 63 byte values for +ve exponents - which isn't enough.
237 * The largest 4 exponent values are used to hold a byte count of the
238 * number of following bytes that contain 8 exponent bits per byte,
239 * This lets us sort exponents from -2^31 to +2^31.
241 * The mantissa is stored 2 digits per byte offset by 0x40, for negative
242 * numbers the order must be reversed (they are bit inverted).
244 * Reverse sorts are done by inverting the sign of the number.
246 #define MAX_EXP_ENC ((int)sizeof(int))
249 number(u_char
*pos
, const u_char
*bufend
, u_char
*line
, u_char
*lineend
,
265 /* Give ourselves space for the key terminator */
268 /* Ensure we have enough space for the exponent */
269 if (pos
+ 1 + MAX_EXP_ENC
> bufend
)
273 if (*line
== '-') { /* set the sign */
277 /* eat initial zeroes */
278 for (; *line
== '0' && line
< lineend
; line
++)
281 /* calculate exponents */
282 if (*line
== DECIMAL_POINT
) {
283 /* Decimal fraction */
285 while (*++line
== '0' && line
< lineend
)
288 /* Large (absolute) value, count digits */
289 for (tline
= line
; *tline
>= '0' &&
290 *tline
<= '9' && tline
< lineend
; tline
++)
294 /* If the first/next character isn't a digit, value is zero */
295 if (*line
< '1' || *line
> '9' || line
>= lineend
) {
296 /* This may be "0", "0.00", "000" or "fubar" but sorts as 0 */
297 /* XXX what about NaN, NAN, inf and INF */
302 /* Maybe here we should allow for e+12 (etc) */
304 if (exponent
< 0x40 - MAX_EXP_ENC
&& -exponent
< 0x40 - MAX_EXP_ENC
) {
305 /* Value ok for simple encoding */
306 /* exponent 0 is 0xc0 for +ve numbers and 0x40 for -ve ones */
308 *pos
++ = negate
^ exponent
;
310 /* Out or range for a single byte */
312 t
= exponent
> 0 ? exponent
: -exponent
;
313 /* Count how many 8-bit bytes are needed */
319 /* 'c' better be 0..3 here - but probably 0..1 */
320 /* Offset just outside valid range */
321 t
= c
+ 0x40 - MAX_EXP_ENC
;
324 *pos
++ = negate
^ (t
+ 0xc0);
325 /* now add each byte, most significant first */
327 *pos
++ = negate
^ (exponent
>> (c
* 8));
330 /* Finally add mantissa, 2 digits per byte */
331 for (last_nz_pos
= pos
; line
< lineend
; ) {
335 val
= (ch
- '0') * 10;
337 if (ch
== DECIMAL_POINT
&& !had_dp
) {
343 while (line
< lineend
) {
345 if (ch
== DECIMAL_POINT
&& !had_dp
) {
349 if (ch
< '0' || ch
> '9')
355 *pos
++ = negate
^ (val
+ 0x40);
360 /* Add key terminator, deleting any trailing "00" */
361 *last_nz_pos
++ = negate
;
363 return (last_nz_pos
);
367 length(u_char
*pos
, const u_char
*bufend
, u_char
*line
, u_char
*lineend
,
373 l
= snprintf((char *)buf
, sizeof(buf
), "%td", lineend
- line
);
374 return number(pos
, bufend
, buf
, buf
+ l
, flag
);