XRootD
XrdFrmTSort.cc
Go to the documentation of this file.
1 /******************************************************************************/
2 /* */
3 /* X r d F r m T S o r t . c c */
4 /* */
5 /* (c) 2009 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 "XrdFrm/XrdFrmFiles.hh"
32 #include "XrdFrm/XrdFrmTSort.hh"
33 //#include "iostream.h"
34 
35 /******************************************************************************/
36 /* A d d */
37 /******************************************************************************/
38 
40 {
41  XrdOucNSWalk::NSEnt *nsp = fsp->baseFile();
42  int n;
43 
44 // Make sure we can actuall add this entry
45 //
46  if (baseT < nsp->Stat.st_atime) return 0;
47 
48 // Get the relative time
49 //
50  fsp->Age = static_cast<int>(baseT - nsp->Stat.st_atime);
51 
52 // Insert into the table
53 //
54  n = fsp->Age/dVal;
55  if (n > 63) n = 63;
56  fsp->Next = FSTab[0][n];
57  FSTab[0][n] = fsp;
58  if (n > DYent) DYent = n;
59 //std::cerr <<"Add " <<std::hex <<fsp->Age <<' ' <<std::dec <<0 <<',' <<n <<' ' <<fsp->basePath() <<std::endl;
60  numEnt++;
61  return 1;
62 }
63 
64 /******************************************************************************/
65 /* Private: B i n */
66 /******************************************************************************/
67 
68 int XrdFrmTSort::Bin(XrdFrmFileset *fsp, int j, int Shift)
69 {
70  XrdFrmFileset *fsq;
71  int k, n = 0;
72 
73  while((fsq = fsp))
74  {fsp = fsp->Next;
75  k = (fsq->Age >> Shift) & tMask;
76  if (k > n) n = k;
77  if (Shift || !sortSZ) fsq->Next = FSTab[j][k];
78  else fsq = Insert(fsq, FSTab[j][k]);
79  FSTab[j][k] = fsq;
80 //std::cerr <<"Bin " <<std::hex <<fsq->Age <<' ' <<std::dec <<j <<',' <<k <<' ' <<fsq->basePath() <<std::endl;
81  }
82  return n;
83 }
84 
85 /******************************************************************************/
86 /* Private: I n s e r t */
87 /******************************************************************************/
88 
89 XrdFrmFileset *XrdFrmTSort::Insert(XrdFrmFileset *newP, XrdFrmFileset *oldP)
90 {
91  XrdFrmFileset *prvP = 0, *nowP = oldP;
92  off_t newSize = newP->baseFile()->Stat.st_size;
93 
94 // Find insertion point of new element (decreasing size order)
95 //
96  while(nowP && newSize < nowP->baseFile()->Stat.st_size)
97  {prvP = nowP; nowP = nowP->Next;}
98 
99 // Perform insertion
100 //
101  if (prvP) {prvP->Next = newP; newP->Next = nowP;}
102  else newP->Next = nowP;
103 
104 // Return correct head of list
105 //
106  return (prvP ? oldP : newP);
107 }
108 
109 /******************************************************************************/
110 /* O l d e s t */
111 /******************************************************************************/
112 
114 {
115  XrdFrmFileset *fsp = 0;
116 
117 // Work backwards on the list, resorting as needed
118 //
119  do {while(SCent >= 0)
120  {if ((fsp = FSTab[3][SCent]))
121  {if (!( FSTab[3][SCent] = fsp->Next)) SCent--;
122  numEnt--;
123 //std::cerr <<"Oldest " <<fsp->Age <<' ' <<fsp->basePath() <<std::endl;
124  return fsp;
125  } else SCent--;
126  }
127 //std::cerr <<"SC=" <<SCent <<" MN=" <<MNent <<" HR=" <<HRent <<" DY=" <<DYent <<std::endl;
128  fsp = 0;
129  while(MNent >= 0 && !fsp) fsp = FSTab[2][MNent--];
130  if (fsp) {FSTab[2][MNent+1]=0; SCent = Bin(fsp, 3, SCshift); continue;}
131  while(HRent >= 0 && !fsp) fsp = FSTab[1][HRent--];
132  if (fsp) {FSTab[1][HRent+1]=0; MNent = Bin(fsp, 2, MNshift); continue;}
133  while(DYent >= 0 && !fsp) fsp = FSTab[0][DYent--];
134  if (fsp) {FSTab[0][DYent+1]=0; HRent = Bin(fsp, 1, HRshift); continue;}
135  } while(numEnt);
136  return 0;
137 }
138 
139 /******************************************************************************/
140 /* P u r g e */
141 /******************************************************************************/
142 
144 {
145  XrdFrmFileset *fsp, *csp;
146  int i, j, aBeg[4] = {DYent, HRent, MNent, SCent};
147 
148  for (i = 0; i < 4; i++)
149  for (j = aBeg[i]; j >= 0; j--)
150  {if ((fsp = FSTab[i][j]))
151  while((csp = fsp)) {fsp = fsp->Next; delete csp;}
152  }
153  Reset();
154 }
155 
156 /******************************************************************************/
157 /* Private: R e s e t */
158 /* */
159 /******************************************************************************/
160 
161 void XrdFrmTSort::Reset()
162 {
163 
164 // Clear the base table and set base time
165 //
166  memset(FSTab, 0, sizeof(FSTab));
167  DYent = HRent = MNent = SCent = -1;
168  baseT = time(0);
169  numEnt = 0;
170 }
struct stat Stat
Definition: XrdCks.cc:49
XrdFrmFileset * Next
Definition: XrdFrmFiles.hh:90
XrdOucNSWalk::NSEnt * baseFile()
Definition: XrdFrmFiles.hh:60
void Purge()
Definition: XrdFrmTSort.cc:143
XrdFrmFileset * Oldest()
Definition: XrdFrmTSort.cc:113
int Add(XrdFrmFileset *fsp)
Definition: XrdFrmTSort.cc:39