Rest of the automake file deletions.
[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
27 #include "dhcpd-pools.h"
28 #include "defaults.h"
29
30 /* Sort functions for range sorting */
31 int intcomp(const void *x, const void *y)
32 {
33         if (*(unsigned long int *) x < *(unsigned long int *) y)
34                 return -1;
35         else if (*(unsigned long int *) y < *(unsigned long int *) x)
36                 return 1;
37         else
38                 return 0;
39 }
40
41 int rangecomp(const void *r1, const void *r2)
42 {
43         if ((((struct range_t *) r1)->first_ip) <
44             (((struct range_t *) r2)->first_ip))
45                 return -1;
46         else if ((((struct range_t *) r2)->first_ip) <
47                  (((struct range_t *) r1)->first_ip))
48                 return 1;
49         else
50                 return 0;
51 }
52
53 unsigned long int ret_ip(struct range_t r)
54 {
55         return (r.first_ip);
56 }
57
58 unsigned long int ret_cur(struct range_t r)
59 {
60         return (r.count);
61 }
62
63 unsigned long int ret_max(struct range_t r)
64 {
65         return (r.last_ip - r.first_ip);
66 }
67
68 unsigned long int ret_percent(struct range_t r)
69 {
70         float f;
71         f = (float) r.count / (r.last_ip - r.first_ip - 1);
72         return ((unsigned long int) (f * 100000));
73 }
74
75 unsigned long int ret_touched(struct range_t r)
76 {
77         return (r.touched);
78 }
79
80 unsigned long int ret_tc(struct range_t r)
81 {
82         return (r.count + r.touched);
83 }
84
85 unsigned long int ret_tcperc(struct range_t r)
86 {
87         float f;
88         f = (float) (r.count + r.touched) / (r.last_ip - r.first_ip - 1);
89         return ((unsigned long int) (f * 10000));
90 }
91
92 void field_selector(char c)
93 {
94         switch (c) {
95         case 'n':
96                 break;
97         case 'i':
98                 returner = ret_ip;
99                 break;
100         case 'm':
101                 returner = ret_max;
102                 break;
103         case 'c':
104                 returner = ret_cur;
105                 break;
106         case 'p':
107                 returner = ret_percent;
108                 break;
109         case 't':
110                 returner = ret_touched;
111                 break;
112         case 'T':
113                 returner = ret_tc;
114                 break;
115         case 'e':
116                 returner = ret_tcperc;
117                 break;
118         default:
119                 eprintf("field_selector: unknown sort order: %c",
120                         config.sort[0]);
121                 usage(EXIT_FAILURE);
122         }
123 }
124
125 /* Needed to support multiple key sorting. */
126 int get_order(struct range_t *left, struct range_t *right)
127 {
128         int i, len, ret;
129         unsigned long int lint, rint;
130
131         len = strlen(config.sort);
132         for (i = 0; i < len; i++) {
133                 /* Handling strings is case of it's own */
134                 if (config.sort[i] == 'n') {
135                         ret =
136                             strcmp(left->shared_net->name,
137                                    right->shared_net->name);
138                         if (ret > 0) {
139                                 return (0);
140                         } else if (ret < 0) {
141                                 return (1);
142                         } else {
143                                 continue;
144                         }
145                 }
146
147                 /* Select which function is pointed by returner */
148                 field_selector(config.sort[i]);
149                 lint = returner(*left);
150                 rint = returner(*right);
151                 /* If fields are equal use next sort method */
152                 if (lint == rint) {
153                         continue;
154                 }
155                 if (lint < rint) {
156                         return (1);
157                 }
158                 return (0);
159         }
160
161         /* If all returners where equal */
162         return (0);
163 }
164
165 void mergesort_ranges(struct range_t *orig, int size, struct range_t *temp)
166 {
167         int left, right, i;
168         struct range_t hold;
169
170         if (size < MIN_MERGE_SIZE) {
171                 for (left = 0; left < size; left++) {
172                         hold = *(orig + left);
173                         for (right = left - 1; right >= 0; right--) {
174                                 if (get_order((orig + right), &hold)) {
175                                         break;
176                                 }
177                                 *(orig + right + 1) = *(orig + right);
178                         }
179                         *(orig + right + 1) = hold;
180                 }
181                 return;
182         }
183
184         mergesort_ranges(orig, size / 2, temp);
185         mergesort_ranges(orig + size / 2, size - size / 2, temp);
186
187         left = 0;
188         right = size / 2;
189         i = 0;
190
191         while (left < size / 2 && right < size) {
192                 if (get_order((orig + left), (orig + right))) {
193                         *(temp + i) = *(orig + left);
194                         left++;
195                 } else {
196                         *(temp + i) = *(orig + right);
197                         right++;
198                 }
199                 i++;
200         }
201         while (left < size / 2) {
202                 *(temp + i) = *(orig + left);
203                 left++;
204                 i++;
205         }
206         while (right < size) {
207                 *(temp + i) = *(orig + right);
208                 right++;
209                 i++;
210         }
211
212         memcpy(orig, temp, size * sizeof(struct range_t));
213 }