XRootD
XrdCmsNash.cc
Go to the documentation of this file.
1 /******************************************************************************/
2 /* */
3 /* X r d C m s N a s h . h h */
4 /* */
5 /* (c) 2007 by the Board of Trustees of the Leland Stanford, Jr., University */
6 /* All Rights Reserved */
7 /* Produced by Andrew Hanushevsky for Stanford University under contract */
8 /* DE-AC02-76-SFO0515 with the Department of Energy */
9 /* */
10 /* This file is part of the XRootD software suite. */
11 /* */
12 /* XRootD is free software: you can redistribute it and/or modify it under */
13 /* the terms of the GNU Lesser General Public License as published by the */
14 /* Free Software Foundation, either version 3 of the License, or (at your */
15 /* option) any later version. */
16 /* */
17 /* XRootD is distributed in the hope that it will be useful, but WITHOUT */
18 /* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or */
19 /* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public */
20 /* License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with XRootD in a file called COPYING.LESSER (LGPL license) and file */
24 /* COPYING (GPL license). If not, see <http://www.gnu.org/licenses/>. */
25 /* */
26 /* The copyright holder's institutional names and contributor's names may not */
27 /* be used to endorse or promote products derived from this software without */
28 /* specific prior written permission of the institution or contributor. */
29 /******************************************************************************/
30 
31 #include <cstdlib>
32 
33 #include "XrdCms/XrdCmsNash.hh"
34 
35 /******************************************************************************/
36 /* C o n s t r u c t o r */
37 /******************************************************************************/
38 
39 XrdCmsNash::XrdCmsNash(int psize, int csize)
40 {
41  prevtablesize = psize;
42  nashtablesize = csize;
43  Threshold = (csize * LoadMax) / 100;
44  nashnum = 0;
45  nashtable = (XrdCmsKeyItem **)
46  malloc( (size_t)(csize*sizeof(XrdCmsKeyItem *)) );
47  memset((void *)nashtable, 0, (size_t)(csize*sizeof(XrdCmsKeyItem *)));
48 }
49 
50 /******************************************************************************/
51 /* public A d d */
52 /******************************************************************************/
53 
55 {
56  XrdCmsKeyItem *hip;
57  unsigned int kent;
58 
59 // Allocate the entry
60 //
61  if (!(hip = XrdCmsKeyItem::Alloc(Key.TOD))) return (XrdCmsKeyItem *)0;
62 
63 // Check if we should expand the table
64 //
65  if (++nashnum > Threshold) Expand();
66 
67 // Fill out the key data
68 //
69  if (!Key.Hash) Key.setHash();
70  hip->Key = Key;
71 
72 // Add the entry to the table
73 //
74  kent = Key.Hash % nashtablesize;
75  hip->Next = nashtable[kent];
76  nashtable[kent] = hip;
77  return hip;
78 }
79 
80 /******************************************************************************/
81 /* private E x p a n d */
82 /******************************************************************************/
83 
84 void XrdCmsNash::Expand()
85 {
86  int newsize, newent, i;
87  size_t memlen;
88  XrdCmsKeyItem **newtab, *nip, *nextnip;
89 
90 // Compute new size for table using a fibonacci series
91 //
92  newsize = prevtablesize + nashtablesize;
93 
94 // Allocate the new table
95 //
96  memlen = (size_t)(newsize*sizeof(XrdCmsKeyItem *));
97  if (!(newtab = (XrdCmsKeyItem **) malloc(memlen))) return;
98  memset((void *)newtab, 0, memlen);
99 
100 // Redistribute all of the current items
101 //
102  for (i = 0; i < nashtablesize; i++)
103  {nip = nashtable[i];
104  while(nip)
105  {nextnip = nip->Next;
106  newent = nip->Key.Hash % newsize;
107  nip->Next = newtab[newent];
108  newtab[newent] = nip;
109  nip = nextnip;
110  }
111  }
112 
113 // Free the old table and plug in the new table
114 //
115  free((void *)nashtable);
116  nashtable = newtab;
117  prevtablesize = nashtablesize;
118  nashtablesize = newsize;
119 
120 // Compute new expansion threshold
121 //
122  Threshold = static_cast<int>((static_cast<long long>(newsize)*LoadMax)/100);
123 }
124 
125 /******************************************************************************/
126 /* public F i n d */
127 /******************************************************************************/
128 
130 {
131  XrdCmsKeyItem *nip;
132  unsigned int kent;
133 
134 // Check if we already have a hash value and get one if not
135 //
136  if (!Key.Hash) Key.setHash();
137 
138 // Compute position of the hash table entry
139 //
140  kent = Key.Hash%nashtablesize;
141 
142 // Find the entry
143 //
144  nip = nashtable[kent];
145  while(nip && nip->Key != Key) nip = nip->Next;
146  return nip;
147 }
148 
149 /******************************************************************************/
150 /* public R e c y c l e */
151 /******************************************************************************/
152 
153 // The item must have been previously unload which will place the original
154 // hash value in Loc.HashSave. Yes, not very OO but very fast.
155 //
157 {
158  XrdCmsKeyItem *nip, *pip = 0;
159  unsigned int kent;
160 
161 // Compute position of the hash table entry
162 //
163  kent = rip->Loc.HashSave%nashtablesize;
164 
165 // Find the entry
166 //
167  nip = nashtable[kent];
168  while(nip && nip != rip) {pip = nip; nip = nip->Next;}
169 
170 // Remove and recycle if found
171 //
172  if (nip)
173  {if (pip) pip->Next = nip->Next;
174  else nashtable[kent] = nip->Next;
175  rip->Recycle();
176  nashnum--;
177  }
178  return nip != 0;
179 }
static XrdCmsKeyItem * Alloc(unsigned int theTock)
Definition: XrdCmsKey.cc:71
void Recycle()
Definition: XrdCmsKey.cc:101
XrdCmsKeyLoc Loc
Definition: XrdCmsKey.hh:129
XrdCmsKey Key
Definition: XrdCmsKey.hh:130
XrdCmsKeyItem * Next
Definition: XrdCmsKey.hh:131
void setHash()
Definition: XrdCmsKey.cc:48
unsigned int Hash
Definition: XrdCmsKey.hh:53
unsigned char TOD
Definition: XrdCmsKey.hh:55
XrdCmsKeyItem * Add(XrdCmsKey &Key)
Definition: XrdCmsNash.cc:54
XrdCmsKeyItem * Find(XrdCmsKey &Key)
Definition: XrdCmsNash.cc:129
XrdCmsNash(int psize=17711, int size=28657)
Definition: XrdCmsNash.cc:39
int Recycle(XrdCmsKeyItem *rip)
Definition: XrdCmsNash.cc:156