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