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 #ifdef HAVE_CONFIG_H
  19 #include <config.h>
  20 #endif
  21
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <errno.h>
  26 #include <err.h>
  27
  28 #include "dhcpd-pools.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                 warnx("field_selector: unknown sort order `%c'", c);
 120                 errx(EXIT_FAILURE, "Try `%s --help' for more information.",
 121                      program_invocation_short_name);
 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 (0 < ret) {
 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         /* Merge sort split size */
 170         static const int MIN_MERGE_SIZE = 8;
 171
 172         if (size < MIN_MERGE_SIZE) {
 173                 for (left = 0; left < size; left++) {
 174                         hold = *(orig + left);
 175                         for (right = left - 1; 0 <= right; right--) {
 176                                 if (get_order((orig + right), &hold)) {
 177                                         break;
 178                                 }
 179                                 *(orig + right + 1) = *(orig + right);
 180                         }
 181                         *(orig + right + 1) = hold;
 182                 }
 183                 return;
 184         }
 185
 186         mergesort_ranges(orig, size / 2, temp);
 187         mergesort_ranges(orig + size / 2, size - size / 2, temp);
 188
 189         left = 0;
 190         right = size / 2;
 191         i = 0;
 192
 193         while (left < size / 2 && right < size) {
 194                 if (get_order((orig + left), (orig + right))) {
 195                         *(temp + i) = *(orig + left);
 196                         left++;
 197                 } else {
 198                         *(temp + i) = *(orig + right);
 199                         right++;
 200                 }
 201                 i++;
 202         }
 203         while (left < size / 2) {
 204                 *(temp + i) = *(orig + left);
 205                 left++;
 206                 i++;
 207         }
 208         while (right < size) {
 209                 *(temp + i) = *(orig + right);
 210                 right++;
 211                 i++;
 212         }
 213
 214         memcpy(orig, temp, size * sizeof(struct range_t));
 215 }