2 * copyright (c) 2001-2012 Emil Mikulic.
4 * hosts_sort.c: quicksort a table of buckets.
6 * You may use, modify and redistribute this file under the terms of the
7 * GNU General Public License version 2. (see COPYING.GPL)
14 static int cmp_u64(const uint64_t a
, const uint64_t b
) {
15 if (a
< b
) return (1);
16 if (a
> b
) return (-1);
20 static int cmp_i64(const int64_t a
, const int64_t b
) {
21 if (a
< b
) return (1);
22 if (a
> b
) return (-1);
26 /* Comparator for sorting 'struct bucket' */
27 static int cmp(const struct bucket
* const *x
, const struct bucket
* const *y
,
28 const enum sort_dir dir
) {
31 return cmp_u64((*x
)->in
, (*y
)->in
);
33 return cmp_u64((*x
)->out
, (*y
)->out
);
35 return cmp_u64((*x
)->total
, (*y
)->total
);
37 return cmp_i64((*x
)->u
.host
.last_seen_mono
,
38 (*y
)->u
.host
.last_seen_mono
);
40 errx(1, "cmp: unknown direction: %d", dir
);
45 * The quicksort code is derived from FreeBSD's
46 * src/lib/libc/stdlib/qsort.c v1.12
50 * Copyright (c) 1992, 1993
51 * The Regents of the University of California. All rights reserved.
53 * Redistribution and use in source and binary forms, with or without
54 * modification, are permitted provided that the following conditions
56 * 1. Redistributions of source code must retain the above copyright
57 * notice, this list of conditions and the following disclaimer.
58 * 2. Redistributions in binary form must reproduce the above copyright
59 * notice, this list of conditions and the following disclaimer in the
60 * documentation and/or other materials provided with the distribution.
61 * 3. All advertising materials mentioning features or use of this software
62 * must display the following acknowledgement:
63 * This product includes software developed by the University of
64 * California, Berkeley and its contributors.
65 * 4. Neither the name of the University nor the names of its contributors
66 * may be used to endorse or promote products derived from this software
67 * without specific prior written permission.
69 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
70 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
71 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
72 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
73 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
74 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
75 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
76 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
77 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
78 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
83 vecswap(const struct bucket
**pi
, const struct bucket
**pj
, int n
)
89 const struct bucket
*t
= *pi
;
95 #define swap(a, b) { \
96 const struct bucket *t = *(const struct bucket **)(a); \
97 *(const struct bucket **)(a) = *(const struct bucket **)(b); \
98 *(const struct bucket **)(b) = t; \
101 static const struct bucket
**
102 med3(const struct bucket
**a
,
103 const struct bucket
**b
,
104 const struct bucket
**c
,
105 const enum sort_dir dir
)
107 return (cmp(a
, b
, dir
) < 0)
108 ? (cmp(b
, c
, dir
) < 0 ? b
: (cmp(a
, c
, dir
) < 0 ? c
: a
))
109 : (cmp(b
, c
, dir
) > 0 ? b
: (cmp(a
, c
, dir
) < 0 ? a
: c
));
112 /* Partial sort - only sort elements in the range [left:right] */
114 qsort_buckets(const struct bucket
**a
, size_t n
,
115 size_t left
, size_t right
,
116 const enum sort_dir dir
)
118 const struct bucket
**pa
, **pb
, **pc
, **pd
, **pl
, **pm
, **pn
;
124 for (pm
= a
+1; pm
< a
+n
; pm
++)
126 (pl
> a
) && (cmp(pl
-1, pl
, dir
) > 0);
137 pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, dir
);
138 pm
= med3(pm
- d
, pm
, pm
+ d
, dir
);
139 pn
= med3(pn
- 2 * d
, pn
- d
, pn
, dir
);
141 pm
= med3(pl
, pm
, pn
, dir
);
146 pc
= pd
= a
+ (n
- 1);
148 while (pb
<= pc
&& (r
= cmp(pb
, a
, dir
)) <= 0) {
156 while (pb
<= pc
&& (r
= cmp(pc
, a
, dir
)) >= 0) {
171 if (swap_cnt
== 0) { /* Switch to insertion sort */
172 for (pm
= a
+ 1; pm
< a
+n
; pm
++)
174 (pl
> a
) && (cmp(pl
-1, pl
, dir
) > 0);
181 r
= MIN(pa
- a
, pb
- pa
);
182 vecswap(a
, pb
- r
, r
);
183 r
= MIN(pd
- pc
, pn
- pd
- 1);
184 vecswap(pb
, pn
- r
, r
);
185 if (((r
= pb
- pa
) > 1) && ((unsigned)r
>= left
))
186 qsort_buckets(a
, r
, left
, right
, dir
);
187 if (((r
= pd
- pc
) > 1) && (n
- r
<= right
)) {
188 /* Iterate rather than recurse to save stack space */
198 /* qsort(pn - r, r, cmp);*/
201 /* vim:set ts=3 sw=3 tw=78 expandtab: */