xrootd/XrdOuc/XrdOucRash.icc

0001 /******************************************************************************/
0002 /*                                                                            */
0003 /*                        X r d O u c R a s h . i c c                         */
0004 /*                                                                            */
0005 /* (c) 2005 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
0032 #include "XrdSys/XrdSysPlatform.hh"
0033
0034 /******************************************************************************/
0035 /*                                   A d d                                    */
0036 /******************************************************************************/
0037
0038 template<typename K, typename V>
0039 V *XrdOucRash<K,V>::Add(K KeyVal, V &KeyData, time_t LifeTime,
0040                        XrdOucRash_Options opt)
0041 {
0042     time_t lifetime, KeyTime=0;
0043     XrdOucRash_Item<K,V> *hip;
0044     XrdOucRash_Tent<K,V> *hiploc;
0045
0046 // Look up the entry. If found, either return an error or delete it
0047 // because caller wanted it replaced or it has expired.
0048 //
0049    if ((hip = Lookup(KeyVal, &hiploc)))
0050        {if (opt & Rash_count)
0051            {hip->Update(hip->Count()+1,
0052                        (LifeTime || hip->Time() ? LifeTime + time(0) : 0) );}
0053         if (!(opt & Rash_replace)
0054         && ((lifetime=hip->Time())==0||lifetime>=time(0))) return hip->Data();
0055         hip->Set(KeyData, KeyTime);
0056         return (V *)0;
0057        }
0058
0059 // Create a new item
0060 //
0061    if (LifeTime) KeyTime = LifeTime + time(0);
0062    if ( !(hip = new XrdOucRash_Item<K,V>(KeyVal, KeyData, KeyTime)) )
0063       throw ENOMEM;
0064
0065 // Add this item to the table
0066 //
0067     Insert(KeyVal, hip);
0068     return (V *)0;
0069 }
0070
0071 /******************************************************************************/
0072 /*                                   D e l                                    */
0073 /******************************************************************************/
0074
0075 template<typename K, typename V>
0076 int XrdOucRash<K,V>::Del(K KeyVal)
0077 {
0078     XrdOucRash_Item<K,V> *hip;
0079     XrdOucRash_Tent<K,V> *hiploc;
0080     int cnt;
0081
0082 // Look up the entry. If not found, indicate so.
0083 //
0084    if (!(hip = Lookup(KeyVal, &hiploc))) return -ENOENT;
0085
0086 // Delete the item and return
0087 //
0088    if ((cnt = hip->Count())) {hip->Update(cnt-1, 0); return cnt;}
0089    delete hip;
0090    hiploc->Item = (XrdOucRash_Item<K,V> *)0;
0091    rashnum--;
0092    return 0;
0093
0094 }
0095
0096 /******************************************************************************/
0097 /*                                  F i n d                                   */
0098 /******************************************************************************/
0099
0100 template<typename K, typename V>
0101 V *XrdOucRash<K,V>::Find(K KeyVal, time_t *KeyTime)
0102 {
0103   XrdOucRash_Item<K,V> *hip;
0104   XrdOucRash_Tent<K,V> *hiploc;
0105   time_t lifetime = 0;
0106
0107 // Find the entry (remove it if expired and return nothing)
0108 //
0109    if (!(hip = Lookup(KeyVal, &hiploc))) return (V *)0;
0110    if ( (lifetime = hip->Time()) && lifetime < time(0) )
0111       {delete hip;
0112        hiploc->Item = (XrdOucRash_Item<K,V> *)0;
0113        rashnum--;
0114        if (KeyTime) *KeyTime = (time_t)0;
0115        return (V *)0;
0116       }
0117
0118 // Return actual information
0119 //
0120    if (KeyTime) *KeyTime = lifetime;
0121    return hip->Data();
0122 }
0123
0124 /******************************************************************************/
0125 /*                                 P u r g e                                  */
0126 /******************************************************************************/
0127
0128 template<typename K, typename V>
0129 void XrdOucRash<K,V>::Purge()
0130 {
0131      int i;
0132
0133 // Run through the major table and delete each item in the main table
0134 // the deletion automatically propagates.
0135 //
0136    for (i = 0; i < 16; i++)
0137        {if (rashTable[i].Item)
0138            {delete rashTable[i].Item;  rashTable[i].Item  = 0;}
0139         if (rashTable[i].Table)
0140            {delete []rashTable[i].Table; rashTable[i].Table = 0;}
0141        }
0142    rashnum = 0;
0143 }
0144
0145 /******************************************************************************/
0146 /*                       P r i v a t e   M e t h o d s                        */
0147 /******************************************************************************/
0148 /******************************************************************************/
0149 /*                                 A p p l y                                  */
0150 /******************************************************************************/
0151
0152 template<typename K, typename V>
0153 V *XrdOucRash<K,V>::Apply(XrdOucRash_Tent<K,V> *tab,
0154                           int (*func)(K, V, void *), void *Arg)
0155 {
0156      int i, rc;
0157      time_t lifetime;
0158      XrdOucRash_Item<K,V> *hip;
0159      V *theVal;
0160
0161      //Run through all the entries, applying the function to each. Expire
0162      // dead entries by pretending that the function asked for a deletion.
0163      //
0164      for (i = 0; i < 16; i++)
0165          {if ((hip = tab[i].Item))
0166              {if ((lifetime = hip->Time()) && lifetime < time(0)) rc = -1;
0167                  else if ( (rc = (*func)(hip->Key(), *hip->Data(), Arg)) > 0 )
0168                          return hip->Data();
0169               if (rc < 0) {delete hip;
0170                            tab[i].Item = (XrdOucRash_Item<K,V> *)0;
0171                            rashnum--;
0172                           }
0173              }
0174           if (tab[i].Table && (theVal = Apply(tab[i].Table, func, Arg)))
0175              return theVal;
0176          }
0177      return (V *)0;
0178 }
0179
0180 /******************************************************************************/
0181 /*                                L o o k u p                                 */
0182 /******************************************************************************/
0183
0184 template<typename K, typename V>
0185 XrdOucRash_Item<K,V> *XrdOucRash<K,V>::Lookup(K theKey,
0186                                               XrdOucRash_Tent<K,V> **tloc)
0187 {
0188    unsigned long long kVal = key2ull(theKey);
0189    XrdOucRash_Tent<K,V> *tab = rashTable;
0190    int j;
0191
0192 // Traverse the binary tree and find the entry
0193 //
0194    do {j = kVal & 0x0f;
0195        kVal = kVal >> 4;
0196       } while(kVal && (tab = tab[j].Table));
0197
0198 // Return result
0199 //
0200    if (tab)
0201       {*tloc = &tab[j];
0202        return tab[j].Item;
0203       } else {
0204        *tloc = 0;
0205        return 0;
0206      }
0207 }
0208
0209 /******************************************************************************/
0210 /*                                I n s e r t                                 */
0211 /******************************************************************************/
0212
0213 template<typename K, typename V>
0214 void XrdOucRash<K,V>::Insert(K theKey, XrdOucRash_Item<K,V> *theItem)
0215 {
0216    unsigned long long kVal = key2ull(theKey);
0217    XrdOucRash_Tent<K,V> *tab = rashTable;
0218    int j;
0219
0220 // Traverse the binary tree and find the entry
0221 //
0222    do {j = kVal & 0x0f;
0223        if ((kVal = kVal >> 4))
0224           {if (tab[j].Table) tab = tab[j].Table;
0225               else tab = tab[j].Table = new XrdOucRash_Tent<K,V>[16]();
0226           }
0227       } while(kVal);
0228
0229 // Insert the entry
0230 //
0231    tab[j].Item = theItem;
0232    rashnum++;
0233 }
0234
0235 /******************************************************************************/
0236 /*                               k e y 2 u l l                                */
0237 /******************************************************************************/
0238
0239 template<typename K, typename V>
0240 unsigned long long XrdOucRash<K,V>::key2ull(K theKey)
0241 {
0242 #ifdef Xrd_Big_Endian
0243    union {unsigned long long us; K kv[8/sizeof(K)];} Val;
0244    Val.us = 0;
0245    Val.kv[8/sizeof(K)-1] = theKey;
0246 #else
0247    union {unsigned long long us; K kv;} Val;
0248    Val.us = 0;
0249    Val.kv = theKey;
0250 #endif
0251    return Val.us;
0252 }