XrdOucHash.hh

Go to the documentation of this file.
00001 #ifndef __OOUC_HASH__
00002 #define __OOUC_HASH__
00003 /******************************************************************************/
00004 /*                                                                            */
00005 /*                         X r d O u c H a s h . h h                          */
00006 /*                                                                            */
00007 /* (c) 2004 by the Board of Trustees of the Leland Stanford, Jr., University  */
00008 /*   Produced by Andrew Hanushevsky for Stanford University under contract    */
00009 /*              DE-AC02-76-SFO0515 with the Department of Energy              */
00010 /*                                                                            */
00011 /* This file is part of the XRootD software suite.                            */
00012 /*                                                                            */
00013 /* XRootD is free software: you can redistribute it and/or modify it under    */
00014 /* the terms of the GNU Lesser General Public License as published by the     */
00015 /* Free Software Foundation, either version 3 of the License, or (at your     */
00016 /* option) any later version.                                                 */
00017 /*                                                                            */
00018 /* XRootD is distributed in the hope that it will be useful, but WITHOUT      */
00019 /* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or      */
00020 /* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public       */
00021 /* License for more details.                                                  */
00022 /*                                                                            */
00023 /* You should have received a copy of the GNU Lesser General Public License   */
00024 /* along with XRootD in a file called COPYING.LESSER (LGPL license) and file  */
00025 /* COPYING (GPL license).  If not, see <http://www.gnu.org/licenses/>.        */
00026 /*                                                                            */
00027 /* The copyright holder's institutional names and contributor's names may not */
00028 /* be used to endorse or promote products derived from this software without  */
00029 /* specific prior written permission of the institution or contributor.       */
00030 /******************************************************************************/
00031 
00032 #include <stdlib.h>
00033 #include <sys/types.h>
00034 #include <string.h>
00035 #include <time.h>
00036 
00037 /*
00038 Hash_data_is_key - The key and data are the same so when an item is added
00039                    the data pointer is set to the key address.
00040 Hash_replace     - When adding an item, any existing item is replaced.
00041 Hash_count       - The number of deletion requests must equal the number of
00042                    additions before the item is actually deleted.
00043 Hash_keep        - When the item is added, the key is not duplicated and
00044                    when the item is deleted, the key *and* data are not deleted.
00045 Hash_dofree      - When an item is deleted the data is released using free()
00046                    instead of delete().
00047 Hash_keepdata    - Works like Hash_keep but only applies to the data object.
00048                    When adding the entry, the key is strdup'd and when deleting
00049                    an entry, the key is freed.
00050 */
00051 enum XrdOucHash_Options {Hash_default     = 0x0000,
00052                         Hash_data_is_key = 0x0001,
00053                         Hash_replace     = 0x0002,
00054                         Hash_count       = 0x0004,
00055                         Hash_keep        = 0x0008,
00056                         Hash_dofree      = 0x0010,
00057                         Hash_keepdata    = 0x0020
00058                        };
00059   
00060 template<class T>
00061 class XrdOucHash_Item
00062 {
00063 public:
00064 int                 Count() {return keycount;}
00065 
00066 T                   *Data() {return keydata;}
00067 
00068       unsigned long  Hash() {return keyhash;}
00069 
00070 const char          *Key()  {return keyval;}
00071 
00072 XrdOucHash_Item<T>   *Next() {return next;}
00073 
00074 time_t               Time() {return keytime;}
00075 
00076 void                 Update(int newcount, time_t newtime)
00077                             {keycount = newcount; 
00078                              if (newtime) keytime = newtime;
00079                             }
00080 
00081 int                  Same(const unsigned long KeyHash, const char *KeyVal)
00082                          {return keyhash == KeyHash && !strcmp(keyval, KeyVal);}
00083 
00084 void                 SetNext(XrdOucHash_Item<T> *item) {next = item;}
00085 
00086      XrdOucHash_Item(unsigned long      KeyHash,
00087                     const char        *KeyVal,
00088                     T                 *KeyData,
00089                     time_t             KeyTime,
00090                     XrdOucHash_Item<T> *KeyNext,
00091                     XrdOucHash_Options  KeyOpts)
00092           {keyhash = KeyHash; 
00093            if (KeyOpts & Hash_keep) keyval = KeyVal;
00094               else keyval  = strdup(KeyVal);
00095            if (KeyOpts & Hash_data_is_key) keydata = (T *)keyval;
00096               else keydata = KeyData;
00097            keytime = KeyTime;
00098            entopts = KeyOpts;
00099            next    = KeyNext;
00100            keycount= 0;
00101           }
00102 
00103     ~XrdOucHash_Item()
00104           {if (!(entopts & Hash_keep))
00105               {if (keydata && keydata != (T *)keyval 
00106                && !(entopts & Hash_keepdata))
00107                   {if (entopts & Hash_dofree) free(keydata);
00108                       else delete keydata;
00109                   }
00110                if (keyval)  free((void *)keyval);
00111               }
00112            keydata = 0; keyval = 0; keycount = 0;
00113           }
00114 
00115 private:
00116 
00117 XrdOucHash_Item<T> *next;
00118 const char        *keyval;
00119 unsigned long      keyhash;
00120 T                 *keydata;
00121 time_t             keytime;
00122 int                keycount;
00123 XrdOucHash_Options  entopts;
00124 };
00125 
00126 template<class T>
00127 class XrdOucHash
00128 {
00129 public:
00130 
00131 // Add() adds a new item to the hash. If it exists and repl = 0 then the old
00132 //       entry is returned and the new data is not added. Otherwise the current
00133 //       entry is replaced (see Rep()) and 0 is returned. If we have no memory
00134 //       to add the new entry, an ENOMEM exception is thrown. The
00135 //       LifeTime value is the number of seconds this entry is to be considered
00136 //       valid. When the time has passed, the entry may be deleted. A value
00137 //       of zero, keeps the entry until explicitly deleted. A special feature
00138 //       allows the data to be associated with the key to be the actual key
00139 //       using the Hash_data_is_key option. In this case, KeyData is ignored.
00140 //       The Hash_count option keeps track of duplicate key entries for Del.
00141 //
00142 T           *Add(const char *KeyVal, T *KeyData, const int LifeTime=0, 
00143                  XrdOucHash_Options opt=Hash_default);
00144 
00145 // Del() deletes the item from the hash. If it doesn't exist, it returns
00146 //       -ENOENT. Otherwise 0 is returned. If the Hash_count option is specified
00147 //       tyhen the entry is only deleted when the entry count is below 0.
00148 //
00149 int          Del(const char *KeyVal, XrdOucHash_Options opt = Hash_default);
00150 
00151 // Find() simply looks up an entry in the cache. It can optionally return the
00152 //        lifetime associated with the entry. If the
00153 //
00154 T           *Find(const char *KeyVal, time_t *KeyTime=0);
00155 
00156 // Num() returns the number of items in the hash table
00157 //
00158 int          Num() {return hashnum;}
00159 
00160 // Purge() simply deletes all of the appendages to the table.
00161 //
00162 void         Purge();
00163 
00164 // Rep() is simply Add() that allows replacement.
00165 //
00166 T           *Rep(const char *KeyVal, T *KeyData, const int LifeTime=0,
00167                  XrdOucHash_Options opt=Hash_default)
00168                 {return Add(KeyVal, KeyData, LifeTime, 
00169                             (XrdOucHash_Options)(opt | Hash_replace));}
00170 
00171 // Apply() applies the specified function to every item in the hash. The
00172 //         first argument is the key value, the second is the associated data,
00173 //         the third argument is whatever is the passed in void *variable, The
00174 //         following actions occur for values returned by the applied function:
00175 //         <0 - The hash table item is deleted.
00176 //         =0 - The next hash table item is processed.
00177 //         >0 - Processing stops and the hash table item is returned.
00178 //
00179 T           *Apply(int (*func)(const char *, T *, void *), void *Arg);
00180 
00181 // When allocateing a new hash, specify the required starting size. Make
00182 // sure that the previous number is the correct Fibonocci antecedent. The
00183 // series is simply n[j] = n[j-1] + n[j-2].
00184 //
00185     XrdOucHash(int psize = 89, int size=144, int load=80);
00186    ~XrdOucHash() {if (hashtable) {Purge(); free(hashtable); hashtable = 0;}}
00187 
00188 private:
00189 void Remove(int kent, XrdOucHash_Item<T> *hip, XrdOucHash_Item<T> *phip);
00190 
00191 XrdOucHash_Item<T> *Search(XrdOucHash_Item<T> *hip, 
00192                           const unsigned long khash,
00193                           const char *kval, 
00194                           XrdOucHash_Item<T> **phip=0);
00195 
00196 unsigned long HashVal(const char *KeyVal);
00197 
00198 void Expand();
00199 
00200 XrdOucHash_Item<T> **hashtable;
00201 int                 prevtablesize;
00202 int                 hashtablesize;
00203 int                 hashnum;
00204 int                 hashmax;
00205 int                 hashload;
00206 };
00207 
00208 /******************************************************************************/
00209 /*                 A c t u a l   I m p l e m e n t a t i o n                  */
00210 /******************************************************************************/
00211   
00212 #include "XrdOuc/XrdOucHash.icc"
00213 #endif

Generated on 5 Oct 2016 for xrootd by  doxygen 1.4.7