src/sort.c

   1 /*
   2  * The dhcpd-pools has BSD 2-clause license which also known as "Simplified
   3  * BSD License" or "FreeBSD License".
   4  *
   5  * Copyright 2006- Sami Kerola. All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions are
   9  * met:
  10  *
  11  *    1. Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *
  14  *    2. Redistributions in binary form must reproduce the above copyright
  15  *       notice, this list of conditions and the following disclaimer in the
  16  *       documentation and/or other materials provided with the
  17  *       distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND ANY EXPRESS
  20  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  21  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> OR CONTRIBUTORS BE
  23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  29  * THE POSSIBILITY OF SUCH DAMAGE.
  30  *
  31  * The views and conclusions contained in the software and documentation are
  32  * those of the authors and should not be interpreted as representing
  33  * official policies, either expressed or implied, of Sami Kerola.
  34  */
  35
  36 #include <config.h>
  37 #include <err.h>
  38 #include <errno.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41
  42 #include "dhcpd-pools.h"
  43
  44 /* Sort functions for range sorting */
  45 int intcomp(const void *x, const void *y)
  46 {
  47         if (*(unsigned long int *) x < *(unsigned long int *) y)
  48                 return -1;
  49         else if (*(unsigned long int *) y < *(unsigned long int *) x)
  50                 return 1;
  51         else
  52                 return 0;
  53 }
  54
  55 int rangecomp(const void *r1, const void *r2)
  56 {
  57         if ((((struct range_t *) r1)->first_ip) <
  58             (((struct range_t *) r2)->first_ip))
  59                 return -1;
  60         else if ((((struct range_t *) r2)->first_ip) <
  61                  (((struct range_t *) r1)->first_ip))
  62                 return 1;
  63         else
  64                 return 0;
  65 }
  66
  67 unsigned long int ret_ip(struct range_t r)
  68 {
  69         return (r.first_ip);
  70 }
  71
  72 unsigned long int ret_cur(struct range_t r)
  73 {
  74         return (r.count);
  75 }
  76
  77 unsigned long int ret_max(struct range_t r)
  78 {
  79         return (r.last_ip - r.first_ip);
  80 }
  81
  82 unsigned long int ret_percent(struct range_t r)
  83 {
  84         float f;
  85         f = (float) r.count / (r.last_ip - r.first_ip - 1);
  86         return ((unsigned long int) (f * 100000));
  87 }
  88
  89 unsigned long int ret_touched(struct range_t r)
  90 {
  91         return (r.touched);
  92 }
  93
  94 unsigned long int ret_tc(struct range_t r)
  95 {
  96         return (r.count + r.touched);
  97 }
  98
  99 unsigned long int ret_tcperc(struct range_t r)
 100 {
 101         float f;
 102         f = (float) (r.count + r.touched) / (r.last_ip - r.first_ip - 1);
 103         return ((unsigned long int) (f * 10000));
 104 }
 105
 106 void field_selector(char c)
 107 {
 108         switch (c) {
 109         case 'n':
 110                 break;
 111         case 'i':
 112                 returner = ret_ip;
 113                 break;
 114         case 'm':
 115                 returner = ret_max;
 116                 break;
 117         case 'c':
 118                 returner = ret_cur;
 119                 break;
 120         case 'p':
 121                 returner = ret_percent;
 122                 break;
 123         case 't':
 124                 returner = ret_touched;
 125                 break;
 126         case 'T':
 127                 returner = ret_tc;
 128                 break;
 129         case 'e':
 130                 returner = ret_tcperc;
 131                 break;
 132         default:
 133                 warnx("field_selector: unknown sort order `%c'", c);
 134                 errx(EXIT_FAILURE, "Try `%s --help' for more information.",
 135                      program_invocation_short_name);
 136         }
 137 }
 138
 139 /* Needed to support multiple key sorting. */
 140 int get_order(struct range_t *left, struct range_t *right)
 141 {
 142         int i, len, ret;
 143         unsigned long int lint, rint;
 144
 145         len = strlen(config.sort);
 146         for (i = 0; i < len; i++) {
 147                 /* Handling strings is case of it's own */
 148                 if (config.sort[i] == 'n') {
 149                         ret =
 150                             strcmp(left->shared_net->name,
 151                                    right->shared_net->name);
 152                         if (0 < ret) {
 153                                 return (0);
 154                         } else if (ret < 0) {
 155                                 return (1);
 156                         } else {
 157                                 continue;
 158                         }
 159                 }
 160
 161                 /* Select which function is pointed by returner */
 162                 field_selector(config.sort[i]);
 163                 lint = returner(*left);
 164                 rint = returner(*right);
 165                 /* If fields are equal use next sort method */
 166                 if (lint == rint) {
 167                         continue;
 168                 }
 169                 if (lint < rint) {
 170                         return (1);
 171                 }
 172                 return (0);
 173         }
 174
 175         /* If all returners where equal */
 176         return (0);
 177 }
 178
 179 void mergesort_ranges(struct range_t *orig, int size, struct range_t *temp)
 180 {
 181         int left, right, i;
 182         struct range_t hold;
 183         /* Merge sort split size */
 184         static const int MIN_MERGE_SIZE = 8;
 185
 186         if (size < MIN_MERGE_SIZE) {
 187                 for (left = 0; left < size; left++) {
 188                         hold = *(orig + left);
 189                         for (right = left - 1; 0 <= right; right--) {
 190                                 if (get_order((orig + right), &hold)) {
 191                                         break;
 192                                 }
 193                                 *(orig + right + 1) = *(orig + right);
 194                         }
 195                         *(orig + right + 1) = hold;
 196                 }
 197                 return;
 198         }
 199
 200         mergesort_ranges(orig, size / 2, temp);
 201         mergesort_ranges(orig + size / 2, size - size / 2, temp);
 202
 203         left = 0;
 204         right = size / 2;
 205         i = 0;
 206
 207         while (left < size / 2 && right < size) {
 208                 if (get_order((orig + left), (orig + right))) {
 209                         *(temp + i) = *(orig + left);
 210                         left++;
 211                 } else {
 212                         *(temp + i) = *(orig + right);
 213                         right++;
 214                 }
 215                 i++;
 216         }
 217         while (left < size / 2) {
 218                 *(temp + i) = *(orig + left);
 219                 left++;
 220                 i++;
 221         }
 222         while (right < size) {
 223                 *(temp + i) = *(orig + right);
 224                 right++;
 225                 i++;
 226         }
 227
 228         memcpy(orig, temp, size * sizeof(struct range_t));
 229 }