]>
Commit | Line | Data |
---|---|---|
6068ae56 FM |
1 | /* |
2 | * SARG Squid Analysis Report Generator http://sarg.sourceforge.net | |
67302a9e | 3 | * 1998, 2013 |
6068ae56 FM |
4 | * |
5 | * SARG donations: | |
6 | * please look at http://sarg.sourceforge.net/donations.php | |
7 | * Support: | |
8 | * http://sourceforge.net/projects/sarg/forums/forum/363374 | |
9 | * --------------------------------------------------------------------- | |
10 | * | |
11 | * This program is free software; you can redistribute it and/or modify | |
12 | * it under the terms of the GNU General Public License as published by | |
13 | * the Free Software Foundation; either version 2 of the License, or | |
14 | * (at your option) any later version. | |
15 | * | |
16 | * This program is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | * GNU General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU General Public License | |
22 | * along with this program; if not, write to the Free Software | |
23 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
24 | * | |
25 | */ | |
26 | ||
27 | #include "include/conf.h" | |
28 | #include "include/defs.h" | |
29 | #include "include/stringbuffer.h" | |
30 | #include "include/filelist.h" | |
31 | ||
32 | struct DirEntryStruct | |
33 | { | |
34 | //! Next entry at the same level. | |
35 | struct DirEntryStruct *Sibbling; | |
36 | //! First child of this entry. | |
37 | struct DirEntryStruct *Child; | |
38 | //! Name of this entry. | |
39 | char *Name; | |
40 | //! \c True if it contains any wildcard. | |
41 | bool IsMask; | |
42 | }; | |
43 | ||
44 | /*! | |
45 | * \brief List of files. | |
46 | * | |
47 | * The list may contain wildcards. | |
48 | */ | |
49 | struct FileListStruct | |
50 | { | |
51 | //! Root of the tree. | |
52 | struct DirEntryStruct *First; | |
53 | //! Buffer containing the file name strings. | |
54 | StringBufferObject Buffer; | |
55 | //! Deepest level of the tree. | |
56 | int TreeDepth; | |
57 | //! \c True if the tree depth is correct. | |
58 | bool TreeDepthOk; | |
59 | }; | |
60 | ||
61 | struct DirEntryIterator | |
62 | { | |
63 | //! The current node at each level. | |
64 | struct DirEntryStruct *Dir; | |
65 | //! Length of the path up to that level. | |
66 | int PathLength; | |
67 | }; | |
68 | ||
69 | /*! | |
70 | * \brief Iterator of the file list. | |
71 | */ | |
72 | struct _FileListIterator | |
73 | { | |
74 | //! File list object from which we are iterating. | |
75 | FileListObject Parent; | |
76 | //! Current path being stored in the object. | |
77 | char *CurrentPath; | |
78 | //! Number of bytes allocated for the current path. | |
79 | int CurrentPathSize; | |
80 | //! Level known to be stored in the path. | |
81 | int CurrentPathLevel; | |
82 | //! Tree depth when the iteration started. | |
83 | int TreeDepth; | |
84 | //! Current level being iterated over. | |
85 | int Level; | |
86 | //! The current node at each level. | |
87 | struct DirEntryIterator *DirNodes; | |
88 | }; | |
89 | ||
90 | ||
91 | /*! | |
92 | * Create an object to store the files to process. | |
93 | * | |
94 | * \return The created object or NULL if it failed. | |
95 | * The object must be destroyed with a call to FileList_Destroy(). | |
96 | */ | |
97 | FileListObject FileList_Create(void) | |
98 | { | |
99 | FileListObject FObj; | |
100 | ||
101 | FObj=(FileListObject)calloc(1,sizeof(*FObj)); | |
102 | if (!FObj) | |
103 | return(NULL); | |
104 | ||
105 | return(FObj); | |
106 | } | |
107 | ||
108 | /*! | |
109 | * Destroy the entries tree. | |
110 | */ | |
111 | static void FileList_DestroyEntry(struct DirEntryStruct *Entry) | |
112 | { | |
113 | struct DirEntryStruct *Next; | |
114 | ||
115 | while (Entry) | |
116 | { | |
117 | if (Entry->Child) | |
118 | FileList_DestroyEntry(Entry->Child); | |
119 | Next=Entry->Sibbling; | |
120 | free(Entry); | |
121 | Entry=Next; | |
122 | } | |
123 | } | |
124 | ||
125 | /*! | |
126 | * Destroy the object created by FileList_Create(). | |
127 | * | |
128 | * \param FPtr A pointer to the object to destroy. It is | |
129 | * reset to NULL before the function returns. | |
130 | */ | |
131 | void FileList_Destroy(FileListObject *FPtr) | |
132 | { | |
133 | FileListObject FObj; | |
134 | ||
135 | if (!FPtr || !*FPtr) return; | |
136 | FObj=*FPtr; | |
137 | *FPtr=NULL; | |
138 | ||
139 | FileList_DestroyEntry(FObj->First); | |
140 | StringBuffer_Destroy(&FObj->Buffer); | |
141 | free(FObj); | |
142 | } | |
143 | ||
144 | /*! | |
145 | * Store an entry in the tree. | |
146 | * | |
147 | * \param FObj The file list object created by FileList_Create(). | |
148 | * \param FileName Name of the file to store recursively. | |
149 | * | |
150 | * \return The branch created with all the entries in \c FileName. | |
151 | * The returned value is NULL if \c FileName could not be added. | |
152 | */ | |
153 | static struct DirEntryStruct *FileList_StoreEntry(FileListObject FObj,const char *FileName) | |
154 | { | |
155 | struct DirEntryStruct *Entry; | |
156 | int i; | |
157 | bool IsMask=false; | |
158 | int LastDir=-1; | |
159 | int Next=-1; | |
160 | ||
161 | Entry=(struct DirEntryStruct *)calloc(1,sizeof(*Entry)); | |
162 | if (!Entry) return(NULL); | |
163 | for (i=0 ; FileName[i] ; i++) | |
164 | { | |
165 | if (FileName[i]=='/') | |
166 | { | |
167 | if (IsMask) | |
168 | { | |
169 | /* The path contains a wildcard. There are no directories | |
170 | * before this path or it would have been caught by the other | |
171 | * break in this loop. We store it. | |
172 | */ | |
173 | Next=i; | |
174 | break; | |
175 | } | |
176 | LastDir=i; | |
177 | } | |
178 | else if (FileName[i]=='*' || FileName[i]=='?') | |
179 | { | |
180 | if (LastDir>=0) | |
181 | { | |
182 | /* Some directories without wildcards before this directory | |
183 | * with wildcard. We store the previous directories in one | |
184 | * entry and disregard, for now, the current path level. | |
185 | */ | |
186 | Next=LastDir; | |
187 | break; | |
188 | } | |
189 | IsMask=true; | |
190 | } | |
191 | } | |
192 | Entry->Name=StringBuffer_StoreLength(FObj->Buffer,FileName,(Next<0) ? i : Next); | |
193 | if (!Entry->Name) | |
194 | { | |
195 | free(Entry); | |
196 | return(NULL); | |
197 | } | |
198 | Entry->IsMask=IsMask; | |
199 | if (Next>0) | |
200 | { | |
201 | FObj->TreeDepthOk=false; //it will have to be recomputed | |
202 | Entry->Child=FileList_StoreEntry(FObj,FileName+Next+1); | |
203 | if (!Entry->Child) | |
204 | { | |
205 | free(Entry); | |
206 | return(NULL); | |
207 | } | |
208 | } | |
209 | return(Entry); | |
210 | } | |
211 | ||
212 | /*! | |
213 | * Store a file in the internal data structure. | |
214 | * | |
215 | * \param FObj The file list object created by FileList_Create(). | |
216 | * \param EntryPtr Pointer to the tree node to add or create. | |
217 | * \param FileName The name of the file. | |
218 | * | |
219 | * \return \c True on success or \c false on failure. | |
220 | */ | |
221 | static bool FileList_AddFileRecursive(FileListObject FObj,struct DirEntryStruct **EntryPtr,const char *FileName) | |
222 | { | |
223 | int i; | |
224 | struct DirEntryStruct *Entry; | |
225 | struct DirEntryStruct *Last; | |
226 | int LastDir; | |
227 | ||
228 | if (!*EntryPtr) | |
229 | { | |
230 | Entry=FileList_StoreEntry(FObj,FileName); | |
231 | if (!Entry) return(false); | |
232 | *EntryPtr=Entry; | |
233 | return(true); | |
234 | } | |
235 | ||
236 | // find where to store the file name in the existing tree | |
237 | Last=NULL; | |
238 | for (Entry=*EntryPtr ; Entry ; Entry=Entry->Sibbling) | |
239 | { | |
240 | LastDir=-1; | |
241 | for (i=0 ; Entry->Name[i] && FileName[i] && Entry->Name[i]==FileName[i] ; i++) | |
242 | { | |
243 | if (FileName[i]=='/') | |
244 | LastDir=i; | |
245 | } | |
246 | if (FileName[i]=='/' && Entry->Name[i]=='\0') | |
247 | { | |
248 | //root is matching, check sub level | |
249 | return(FileList_AddFileRecursive(FObj,&Entry->Child,FileName+i+1)); | |
250 | } | |
251 | if (LastDir>0) | |
252 | { | |
253 | //paths begin with the same directory but diverges at LastDir | |
254 | struct DirEntryStruct *Split; | |
255 | ||
256 | Split=(struct DirEntryStruct *)calloc(1,sizeof(*Split)); | |
257 | if (!Split) return(false); | |
258 | Split->Name=Entry->Name+LastDir+1; | |
259 | Split->Child=Entry->Child; | |
260 | Entry->Name[LastDir]='\0'; | |
261 | Entry->Child=Split; | |
262 | return(FileList_AddFileRecursive(FObj,&Entry->Child,FileName+LastDir+1)); | |
263 | } | |
264 | Last=Entry; | |
265 | } | |
266 | ||
267 | // add a new entry | |
268 | Entry=FileList_StoreEntry(FObj,FileName); | |
269 | if (!Entry) return(false); | |
270 | Last->Sibbling=Entry; | |
271 | ||
272 | return(true); | |
273 | } | |
274 | ||
275 | /*! | |
276 | * Add a file to the object. | |
277 | * | |
278 | * \param FObj The object created by FileList_Create(). | |
279 | * \param FileName The file name to add to the list. | |
280 | * | |
281 | * \return \c True if the file was added or \c false if it | |
282 | * failed. The function may fail if a parameter is invalid. | |
283 | * It will also fail if the memory cannot be allocated. | |
284 | */ | |
285 | bool FileList_AddFile(FileListObject FObj,const char *FileName) | |
286 | { | |
287 | if (!FObj || !FileName) return(false); | |
288 | ||
289 | if (!FObj->Buffer) | |
290 | { | |
291 | FObj->Buffer=StringBuffer_Create(); | |
292 | if (!FObj->Buffer) | |
293 | return(false); | |
294 | } | |
295 | ||
296 | return(FileList_AddFileRecursive(FObj,&FObj->First,FileName)); | |
297 | } | |
298 | ||
299 | /*! | |
300 | * Recursively measure the tree depth. | |
301 | * | |
302 | * \param FObj File list object created by FileList_Create(). | |
303 | * \param Entry Node whose child are to be processed. | |
304 | * \param Level Current level. | |
305 | */ | |
306 | static void FileList_SetDepth(FileListObject FObj,struct DirEntryStruct *Entry,int Level) | |
307 | { | |
308 | if (Level>FObj->TreeDepth) FObj->TreeDepth=Level; | |
309 | while (Entry) | |
310 | { | |
311 | if (Entry->Child) | |
312 | FileList_SetDepth(FObj,Entry->Child,Level+1); | |
313 | Entry=Entry->Sibbling; | |
314 | } | |
315 | } | |
316 | ||
317 | /*! | |
318 | * Start the iteration over the files in the list. | |
319 | * | |
320 | * \param FObj The object to iterate over. | |
321 | * | |
322 | * \return The iterator structure to pass ot FileListIter_Next() | |
323 | * to get the first file name or NULL if an error occured. | |
324 | */ | |
325 | FileListIterator FileListIter_Open(FileListObject FObj) | |
326 | { | |
327 | struct _FileListIterator *FIter; | |
328 | struct DirEntryStruct *Dir; | |
329 | ||
330 | FIter=(FileListIterator)calloc(1,sizeof(*FIter)); | |
331 | if (!FIter) return(NULL); | |
332 | FIter->Parent=FObj; | |
333 | ||
334 | // compute the depth of the tree. | |
335 | /* | |
336 | * The tree depth computation is not thread safe. A lock is necessary around | |
337 | * the following code to make it thread safe. | |
338 | */ | |
339 | if (!FObj->TreeDepthOk) | |
340 | { | |
341 | FObj->TreeDepth=0; | |
342 | if (FObj->First) FileList_SetDepth(FObj,FObj->First,1); | |
343 | FObj->TreeDepthOk=true; | |
344 | } | |
345 | FIter->TreeDepth=FObj->TreeDepth; | |
346 | FIter->Level=-1; | |
347 | FIter->CurrentPathSize=0; | |
348 | FIter->CurrentPathLevel=0; | |
349 | if (FIter->TreeDepth>0) | |
350 | { | |
351 | FIter->DirNodes=(struct DirEntryIterator *)calloc(FIter->TreeDepth,sizeof(struct DirEntryIterator)); | |
352 | if (!FIter->DirNodes) | |
353 | { | |
354 | FileListIter_Close(FIter); | |
355 | return(NULL); | |
356 | } | |
357 | for (Dir=FObj->First ; Dir ; Dir=Dir->Child) | |
358 | { | |
359 | FIter->DirNodes[++FIter->Level].Dir=Dir; | |
360 | } | |
361 | } | |
362 | ||
363 | return(FIter); | |
364 | } | |
365 | ||
366 | /*! | |
367 | * Get the next entry in the directory tree. | |
368 | */ | |
369 | static void FileListIter_GetNext(struct _FileListIterator *FIter) | |
370 | { | |
371 | struct DirEntryStruct *Dir; | |
372 | ||
373 | FIter->CurrentPathLevel=0; | |
374 | while (FIter->Level>=0) | |
375 | { | |
376 | Dir=FIter->DirNodes[FIter->Level].Dir; | |
377 | if (Dir->Sibbling) | |
378 | { | |
379 | Dir=Dir->Sibbling; | |
380 | FIter->DirNodes[FIter->Level].Dir=Dir; | |
381 | FIter->CurrentPathLevel=FIter->Level; | |
382 | while (Dir->Child) | |
383 | { | |
384 | if (FIter->Level>=FIter->TreeDepth) break; | |
385 | Dir=Dir->Child; | |
386 | FIter->DirNodes[FIter->Level++].Dir=Dir; | |
387 | } | |
388 | break; | |
389 | } | |
390 | FIter->Level--; | |
391 | } | |
392 | } | |
393 | ||
394 | /*! | |
395 | * Get the next file in the list. | |
396 | * | |
397 | * \param FIter The iterator created by FileListIter_Open(). | |
398 | * | |
399 | * \return The iterator function containing the next file name or NULL | |
400 | * if there are no more files. | |
401 | */ | |
402 | const char *FileListIter_Next(struct _FileListIterator *FIter) | |
403 | { | |
404 | int Length; | |
405 | int Level; | |
406 | struct DirEntryIterator *DIter; | |
407 | ||
408 | if (!FIter) return(NULL); | |
409 | if (!FIter->DirNodes) return(NULL); | |
410 | if (FIter->Level<0 || FIter->Level>=FIter->TreeDepth) return(NULL); | |
411 | ||
412 | // how much space to store the path | |
413 | Length=FIter->DirNodes[FIter->CurrentPathLevel].PathLength; | |
414 | for (Level=FIter->CurrentPathLevel ; Level<=FIter->Level ; Level++) | |
415 | { | |
416 | DIter=FIter->DirNodes+Level; | |
417 | DIter->PathLength=Length;; | |
418 | Length+=strlen(DIter->Dir->Name)+1; | |
419 | } | |
420 | ||
421 | // get the memory to store the path | |
422 | if (Length>FIter->CurrentPathSize) | |
423 | { | |
424 | char *temp=realloc(FIter->CurrentPath,Length); | |
425 | if (!temp) return(NULL); | |
426 | FIter->CurrentPath=temp; | |
427 | FIter->CurrentPathSize=Length; | |
428 | } | |
429 | ||
430 | for (Level=FIter->CurrentPathLevel ; Level<=FIter->Level ; Level++) | |
431 | { | |
432 | DIter=FIter->DirNodes+Level; | |
433 | if (Level>0) FIter->CurrentPath[DIter->PathLength-1]='/'; | |
434 | strcpy(FIter->CurrentPath+DIter->PathLength,DIter->Dir->Name); | |
435 | } | |
436 | FIter->CurrentPathLevel=Level; | |
437 | ||
438 | FileListIter_GetNext(FIter); | |
439 | return(FIter->CurrentPath); | |
440 | } | |
441 | ||
442 | /*! | |
443 | * Get the next file entry in the list without expanding the | |
444 | * wildcards. | |
445 | * | |
446 | * \param FIter The iterator created by FileListIter_Open(). | |
447 | * | |
448 | * \return The iterator function containing the next file name or NULL | |
449 | * if there are no more files. | |
450 | */ | |
451 | const char *FileListIter_NextWithMask(struct _FileListIterator *FIter) | |
452 | { | |
453 | int Length; | |
454 | int Level; | |
455 | struct DirEntryIterator *DIter; | |
456 | ||
457 | if (!FIter) return(NULL); | |
458 | if (!FIter->DirNodes) return(NULL); | |
459 | if (FIter->Level<0 || FIter->Level>=FIter->TreeDepth) return(NULL); | |
460 | ||
461 | // how much space to store the path | |
462 | Length=FIter->DirNodes[FIter->CurrentPathLevel].PathLength; | |
463 | for (Level=FIter->CurrentPathLevel ; Level<=FIter->Level ; Level++) | |
464 | { | |
465 | DIter=FIter->DirNodes+Level; | |
466 | DIter->PathLength=Length;; | |
467 | Length+=strlen(DIter->Dir->Name)+1; | |
468 | } | |
469 | ||
470 | // get the memory to store the path | |
471 | if (Length>FIter->CurrentPathSize) | |
472 | { | |
473 | char *temp=realloc(FIter->CurrentPath,Length); | |
474 | if (!temp) return(NULL); | |
475 | FIter->CurrentPath=temp; | |
476 | FIter->CurrentPathSize=Length; | |
477 | } | |
478 | ||
479 | for (Level=FIter->CurrentPathLevel ; Level<=FIter->Level ; Level++) | |
480 | { | |
481 | DIter=FIter->DirNodes+Level; | |
482 | if (Level>0) FIter->CurrentPath[DIter->PathLength-1]='/'; | |
483 | strcpy(FIter->CurrentPath+DIter->PathLength,DIter->Dir->Name); | |
484 | } | |
485 | FIter->CurrentPathLevel=Level; | |
486 | ||
487 | FileListIter_GetNext(FIter); | |
488 | return(FIter->CurrentPath); | |
489 | } | |
490 | ||
491 | /*! | |
492 | * Destroy the iterator created by FileListIter_Open(). | |
493 | */ | |
494 | void FileListIter_Close(struct _FileListIterator *FIter) | |
495 | { | |
496 | if (FIter) | |
497 | { | |
498 | if (FIter->CurrentPath) free(FIter->CurrentPath); | |
499 | if (FIter->DirNodes) free(FIter->DirNodes); | |
500 | free(FIter); | |
501 | } | |
502 | } |