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