db_idspace.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:2k
- /*-
- * 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];
- }
- }