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/extracttar.h>
  40 #include <apt-pkg/error.h>
  41
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include <malloc.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 = (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(FILE *Out,unsigned int Current,unsigned int 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       fputc('\t',Out);
 251
 252    // Fill the last bit with spaces
 253    for (; Current < Target; Current++)
 254       fputc(' ',Out);
 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(FILE *Out)
 264 {
 265    char Buffer[1024];
 266    Buffer[0] = 0;
 267    DoPrint(Out,&Root,Buffer);
 268 }
 269 void GenContents::DoPrint(FILE *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          fputs(Buf,Out);
 287          WriteSpace(Out,strlen(Buf),60);
 288          for (Node *I = Top; I != 0; I = I->Dups)
 289          {
 290             if (I != Top)
 291                fputc(',',Out);
 292             fputs(I->Package,Out);
 293          }
 294          fputc('\n',Out);
 295       }
 296    }
 297
 298    // Go along the directory link
 299    DoPrint(Out,Top->DirDown,Buf);
 300    *OldEnd = 0;
 301
 302    // Go right
 303    DoPrint(Out,Top->BTreeRight,Buf);
 304 }
 305                                                                         /*}}}*/
 306
 307 // ContentsExtract::Read - Read the archive                             /*{{{*/
 308 // ---------------------------------------------------------------------
 309 /* */
 310 bool ContentsExtract::Read(debDebFile &Deb)
 311 {
 312    Reset();
 313    return Deb.ExtractArchive(*this);
 314 }
 315                                                                         /*}}}*/
 316 // ContentsExtract::DoItem - Extract an item                            /*{{{*/
 317 // ---------------------------------------------------------------------
 318 /* This just tacks the name onto the end of our memory buffer */
 319 bool ContentsExtract::DoItem(Item &Itm,int &Fd)
 320 {
 321    unsigned long Len = strlen(Itm.Name);
 322
 323    // Strip leading ./'s
 324    if (Itm.Name[0] == '.' && Itm.Name[1] == '/')
 325    {
 326       // == './'
 327       if (Len == 2)
 328          return true;
 329
 330       Len -= 2;
 331       Itm.Name += 2;
 332    }
 333
 334    // Allocate more storage for the string list
 335    if (CurSize + Len + 2 >= MaxSize || Data == 0)
 336    {
 337       if (MaxSize == 0)
 338          MaxSize = 512*1024/2;
 339       char *NewData = (char *)realloc(Data,MaxSize*2);
 340       if (NewData == 0)
 341          return _error->Error(_("realloc - Failed to allocate memory"));
 342       Data = NewData;
 343       MaxSize *= 2;
 344    }
 345
 346    strcpy(Data+CurSize,Itm.Name);
 347    CurSize += Len + 1;
 348    return true;
 349 }
 350                                                                         /*}}}*/
 351 // ContentsExtract::TakeContents - Load the contents data               /*{{{*/
 352 // ---------------------------------------------------------------------
 353 /* */
 354 bool ContentsExtract::TakeContents(const void *NewData,unsigned long long Length)
 355 {
 356    if (Length == 0)
 357    {
 358       CurSize = 0;
 359       return true;
 360    }
 361
 362    // Allocate more storage for the string list
 363    if (Length + 2 >= MaxSize || Data == 0)
 364    {
 365       if (MaxSize == 0)
 366          MaxSize = 512*1024/2;
 367       while (MaxSize*2 <= Length)
 368          MaxSize *= 2;
 369
 370       char *NewData = (char *)realloc(Data,MaxSize*2);
 371       if (NewData == 0)
 372          return _error->Error(_("realloc - Failed to allocate memory"));
 373       Data = NewData;
 374       MaxSize *= 2;
 375    }
 376    memcpy(Data,NewData,Length);
 377    CurSize = Length;
 378
 379    return Data[CurSize-1] == 0;
 380 }
 381                                                                         /*}}}*/
 382 // ContentsExtract::Add - Read the contents data into the sorter        /*{{{*/
 383 // ---------------------------------------------------------------------
 384 /* */
 385 void ContentsExtract::Add(GenContents &Contents,std::string const &Package)
 386 {
 387    const char *Start = Data;
 388    char *Pkg = Contents.Mystrdup(Package.c_str());
 389    for (const char *I = Data; I < Data + CurSize; I++)
 390    {
 391       if (*I == 0)
 392       {
 393          Contents.Add(Start,Pkg);
 394          Start = ++I;
 395       }
 396    }
 397 }
 398                                                                         /*}}}*/