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