summaryrefslogtreecommitdiff
path: root/lib/util/idtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/util/idtree.c')
-rw-r--r--lib/util/idtree.c403
1 files changed, 403 insertions, 0 deletions
diff --git a/lib/util/idtree.c b/lib/util/idtree.c
new file mode 100644
index 0000000000..193922973f
--- /dev/null
+++ b/lib/util/idtree.c
@@ -0,0 +1,403 @@
+/*
+ Unix SMB/CIFS implementation.
+
+ very efficient functions to manage mapping a id (such as a fnum) to
+ a pointer. This is used for fnum and search id allocation.
+
+ Copyright (C) Andrew Tridgell 2004
+
+ This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
+ written by Jim Houston jim.houston@ccur.com, and is
+ Copyright (C) 2002 by Concurrent Computer Corporation
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ see the section marked "public interface" below for documentation
+*/
+
+/**
+ * @file
+ */
+
+#include "includes.h"
+
+#define IDR_BITS 5
+#define IDR_FULL 0xfffffffful
+#if 0 /* unused */
+#define TOP_LEVEL_FULL (IDR_FULL >> 30)
+#endif
+#define IDR_SIZE (1 << IDR_BITS)
+#define IDR_MASK ((1 << IDR_BITS)-1)
+#define MAX_ID_SHIFT (sizeof(int)*8 - 1)
+#define MAX_ID_BIT (1U << MAX_ID_SHIFT)
+#define MAX_ID_MASK (MAX_ID_BIT - 1)
+#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
+#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
+
+#define set_bit(bit, v) (v) |= (1<<(bit))
+#define clear_bit(bit, v) (v) &= ~(1<<(bit))
+#define test_bit(bit, v) ((v) & (1<<(bit)))
+
+struct idr_layer {
+ uint32_t bitmap;
+ struct idr_layer *ary[IDR_SIZE];
+ int count;
+};
+
+struct idr_context {
+ struct idr_layer *top;
+ struct idr_layer *id_free;
+ int layers;
+ int id_free_cnt;
+};
+
+static struct idr_layer *alloc_layer(struct idr_context *idp)
+{
+ struct idr_layer *p;
+
+ if (!(p = idp->id_free))
+ return NULL;
+ idp->id_free = p->ary[0];
+ idp->id_free_cnt--;
+ p->ary[0] = NULL;
+ return p;
+}
+
+static int find_next_bit(uint32_t bm, int maxid, int n)
+{
+ while (n<maxid && !test_bit(n, bm)) n++;
+ return n;
+}
+
+static void free_layer(struct idr_context *idp, struct idr_layer *p)
+{
+ p->ary[0] = idp->id_free;
+ idp->id_free = p;
+ idp->id_free_cnt++;
+}
+
+static int idr_pre_get(struct idr_context *idp)
+{
+ while (idp->id_free_cnt < IDR_FREE_MAX) {
+ struct idr_layer *new = talloc_zero(idp, struct idr_layer);
+ if(new == NULL)
+ return (0);
+ free_layer(idp, new);
+ }
+ return 1;
+}
+
+static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
+{
+ int n, m, sh;
+ struct idr_layer *p, *new;
+ struct idr_layer *pa[MAX_LEVEL];
+ int l, id, oid;
+ uint32_t bm;
+
+ memset(pa, 0, sizeof(pa));
+
+ id = *starting_id;
+restart:
+ p = idp->top;
+ l = idp->layers;
+ pa[l--] = NULL;
+ while (1) {
+ /*
+ * We run around this while until we reach the leaf node...
+ */
+ n = (id >> (IDR_BITS*l)) & IDR_MASK;
+ bm = ~p->bitmap;
+ m = find_next_bit(bm, IDR_SIZE, n);
+ if (m == IDR_SIZE) {
+ /* no space available go back to previous layer. */
+ l++;
+ oid = id;
+ id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
+
+ /* if already at the top layer, we need to grow */
+ if (!(p = pa[l])) {
+ *starting_id = id;
+ return -2;
+ }
+
+ /* If we need to go up one layer, continue the
+ * loop; otherwise, restart from the top.
+ */
+ sh = IDR_BITS * (l + 1);
+ if (oid >> sh == id >> sh)
+ continue;
+ else
+ goto restart;
+ }
+ if (m != n) {
+ sh = IDR_BITS*l;
+ id = ((id >> sh) ^ n ^ m) << sh;
+ }
+ if ((id >= MAX_ID_BIT) || (id < 0))
+ return -1;
+ if (l == 0)
+ break;
+ /*
+ * Create the layer below if it is missing.
+ */
+ if (!p->ary[m]) {
+ if (!(new = alloc_layer(idp)))
+ return -1;
+ p->ary[m] = new;
+ p->count++;
+ }
+ pa[l--] = p;
+ p = p->ary[m];
+ }
+ /*
+ * We have reached the leaf node, plant the
+ * users pointer and return the raw id.
+ */
+ p->ary[m] = (struct idr_layer *)ptr;
+ set_bit(m, p->bitmap);
+ p->count++;
+ /*
+ * If this layer is full mark the bit in the layer above
+ * to show that this part of the radix tree is full.
+ * This may complete the layer above and require walking
+ * up the radix tree.
+ */
+ n = id;
+ while (p->bitmap == IDR_FULL) {
+ if (!(p = pa[++l]))
+ break;
+ n = n >> IDR_BITS;
+ set_bit((n & IDR_MASK), p->bitmap);
+ }
+ return(id);
+}
+
+static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
+{
+ struct idr_layer *p, *new;
+ int layers, v, id;
+
+ idr_pre_get(idp);
+
+ id = starting_id;
+build_up:
+ p = idp->top;
+ layers = idp->layers;
+ if (!p) {
+ if (!(p = alloc_layer(idp)))
+ return -1;
+ layers = 1;
+ }
+ /*
+ * Add a new layer to the top of the tree if the requested
+ * id is larger than the currently allocated space.
+ */
+ while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
+ layers++;
+ if (!p->count)
+ continue;
+ if (!(new = alloc_layer(idp))) {
+ /*
+ * The allocation failed. If we built part of
+ * the structure tear it down.
+ */
+ for (new = p; p && p != idp->top; new = p) {
+ p = p->ary[0];
+ new->ary[0] = NULL;
+ new->bitmap = new->count = 0;
+ free_layer(idp, new);
+ }
+ return -1;
+ }
+ new->ary[0] = p;
+ new->count = 1;
+ if (p->bitmap == IDR_FULL)
+ set_bit(0, new->bitmap);
+ p = new;
+ }
+ idp->top = p;
+ idp->layers = layers;
+ v = sub_alloc(idp, ptr, &id);
+ if (v == -2)
+ goto build_up;
+ return(v);
+}
+
+static int sub_remove(struct idr_context *idp, int shift, int id)
+{
+ struct idr_layer *p = idp->top;
+ struct idr_layer **pa[MAX_LEVEL];
+ struct idr_layer ***paa = &pa[0];
+ int n;
+
+ *paa = NULL;
+ *++paa = &idp->top;
+
+ while ((shift > 0) && p) {
+ n = (id >> shift) & IDR_MASK;
+ clear_bit(n, p->bitmap);
+ *++paa = &p->ary[n];
+ p = p->ary[n];
+ shift -= IDR_BITS;
+ }
+ n = id & IDR_MASK;
+ if (p != NULL && test_bit(n, p->bitmap)) {
+ clear_bit(n, p->bitmap);
+ p->ary[n] = NULL;
+ while(*paa && ! --((**paa)->count)){
+ free_layer(idp, **paa);
+ **paa-- = NULL;
+ }
+ if ( ! *paa )
+ idp->layers = 0;
+ return 0;
+ }
+ return -1;
+}
+
+static void *_idr_find(struct idr_context *idp, int id)
+{
+ int n;
+ struct idr_layer *p;
+
+ n = idp->layers * IDR_BITS;
+ p = idp->top;
+ /*
+ * This tests to see if bits outside the current tree are
+ * present. If so, tain't one of ours!
+ */
+ if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
+ return NULL;
+
+ /* Mask off upper bits we don't use for the search. */
+ id &= MAX_ID_MASK;
+
+ while (n >= IDR_BITS && p) {
+ n -= IDR_BITS;
+ p = p->ary[(id >> n) & IDR_MASK];
+ }
+ return((void *)p);
+}
+
+static int _idr_remove(struct idr_context *idp, int id)
+{
+ struct idr_layer *p;
+
+ /* Mask off upper bits we don't use for the search. */
+ id &= MAX_ID_MASK;
+
+ if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
+ return -1;
+ }
+
+ if ( idp->top && idp->top->count == 1 &&
+ (idp->layers > 1) &&
+ idp->top->ary[0]) {
+ /* We can drop a layer */
+ p = idp->top->ary[0];
+ idp->top->bitmap = idp->top->count = 0;
+ free_layer(idp, idp->top);
+ idp->top = p;
+ --idp->layers;
+ }
+ while (idp->id_free_cnt >= IDR_FREE_MAX) {
+ p = alloc_layer(idp);
+ talloc_free(p);
+ }
+ return 0;
+}
+
+/************************************************************************
+ this is the public interface
+**************************************************************************/
+
+/**
+ initialise a idr tree. The context return value must be passed to
+ all subsequent idr calls. To destroy the idr tree use talloc_free()
+ on this context
+ */
+_PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
+{
+ return talloc_zero(mem_ctx, struct idr_context);
+}
+
+/**
+ allocate the next available id, and assign 'ptr' into its slot.
+ you can retrieve later this pointer using idr_find()
+*/
+_PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
+{
+ int ret = idr_get_new_above_int(idp, ptr, 0);
+ if (ret > limit) {
+ idr_remove(idp, ret);
+ return -1;
+ }
+ return ret;
+}
+
+/**
+ allocate a new id, giving the first available value greater than or
+ equal to the given starting id
+*/
+_PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
+{
+ int ret = idr_get_new_above_int(idp, ptr, starting_id);
+ if (ret > limit) {
+ idr_remove(idp, ret);
+ return -1;
+ }
+ return ret;
+}
+
+/**
+ allocate a new id randomly in the given range
+*/
+_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
+{
+ int id;
+
+ /* first try a random starting point in the whole range, and if that fails,
+ then start randomly in the bottom half of the range. This can only
+ fail if the range is over half full */
+ id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
+ if (id == -1) {
+ id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
+ }
+
+ return id;
+}
+
+/**
+ find a pointer value previously set with idr_get_new given an id
+*/
+_PUBLIC_ void *idr_find(struct idr_context *idp, int id)
+{
+ return _idr_find(idp, id);
+}
+
+/**
+ remove an id from the idr tree
+*/
+_PUBLIC_ int idr_remove(struct idr_context *idp, int id)
+{
+ int ret;
+ ret = _idr_remove((struct idr_context *)idp, id);
+ if (ret != 0) {
+ DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
+ }
+ return ret;
+}
generated by cgit (git 2.34.1) at 2024-11-19 11:12:45 +0000