1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2001,2008 Oracle. All rights reserved. 5 * 6 * $Id: db_idspace.c,v 12.7 2008/01/08 20:58:08 bostic Exp $ 7 */ 8 9#include "db_config.h" 10 11#include "db_int.h" 12 13static int __db_idcmp __P((const void *, const void *)); 14 15static 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 */ 43void 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} 86