XRootD
Loading...
Searching...
No Matches
XrdOucHash.icc
Go to the documentation of this file.
1/******************************************************************************/
2/* */
3/* X r d O u c H a s h . i c c */
4/* */
5/* (c) 2004 by the Board of Trustees of the Leland Stanford, Jr., University */
6/* Produced by Andrew Hanushevsky for Stanford University under contract */
7/* DE-AC02-76-SFO0515 with the Department of Energy */
8/* */
9/* This file is part of the XRootD software suite. */
10/* */
11/* XRootD is free software: you can redistribute it and/or modify it under */
12/* the terms of the GNU Lesser General Public License as published by the */
13/* Free Software Foundation, either version 3 of the License, or (at your */
14/* option) any later version. */
15/* */
16/* XRootD is distributed in the hope that it will be useful, but WITHOUT */
17/* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or */
18/* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public */
19/* License for more details. */
20/* */
21/* You should have received a copy of the GNU Lesser General Public License */
22/* along with XRootD in a file called COPYING.LESSER (LGPL license) and file */
23/* COPYING (GPL license). If not, see <http://www.gnu.org/licenses/>. */
24/* */
25/* The copyright holder's institutional names and contributor's names may not */
26/* be used to endorse or promote products derived from this software without */
27/* specific prior written permission of the institution or contributor. */
28/******************************************************************************/
29
30#include <cerrno>
31#include <cstring>
32
33/******************************************************************************/
34/* E x t e r n a l H a s h F u n c t i o n */
35/******************************************************************************/
36
37extern unsigned long XrdOucHashVal(const char *KeyVal);
38
39/******************************************************************************/
40/* C o n s t r u c t o r */
41/******************************************************************************/
42
43template<class T>
44XrdOucHash<T>::XrdOucHash(int psize, int csize, int load)
45{
46 prevtablesize = psize;
47 hashtablesize = csize;
48 hashload = load;
49 hashmax = (csize * load) / 100;
50 hashnum = 0;
51 hashtable = (XrdOucHash_Item<T> **)
52 malloc( (size_t)(csize*sizeof(XrdOucHash_Item<T> *)) );
53 memset((void *)hashtable, 0, (size_t)(csize*sizeof(XrdOucHash_Item<T> *)));
54}
55
56/******************************************************************************/
57/* A d d */
58/******************************************************************************/
59
60template<class T>
61T *XrdOucHash<T>::Add(const char *KeyVal, T *KeyData, const int LifeTime,
63{
64 unsigned long khash = XrdOucHashVal(KeyVal);
65 int hent;
66 time_t lifetime, KeyTime=0;
67 XrdOucHash_Item<T> *hip, *newhip, *prevhip;
68
69 // Compute the hash index and look up the entry. If found, either
70 // return an error or delete it because caller wanted it replaced or
71 // it has expired.
72 //
73 hent = khash % hashtablesize;
74 if ((hip = hashtable[hent]) && (hip = Search(hip, khash, KeyVal, &prevhip)))
75 {if (opt & Hash_count)
76 {hip->Update(hip->Count()+1,
77 (LifeTime || hip->Time() ? LifeTime + time(0) : 0) );}
78 if (!(opt & Hash_replace)
79 && ((lifetime=hip->Time())==0||lifetime>=time(0))) return hip->Data();
80 Remove(hent, hip, prevhip);
81 } else {
82 // Check if we should expand the table
83 //
84 if (hashnum >= hashmax) {Expand(); hent = khash % hashtablesize;}
85 }
86
87 // Add the entry
88 //
89 if (LifeTime) KeyTime = LifeTime + time(0);
90 if ( !(newhip = new XrdOucHash_Item<T>(khash, KeyVal, KeyData, KeyTime,
91 hashtable[hent], opt)) ) throw ENOMEM;
92 hashtable[hent] = newhip;
93 hashnum++;
94 return (T *)0;
95}
96
97/******************************************************************************/
98/* A p p l y */
99/******************************************************************************/
100
101template<class T>
102T *XrdOucHash<T>::Apply(int (*func)(const char *, T *, void *), void *Arg)
103{
104 int i, rc;
105 time_t lifetime;
106 XrdOucHash_Item<T> *hip, *prevhip, *nexthip;
107
108 //Run through all the entries, applying the function to each. Expire
109 // dead entries by pretending that the function asked for a deletion.
110 //
111 for (i = 0; i < hashtablesize; i++)
112 {hip = hashtable[i]; prevhip = 0;
113 while(hip)
114 {nexthip = hip->Next();
115 if ((lifetime = hip->Time()) && lifetime < time(0)) rc = -1;
116 else if ( (rc = (*func)(hip->Key(), hip->Data(), Arg)) > 0 )
117 return hip->Data();
118 if (rc < 0)
119 {delete hip;
120 if (prevhip) prevhip->SetNext(nexthip);
121 else hashtable[i] = nexthip;
122 hashnum--;
123 }
124 else prevhip = hip;
125 hip = nexthip;
126 }
127 }
128 return (T *)0;
129}
130
131/******************************************************************************/
132/* D e l */
133/******************************************************************************/
134
135template<class T>
137{
138 unsigned long khash = XrdOucHashVal(KeyVal);
139 int hent, cnt;
140 XrdOucHash_Item<T> *hip, *phip, *thip;
141
142 // Compute the hash index and look up the entry. If found, return it.
143 //
144 hent = khash % hashtablesize;
145 if (!(thip = hashtable[hent])) return -ENOENT;
146 if (!( hip = Search(thip, khash, KeyVal, &phip) ) ) return -ENOENT;
147
148 // Delete the item and return
149 //
150 if ((cnt = hip->Count()) <= 0) Remove(hent, hip, phip);
151 else hip->Update(cnt-1, 0);
152 return 0;
153}
155/******************************************************************************/
156/* F i n d */
157/******************************************************************************/
158
159template<class T>
160T *XrdOucHash<T>::Find(const char *KeyVal, time_t *KeyTime)
161{
162 unsigned long khash = XrdOucHashVal(KeyVal);
163 int kent;
164 time_t lifetime = 0;
165 XrdOucHash_Item<T> *phip, *hip;
166
167// Compute position of the hash table entry
168//
169 kent = khash%hashtablesize;
170
171// Find the entry (remove it if expired and return nothing)
172//
173 if ((hip = hashtable[kent]))
174 if ((hip = Search(hip, khash, KeyVal, &phip)))
175 if ( (lifetime = hip->Time()) && lifetime < time(0) )
176 {Remove(kent, hip, phip);
177 if (KeyTime) *KeyTime = (time_t)0;
178 return (T *)0;
180
181// Return actual information
182//
183 if (KeyTime) *KeyTime = lifetime;
184 if (hip) return hip->Data();
185 return (T *)0;
186}
187
188/******************************************************************************/
189/* P u r g e */
190/******************************************************************************/
191
192template<class T>
194{
195 int i;
196 XrdOucHash_Item<T> *hip, *nexthip;
197
198 //Run through all the entries, deleting each one
199 //
200 for (i = 0; i < hashtablesize; i++)
201 {hip = hashtable[i]; hashtable[i] = 0;
202 while(hip)
203 {nexthip = hip->Next();
204 delete hip;
205 hip = nexthip;
206 }
207 }
208 hashnum = 0;
209}
210
211/******************************************************************************/
212/* P r i v a t e M e t h o d s */
213/******************************************************************************/
214
215/******************************************************************************/
216/* E x p a n d */
217/******************************************************************************/
218
219template<class T>
220void XrdOucHash<T>::Expand()
221{
222 int newsize, newent, i;
223 size_t memlen;
224 XrdOucHash_Item<T> **newtab, *hip, *nexthip;
225
226 // Compute new size for table using a fibonacci series
227 //
228 newsize = prevtablesize +hashtablesize;
229
230 // Allocate the new table
231 //
232 memlen = (size_t)(newsize*sizeof(XrdOucHash_Item<T> *));
233 if (!(newtab = (XrdOucHash_Item<T> **) malloc(memlen))) throw ENOMEM;
234 memset((void *)newtab, 0, memlen);
235
236 // Redistribute all of the current items
237 //
238 for (i = 0; i < hashtablesize; i++)
239 {hip = hashtable[i];
240 while(hip)
241 {nexthip = hip->Next();
242 newent = (hip->Hash()) % newsize;
243 hip->SetNext(newtab[newent]);
244 newtab[newent] = hip;
245 hip = nexthip;
246 }
247 }
248
249 // Free the old table and plug in the new table
250 //
251 free((void *)hashtable);
252 hashtable = newtab;
253 prevtablesize = hashtablesize;
254 hashtablesize = newsize;
255
256 // Compute new expansion threshold
257 //
258 hashmax = static_cast<int>((static_cast<long long>(newsize)*hashload)/100);
259}
260
261/******************************************************************************/
262/* R e m o v e */
263/******************************************************************************/
264
265template<class T>
266void XrdOucHash<T>::Remove(int kent, XrdOucHash_Item<T> *hip,
267 XrdOucHash_Item<T> *phip)
268{
269 if (phip) phip->SetNext(hip->Next());
270 else hashtable[kent] = hip->Next();
271 delete hip;
272 hashnum--;
273}
274
275/******************************************************************************/
276/* S e a r c h */
277/******************************************************************************/
278
279template<class T>
280XrdOucHash_Item<T> *XrdOucHash<T>::Search(XrdOucHash_Item<T> *hip,
281 const unsigned long khash,
282 const char *kval,
283 XrdOucHash_Item<T> **pitem)
284{
285 XrdOucHash_Item<T> *prevp = 0;
286
287 // Scan through the chain looking for a match
288 //
289 while(hip && !hip->Same(khash, kval))
290 {prevp = hip;
291 hip = hip->Next();
292 }
293 if (pitem) *pitem = prevp;
294 return hip;
295}
XrdOucHash_Options
Definition XrdOucHash.hh:51
@ Hash_count
Definition XrdOucHash.hh:54
@ Hash_replace
Definition XrdOucHash.hh:53
unsigned long XrdOucHashVal(const char *KeyVal)
unsigned long Hash()
Definition XrdOucHash.hh:68
int Same(const unsigned long KeyHash, const char *KeyVal)
Definition XrdOucHash.hh:81
XrdOucHash_Item< T > * Next()
Definition XrdOucHash.hh:72
void Update(int newcount, time_t newtime)
Definition XrdOucHash.hh:76
const char * Key()
Definition XrdOucHash.hh:70
void SetNext(XrdOucHash_Item< T > *item)
Definition XrdOucHash.hh:84
int Del(const char *KeyVal, XrdOucHash_Options opt=Hash_default)
T * Apply(int(*func)(const char *, T *, void *), void *Arg)
T * Add(const char *KeyVal, T *KeyData, const int LifeTime=0, XrdOucHash_Options opt=Hash_default)
T * Find(const char *KeyVal, time_t *KeyTime=0)
XrdOucHash(int psize=89, int size=144, int load=80)