XRootD
XrdOucRash.icc
Go to the documentation of this file.
1 /******************************************************************************/
2 /* */
3 /* X r d O u c R a s h . i c c */
4 /* */
5 /* (c) 2005 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 
32 #include "XrdSys/XrdSysPlatform.hh"
33 
34 /******************************************************************************/
35 /* A d d */
36 /******************************************************************************/
37 
38 template<typename K, typename V>
39 V *XrdOucRash<K,V>::Add(K KeyVal, V &KeyData, time_t LifeTime,
41 {
42  time_t lifetime, KeyTime=0;
44  XrdOucRash_Tent<K,V> *hiploc;
45 
46 // Look up the entry. If found, either return an error or delete it
47 // because caller wanted it replaced or it has expired.
48 //
49  if ((hip = Lookup(KeyVal, &hiploc)))
50  {if (opt & Rash_count)
51  {hip->Update(hip->Count()+1,
52  (LifeTime || hip->Time() ? LifeTime + time(0) : 0) );}
53  if (!(opt & Rash_replace)
54  && ((lifetime=hip->Time())==0||lifetime>=time(0))) return hip->Data();
55  hip->Set(KeyData, KeyTime);
56  return (V *)0;
57  }
58 
59 // Create a new item
60 //
61  if (LifeTime) KeyTime = LifeTime + time(0);
62  if ( !(hip = new XrdOucRash_Item<K,V>(KeyVal, KeyData, KeyTime)) )
63  throw ENOMEM;
64 
65 // Add this item to the table
66 //
67  Insert(KeyVal, hip);
68  return (V *)0;
69 }
70 
71 /******************************************************************************/
72 /* D e l */
73 /******************************************************************************/
74 
75 template<typename K, typename V>
76 int XrdOucRash<K,V>::Del(K KeyVal)
77 {
79  XrdOucRash_Tent<K,V> *hiploc;
80  int cnt;
81 
82 // Look up the entry. If not found, indicate so.
83 //
84  if (!(hip = Lookup(KeyVal, &hiploc))) return -ENOENT;
85 
86 // Delete the item and return
87 //
88  if ((cnt = hip->Count())) {hip->Update(cnt-1, 0); return cnt;}
89  delete hip;
90  hiploc->Item = (XrdOucRash_Item<K,V> *)0;
91  rashnum--;
92  return 0;
93 
94 }
95 
96 /******************************************************************************/
97 /* F i n d */
98 /******************************************************************************/
99 
100 template<typename K, typename V>
101 V *XrdOucRash<K,V>::Find(K KeyVal, time_t *KeyTime)
102 {
104  XrdOucRash_Tent<K,V> *hiploc;
105  time_t lifetime = 0;
106 
107 // Find the entry (remove it if expired and return nothing)
108 //
109  if (!(hip = Lookup(KeyVal, &hiploc))) return (V *)0;
110  if ( (lifetime = hip->Time()) && lifetime < time(0) )
111  {delete hip;
112  hiploc->Item = (XrdOucRash_Item<K,V> *)0;
113  rashnum--;
114  if (KeyTime) *KeyTime = (time_t)0;
115  return (V *)0;
116  }
117 
118 // Return actual information
119 //
120  if (KeyTime) *KeyTime = lifetime;
121  return hip->Data();
122 }
123 
124 /******************************************************************************/
125 /* P u r g e */
126 /******************************************************************************/
127 
128 template<typename K, typename V>
130 {
131  int i;
132 
133 // Run through the major table and delete each item in the main table
134 // the deletion automatically propagates.
135 //
136  for (i = 0; i < 16; i++)
137  {if (rashTable[i].Item)
138  {delete rashTable[i].Item; rashTable[i].Item = 0;}
139  if (rashTable[i].Table)
140  {delete []rashTable[i].Table; rashTable[i].Table = 0;}
141  }
142  rashnum = 0;
143 }
144 
145 /******************************************************************************/
146 /* P r i v a t e M e t h o d s */
147 /******************************************************************************/
148 /******************************************************************************/
149 /* A p p l y */
150 /******************************************************************************/
151 
152 template<typename K, typename V>
154  int (*func)(K, V, void *), void *Arg)
155 {
156  int i, rc;
157  time_t lifetime;
159  V *theVal;
160 
161  //Run through all the entries, applying the function to each. Expire
162  // dead entries by pretending that the function asked for a deletion.
163  //
164  for (i = 0; i < 16; i++)
165  {if ((hip = tab[i].Item))
166  {if ((lifetime = hip->Time()) && lifetime < time(0)) rc = -1;
167  else if ( (rc = (*func)(hip->Key(), *hip->Data(), Arg)) > 0 )
168  return hip->Data();
169  if (rc < 0) {delete hip;
170  tab[i].Item = (XrdOucRash_Item<K,V> *)0;
171  rashnum--;
172  }
173  }
174  if (tab[i].Table && (theVal = Apply(tab[i].Table, func, Arg)))
175  return theVal;
176  }
177  return (V *)0;
178 }
179 
180 /******************************************************************************/
181 /* L o o k u p */
182 /******************************************************************************/
183 
184 template<typename K, typename V>
186  XrdOucRash_Tent<K,V> **tloc)
187 {
188  unsigned long long kVal = key2ull(theKey);
189  XrdOucRash_Tent<K,V> *tab = rashTable;
190  int j;
191 
192 // Traverse the binary tree and find the entry
193 //
194  do {j = kVal & 0x0f;
195  kVal = kVal >> 4;
196  } while(kVal && (tab = tab[j].Table));
197 
198 // Return result
199 //
200  if (tab)
201  {*tloc = &tab[j];
202  return tab[j].Item;
203  } else {
204  *tloc = 0;
205  return 0;
206  }
207 }
208 
209 /******************************************************************************/
210 /* I n s e r t */
211 /******************************************************************************/
212 
213 template<typename K, typename V>
214 void XrdOucRash<K,V>::Insert(K theKey, XrdOucRash_Item<K,V> *theItem)
215 {
216  unsigned long long kVal = key2ull(theKey);
217  XrdOucRash_Tent<K,V> *tab = rashTable;
218  int j;
219 
220 // Traverse the binary tree and find the entry
221 //
222  do {j = kVal & 0x0f;
223  if ((kVal = kVal >> 4))
224  {if (tab[j].Table) tab = tab[j].Table;
225  else tab = tab[j].Table = new XrdOucRash_Tent<K,V>[16]();
226  }
227  } while(kVal);
228 
229 // Insert the entry
230 //
231  tab[j].Item = theItem;
232  rashnum++;
233 }
234 
235 /******************************************************************************/
236 /* k e y 2 u l l */
237 /******************************************************************************/
238 
239 template<typename K, typename V>
240 unsigned long long XrdOucRash<K,V>::key2ull(K theKey)
241 {
242 #ifdef Xrd_Big_Endian
243  union {unsigned long long us; K kv[8/sizeof(K)];} Val;
244  Val.us = 0;
245  Val.kv[8/sizeof(K)-1] = theKey;
246 #else
247  union {unsigned long long us; K kv;} Val;
248  Val.us = 0;
249  Val.kv = theKey;
250 #endif
251  return Val.us;
252 }
XrdOucRash_Options
Definition: XrdOucRash.hh:52
@ Rash_replace
Definition: XrdOucRash.hh:53
@ Rash_count
Definition: XrdOucRash.hh:54
time_t Time()
Definition: XrdOucRash.hh:67
void Set(V &keyData, time_t newtime)
Definition: XrdOucRash.hh:74
void Update(int newcount, time_t newtime)
Definition: XrdOucRash.hh:69
XrdOucRash_Tent< K, V > * Table
Definition: XrdOucRash.hh:102
XrdOucRash_Item< K, V > * Item
Definition: XrdOucRash.hh:103
V * Add(K KeyVal, V &KeyData, time_t LifeTime=0, XrdOucRash_Options opt=Rash_default)
Definition: XrdOucRash.icc:39
int Del(K KeyVal)
Definition: XrdOucRash.icc:76
V * Apply(int(*func)(K, V, void *), void *Arg)
Definition: XrdOucRash.hh:163
V * Find(K KeyVal, time_t *KeyTime=0)
Definition: XrdOucRash.icc:101
void Purge()
Definition: XrdOucRash.icc:129
static auto Apply(FUNC &&func, std::tuple< ARGs... > &tup) -> decltype(tuple_call_impl(func, tup, typename seq_gen< sizeof...(ARGs)>::type{}))
Definition: XrdClApply.hh:64