ftparchive/contents.cc

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