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 #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                 warnx("field_selector: unknown sort order `%c'", c);
 121                 errx(EXIT_FAILURE, "Try `%s --help' for more information.",
 122                      program_invocation_short_name);
 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 }