From d1f0a3e101cc6e7371c5f3a5aa535c08e4617bb5 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Sat, 27 Nov 2004 23:40:22 -0500 Subject: [svn-r9588] Purpose: Bug fix Description: Correct off-by-on error which could cause invalid # of levels to be used for a skip list node, in rare circumstances. Change from srandom()/random() to more portable srand()/rand() routines for random # generation. Pre-compute the probability factor for computing the level of new nodes, for a minor speedup. Platforms tested: FreeBSD 4.10 (sleipnir) IRIX64 6.5 (modi4) Solaris 2.8 (sol) AIX 5.1(?) (copper) --- src/H5SL.c | 22 +++++++++++++--------- 1 file changed, 13 insertions(+), 9 deletions(-) diff --git a/src/H5SL.c b/src/H5SL.c index 7f4b187..9f1f4a6 100644 --- a/src/H5SL.c +++ b/src/H5SL.c @@ -122,6 +122,7 @@ struct H5SL_t { /* Static values for each list */ H5SL_type_t type; /* Type of skip list */ double p; /* Probability of using a higher level [0..1) */ + int p1; /* Probability converted into appropriate value for random # generator on this machine */ size_t max_level; /* Maximum number of levels */ /* Dynamic values for each list */ @@ -136,7 +137,7 @@ static int interface_initialize_g = 0; /* Static functions */ static herr_t H5SL_init_interface(void); -static size_t H5SL_random_level(double p, size_t max_level); +static size_t H5SL_random_level(int p1, size_t max_level); static H5SL_node_t * H5SL_new_node(size_t lvl, void *item, void *key); /* Declare a free list to manage the H5SL_t struct */ @@ -169,7 +170,7 @@ H5SL_init_interface(void) /* Create randomized set of numbers */ curr_time=HDtime(NULL); - HDsrandom((unsigned long)curr_time); + HDsrand((unsigned)curr_time); FUNC_LEAVE_NOAPI(SUCCEED) } /* end H5SL_init_interface() */ @@ -182,7 +183,7 @@ H5SL_init_interface(void) Generate a random level USAGE size_t H5SL_random_level(p,max_level) - double p; IN: probability distribution + int p1; IN: probability distribution size_t max_level; IN: Maximum level for node height RETURNS @@ -199,14 +200,17 @@ H5SL_init_interface(void) REVISION LOG --------------------------------------------------------------------------*/ static size_t -H5SL_random_level(double p, size_t max_level) +H5SL_random_level(int p1, size_t max_level) { size_t lvl; /* Level generated */ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_random_level); + /* Account for starting at zero offset */ + max_level--; + lvl=0; - while((((double)HDrandom())/((double)LONG_MAX))

type=type; - new_slist->p=p; + new_slist->p1=p*RAND_MAX; new_slist->max_level=max_level; /* Set the dynamic internal fields */ @@ -423,7 +427,7 @@ H5SL_insert(H5SL_t *slist, void *item, void *key) /* 'key' must not have been found in existing list, if we get here */ /* Generate level for new node */ - lvl=H5SL_random_level(slist->p,slist->max_level); + lvl=H5SL_random_level(slist->p1,slist->max_level); if((int)lvl>slist->curr_level) { /* Cap the increase in the current level to just one greater */ lvl=slist->curr_level+1; @@ -432,12 +436,12 @@ H5SL_insert(H5SL_t *slist, void *item, void *key) update[lvl]=&slist->header->forward[lvl]; /* Increase the maximum level of the list */ - slist->curr_level=lvl; + slist->curr_level=(int)lvl; } /* end if */ /* Create new node of proper level */ if((x=H5SL_new_node(lvl,item,key))==NULL) - HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,NULL,"can't create new skip list node"); + HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,FAIL,"can't create new skip list node"); /* Link the new node into the existing list */ for(i=0; i<=(int)lvl; i++) { -- cgit v0.12