xrootd/XrdOuc/XrdOucHash.icc

0001 /******************************************************************************/
0002 /*                                                                            */
0003 /*                        X r d O u c H a s h . i c c                         */
0004 /*                                                                            */
0005 /* (c) 2004 by the Board of Trustees of the Leland Stanford, Jr., University  */
0006 /*   Produced by Andrew Hanushevsky for Stanford University under contract    */
0007 /*              DE-AC02-76-SFO0515 with the Department of Energy              */
0008 /*                                                                            */
0009 /* This file is part of the XRootD software suite.                            */
0010 /*                                                                            */
0011 /* XRootD is free software: you can redistribute it and/or modify it under    */
0012 /* the terms of the GNU Lesser General Public License as published by the     */
0013 /* Free Software Foundation, either version 3 of the License, or (at your     */
0014 /* option) any later version.                                                 */
0015 /*                                                                            */
0016 /* XRootD is distributed in the hope that it will be useful, but WITHOUT      */
0017 /* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or      */
0018 /* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public       */
0019 /* License for more details.                                                  */
0020 /*                                                                            */
0021 /* You should have received a copy of the GNU Lesser General Public License   */
0022 /* along with XRootD in a file called COPYING.LESSER (LGPL license) and file  */
0023 /* COPYING (GPL license).  If not, see <http://www.gnu.org/licenses/>.        */
0024 /*                                                                            */
0025 /* The copyright holder's institutional names and contributor's names may not */
0026 /* be used to endorse or promote products derived from this software without  */
0027 /* specific prior written permission of the institution or contributor.       */
0028 /******************************************************************************/
0029
0030 #include <cerrno>
0031 #include <cstring>
0032
0033 /******************************************************************************/
0034 /*                E x t e r n a l   H a s h   F u n c t i o n                 */
0035 /******************************************************************************/
0036
0037 extern unsigned long XrdOucHashVal(const char *KeyVal);
0038
0039 /******************************************************************************/
0040 /*                           C o n s t r u c t o r                            */
0041 /******************************************************************************/
0042
0043 template<class T>
0044 XrdOucHash<T>::XrdOucHash(int psize, int csize, int load)
0045 {
0046      prevtablesize = psize;
0047      hashtablesize = csize;
0048      hashload      = load;
0049      hashmax       = (csize * load) / 100;
0050      hashnum       = 0;
0051      hashtable     = (XrdOucHash_Item<T> **)
0052                      malloc( (size_t)(csize*sizeof(XrdOucHash_Item<T> *)) );
0053      memset((void *)hashtable, 0, (size_t)(csize*sizeof(XrdOucHash_Item<T> *)));
0054 }
0055
0056 /******************************************************************************/
0057 /*                                   A d d                                    */
0058 /******************************************************************************/
0059
0060 template<class T>
0061 T *XrdOucHash<T>::Add(const char *KeyVal, T *KeyData, const int LifeTime,
0062                      XrdOucHash_Options opt)
0063 {
0064     unsigned long khash = XrdOucHashVal(KeyVal);
0065     int hent;
0066     time_t lifetime, KeyTime=0;
0067     XrdOucHash_Item<T> *hip, *newhip, *prevhip;
0068
0069     // Compute the hash index and look up the entry. If found, either
0070     // return an error or delete it because caller wanted it replaced or
0071     // it has expired.
0072     //
0073     hent = khash % hashtablesize;
0074     if ((hip = hashtable[hent]) && (hip = Search(hip, khash, KeyVal, &prevhip)))
0075        {if (opt & Hash_count)
0076            {hip->Update(hip->Count()+1,
0077                        (LifeTime || hip->Time() ? LifeTime + time(0) : 0) );}
0078         if (!(opt & Hash_replace)
0079         && ((lifetime=hip->Time())==0||lifetime>=time(0))) return hip->Data();
0080         Remove(hent, hip, prevhip);
0081        } else {
0082        // Check if we should expand the table
0083        //
0084        if (hashnum >= hashmax) {Expand(); hent = khash % hashtablesize;}
0085        }
0086
0087     // Add the entry
0088     //
0089     if (LifeTime) KeyTime = LifeTime + time(0);
0090     if ( !(newhip = new XrdOucHash_Item<T>(khash, KeyVal, KeyData, KeyTime,
0091                              hashtable[hent], opt)) ) throw ENOMEM;
0092     hashtable[hent] = newhip;
0093     hashnum++;
0094     return (T *)0;
0095 }
0096
0097 /******************************************************************************/
0098 /*                                 A p p l y                                  */
0099 /******************************************************************************/
0100
0101 template<class T>
0102 T *XrdOucHash<T>::Apply(int (*func)(const char *, T *, void *), void *Arg)
0103 {
0104      int i, rc;
0105      time_t lifetime;
0106      XrdOucHash_Item<T> *hip, *prevhip, *nexthip;
0107
0108      //Run through all the entries, applying the function to each. Expire
0109      // dead entries by pretending that the function asked for a deletion.
0110      //
0111      for (i = 0; i < hashtablesize; i++)
0112          {hip = hashtable[i]; prevhip = 0;
0113           while(hip)
0114                {nexthip = hip->Next();
0115                 if ((lifetime = hip->Time()) && lifetime < time(0)) rc = -1;
0116                    else if ( (rc = (*func)(hip->Key(), hip->Data(), Arg)) > 0 )
0117                         return hip->Data();
0118                 if (rc < 0)
0119                    {delete hip;
0120                     if (prevhip) prevhip->SetNext(nexthip);
0121                        else hashtable[i] = nexthip;
0122                     hashnum--;
0123                    }
0124                    else prevhip = hip;
0125                 hip = nexthip;
0126                }
0127          }
0128      return (T *)0;
0129 }
0130
0131 /******************************************************************************/
0132 /*                                   D e l                                    */
0133 /******************************************************************************/
0134
0135 template<class T>
0136 int XrdOucHash<T>::Del(const char *KeyVal, XrdOucHash_Options)
0137 {
0138     unsigned long khash = XrdOucHashVal(KeyVal);
0139     int hent, cnt;
0140     XrdOucHash_Item<T> *hip, *phip, *thip;
0141
0142     // Compute the hash index and look up the entry. If found, return it.
0143     //
0144     hent = khash % hashtablesize;
0145     if (!(thip = hashtable[hent])) return -ENOENT;
0146     if (!( hip = Search(thip, khash, KeyVal, &phip) ) ) return -ENOENT;
0147
0148    // Delete the item and return
0149    //
0150    if ((cnt = hip->Count()) <= 0) Remove(hent, hip, phip);
0151       else hip->Update(cnt-1, 0);
0152    return 0;
0153 }
0154
0155 /******************************************************************************/
0156 /*                                  F i n d                                   */
0157 /******************************************************************************/
0158
0159 template<class T>
0160 T *XrdOucHash<T>::Find(const char *KeyVal, time_t *KeyTime)
0161 {
0162   unsigned long khash = XrdOucHashVal(KeyVal);
0163   int kent;
0164   time_t lifetime = 0;
0165   XrdOucHash_Item<T> *phip, *hip;
0166
0167 // Compute position of the hash table entry
0168 //
0169    kent = khash%hashtablesize;
0170
0171 // Find the entry (remove it if expired and return nothing)
0172 //
0173    if ((hip = hashtable[kent]))
0174       if ((hip = Search(hip, khash, KeyVal, &phip)))
0175           if ( (lifetime = hip->Time()) && lifetime < time(0) )
0176             {Remove(kent, hip, phip);
0177              if (KeyTime) *KeyTime = (time_t)0;
0178              return (T *)0;
0179             }
0180
0181 // Return actual information
0182 //
0183    if (KeyTime) *KeyTime = lifetime;
0184    if (hip) return hip->Data();
0185    return (T *)0;
0186 }
0187
0188 /******************************************************************************/
0189 /*                                 P u r g e                                  */
0190 /******************************************************************************/
0191
0192 template<class T>
0193 void XrdOucHash<T>::Purge()
0194 {
0195      int i;
0196      XrdOucHash_Item<T> *hip, *nexthip;
0197
0198      //Run through all the entries, deleting each one
0199      //
0200      for (i = 0; i < hashtablesize; i++)
0201          {hip = hashtable[i]; hashtable[i] = 0;
0202           while(hip)
0203                {nexthip = hip->Next();
0204                 delete hip;
0205                 hip = nexthip;
0206                }
0207          }
0208      hashnum = 0;
0209 }
0210
0211 /******************************************************************************/
0212 /*                       P r i v a t e   M e t h o d s                        */
0213 /******************************************************************************/
0214
0215 /******************************************************************************/
0216 /*                                E x p a n d                                 */
0217 /******************************************************************************/
0218
0219 template<class T>
0220 void XrdOucHash<T>::Expand()
0221 {
0222     int newsize, newent, i;
0223     size_t memlen;
0224     XrdOucHash_Item<T> **newtab, *hip, *nexthip;
0225
0226     // Compute new size for table using a fibonacci series
0227     //
0228     newsize = prevtablesize +hashtablesize;
0229
0230     // Allocate the new table
0231     //
0232     memlen = (size_t)(newsize*sizeof(XrdOucHash_Item<T> *));
0233     if (!(newtab = (XrdOucHash_Item<T> **) malloc(memlen))) throw ENOMEM;
0234     memset((void *)newtab, 0, memlen);
0235
0236     // Redistribute all of the current items
0237     //
0238     for (i = 0; i < hashtablesize; i++)
0239         {hip = hashtable[i];
0240          while(hip)
0241            {nexthip = hip->Next();
0242             newent  = (hip->Hash()) % newsize;
0243             hip->SetNext(newtab[newent]);
0244             newtab[newent] = hip;
0245             hip = nexthip;
0246            }
0247         }
0248
0249     // Free the old table and plug in the new table
0250     //
0251     free((void *)hashtable);
0252     hashtable     = newtab;
0253     prevtablesize = hashtablesize;
0254     hashtablesize = newsize;
0255
0256     // Compute new expansion threshold
0257     //
0258     hashmax = static_cast<int>((static_cast<long long>(newsize)*hashload)/100);
0259 }
0260
0261 /******************************************************************************/
0262 /*                                R e m o v e                                 */
0263 /******************************************************************************/
0264
0265 template<class T>
0266 void XrdOucHash<T>::Remove(int kent, XrdOucHash_Item<T> *hip,
0267                                     XrdOucHash_Item<T> *phip)
0268 {
0269      if (phip) phip->SetNext(hip->Next());
0270         else hashtable[kent] = hip->Next();
0271      delete hip;
0272      hashnum--;
0273 }
0274
0275 /******************************************************************************/
0276 /*                                S e a r c h                                 */
0277 /******************************************************************************/
0278
0279 template<class T>
0280 XrdOucHash_Item<T> *XrdOucHash<T>::Search(XrdOucHash_Item<T>  *hip,
0281                                         const unsigned long khash,
0282                                         const char         *kval,
0283                                         XrdOucHash_Item<T> **pitem)
0284 {
0285    XrdOucHash_Item<T> *prevp = 0;
0286
0287    // Scan through the chain looking for a match
0288    //
0289    while(hip && !hip->Same(khash, kval))
0290         {prevp = hip;
0291          hip = hip->Next();
0292         }
0293    if (pitem) *pitem = prevp;
0294    return hip;
0295 }