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