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