1 // -*- mode: cpp; mode: fold -*-
3 // $Id: contents.cc,v 1.4 2003/02/10 07:34:41 doogie Exp $
4 /* ######################################################################
6 contents - Archive contents generator
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.
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.
22 The tree looks something like:
30 The ---> is the DirDown link
33 ##################################################################### */
35 // Include Files /*{{{*/
38 #include <apt-pkg/debfile.h>
39 #include <apt-pkg/dirstream.h>
40 #include <apt-pkg/error.h>
51 // GenContents::~GenContents - Free allocated memory /*{{{*/
52 // ---------------------------------------------------------------------
53 /* Since all our allocations are static big-block allocations all that is
54 needed is to free all of them. */
55 GenContents::~GenContents()
57 while (BlockList
!= 0)
59 BigBlock
*Old
= BlockList
;
60 BlockList
= Old
->Next
;
66 // GenContents::Mystrdup - Custom strdup /*{{{*/
67 // ---------------------------------------------------------------------
68 /* This strdup also uses a large block allocator to eliminate glibc
70 char *GenContents::Mystrdup(const char *From
)
72 unsigned int Len
= strlen(From
) + 1;
76 StrPool
= (char *)malloc(StrLeft
);
78 BigBlock
*Block
= new BigBlock
;
79 Block
->Block
= StrPool
;
80 Block
->Next
= BlockList
;
84 memcpy(StrPool
,From
,Len
);
92 // GenContents::Node::operator new - Big block allocator /*{{{*/
93 // ---------------------------------------------------------------------
94 /* This eliminates glibc's malloc overhead by allocating large blocks and
95 having a continuous set of Nodes. This takes about 8 bytes off each nodes
96 space needs. Freeing is not supported. */
97 void *GenContents::Node::operator new(size_t Amount
,GenContents
*Owner
)
99 if (Owner
->NodeLeft
== 0)
101 Owner
->NodeLeft
= 10000;
102 Owner
->NodePool
= (Node
*)malloc(Amount
*Owner
->NodeLeft
);
103 BigBlock
*Block
= new BigBlock
;
104 Block
->Block
= Owner
->NodePool
;
105 Block
->Next
= Owner
->BlockList
;
106 Owner
->BlockList
= Block
;
110 return Owner
->NodePool
++;
113 // GenContents::Grab - Grab a new node representing Name under Top /*{{{*/
114 // ---------------------------------------------------------------------
115 /* This grabs a new node representing the pathname component Name under
116 the node Top. The node is given the name Package. It is assumed that Name
117 is inside of top. If a duplicate already entered name is found then
118 a note is made on the Dup list and the previous in-tree node is returned. */
119 GenContents::Node
*GenContents::Grab(GenContents::Node
*Top
,const char *Name
,
122 /* We drop down to the next dir level each call. This simplifies
123 the calling routine */
124 if (Top
->DirDown
== 0)
126 Node
*Item
= new(this) Node
;
127 Item
->Path
= Mystrdup(Name
);
128 Item
->Package
= Package
;
137 Res
= strcmp(Name
,Top
->Path
);
142 // See if this the the same package (multi-version dup)
143 if (Top
->Package
== Package
||
144 strcasecmp(Top
->Package
,Package
) == 0)
147 // Look for an already existing Dup
148 for (Node
*I
= Top
->Dups
; I
!= 0; I
= I
->Dups
)
149 if (I
->Package
== Package
||
150 strcasecmp(I
->Package
,Package
) == 0)
154 Node
*Item
= new(this) Node
;
155 Item
->Path
= Top
->Path
;
156 Item
->Package
= Package
;
157 Item
->Dups
= Top
->Dups
;
162 // Continue to traverse the tree
165 if (Top
->BTreeLeft
== 0)
167 Top
= Top
->BTreeLeft
;
171 if (Top
->BTreeRight
== 0)
173 Top
= Top
->BTreeRight
;
177 // The item was not found in the tree
178 Node
*Item
= new(this) Node
;
179 Item
->Path
= Mystrdup(Name
);
180 Item
->Package
= Package
;
182 // Link it into the tree
185 Item
->BTreeLeft
= Top
->BTreeLeft
;
186 Top
->BTreeLeft
= Item
;
190 Item
->BTreeRight
= Top
->BTreeRight
;
191 Top
->BTreeRight
= Item
;
197 // GenContents::Add - Add a path to the tree /*{{{*/
198 // ---------------------------------------------------------------------
199 /* This takes a full pathname and adds it into the tree. We split the
200 pathname into directory fragments adding each one as we go. Technically
201 in output from tar this should result in hitting previous items. */
202 void GenContents::Add(const char *Dir
,const char *Package
)
204 Node
*Root
= &this->Root
;
206 // Drop leading slashes
207 while (*Dir
== '/' && *Dir
!= 0)
210 // Run over the string and grab out each bit up to and including a /
211 const char *Start
= Dir
;
215 if (*I
!= '/' || I
- Start
<= 1)
222 // Copy the path fragment over
224 strncpy(Tmp
,Start
,I
- Start
);
227 // Grab a node for it
228 Root
= Grab(Root
,Tmp
,Package
);
233 // The final component if it does not have a trailing /
235 Grab(Root
,Start
,Package
);
238 // GenContents::WriteSpace - Write a given number of white space chars /*{{{*/
239 // ---------------------------------------------------------------------
240 /* We mod 8 it and write tabs where possible. */
241 void GenContents::WriteSpace(FILE *Out
,unsigned int Current
,unsigned int Target
)
243 if (Target
<= Current
)
244 Target
= Current
+ 1;
246 /* Now we write tabs so long as the next tab stop would not pass
248 for (; (Current
/8 + 1)*8 < Target
; Current
= (Current
/8 + 1)*8)
251 // Fill the last bit with spaces
252 for (; Current
< Target
; Current
++)
256 // GenContents::Print - Display the tree /*{{{*/
257 // ---------------------------------------------------------------------
258 /* This is the final result function. It takes the tree and recursively
259 calls itself and runs over each section of the tree printing out
260 the pathname and the hit packages. We use Buf to build the pathname
261 summed over all the directory parents of this node. */
262 void GenContents::Print(FILE *Out
)
266 DoPrint(Out
,&Root
,Buffer
);
268 void GenContents::DoPrint(FILE *Out
,GenContents::Node
*Top
, char *Buf
)
274 DoPrint(Out
,Top
->BTreeLeft
,Buf
);
276 // Print the current dir location and then descend to lower dirs
277 char *OldEnd
= Buf
+ strlen(Buf
);
280 strcat(Buf
,Top
->Path
);
282 // Do not show the item if it is a directory with dups
283 if (Top
->Path
[strlen(Top
->Path
)-1] != '/' /*|| Top->Dups == 0*/)
286 WriteSpace(Out
,strlen(Buf
),60);
287 for (Node
*I
= Top
; I
!= 0; I
= I
->Dups
)
291 fputs(I
->Package
,Out
);
297 // Go along the directory link
298 DoPrint(Out
,Top
->DirDown
,Buf
);
302 DoPrint(Out
,Top
->BTreeRight
,Buf
);
306 // ContentsExtract::Read - Read the archive /*{{{*/
307 // ---------------------------------------------------------------------
309 bool ContentsExtract::Read(debDebFile
&Deb
)
312 return Deb
.ExtractArchive(*this);
315 // ContentsExtract::DoItem - Extract an item /*{{{*/
316 // ---------------------------------------------------------------------
317 /* This just tacks the name onto the end of our memory buffer */
318 bool ContentsExtract::DoItem(Item
&Itm
, int &/*Fd*/)
320 unsigned long Len
= strlen(Itm
.Name
);
322 // Strip leading ./'s
323 if (Itm
.Name
[0] == '.' && Itm
.Name
[1] == '/')
333 // Allocate more storage for the string list
334 if (CurSize
+ Len
+ 2 >= MaxSize
|| Data
== 0)
337 MaxSize
= 512*1024/2;
338 char *NewData
= (char *)realloc(Data
,MaxSize
*2);
340 return _error
->Error(_("realloc - Failed to allocate memory"));
345 strcpy(Data
+CurSize
,Itm
.Name
);
350 // ContentsExtract::TakeContents - Load the contents data /*{{{*/
351 // ---------------------------------------------------------------------
353 bool ContentsExtract::TakeContents(const void *NewData
,unsigned long long Length
)
361 // Allocate more storage for the string list
362 if (Length
+ 2 >= MaxSize
|| Data
== 0)
365 MaxSize
= 512*1024/2;
366 while (MaxSize
*2 <= Length
)
369 char *NewData
= (char *)realloc(Data
,MaxSize
*2);
371 return _error
->Error(_("realloc - Failed to allocate memory"));
375 memcpy(Data
,NewData
,Length
);
378 return Data
[CurSize
-1] == 0;
381 // ContentsExtract::Add - Read the contents data into the sorter /*{{{*/
382 // ---------------------------------------------------------------------
384 void ContentsExtract::Add(GenContents
&Contents
,std::string
const &Package
)
386 const char *Start
= Data
;
387 char *Pkg
= Contents
.Mystrdup(Package
.c_str());
388 for (const char *I
= Data
; I
< Data
+ CurSize
; I
++)
392 Contents
.Add(Start
,Pkg
);