src/sort.c

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