/******************************************************************************/
/* */
/* X r d C m s N a s h . h h */
/* */
/* (c) 2007 by the Board of Trustees of the Leland Stanford, Jr., University */
/* All Rights Reserved */
/* Produced by Andrew Hanushevsky for Stanford University under contract */
/* DE-AC02-76-SFO0515 with the Department of Energy */
/* */
/* This file is part of the XRootD software suite. */
/* */
/* XRootD is free software: you can redistribute it and/or modify it under */
/* the terms of the GNU Lesser General Public License as published by the */
/* Free Software Foundation, either version 3 of the License, or (at your */
/* option) any later version. */
/* */
/* XRootD 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 Lesser General Public */
/* License for more details. */
/* */
/* You should have received a copy of the GNU Lesser General Public License */
/* along with XRootD in a file called COPYING.LESSER (LGPL license) and file */
/* COPYING (GPL license). If not, see . */
/* */
/* The copyright holder's institutional names and contributor's names may not */
/* be used to endorse or promote products derived from this software without */
/* specific prior written permission of the institution or contributor. */
/******************************************************************************/
#include
#include "XrdCms/XrdCmsNash.hh"
/******************************************************************************/
/* C o n s t r u c t o r */
/******************************************************************************/
XrdCmsNash::XrdCmsNash(int psize, int csize)
{
prevtablesize = psize;
nashtablesize = csize;
Threshold = (csize * LoadMax) / 100;
nashnum = 0;
nashtable = (XrdCmsKeyItem **)
malloc( (size_t)(csize*sizeof(XrdCmsKeyItem *)) );
memset((void *)nashtable, 0, (size_t)(csize*sizeof(XrdCmsKeyItem *)));
}
/******************************************************************************/
/* public A d d */
/******************************************************************************/
XrdCmsKeyItem *XrdCmsNash::Add(XrdCmsKey &Key)
{
XrdCmsKeyItem *hip;
unsigned int kent;
// Allocate the entry
//
if (!(hip = XrdCmsKeyItem::Alloc(Key.TOD))) return (XrdCmsKeyItem *)0;
// Check if we should expand the table
//
if (++nashnum > Threshold) Expand();
// Fill out the key data
//
if (!Key.Hash) Key.setHash();
hip->Key = Key;
// Add the entry to the table
//
kent = Key.Hash % nashtablesize;
hip->Next = nashtable[kent];
nashtable[kent] = hip;
return hip;
}
/******************************************************************************/
/* private E x p a n d */
/******************************************************************************/
void XrdCmsNash::Expand()
{
int newsize, newent, i;
size_t memlen;
XrdCmsKeyItem **newtab, *nip, *nextnip;
// Compute new size for table using a fibonacci series
//
newsize = prevtablesize + nashtablesize;
// Allocate the new table
//
memlen = (size_t)(newsize*sizeof(XrdCmsKeyItem *));
if (!(newtab = (XrdCmsKeyItem **) malloc(memlen))) return;
memset((void *)newtab, 0, memlen);
// Redistribute all of the current items
//
for (i = 0; i < nashtablesize; i++)
{nip = nashtable[i];
while(nip)
{nextnip = nip->Next;
newent = nip->Key.Hash % newsize;
nip->Next = newtab[newent];
newtab[newent] = nip;
nip = nextnip;
}
}
// Free the old table and plug in the new table
//
free((void *)nashtable);
nashtable = newtab;
prevtablesize = nashtablesize;
nashtablesize = newsize;
// Compute new expansion threshold
//
Threshold = static_cast((static_cast(newsize)*LoadMax)/100);
}
/******************************************************************************/
/* public F i n d */
/******************************************************************************/
XrdCmsKeyItem *XrdCmsNash::Find(XrdCmsKey &Key)
{
XrdCmsKeyItem *nip;
unsigned int kent;
// Check if we already have a hash value and get one if not
//
if (!Key.Hash) Key.setHash();
// Compute position of the hash table entry
//
kent = Key.Hash%nashtablesize;
// Find the entry
//
nip = nashtable[kent];
while(nip && nip->Key != Key) nip = nip->Next;
return nip;
}
/******************************************************************************/
/* public R e c y c l e */
/******************************************************************************/
// The item must have been previously unload which will place the original
// hash value in Loc.HashSave. Yes, not very OO but very fast.
//
int XrdCmsNash::Recycle(XrdCmsKeyItem *rip)
{
XrdCmsKeyItem *nip, *pip = 0;
unsigned int kent;
// Compute position of the hash table entry
//
kent = rip->Loc.HashSave%nashtablesize;
// Find the entry
//
nip = nashtable[kent];
while(nip && nip != rip) {pip = nip; nip = nip->Next;}
// Remove and recycle if found
//
if (nip)
{if (pip) pip->Next = nip->Next;
else nashtable[kent] = nip->Next;
rip->Recycle();
nashnum--;
}
return nip != 0;
}