XRootD
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 
37 extern unsigned long XrdOucHashVal(const char *KeyVal);
38 
39 /******************************************************************************/
40 /* C o n s t r u c t o r */
41 /******************************************************************************/
42 
43 template<class T>
44 XrdOucHash<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 
60 template<class T>
61 T *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 
101 template<class T>
102 T *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 
135 template<class T>
136 int XrdOucHash<T>::Del(const char *KeyVal, XrdOucHash_Options)
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 }
154 
155 /******************************************************************************/
156 /* F i n d */
157 /******************************************************************************/
158 
159 template<class T>
160 T *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;
179  }
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 
192 template<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 
219 template<class T>
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 
265 template<class T>
266 void 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 
279 template<class T>
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
void Update(int newcount, time_t newtime)
Definition: XrdOucHash.hh:76
time_t Time()
Definition: XrdOucHash.hh:74
XrdOucHash_Item< T > * Next()
Definition: XrdOucHash.hh:72
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)
Definition: XrdOucHash.icc:136
void Purge()
Definition: XrdOucHash.icc:193
T * Apply(int(*func)(const char *, T *, void *), void *Arg)
Definition: XrdOucHash.icc:102
T * Add(const char *KeyVal, T *KeyData, const int LifeTime=0, XrdOucHash_Options opt=Hash_default)
Definition: XrdOucHash.icc:61
T * Find(const char *KeyVal, time_t *KeyTime=0)
Definition: XrdOucHash.icc:160
XrdOucHash(int psize=89, int size=144, int load=80)
Definition: XrdOucHash.icc:44