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 }