ftparchive/contents.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: contents.cc,v 1.3 2001/02/27 04:24:09 jgg Exp $
   4 /* ######################################################################
   5
   6    contents - Archive contents generator
   7
   8    The GenContents class is a back end for an archive contents generator.
   9    It takes a list of per-deb file name and merges it into a memory
  10    database of all previous output. This database is stored as a set
  11    of binary trees linked across directories to form a tree of all files+dirs
  12    given to it. The tree will also be sorted as it is built up thus
  13    removing the massive sort time overhead.
  14
  15    By breaking all the pathnames into components and storing them
  16    separately a space savings is realized by not duplicating the string
  17    over and over again. Ultimately this saving is sacrificed to storage of
  18    the tree structure itself but the tree structure yields a speed gain
  19    in the sorting and processing. Ultimately it takes about 5 seconds to
  20    do 141000 nodes and about 5 meg of ram.
  21
  22    The tree looks something like:
  23
  24      usr/
  25       / \             / libslang
  26    bin/ lib/ --> libc6
  27         /   \         \ libfoo
  28    games/  sbin/
  29
  30    The ---> is the DirDown link
  31
  32
  33    ##################################################################### */
  34                                                                         /*}}}*/
  35 // Include Files                                                        /*{{{*/
  36 #include "contents.h"
  37
  38 #include <apt-pkg/extracttar.h>
  39 #include <apt-pkg/error.h>
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <malloc.h>
  44                                                                         /*}}}*/
  45
  46 // GenContents::~GenContents - Free allocated memory                    /*{{{*/
  47 // ---------------------------------------------------------------------
  48 /* Since all our allocations are static big-block allocations all that is
  49    needed is to free all of them. */
  50 GenContents::~GenContents()
  51 {
  52    while (BlockList != 0)
  53    {
  54       BigBlock *Old = BlockList;
  55       BlockList = Old->Next;
  56       free(Old->Block);
  57       delete Old;
  58    }
  59 }
  60                                                                         /*}}}*/
  61 // GenContents::Mystrdup - Custom strdup                                /*{{{*/
  62 // ---------------------------------------------------------------------
  63 /* This strdup also uses a large block allocator to eliminate glibc
  64    overhead */
  65 char *GenContents::Mystrdup(const char *From)
  66 {
  67    unsigned int Len = strlen(From) + 1;
  68    if (StrLeft <= Len)
  69    {
  70       StrLeft = 4096*10;
  71       StrPool = (char *)malloc(StrLeft);
  72
  73       BigBlock *Block = new BigBlock;
  74       Block->Block = StrPool;
  75       Block->Next = BlockList;
  76       BlockList = Block;
  77    }
  78
  79    memcpy(StrPool,From,Len);
  80    StrLeft -= Len;
  81
  82    char *Res = StrPool;
  83    StrPool += Len;
  84    return Res;
  85 }
  86                                                                         /*}}}*/
  87 // GenContents::Node::operator new - Big block allocator                /*{{{*/
  88 // ---------------------------------------------------------------------
  89 /* This eliminates glibc's malloc overhead by allocating large blocks and
  90    having a continuous set of Nodes. This takes about 8 bytes off each nodes
  91    space needs. Freeing is not supported. */
  92 void *GenContents::Node::operator new(size_t Amount,GenContents *Owner)
  93 {
  94    if (Owner->NodeLeft == 0)
  95    {
  96       Owner->NodeLeft = 10000;
  97       Owner->NodePool = (Node *)malloc(Amount*Owner->NodeLeft);
  98       BigBlock *Block = new BigBlock;
  99       Block->Block = Owner->NodePool;
 100       Block->Next = Owner->BlockList;
 101       Owner->BlockList = Block;
 102    }
 103
 104    Owner->NodeLeft--;
 105    return Owner->NodePool++;
 106 }
 107                                                                         /*}}}*/
 108 // GenContents::Grab - Grab a new node representing Name under Top      /*{{{*/
 109 // ---------------------------------------------------------------------
 110 /* This grabs a new node representing the pathname component Name under
 111    the node Top. The node is given the name Package. It is assumed that Name
 112    is inside of top. If a duplicate already entered name is found then
 113    a note is made on the Dup list and the previous in-tree node is returned. */
 114 GenContents::Node *GenContents::Grab(GenContents::Node *Top,const char *Name,
 115                         const char *Package)
 116 {
 117    /* We drop down to the next dir level each call. This simplifies
 118       the calling routine */
 119    if (Top->DirDown == 0)
 120    {
 121       Node *Item = new(this) Node;
 122       Item->Path = Mystrdup(Name);
 123       Item->Package = Package;
 124       Top->DirDown = Item;
 125       return Item;
 126    }
 127    Top = Top->DirDown;
 128
 129    int Res;
 130    while (1)
 131    {
 132       Res = strcmp(Name,Top->Path);
 133
 134       // Collision!
 135       if (Res == 0)
 136       {
 137          // See if this the the same package (multi-version dup)
 138          if (Top->Package == Package ||
 139              strcasecmp(Top->Package,Package) == 0)
 140             return Top;
 141
 142          // Look for an already existing Dup
 143          for (Node *I = Top->Dups; I != 0; I = I->Dups)
 144             if (I->Package == Package ||
 145                 strcasecmp(I->Package,Package) == 0)
 146                return Top;
 147
 148          // Add the dup in
 149          Node *Item = new(this) Node;
 150          Item->Path = Top->Path;
 151          Item->Package = Package;
 152          Item->Dups = Top->Dups;
 153          Top->Dups = Item;
 154          return Top;
 155       }
 156
 157       // Continue to traverse the tree
 158       if (Res < 0)
 159       {
 160          if (Top->BTreeLeft == 0)
 161             break;
 162          Top = Top->BTreeLeft;
 163       }
 164       else
 165       {
 166          if (Top->BTreeRight == 0)
 167             break;
 168          Top = Top->BTreeRight;
 169       }
 170    }
 171
 172    // The item was not found in the tree
 173    Node *Item = new(this) Node;
 174    Item->Path = Mystrdup(Name);
 175    Item->Package = Package;
 176
 177    // Link it into the tree
 178    if (Res < 0)
 179    {
 180       Item->BTreeLeft = Top->BTreeLeft;
 181       Top->BTreeLeft = Item;
 182    }
 183    else
 184    {
 185       Item->BTreeRight = Top->BTreeRight;
 186       Top->BTreeRight = Item;
 187    }
 188
 189    return Item;
 190 }
 191                                                                         /*}}}*/
 192 // GenContents::Add - Add a path to the tree                            /*{{{*/
 193 // ---------------------------------------------------------------------
 194 /* This takes a full pathname and adds it into the tree. We split the
 195    pathname into directory fragments adding each one as we go. Technically
 196    in output from tar this should result in hitting previous items. */
 197 void GenContents::Add(const char *Dir,const char *Package)
 198 {
 199    Node *Root = &this->Root;
 200
 201    // Drop leading slashes
 202    while (*Dir == '/' && *Dir != 0)
 203       Dir++;
 204
 205    // Run over the string and grab out each bit up to and including a /
 206    const char *Start = Dir;
 207    const char *I = Dir;
 208    while (*I != 0)
 209    {
 210       if (*I != '/' || I - Start <= 1)
 211       {
 212          I++;
 213          continue;
 214       }
 215       I++;
 216
 217       // Copy the path fragment over
 218       char Tmp[1024];
 219       strncpy(Tmp,Start,I - Start);
 220       Tmp[I - Start] = 0;
 221
 222       // Grab a node for it
 223       Root = Grab(Root,Tmp,Package);
 224
 225       Start = I;
 226    }
 227
 228    // The final component if it does not have a trailing /
 229    if (I - Start >= 1)
 230       Root = Grab(Root,Start,Package);
 231 }
 232                                                                         /*}}}*/
 233 // GenContents::WriteSpace - Write a given number of white space chars  /*{{{*/
 234 // ---------------------------------------------------------------------
 235 /* We mod 8 it and write tabs where possible. */
 236 void GenContents::WriteSpace(FILE *Out,unsigned int Current,unsigned int Target)
 237 {
 238    if (Target <= Current)
 239       Target = Current + 1;
 240
 241    /* Now we write tabs so long as the next tab stop would not pass
 242       the target */
 243    for (; (Current/8 + 1)*8 < Target; Current = (Current/8 + 1)*8)
 244       fputc('\t',Out);
 245
 246    // Fill the last bit with spaces
 247    for (; Current < Target; Current++)
 248       fputc(' ',Out);
 249 }
 250                                                                         /*}}}*/
 251 // GenContents::Print - Display the tree                                /*{{{*/
 252 // ---------------------------------------------------------------------
 253 /* This is the final result function. It takes the tree and recursively
 254    calls itself and runs over each section of the tree printing out
 255    the pathname and the hit packages. We use Buf to build the pathname
 256    summed over all the directory parents of this node. */
 257 void GenContents::Print(FILE *Out)
 258 {
 259    char Buffer[1024];
 260    Buffer[0] = 0;
 261    DoPrint(Out,&Root,Buffer);
 262 }
 263 void GenContents::DoPrint(FILE *Out,GenContents::Node *Top, char *Buf)
 264 {
 265    if (Top == 0)
 266       return;
 267
 268    // Go left
 269    DoPrint(Out,Top->BTreeLeft,Buf);
 270
 271    // Print the current dir location and then descend to lower dirs
 272    char *OldEnd = Buf + strlen(Buf);
 273    if (Top->Path != 0)
 274    {
 275       strcat(Buf,Top->Path);
 276
 277       // Do not show the item if it is a directory with dups
 278       if (Top->Path[strlen(Top->Path)-1] != '/' /*|| Top->Dups == 0*/)
 279       {
 280          fputs(Buf,Out);
 281          WriteSpace(Out,strlen(Buf),60);
 282          for (Node *I = Top; I != 0; I = I->Dups)
 283          {
 284             if (I != Top)
 285                fputc(',',Out);
 286             fputs(I->Package,Out);
 287          }
 288          fputc('\n',Out);
 289       }
 290    }
 291
 292    // Go along the directory link
 293    DoPrint(Out,Top->DirDown,Buf);
 294    *OldEnd = 0;
 295
 296    // Go right
 297    DoPrint(Out,Top->BTreeRight,Buf);
 298 }
 299                                                                         /*}}}*/
 300
 301 // ContentsExtract::Read - Read the archive                             /*{{{*/
 302 // ---------------------------------------------------------------------
 303 /* */
 304 bool ContentsExtract::Read(debDebFile &Deb)
 305 {
 306    Reset();
 307
 308    // Get the archive member and positition the file
 309    const ARArchive::Member *Member = Deb.GotoMember("data.tar.gz");
 310    if (Member == 0)
 311       return false;
 312
 313    // Extract it.
 314    ExtractTar Tar(Deb.GetFile(),Member->Size);
 315    if (Tar.Go(*this) == false)
 316       return false;
 317    return true;
 318 }
 319                                                                         /*}}}*/
 320 // ContentsExtract::DoItem - Extract an item                            /*{{{*/
 321 // ---------------------------------------------------------------------
 322 /* This just tacks the name onto the end of our memory buffer */
 323 bool ContentsExtract::DoItem(Item &Itm,int &Fd)
 324 {
 325    unsigned long Len = strlen(Itm.Name);
 326
 327    // Strip leading ./'s
 328    if (Itm.Name[0] == '.' && Itm.Name[1] == '/')
 329    {
 330       // == './'
 331       if (Len == 2)
 332          return true;
 333
 334       Len -= 2;
 335       Itm.Name += 2;
 336    }
 337
 338    // Allocate more storage for the string list
 339    if (CurSize + Len + 2 >= MaxSize || Data == 0)
 340    {
 341       if (MaxSize == 0)
 342          MaxSize = 512*1024/2;
 343       char *NewData = (char *)realloc(Data,MaxSize*2);
 344       if (NewData == 0)
 345          return _error->Error("realloc - Failed to allocate memory");
 346       Data = NewData;
 347       MaxSize *= 2;
 348    }
 349
 350    strcpy(Data+CurSize,Itm.Name);
 351    CurSize += Len + 1;
 352    return true;
 353 }
 354                                                                         /*}}}*/
 355 // ContentsExtract::TakeContents - Load the contents data               /*{{{*/
 356 // ---------------------------------------------------------------------
 357 /* */
 358 bool ContentsExtract::TakeContents(const void *NewData,unsigned long Length)
 359 {
 360    if (Length == 0)
 361    {
 362       CurSize = 0;
 363       return true;
 364    }
 365
 366    // Allocate more storage for the string list
 367    if (Length + 2 >= MaxSize || Data == 0)
 368    {
 369       if (MaxSize == 0)
 370          MaxSize = 512*1024/2;
 371       while (MaxSize*2 <= Length)
 372          MaxSize *= 2;
 373
 374       char *NewData = (char *)realloc(Data,MaxSize*2);
 375       if (NewData == 0)
 376          return _error->Error("realloc - Failed to allocate memory");
 377       Data = NewData;
 378       MaxSize *= 2;
 379    }
 380    memcpy(Data,NewData,Length);
 381    CurSize = Length;
 382
 383    return Data[CurSize-1] == 0;
 384 }
 385                                                                         /*}}}*/
 386 // ContentsExtract::Add - Read the contents data into the sorter        /*{{{*/
 387 // ---------------------------------------------------------------------
 388 /* */
 389 void ContentsExtract::Add(GenContents &Contents,string Package)
 390 {
 391    const char *Start = Data;
 392    char *Pkg = Contents.Mystrdup(Package.c_str());
 393    for (const char *I = Data; I < Data + CurSize; I++)
 394    {
 395       if (*I == 0)
 396       {
 397          Contents.Add(Start,Pkg);
 398          Start = ++I;
 399       }
 400    }
 401 }
 402                                                                         /*}}}*/