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