filelist.c

   1 /*
   2  * SARG Squid Analysis Report Generator      http://sarg.sourceforge.net
   3  *                                                            1998, 2013
   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 }