Fix "clock error" due to machine reboot.
[darkstat] / hosts_sort.c
1 /* darkstat 3
2 * copyright (c) 2001-2012 Emil Mikulic.
3 *
4 * hosts_sort.c: quicksort a table of buckets.
5 *
6 * You may use, modify and redistribute this file under the terms of the
7 * GNU General Public License version 2. (see COPYING.GPL)
8 */
9
10 #include "cdefs.h"
11 #include "err.h"
12 #include "hosts_db.h"
13
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);
17 return (0);
18 }
19
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);
23 return (0);
24 }
25
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) {
29 switch (dir) {
30 case IN:
31 return cmp_u64((*x)->in, (*y)->in);
32 case OUT:
33 return cmp_u64((*x)->out, (*y)->out);
34 case TOTAL:
35 return cmp_u64((*x)->total, (*y)->total);
36 case LASTSEEN:
37 return cmp_i64((*x)->u.host.last_seen_mono,
38 (*y)->u.host.last_seen_mono);
39 default:
40 errx(1, "cmp: unknown direction: %d", dir);
41 }
42 }
43
44 /*
45 * The quicksort code is derived from FreeBSD's
46 * src/lib/libc/stdlib/qsort.c v1.12
47 */
48
49 /*-
50 * Copyright (c) 1992, 1993
51 * The Regents of the University of California. All rights reserved.
52 *
53 * Redistribution and use in source and binary forms, with or without
54 * modification, are permitted provided that the following conditions
55 * are met:
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.
68 *
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
79 * SUCH DAMAGE.
80 */
81
82 static void
83 vecswap(const struct bucket **pi, const struct bucket **pj, int n)
84 {
85 if (n <= 0)
86 return;
87
88 do {
89 const struct bucket *t = *pi;
90 *pi++ = *pj;
91 *pj++ = t;
92 } while (--n > 0);
93 }
94
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; \
99 }
100
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)
106 {
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 ));
110 }
111
112 /* Partial sort - only sort elements in the range [left:right] */
113 void
114 qsort_buckets(const struct bucket **a, size_t n,
115 size_t left, size_t right,
116 const enum sort_dir dir)
117 {
118 const struct bucket **pa, **pb, **pc, **pd, **pl, **pm, **pn;
119 int d, r, swap_cnt;
120
121 loop:
122 swap_cnt = 0;
123 if (n < 7) {
124 for (pm = a+1; pm < a+n; pm++)
125 for (pl = pm;
126 (pl > a) && (cmp(pl-1, pl, dir) > 0);
127 pl--)
128 swap(pl, pl-1);
129 return;
130 }
131 pm = a + (n / 2);
132 if (n > 7) {
133 pl = a;
134 pn = a + (n - 1);
135 if (n > 40) {
136 d = (n / 8);
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);
140 }
141 pm = med3(pl, pm, pn, dir);
142 }
143 swap(a, pm);
144 pa = pb = a + 1;
145
146 pc = pd = a + (n - 1);
147 for (;;) {
148 while (pb <= pc && (r = cmp(pb, a, dir)) <= 0) {
149 if (r == 0) {
150 swap_cnt = 1;
151 swap(pa, pb);
152 pa++;
153 }
154 pb++;
155 }
156 while (pb <= pc && (r = cmp(pc, a, dir)) >= 0) {
157 if (r == 0) {
158 swap_cnt = 1;
159 swap(pc, pd);
160 pd--;
161 }
162 pc--;
163 }
164 if (pb > pc)
165 break;
166 swap(pb, pc);
167 swap_cnt = 1;
168 pb++;
169 pc--;
170 }
171 if (swap_cnt == 0) { /* Switch to insertion sort */
172 for (pm = a + 1; pm < a+n; pm++)
173 for (pl = pm;
174 (pl > a) && (cmp(pl-1, pl, dir) > 0);
175 pl--)
176 swap(pl, pl-1);
177 return;
178 }
179
180 pn = a + n;
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 */
189 if (n - r > left)
190 left = 0;
191 else
192 left -= n - r;
193 right -= n - r;
194 a += n - r;
195 n = r;
196 goto loop;
197 }
198 /* qsort(pn - r, r, cmp);*/
199 }
200
201 /* vim:set ts=3 sw=3 tw=78 expandtab: */