common/db_idspace.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 2001-2009 Oracle.  All rights reserved.
   5  *
   6  * $Id$
   7  */
   8
   9 #include "db_config.h"
  10
  11 #include "db_int.h"
  12
  13 static int __db_idcmp __P((const void *, const void *));
  14
  15 static int
  16 __db_idcmp(a, b)
  17         const void *a;
  18         const void *b;
  19 {
  20         u_int32_t i, j;
  21
  22         i = *(u_int32_t *)a;
  23         j = *(u_int32_t *)b;
  24
  25         if (i < j)
  26                 return (-1);
  27         else if (i > j)
  28                 return (1);
  29         else
  30                 return (0);
  31 }
  32
  33 /*
  34  * __db_idspace --
  35  *
  36  * On input, minp and maxp contain the minimum and maximum valid values for
  37  * the name space and on return, they contain the minimum and maximum ids
  38  * available (by finding the biggest gap).  The minimum can be an inuse
  39  * value, but the maximum cannot be.
  40  *
  41  * PUBLIC: void __db_idspace __P((u_int32_t *, int, u_int32_t *, u_int32_t *));
  42  */
  43 void
  44 __db_idspace(inuse, n, minp, maxp)
  45         u_int32_t *inuse;
  46         int n;
  47         u_int32_t *minp, *maxp;
  48 {
  49         int i, low;
  50         u_int32_t gap, t;
  51
  52         /* A single locker ID is a special case. */
  53         if (n == 1) {
  54                 /*
  55                  * If the single item in use is the last one in the range,
  56                  * then we've got to perform wrap which means that we set
  57                  * the min to the minimum ID, which is what we came in with,
  58                  * so we don't do anything.
  59                  */
  60                 if (inuse[0] != *maxp)
  61                         *minp = inuse[0];
  62                 *maxp = inuse[0] - 1;
  63                 return;
  64         }
  65
  66         gap = 0;
  67         low = 0;
  68         qsort(inuse, (size_t)n, sizeof(u_int32_t), __db_idcmp);
  69         for (i = 0; i < n - 1; i++)
  70                 if ((t = (inuse[i + 1] - inuse[i])) > gap) {
  71                         gap = t;
  72                         low = i;
  73                 }
  74
  75         /* Check for largest gap at the end of the space. */
  76         if ((*maxp - inuse[n - 1]) + (inuse[0] - *minp) > gap) {
  77                 /* Do same check as we do in the n == 1 case. */
  78                 if (inuse[n - 1] != *maxp)
  79                         *minp = inuse[n - 1];
  80                 *maxp = inuse[0] - 1;
  81         } else {
  82                 *minp = inuse[low];
  83                 *maxp = inuse[low + 1] - 1;
  84         }
  85 }