Not a syscall error, warn should be warnx.
[debian/dhcpd-pools.git] / src / sort.c
1 /*
2 ** Copyright (C) 2006- Sami Kerola <kerolasa@iki.fi>
3 **  
4 ** This program is free software; you can redistribute it and/or modify
5 ** it under the terms of the GNU General Public License as published by
6 ** the Free Software Foundation; either version 2 of the License, or
7 ** (at your option) any later version.
8 ** 
9 ** This program is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 ** GNU General Public License for more details.
13 ** 
14 ** You should have received a copy of the GNU General Public License
15 ** along with this program; if not, write to the Free Software 
16 ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18
19 #ifdef HAVE_CONFIG_H
20 #include <config.h>
21 #endif
22
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <string.h>
26 #include <err.h>
27
28 #include "dhcpd-pools.h"
29 #include "defaults.h"
30
31 /* Sort functions for range sorting */
32 int intcomp(const void *x, const void *y)
33 {
34         if (*(unsigned long int *) x < *(unsigned long int *) y)
35                 return -1;
36         else if (*(unsigned long int *) y < *(unsigned long int *) x)
37                 return 1;
38         else
39                 return 0;
40 }
41
42 int rangecomp(const void *r1, const void *r2)
43 {
44         if ((((struct range_t *) r1)->first_ip) <
45             (((struct range_t *) r2)->first_ip))
46                 return -1;
47         else if ((((struct range_t *) r2)->first_ip) <
48                  (((struct range_t *) r1)->first_ip))
49                 return 1;
50         else
51                 return 0;
52 }
53
54 unsigned long int ret_ip(struct range_t r)
55 {
56         return (r.first_ip);
57 }
58
59 unsigned long int ret_cur(struct range_t r)
60 {
61         return (r.count);
62 }
63
64 unsigned long int ret_max(struct range_t r)
65 {
66         return (r.last_ip - r.first_ip);
67 }
68
69 unsigned long int ret_percent(struct range_t r)
70 {
71         float f;
72         f = (float) r.count / (r.last_ip - r.first_ip - 1);
73         return ((unsigned long int) (f * 100000));
74 }
75
76 unsigned long int ret_touched(struct range_t r)
77 {
78         return (r.touched);
79 }
80
81 unsigned long int ret_tc(struct range_t r)
82 {
83         return (r.count + r.touched);
84 }
85
86 unsigned long int ret_tcperc(struct range_t r)
87 {
88         float f;
89         f = (float) (r.count + r.touched) / (r.last_ip - r.first_ip - 1);
90         return ((unsigned long int) (f * 10000));
91 }
92
93 void field_selector(char c)
94 {
95         switch (c) {
96         case 'n':
97                 break;
98         case 'i':
99                 returner = ret_ip;
100                 break;
101         case 'm':
102                 returner = ret_max;
103                 break;
104         case 'c':
105                 returner = ret_cur;
106                 break;
107         case 'p':
108                 returner = ret_percent;
109                 break;
110         case 't':
111                 returner = ret_touched;
112                 break;
113         case 'T':
114                 returner = ret_tc;
115                 break;
116         case 'e':
117                 returner = ret_tcperc;
118                 break;
119         default:
120                 errx(EXIT_FAILURE,
121                      "field_selector: unknown sort order `%c'",
122                      config.sort[0]);
123         }
124 }
125
126 /* Needed to support multiple key sorting. */
127 int get_order(struct range_t *left, struct range_t *right)
128 {
129         int i, len, ret;
130         unsigned long int lint, rint;
131
132         len = strlen(config.sort);
133         for (i = 0; i < len; i++) {
134                 /* Handling strings is case of it's own */
135                 if (config.sort[i] == 'n') {
136                         ret =
137                             strcmp(left->shared_net->name,
138                                    right->shared_net->name);
139                         if (0 < ret) {
140                                 return (0);
141                         } else if (ret < 0) {
142                                 return (1);
143                         } else {
144                                 continue;
145                         }
146                 }
147
148                 /* Select which function is pointed by returner */
149                 field_selector(config.sort[i]);
150                 lint = returner(*left);
151                 rint = returner(*right);
152                 /* If fields are equal use next sort method */
153                 if (lint == rint) {
154                         continue;
155                 }
156                 if (lint < rint) {
157                         return (1);
158                 }
159                 return (0);
160         }
161
162         /* If all returners where equal */
163         return (0);
164 }
165
166 void mergesort_ranges(struct range_t *orig, int size, struct range_t *temp)
167 {
168         int left, right, i;
169         struct range_t hold;
170
171         if (size < MIN_MERGE_SIZE) {
172                 for (left = 0; left < size; left++) {
173                         hold = *(orig + left);
174                         for (right = left - 1; 0 <= right; right--) {
175                                 if (get_order((orig + right), &hold)) {
176                                         break;
177                                 }
178                                 *(orig + right + 1) = *(orig + right);
179                         }
180                         *(orig + right + 1) = hold;
181                 }
182                 return;
183         }
184
185         mergesort_ranges(orig, size / 2, temp);
186         mergesort_ranges(orig + size / 2, size - size / 2, temp);
187
188         left = 0;
189         right = size / 2;
190         i = 0;
191
192         while (left < size / 2 && right < size) {
193                 if (get_order((orig + left), (orig + right))) {
194                         *(temp + i) = *(orig + left);
195                         left++;
196                 } else {
197                         *(temp + i) = *(orig + right);
198                         right++;
199                 }
200                 i++;
201         }
202         while (left < size / 2) {
203                 *(temp + i) = *(orig + left);
204                 left++;
205                 i++;
206         }
207         while (right < size) {
208                 *(temp + i) = *(orig + right);
209                 right++;
210                 i++;
211         }
212
213         memcpy(orig, temp, size * sizeof(struct range_t));
214 }