xrootd
|
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 /* All Rights Reserved. See XrdInfo.cc for complete License Terms */ 00009 /* Produced by Andrew Hanushevsky for Stanford University under contract */ 00010 /* DE-AC03-76-SFO0515 with the Department of Energy */ 00011 /******************************************************************************/ 00012 00013 // $Id$ 00014 00015 #include <stdlib.h> 00016 #include <sys/types.h> 00017 #include <string.h> 00018 #include <time.h> 00019 00020 /* 00021 Hash_data_is_key - The key and data are the same so when an item is added 00022 the data pointer is set to the key address. 00023 Hash_replace - When adding an item, any existing item is replaced. 00024 Hash_count - The number of deletion requests must equal the number of 00025 additions before the item is actually deleted. 00026 Hash_keep - When the item is added, the key is not duplicated and 00027 when the item is deleted, the key *and* data are not deleted. 00028 Hash_dofree - When an item is deleted the data is released using free() 00029 instead of delete(). 00030 Hash_keepdata - Works like Hash_keep but only applies to the data object. 00031 When adding the entry, the key is strdup'd and when deleting 00032 an entry, the key is freed. 00033 */ 00034 enum XrdOucHash_Options {Hash_default = 0x0000, 00035 Hash_data_is_key = 0x0001, 00036 Hash_replace = 0x0002, 00037 Hash_count = 0x0004, 00038 Hash_keep = 0x0008, 00039 Hash_dofree = 0x0010, 00040 Hash_keepdata = 0x0020 00041 }; 00042 00043 template<class T> 00044 class XrdOucHash_Item 00045 { 00046 public: 00047 int Count() {return keycount;} 00048 00049 T *Data() {return keydata;} 00050 00051 unsigned long Hash() {return keyhash;} 00052 00053 const char *Key() {return keyval;} 00054 00055 XrdOucHash_Item<T> *Next() {return next;} 00056 00057 time_t Time() {return keytime;} 00058 00059 void Update(int newcount, time_t newtime) 00060 {keycount = newcount; 00061 if (newtime) keytime = newtime; 00062 } 00063 00064 int Same(const unsigned long KeyHash, const char *KeyVal) 00065 {return keyhash == KeyHash && !strcmp(keyval, KeyVal);} 00066 00067 void SetNext(XrdOucHash_Item<T> *item) {next = item;} 00068 00069 XrdOucHash_Item(unsigned long KeyHash, 00070 const char *KeyVal, 00071 T *KeyData, 00072 time_t KeyTime, 00073 XrdOucHash_Item<T> *KeyNext, 00074 XrdOucHash_Options KeyOpts) 00075 {keyhash = KeyHash; 00076 if (KeyOpts & Hash_keep) keyval = KeyVal; 00077 else keyval = strdup(KeyVal); 00078 if (KeyOpts & Hash_data_is_key) keydata = (T *)keyval; 00079 else keydata = KeyData; 00080 keytime = KeyTime; 00081 entopts = KeyOpts; 00082 next = KeyNext; 00083 keycount= 0; 00084 } 00085 00086 ~XrdOucHash_Item() 00087 {if (!(entopts & Hash_keep)) 00088 {if (keydata && keydata != (T *)keyval 00089 && !(entopts & Hash_keepdata)) 00090 {if (entopts & Hash_dofree) free(keydata); 00091 else delete keydata; 00092 } 00093 if (keyval) free((void *)keyval); 00094 } 00095 keydata = 0; keyval = 0; keycount = 0; 00096 } 00097 00098 private: 00099 00100 XrdOucHash_Item<T> *next; 00101 const char *keyval; 00102 unsigned long keyhash; 00103 T *keydata; 00104 time_t keytime; 00105 int keycount; 00106 XrdOucHash_Options entopts; 00107 }; 00108 00109 template<class T> 00110 class XrdOucHash 00111 { 00112 public: 00113 00114 // Add() adds a new item to the hash. If it exists and repl = 0 then the old 00115 // entry is returned and the new data is not added. Otherwise the current 00116 // entry is replaced (see Rep()) and 0 is returned. If we have no memory 00117 // to add the new entry, an ENOMEM exception is thrown. The 00118 // LifeTime value is the number of seconds this entry is to be considered 00119 // valid. When the time has passed, the entry may be deleted. A value 00120 // of zero, keeps the entry until explicitly deleted. A special feature 00121 // allows the data to be associated with the key to be the actual key 00122 // using the Hash_data_is_key option. In this case, KeyData is ignored. 00123 // The Hash_count option keeps track of duplicate key entries for Del. 00124 // 00125 T *Add(const char *KeyVal, T *KeyData, const int LifeTime=0, 00126 XrdOucHash_Options opt=Hash_default); 00127 00128 // Del() deletes the item from the hash. If it doesn't exist, it returns 00129 // -ENOENT. Otherwise 0 is returned. If the Hash_count option is specified 00130 // tyhen the entry is only deleted when the entry count is below 0. 00131 // 00132 int Del(const char *KeyVal, XrdOucHash_Options opt = Hash_default); 00133 00134 // Find() simply looks up an entry in the cache. It can optionally return the 00135 // lifetime associated with the entry. If the 00136 // 00137 T *Find(const char *KeyVal, time_t *KeyTime=0); 00138 00139 // Num() returns the number of items in the hash table 00140 // 00141 int Num() {return hashnum;} 00142 00143 // Purge() simply deletes all of the appendages to the table. 00144 // 00145 void Purge(); 00146 00147 // Rep() is simply Add() that allows replacement. 00148 // 00149 T *Rep(const char *KeyVal, T *KeyData, const int LifeTime=0, 00150 XrdOucHash_Options opt=Hash_default) 00151 {return Add(KeyVal, KeyData, LifeTime, 00152 (XrdOucHash_Options)(opt | Hash_replace));} 00153 00154 // Apply() applies the specified function to every item in the hash. The 00155 // first argument is the key value, the second is the associated data, 00156 // the third argument is whatever is the passed in void *variable, The 00157 // following actions occur for values returned by the applied function: 00158 // <0 - The hash table item is deleted. 00159 // =0 - The next hash table item is processed. 00160 // >0 - Processing stops and the hash table item is returned. 00161 // 00162 T *Apply(int (*func)(const char *, T *, void *), void *Arg); 00163 00164 // When allocateing a new hash, specify the required starting size. Make 00165 // sure that the previous number is the correct Fibonocci antecedent. The 00166 // series is simply n[j] = n[j-1] + n[j-2]. 00167 // 00168 XrdOucHash(int psize = 89, int size=144, int load=80); 00169 ~XrdOucHash() {if (hashtable) {Purge(); free(hashtable); hashtable = 0;}} 00170 00171 private: 00172 void Remove(int kent, XrdOucHash_Item<T> *hip, XrdOucHash_Item<T> *phip); 00173 00174 XrdOucHash_Item<T> *Search(XrdOucHash_Item<T> *hip, 00175 const unsigned long khash, 00176 const char *kval, 00177 XrdOucHash_Item<T> **phip=0); 00178 00179 unsigned long HashVal(const char *KeyVal); 00180 00181 void Expand(); 00182 00183 XrdOucHash_Item<T> **hashtable; 00184 int prevtablesize; 00185 int hashtablesize; 00186 int hashnum; 00187 int hashmax; 00188 int hashload; 00189 }; 00190 00191 /******************************************************************************/ 00192 /* A c t u a l I m p l e m e n t a t i o n */ 00193 /******************************************************************************/ 00194 00195 #include "XrdOuc/XrdOucHash.icc" 00196 #endif