From: Rusty Russell Date: Thu, 20 May 2010 12:30:32 +0000 (+0930) Subject: idtree: new module X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=184070eb4a4a2e130c0053eb82fd8c96a19e954f;hp=9f8c65b28acba8e5eabea5d7abd98b19e62d06fe idtree: new module --- diff --git a/ccan/idtree/_info b/ccan/idtree/_info new file mode 100644 index 00000000..058b32b4 --- /dev/null +++ b/ccan/idtree/_info @@ -0,0 +1,53 @@ +#include +#include +#include "config.h" + +/** + * idtree - id allocation tree + * + * There are often cases where you want to provide an integer handle for + * some data, and easily map it back to another structure. + * + * idtree is an efficient implementation of an int->void * mapping, with + * assignment of the lowest available id number. It is from the Linux kernel + * via the Samba project. + * + * Example: + * #include + * #include + * #include + * #include + * + * // Silly example which puts args in the idtree and retreives them + * int main(int argc, char *argv[]) + * { + * struct idtree *idtree = idtree_new(NULL); + * unsigned int i; + * + * // This will return consecutive id numbers. + * for (i = 0; i < argc; i++) { + * printf("idtree_add('%s') -> id %i\n", + * argv[i], idtree_add(idtree, argv[i], -1)); + * } + * for (i = 0; i < argc; i++) { + * printf("id %i -> '%s'\n", i, idtree_lookup(idtree, i)); + * } + * return 0; + * } + * + * Licence: GPL (2 or any later version) + * Maintainer: Rusty Russell + * Author: Jim Houston + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/talloc\n"); + return 0; + } + + return 1; +} diff --git a/ccan/idtree/idtree.c b/ccan/idtree/idtree.c new file mode 100644 index 00000000..bf83c318 --- /dev/null +++ b/ccan/idtree/idtree.c @@ -0,0 +1,344 @@ +/* + Based on SAMBA 7ce1356c9f571c55af70bd6b966fe50898c1582d. + + 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 . +*/ + +#include +#include +#include +#include + +#define IDTREE_BITS 5 +#define IDTREE_FULL 0xfffffffful +#if 0 /* unused */ +#define TOP_LEVEL_FULL (IDTREE_FULL >> 30) +#endif +#define IDTREE_SIZE (1 << IDTREE_BITS) +#define IDTREE_MASK ((1 << IDTREE_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 + IDTREE_BITS - 1) / IDTREE_BITS +#define IDTREE_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 idtree_layer { + uint32_t bitmap; + struct idtree_layer *ary[IDTREE_SIZE]; + int count; +}; + +struct idtree { + struct idtree_layer *top; + struct idtree_layer *id_free; + int layers; + int id_free_cnt; +}; + +static struct idtree_layer *alloc_layer(struct idtree *idp) +{ + struct idtree_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 (nary[0] = idp->id_free; + idp->id_free = p; + idp->id_free_cnt++; +} + +static int idtree_pre_get(struct idtree *idp) +{ + while (idp->id_free_cnt < IDTREE_FREE_MAX) { + struct idtree_layer *pn = talloc_zero(idp, struct idtree_layer); + if(pn == NULL) + return (0); + free_layer(idp, pn); + } + return 1; +} + +static int sub_alloc(struct idtree *idp, const void *ptr, int *starting_id) +{ + int n, m, sh; + struct idtree_layer *p, *pn; + struct idtree_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 >> (IDTREE_BITS*l)) & IDTREE_MASK; + bm = ~p->bitmap; + m = find_next_bit(bm, IDTREE_SIZE, n); + if (m == IDTREE_SIZE) { + /* no space available go back to previous layer. */ + l++; + oid = id; + id = (id | ((1 << (IDTREE_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 = IDTREE_BITS * (l + 1); + if (oid >> sh == id >> sh) + continue; + else + goto restart; + } + if (m != n) { + sh = IDTREE_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 (!(pn = alloc_layer(idp))) + return -1; + p->ary[m] = pn; + 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 idtree_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 == IDTREE_FULL) { + if (!(p = pa[++l])) + break; + n = n >> IDTREE_BITS; + set_bit((n & IDTREE_MASK), p->bitmap); + } + return(id); +} + +static int idtree_get_new_above_int(struct idtree *idp, + const void *ptr, int starting_id) +{ + struct idtree_layer *p, *pn; + int layers, v, id; + + idtree_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*IDTREE_BITS)))) { + layers++; + if (!p->count) + continue; + if (!(pn = alloc_layer(idp))) { + /* + * The allocation failed. If we built part of + * the structure tear it down. + */ + for (pn = p; p && p != idp->top; pn = p) { + p = p->ary[0]; + pn->ary[0] = NULL; + pn->bitmap = pn->count = 0; + free_layer(idp, pn); + } + return -1; + } + pn->ary[0] = p; + pn->count = 1; + if (p->bitmap == IDTREE_FULL) + set_bit(0, pn->bitmap); + p = pn; + } + 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 idtree *idp, int shift, int id) +{ + struct idtree_layer *p = idp->top; + struct idtree_layer **pa[MAX_LEVEL]; + struct idtree_layer ***paa = &pa[0]; + int n; + + *paa = NULL; + *++paa = &idp->top; + + while ((shift > 0) && p) { + n = (id >> shift) & IDTREE_MASK; + clear_bit(n, p->bitmap); + *++paa = &p->ary[n]; + p = p->ary[n]; + shift -= IDTREE_BITS; + } + n = id & IDTREE_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; +} + +void *idtree_lookup(const struct idtree *idp, int id) +{ + int n; + struct idtree_layer *p; + + n = idp->layers * IDTREE_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 + IDTREE_BITS)) + return NULL; + + /* Mask off upper bits we don't use for the search. */ + id &= MAX_ID_MASK; + + while (n >= IDTREE_BITS && p) { + n -= IDTREE_BITS; + p = p->ary[(id >> n) & IDTREE_MASK]; + } + return((void *)p); +} + +bool idtree_remove(struct idtree *idp, int id) +{ + struct idtree_layer *p; + + /* Mask off upper bits we don't use for the search. */ + id &= MAX_ID_MASK; + + if (sub_remove(idp, (idp->layers - 1) * IDTREE_BITS, id) == -1) { + return false; + } + + 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 >= IDTREE_FREE_MAX) { + p = alloc_layer(idp); + talloc_free(p); + } + return true; +} + +struct idtree *idtree_new(void *mem_ctx) +{ + return talloc_zero(mem_ctx, struct idtree); +} + +int idtree_add(struct idtree *idp, const void *ptr, int limit) +{ + int ret = idtree_get_new_above_int(idp, ptr, 0); + if (ret > limit) { + idtree_remove(idp, ret); + return -1; + } + return ret; +} + +int idtree_add_above(struct idtree *idp, const void *ptr, + int starting_id, int limit) +{ + int ret = idtree_get_new_above_int(idp, ptr, starting_id); + if (ret > limit) { + idtree_remove(idp, ret); + return -1; + } + return ret; +} diff --git a/ccan/idtree/idtree.h b/ccan/idtree/idtree.h new file mode 100644 index 00000000..a8f8719b --- /dev/null +++ b/ccan/idtree/idtree.h @@ -0,0 +1,53 @@ +#ifndef CCAN_IDTREE_H +#define CCAN_IDTREE_H +#include + +/** + * idtree_new - create an idr_context + * @mem_ctx: talloc parent to allocate from (may be NULL). + * + * Allocate an empty id tree. You can free it with talloc_free(). + */ +struct idtree *idtree_new(void *mem_ctx); + +/** + * idtree_add - get lowest available id, and assign a pointer to it. + * @idtree: the tree to allocate from + * @ptr: the non-NULL pointer to associate with the id + * @limit: the maximum id to allocate (ie. INT_MAX means no limit). + * + * This returns a non-negative id number, or -1 if all are taken. + */ +int idtree_add(struct idtree *idtree, const void *ptr, int limit); + +/** + * idtree_add_above - get lowest available id, starting at a given value. + * @idtree: the tree to allocate from + * @ptr: the non-NULL pointer to associate with the id + * @starting_id: the minimum id value to consider. + * @limit: the maximum id to allocate (ie. INT_MAX means no limit). + * + * This returns a non-negative id number, or -1 if all are taken. + */ +int idtree_add_above(struct idtree *idtree, const void *ptr, + int starting_id, int limit); + +/** + * idtree_lookup - look up a given id + * @idtree: the tree to look in + * @id: the id to look up + * + * Returns NULL if the value is not found, otherwise the pointer value + * set with the idtree_add()/idtree_add_above(). + */ +void *idtree_lookup(const struct idtree *idtree, int id); + +/** + * idtree_remove - remove a given id. + * @idtree: the tree to remove from + * @id: the id to remove. + * + * Returns false if the id was not in the tree. + */ +bool idtree_remove(struct idtree *idtree, int id); +#endif /* CCAN_IDTREE_H */ diff --git a/ccan/idtree/test/run.c b/ccan/idtree/test/run.c new file mode 100644 index 00000000..bd12f4c3 --- /dev/null +++ b/ccan/idtree/test/run.c @@ -0,0 +1,47 @@ +#include +#include +#include + +#define ALLOC_MAX 32 + +int main(int argc, char *argv[]) +{ + unsigned int i; + const char allocated[ALLOC_MAX] = { 0 }; + struct idtree *idtree; + void *ctx; + + plan_tests(ALLOC_MAX * 5 + 2); + ctx = talloc_named_const(NULL, 1, "test root"); + idtree = idtree_new(ctx); + ok1(talloc_find_parent_byname(idtree, "test root") == ctx); + + for (i = 0; i < ALLOC_MAX; i++) { + int id = idtree_add(idtree, &allocated[i], ALLOC_MAX-1); + ok1(id == i); + ok1(idtree_lookup(idtree, i) == &allocated[i]); + } + ok1(idtree_add(idtree, &allocated[i], ALLOC_MAX-1) == -1); + + /* Remove every second one. */ + for (i = 0; i < ALLOC_MAX; i += 2) + ok1(idtree_remove(idtree, i)); + + for (i = 0; i < ALLOC_MAX; i++) { + if (i % 2 == 0) + ok1(!idtree_lookup(idtree, i)); + else + ok1(idtree_lookup(idtree, i) == &allocated[i]); + } + + /* Now, finally, reallocate. */ + for (i = 0; i < ALLOC_MAX/2; i++) { + ok1(idtree_add(idtree, &allocated[i*2], INT_MAX) == i * 2); + } + + for (i = 0; i < ALLOC_MAX; i++) { + ok1(idtree_lookup(idtree, i) == &allocated[i]); + } + talloc_free(ctx); + exit(exit_status()); +}