]>
Commit | Line | Data |
---|---|---|
b2e465d6 AL |
1 | // -*- mode: cpp; mode: fold -*- |
2 | // Description /*{{{*/ | |
dc738e7a | 3 | // $Id: contents.cc,v 1.4 2003/02/10 07:34:41 doogie Exp $ |
b2e465d6 AL |
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 | ||
dc738e7a | 38 | #include <apti18n.h> |
b2e465d6 AL |
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]; | |
b41fd4ae | 261 | Buffer[0] = 0; |
b2e465d6 AL |
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) | |
dc738e7a | 346 | return _error->Error(_("realloc - Failed to allocate memory")); |
b2e465d6 AL |
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) | |
dc738e7a | 377 | return _error->Error(_("realloc - Failed to allocate memory")); |
b2e465d6 AL |
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 | /*}}}*/ |