From: Andrew Tridgell Date: Fri, 22 Oct 2004 06:46:04 +0000 (+0000) Subject: r3130: - added a LOCAL-IDTREE test suite X-Git-Tag: samba-4.0.0alpha6~801^3~13043 X-Git-Url: http://git.samba.org/samba.git/?p=bbaumbach%2Fsamba-autobuild%2F.git;a=commitdiff_plain;h=517238f0aa1a578aec69a40e92022a7636780c3a r3130: - added a LOCAL-IDTREE test suite - made idtree return a "struct idr_context *" instead of a void* - more efficient idr_remove for ids that are not present (patch from Jim Houston) (This used to be commit f8d12d4b4ae5a38de7869deb782cb8f48504844c) --- diff --git a/source4/lib/idtree.c b/source4/lib/idtree.c index 1243c4f3b91..c4370a812d8 100644 --- a/source4/lib/idtree.c +++ b/source4/lib/idtree.c @@ -44,6 +44,7 @@ #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; @@ -51,14 +52,14 @@ struct idr_layer { int count; }; -struct idr { +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 *idp) +static struct idr_layer *alloc_layer(struct idr_context *idp) { struct idr_layer *p; @@ -72,18 +73,18 @@ static struct idr_layer *alloc_layer(struct idr *idp) 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 idr_pre_get(struct idr *idp) +static int idr_pre_get(struct idr_context *idp) { while (idp->id_free_cnt < IDR_FREE_MAX) { struct idr_layer *new = talloc_zero_p(idp, struct idr_layer); @@ -94,7 +95,7 @@ static int idr_pre_get(struct idr *idp) return 1; } -static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) +static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id) { int n, m, sh; struct idr_layer *p, *new; @@ -166,7 +167,7 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) return(id); } -static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_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; @@ -217,24 +218,25 @@ build_up: return(v); } -static void sub_remove(struct idr *idp, int shift, int id) +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) { - int n = (id >> shift) & IDR_MASK; + n = (id >> shift) & IDR_MASK; clear_bit(n, p->bitmap); *++paa = &p->ary[n]; p = p->ary[n]; shift -= IDR_BITS; } - if (p != NULL) { - int n = id & IDR_MASK; + 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)){ @@ -243,10 +245,12 @@ static void sub_remove(struct idr *idp, int shift, int id) } if ( ! *paa ) idp->layers = 0; + return 0; } + return -1; } -static void *_idr_find(struct idr *idp, int id) +static void *_idr_find(struct idr_context *idp, int id) { int n; struct idr_layer *p; @@ -270,20 +274,17 @@ static void *_idr_find(struct idr *idp, int id) return((void *)p); } -static void _idr_remove(struct idr *idp, int id) +static int _idr_remove(struct idr_context *idp, int id) { struct idr_layer *p; - if (_idr_find(idp, id) == NULL) { - DEBUG(0,("WARNING: attempt to remove non-existant id %d in idtree\n", - id)); - return; - } - /* Mask off upper bits we don't use for the search. */ id &= MAX_ID_MASK; - sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); + 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]) { @@ -297,8 +298,8 @@ static void _idr_remove(struct idr *idp, int id) while (idp->id_free_cnt >= IDR_FREE_MAX) { p = alloc_layer(idp); talloc_free(p); - return; } + return 0; } /************************************************************************ @@ -310,18 +311,18 @@ static void _idr_remove(struct idr *idp, int id) all subsequent idr calls. To destroy the idr tree use talloc_free() on this context */ -void *idr_init(TALLOC_CTX *mem_ctx) +struct idr_context *idr_init(TALLOC_CTX *mem_ctx) { - return talloc_zero_p(mem_ctx, struct idr); + return talloc_zero_p(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() */ -int idr_get_new(void *idp, void *ptr, int limit) +int idr_get_new(struct idr_context *idp, void *ptr, int limit) { - int ret = idr_get_new_above_int((struct idr *)idp, ptr, 0); + int ret = idr_get_new_above_int(idp, ptr, 0); if (ret > limit) { idr_remove(idp, ret); return -1; @@ -333,9 +334,9 @@ int idr_get_new(void *idp, void *ptr, int limit) allocate a new id, giving the first available value greater than or equal to the given starting id */ -int idr_get_new_above(void *idp, void *ptr, int starting_id, int limit) +int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit) { - int ret = idr_get_new_above_int((struct idr *)idp, ptr, starting_id); + int ret = idr_get_new_above_int(idp, ptr, starting_id); if (ret > limit) { idr_remove(idp, ret); return -1; @@ -346,15 +347,20 @@ int idr_get_new_above(void *idp, void *ptr, int starting_id, int limit) /* find a pointer value previously set with idr_get_new given an id */ -void *idr_find(void *idp, int id) +void *idr_find(struct idr_context *idp, int id) { - return _idr_find((struct idr *)idp, id); + return _idr_find(idp, id); } /* remove an id from the idr tree */ -void idr_remove(void *idp, int id) +int idr_remove(struct idr_context *idp, int id) { - return _idr_remove((struct idr *)idp, 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; } diff --git a/source4/torture/config.mk b/source4/torture/config.mk index e64d0418893..49ab3fba438 100644 --- a/source4/torture/config.mk +++ b/source4/torture/config.mk @@ -104,7 +104,8 @@ ADD_OBJ_FILES = \ torture/local/iconv.o \ torture/local/talloc.o \ torture/local/messaging.o \ - torture/local/binding_string.o + torture/local/binding_string.o \ + torture/local/idtree.o REQUIRED_SUBSYSTEMS = \ LIBSMB \ MESSAGING diff --git a/source4/torture/local/idtree.c b/source4/torture/local/idtree.c new file mode 100644 index 00000000000..36360b59175 --- /dev/null +++ b/source4/torture/local/idtree.c @@ -0,0 +1,100 @@ +/* + Unix SMB/CIFS implementation. + + local testing of idtree routines. + + Copyright (C) Andrew Tridgell 2004 + + 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, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +#include "includes.h" + +BOOL torture_local_idtree(int dummy) +{ + struct idr_context *idr; + int i; + int *ids; + int *present; + BOOL ret = True; + extern int torture_numops; + int n = torture_numops; + void *ctx = talloc(NULL, 0); + + idr = idr_init(ctx); + + ids = talloc_zero_array_p(ctx, int, n); + present = talloc_zero_array_p(ctx, int, n); + + for (i=0;i