]> git.saurik.com Git - apt.git/blob - doc/cache.sgml
Updated docs
[apt.git] / doc / cache.sgml
1 <!doctype debiandoc system>
2 <!-- -*- mode: sgml; mode: fold -*- -->
3 <book>
4 <title>APT Cache File Format</title>
5
6 <author>Jason Gunthorpe <email>jgg@debian.org</email></author>
7 <version>$Id: cache.sgml,v 1.4 1998/12/14 02:23:47 jgg Exp $</version>
8
9 <abstract>
10 This document describes the complete implementation and format of the APT
11 Cache file. The APT Cache file is a way for APT to parse and store a
12 large number of package files for display in the UI. It's primary design
13 goal is to make display of a single package in the tree very fast by
14 pre-linking important things like dependencies and provides.
15
16 The specification doubles as documentation for one of the in-memory
17 structures used by the package library and the APT GUI.
18
19 </abstract>
20
21 <copyright>
22 Copyright &copy; Jason Gunthorpe, 1997-1998.
23 <p>
24 APT and this document are free software; you can redistribute them and/or
25 modify them under the terms of the GNU General Public License as published
26 by the Free Software Foundation; either version 2 of the License, or (at your
27 option) any later version.
28
29 <p>
30 For more details, on Debian GNU/Linux systems, see the file
31 /usr/doc/copyright/GPL for the full license.
32 </copyright>
33
34 <toc sect>
35
36 <chapt>Introduction
37 <!-- Purpose {{{ -->
38 <!-- ===================================================================== -->
39 <sect>Purpose
40
41 <p>
42 This document describes the implementation of an architecture
43 dependent binary cache file. The goal of this cache file is two fold,
44 firstly to speed loading and processing of the package file array and
45 secondly to reduce memory consumption of the package file array.
46
47 <p>
48 The implementation is aimed at an environment with many primary package
49 files, for instance someone that has a Package file for their CD-ROM, a
50 Package file for the latest version of the distribution on the CD-ROM and a
51 package file for the development version. Always present is the information
52 contained in the status file which might be considered a separate package
53 file.
54
55 <p>
56 Please understand, this is designed as a -CACHE FILE- it is not ment to be
57 used on any system other than the one it was created for. It is not ment to
58 be authoritative either, ie if a system crash or software failure occures it
59 must be perfectly acceptable for the cache file to be in an inconsistant
60 state. Furthermore at any time the cache file may be erased without losing
61 any information.
62
63 <p>
64 Also the structures and storage layout is optimized for use by the APT
65 GUI and may not be suitable for all purposes. However it should be possible
66 to extend it with associate cache files that contain other information.
67
68 <p>
69 To keep memory use down the cache file only contains often used fields and
70 fields that are inexepensive to store, the Package file has a full list of
71 fields. Also the client may assume that all items are perfectly valid and
72 need not perform checks against their correctness. Removal of information
73 from the cache is possible, but blanks will be left in the file, and
74 unused strings will also be present. The recommended implementation is to
75 simply rebuild the cache each time any of the data files change. It is
76 possible to add a new package file to the cache without any negative side
77 effects.
78
79 <sect1>Note on Pointer access
80 <p>
81 Every item in every structure is stored as the index to that structure.
82 What this means is that once the files is mmaped every data access has to
83 go through a fixup stage to get a real memory pointer. This is done
84 by taking the index, multiplying it by the type size and then adding
85 it to the start address of the memory block. This sounds complex, but
86 in C it is a single array dereference. Because all items are aligned to
87 their size and indexs are stored as multiples of the size of the structure
88 the format is immediately portable to all possible architectures - BUT the
89 generated files are -NOT-.
90
91 <p>
92 This scheme allows code like this to be written:
93 <example>
94 void *Map = mmap(...);
95 Package *PkgList = (Package *)Map;
96 Header *Head = (Header *)Map;
97 char *Strings = (char *)Map;
98 cout << (Strings + PkgList[Head->HashTable[0]]->Name) << endl;
99 </example>
100 <p>
101 Notice the lack of casting or multiplication. The net result is to return
102 the name of the first package in the first hash bucket, without error
103 checks.
104
105 <p>
106 The generator uses allocation pools to group similarly sized structures in
107 large blocks to eliminate any alignment overhead. The generator also
108 assures that no structures overlap and all indexes are unique. Although
109 at first glance it may seem like there is the potential for two structures
110 to exist at the same point the generator never allows this to happen.
111 (See the discussion of free space pools)
112 <!-- }}} -->
113
114 <chapt>Structures
115 <!-- Header {{{ -->
116 <!-- ===================================================================== -->
117 <sect>Header
118 <p>
119 This is the first item in the file.
120 <example>
121 struct Header
122 {
123 // Signature information
124 unsigned long Signature;
125 short MajorVersion;
126 short MinorVersion;
127 bool Dirty;
128
129 // Size of structure values
130 unsigned short HeaderSz;
131 unsigned short PackageSz;
132 unsigned short PackageFileSz;
133 unsigned short VersionSz;
134 unsigned short DependencySz;
135 unsigned short ProvidesSz;
136 unsigned short VerFileSz;
137
138 // Structure counts
139 unsigned long PackageCount;
140 unsigned long VersionCount;
141 unsigned long DependsCount;
142 unsigned long PackageFileCount;
143 unsigned long MaxVerFileSize;
144
145 // Offsets
146 unsigned long FileList; // PackageFile
147 unsigned long StringList; // StringItem
148
149 // Allocation pools
150 struct
151 {
152 unsigned long ItemSize;
153 unsigned long Start;
154 unsigned long Count;
155 } Pools[7];
156
157 // Package name lookup
158 unsigned long HashTable[512]; // Package
159 };
160 </example>
161 <taglist>
162 <tag>Signature<item>
163 This must contain the hex value 0x98FE76DC which is designed to verify
164 that the system loading the image has the same byte order and byte size as
165 the system saving the image
166
167 <tag>MajorVersion
168 <tag>MinorVersion<item>
169 These contain the version of the cache file, currently 0.2.
170
171 <tag>Dirty<item>
172 Dirty is true if the cache file was opened for reading, the client expects
173 to have written things to it and have not fully synced it. The file should
174 be erased and rebuilt if it is true.
175
176 <tag>HeaderSz
177 <tag>PackageSz
178 <tag>PackageFileSz
179 <tag>VersionSz
180 <tag>DependencySz
181 <tag>VerFileSz
182 <tag>ProvidesSz<item>
183 *Sz contains the sizeof() that particular structure. It is used as an
184 extra consistancy check on the structure of the file.
185
186 If any of the size values do not exactly match what the client expects then
187 the client should refuse the load the file.
188
189 <tag>PackageCount
190 <tag>VersionCount
191 <tag>DependsCount
192 <tag>PackageFileCount<item>
193 These indicate the number of each structure contianed in the cache.
194 PackageCount is especially usefull for generating user state structures.
195 See Package::Id for more info.
196
197 <tag>MaxVerFileSize<item>
198 The maximum size of a raw entry from the original Package file
199 (ie VerFile::Size) is stored here.
200
201 <tag>FileList<item>
202 This contains the index of the first PackageFile structure. The PackageFile
203 structures are singely linked lists that represent all package files that
204 have been merged into the cache.
205
206 <tag>StringList<item>
207 This contains a list of all the unique strings (string item type strings) in
208 the cache. The parser reads this list into memory so it can match strings
209 against it.
210
211 <tag>Pools<item>
212 The Pool structures manage the allocation pools that the generator uses.
213 Start indicates the first byte of the pool, Count is the number of objects
214 remaining in the pool and ItemSize is the structure size (alignment factor)
215 of the pool. An ItemSize of 0 indicates the pool is empty. There should be
216 the same number of pools as there are structure types. The generator
217 stores this information so future additions can make use of any unused pool
218 blocks.
219
220 <tag>HashTable<item>
221 HashTable is a hash table that provides indexing for all of the packages.
222 Each package name is inserted into the hash table using the following has
223 function:
224 <example>
225 unsigned long Hash(string Str)
226 {
227 unsigned long Hash = 0;
228 for (const char *I = Str.begin(); I != Str.end(); I++)
229 Hash += *I * ((Str.end() - I + 1));
230 return Hash % _count(Head.HashTable);
231 }
232 </example>
233 <p>
234 By iterating over each entry in the hash table it is possible to iterate over
235 the entire list of packages. Hash Collisions are handled with a singely linked
236 list of packages based at the hash item. The linked list contains only
237 packages that macth the hashing function.
238
239 </taglist>
240 <!-- }}} -->
241 <!-- Package {{{ -->
242 <!-- ===================================================================== -->
243 <sect>Package
244 <p>
245 This contians information for a single unique package. There can be any
246 number of versions of a given package. Package exists in a singly
247 linked list of package records starting at the hash index of the name in
248 the Header->HashTable.
249 <example>
250 struct Pacakge
251 {
252 // Pointers
253 unsigned long Name; // Stringtable
254 unsigned long VersionList; // Version
255 unsigned long TargetVer; // Version
256 unsigned long CurrentVer; // Version
257 unsigned long TargetDist; // StringTable (StringItem)
258 unsigned long Section; // StringTable (StringItem)
259
260 // Linked lists
261 unsigned long NextPackage; // Package
262 unsigned long RevDepends; // Dependency
263 unsigned long ProvidesList; // Provides
264
265 // Install/Remove/Purge etc
266 unsigned char SelectedState; // What
267 unsigned char InstState; // Flags
268 unsigned char CurrentState; // State
269
270 // Unique ID for this pkg
271 unsigned short ID;
272 unsigned long Flags;
273 };
274 </example>
275
276 <taglist>
277 <tag>Name<item>
278 Name of the package.
279
280 <tag>VersionList<item>
281 Base of a singely linked list of version structures. Each structure
282 represents a unique version of the package. The version structures
283 contain links into PackageFile and the original text file as well as
284 detailed infromation about the size and dependencies of the specific
285 package. In this way multiple versions of a package can be cleanly handled
286 by the system. Furthermore, this linked list is guarenteed to be sorted
287 from Highest version to lowest version with no duplicate entries.
288
289 <tag>TargetVer
290 <tag>CurrentVer<item>
291 This is an index (pointer) to the sub version that is being targeted for
292 upgrading. CurrentVer is an index to the installed version, either can be
293 0.
294
295 <tag>TargetDist<item>
296 This indicates the target distribution. Automatic upgrades should not go
297 outside of the specified dist. If it is 0 then the global target dist should
298 be used. The string should be contained in the StringItem list.
299
300 <tag>Section<item>
301 This indicates the deduced section. It should be "Unknown" or the section
302 of the last parsed item.
303
304 <tag>NextPackage<item>
305 Next link in this hash item. This linked list is based at Header.HashTable
306 and contains only packages with the same hash value.
307
308 <tag>RevDepends<item>
309 Reverse Depends is a linked list of all dependencies linked to this package.
310
311 <tag>ProvidesList<item>
312 This is a linked list of all provides for this package name.
313
314 <tag>SelectedState
315 <tag>InstState
316 <tag>CurrentState<item>
317 These corrispond to the 3 items in the Status field found in the status
318 file. See the section on defines for the possible values.
319 <p>
320 SelectedState is the state that the user wishes the package to be
321 in.
322 <p>
323 InstState is the installation state of the package. This normally
324 should be Ok, but if the installation had an accident it may be otherwise.
325 <p>
326 CurrentState indicates if the package is installed, partially installed or
327 not installed.
328
329 <tag>ID<item>
330 ID is a value from 0 to Header->PackageCount. It is a unique value assigned
331 by the generator. This allows clients to create an array of size PackageCount
332 and use it to store state information for the package map. For instance the
333 status file emitter uses this to track which packages have been emitted
334 already.
335
336 <tag>Flags<item>
337 Flags are some usefull indicators of the package's state.
338
339 </taglist>
340
341 <!-- }}} -->
342 <!-- PackageFile {{{ -->
343 <!-- ===================================================================== -->
344 <sect>PackageFile
345 <p>
346 This contians information for a single package file. Package files are
347 referenced by Version structures. This is a singly linked list based from
348 Header.FileList
349 <example>
350 struct PackageFile
351 {
352 // Names
353 unsigned long FileName; // Stringtable
354 unsigned long Archive; // Stringtable
355 unsigned long Component; // Stringtable
356 unsigned long Version; // Stringtable
357 unsigned long Origin; // Stringtable
358 unsigned long Label; // Stringtable
359 unsigned long Architecture; // Stringtable
360 unsigned long Size;
361 unsigned char NotAutomatic; // Bool
362
363 // Linked list
364 unsigned long NextFile; // PackageFile
365 unsigned short ID;
366 unsigned long Flags;
367 time_t mtime; // Modification time
368 };
369 </example>
370 <taglist>
371
372 <tag>FileName<item>
373 Refers the the physical disk file that this PacakgeFile represents.
374
375 <tag>Archive
376 <tag>Component
377 <tag>Version
378 <tag>Origin
379 <tag>Label
380 <tag>Architecture
381 <tag>NotAutomatic<item>
382 This is the release information. Please see the files document for a
383 description of what the release information means.
384
385 <tag>Size<item>
386 Size is provided as a simple check to ensure that the package file has not
387 been altered.
388
389 <tag>ID<item>
390 See Package::ID.
391
392 <tag>Flags<item>
393 Provides some flags for the PackageFile, see the section on defines.
394
395 <tag>mtime<item>
396 Modification time for the file at time of cache generation.
397
398 </taglist>
399
400 <!-- }}} -->
401 <!-- Version {{{ -->
402 <!-- ===================================================================== -->
403 <sect>Version
404 <p>
405 This contians the information for a single version of a package. This is a
406 singley linked list based from Package.Versionlist.
407
408 <p>
409 The version list is always sorted from highest version to lowest version by
410 the generator. Also there may not be any duplicate entries in the list (same
411 VerStr).
412
413 <example>
414 struct Version
415 {
416 unsigned long VerStr; // Stringtable
417 unsigned long Section; // StringTable (StringItem)
418
419 // Lists
420 unsigned long FileList; // VerFile
421 unsigned long NextVer; // Version
422 unsigned long DependsList; // Dependency
423 unsigned long ParentPkg; // Package
424 unsigned long ProvidesList; // Provides
425
426 unsigned long Size;
427 unsigned long InstalledSize;
428 unsigned short ID;
429 unsigned char Priority;
430 };
431 </example>
432 <taglist>
433
434 <tag>VerStr<item>
435 This is the complete version string.
436
437 <tag>FileList<item>
438 References the all the PackageFile's that this version came out of. FileList
439 can be used to determine what distribution(s) the Version applies to. If
440 FileList is 0 then this is a blank version. The structure should also have
441 a 0 in all other fields excluding VerStr and Possibly NextVer.
442
443 <tag>Section<item>
444 This string indicates which section it is part of. The string should be
445 contained in the StringItem list.
446
447 <tag>NextVer<item>
448 Next step in the linked list.
449
450 <tag>DependsList<item>
451 This is the base of the dependency list.
452
453 <tag>ParentPkg<item>
454 This links the version to the owning package, allowing reverse dependencies
455 to determine the package.
456
457 <tag>ProvidesList<item>
458 Head of the linked list of Provides::NextPkgProv, forward provides.
459
460 <tag>Size
461 <tag>InstalledSize<item>
462 The archive size for this version. For debian this is the size of the .deb
463 file. Installed size is the uncompressed size for this version
464
465 <tag>ID<item>
466 See Package::ID.
467
468 <tag>Priority<item>
469 This is the parsed priority value of the package.
470 </taglist>
471
472 <!-- }}} -->
473 <!-- Dependency {{{ -->
474 <!-- ===================================================================== -->
475 <sect>Dependency
476 <p>
477 Dependency contains the information for a single dependency record. The records
478 are split up like this to ease processing by the client. The base of list
479 linked list is Version.DependsList. All forms of dependencies are recorded
480 here including Conflicts, Suggests and Recommends.
481
482 <p>
483 Multiple depends on the same package must be grouped together in
484 the Dependency lists. Clients should assume this is always true.
485
486 <example>
487 struct Dependency
488 {
489 unsigned long Version; // Stringtable
490 unsigned long Package; // Package
491 unsigned long NextDepends; // Dependency
492 unsigned long NextRevDepends; // Reverse dependency linking
493 unsigned long ParentVer; // Upwards parent version link
494
495 // Specific types of depends
496 unsigned char Type;
497 unsigned char CompareOp;
498 unsigned short ID;
499 };
500 </example>
501 <taglist>
502 <tag>Version<item>
503 The string form of the version that the dependency is applied against.
504
505 <tag>Package<item>
506 The index of the package file this depends applies to. If the package file
507 does not already exist when the dependency is inserted a blank one (no
508 version records) should be created.
509
510 <tag>NextDepends<item>
511 Linked list based off a Version structure of all the dependencies in that
512 version.
513
514 <tag>NextRevDepends<item>
515 Reverse dependency linking, based off a Package structure. This linked list
516 is a list of all packages that have a depends line for a given package.
517
518 <tag>ParentVer<item>
519 Parent version linking, allows the reverse dependency list to link
520 back to the version and package that the dependency are for.
521
522 <tag>Type<item>
523 Describes weather it is depends, predepends, recommends, suggests, etc.
524
525 <tag>CompareOp<item>
526 Describes the comparison operator specified on the depends line. If the high
527 bit is set then it is a logical or with the previous record.
528
529 <tag>ID<item>
530 See Package::ID.
531
532 </taglist>
533
534 <!-- }}} -->
535 <!-- Provides {{{ -->
536 <!-- ===================================================================== -->
537 <sect>Provides
538 <p>
539 Provides handles virtual packages. When a Provides: line is encountered
540 a new provides record is added associating the package with a virtual
541 package name. The provides structures are linked off the package structures.
542 This simplifies the analysis of dependencies and other aspects A provides
543 refers to a specific version of a specific package, not all versions need to
544 provide that provides.
545
546 <p>
547 There is a linked list of provided package names started from each
548 version that provides packages. This is the forwards provides mechanism.
549 <example>
550 struct Provides
551 {
552 unsigned long ParentPkg; // Package
553 unsigned long Version; // Version
554 unsigned long ProvideVersion; // Stringtable
555 unsigned long NextProvides; // Provides
556 unsigned long NextPkgProv; // Provides
557 };
558 </example>
559 <taglist>
560 <tag>ParentPkg<item>
561 The index of the package that head of this linked list is in. ParentPkg->Name
562 is the name of the provides.
563
564 <tag>Version<item>
565 The index of the version this provide line applies to.
566
567 <tag>ProvideVersion<item>
568 Each provides can specify a version in the provides line. This version allows
569 dependencies to depend on specific versions of a Provides, as well as allowing
570 Provides to override existing packages. This is experimental.
571
572 <tag>NextProvides<item>
573 Next link in the singly linked list of provides (based off package)
574
575 <tag>NextPkgProv<item>
576 Next link in the singly linked list of provides for 'Version'.
577
578 </taglist>
579
580 <!-- }}} -->
581 <!-- VerFile {{{ -->
582 <!-- ===================================================================== -->
583 <sect>VerFile
584 <p>
585 VerFile associates a version with a PackageFile, this allows a full
586 description of all Versions in all files (and hence all sources) under
587 consideration.
588
589 <example>
590 struct pkgCache::VerFile
591 {
592 unsigned long File; // PackageFile
593 unsigned long NextFile; // PkgVerFile
594 unsigned long Offset;
595 unsigned short Size;
596 }
597 </example>
598 <taglist>
599 <tag>File<item>
600 The index of the package file that this version was found in.
601
602 <tag>NextFile<item>
603 The next step in the linked list.
604
605 <tag>Offset
606 <tag>Size<item>
607 These describe the exact position in the package file for the section from
608 this version.
609 </taglist>
610
611 <!-- }}} -->
612 <!-- StringItem {{{ -->
613 <!-- ===================================================================== -->
614 <sect>StringItem
615 <p>
616 StringItem is used for generating single instances of strings. Some things
617 like Section Name are are usefull to have as unique tags. It is part of
618 a linked list based at Header::StringList.
619 <example>
620 struct StringItem
621 {
622 unsigned long String; // Stringtable
623 unsigned long NextItem; // StringItem
624 };
625 </example>
626 <taglist>
627 <tag>String<item>
628 The string this refers to.
629
630 <tag>NextItem<item>
631 Next link in the chain.
632 </taglist>
633 <!-- }}} -->
634 <!-- StringTable {{{ -->
635 <!-- ===================================================================== -->
636 <sect>StringTable
637 <p>
638 All strings are simply inlined any place in the file that is natural for the
639 writer. The client should make no assumptions about the positioning of
640 strings. All stringtable values point to a byte offset from the start of the
641 file that a null terminated string will begin.
642 <!-- }}} -->
643 <!-- Defines {{{ -->
644 <!-- ===================================================================== -->
645 <sect>Defines
646 <p>
647 Several structures use variables to indicate things. Here is a list of all
648 of them.
649
650 <sect1>Definitions for Dependency::Type
651 <p>
652 <example>
653 #define pkgDEP_Depends 1
654 #define pkgDEP_PreDepends 2
655 #define pkgDEP_Suggests 3
656 #define pkgDEP_Recommends 4
657 #define pkgDEP_Conflicts 5
658 #define pkgDEP_Replaces 6
659 </example>
660 </sect1>
661
662 <sect1>Definitions for Dependency::CompareOp
663 <p>
664 <example>
665 #define pkgOP_OR 0x10
666 #define pkgOP_LESSEQ 0x1
667 #define pkgOP_GREATEREQ 0x2
668 #define pkgOP_LESS 0x3
669 #define pkgOP_GREATER 0x4
670 #define pkgOP_EQUALS 0x5
671 </example>
672 The lower 4 bits are used to indicate what operator is being specified and
673 the upper 4 bits are flags. pkgOP_OR indicates that the next package is
674 or'd with the current package.
675 </sect1>
676
677 <sect1>Definitions for Package::SelectedState
678 <p>
679 <example>
680 #define pkgSTATE_Unkown 0
681 #define pkgSTATE_Install 1
682 #define pkgSTATE_Hold 2
683 #define pkgSTATE_DeInstall 3
684 #define pkgSTATE_Purge 4
685 </example>
686 </sect1>
687
688 <sect1>Definitions for Package::InstState
689 <p>
690 <example>
691 #define pkgSTATE_Ok 0
692 #define pkgSTATE_ReInstReq 1
693 #define pkgSTATE_Hold 2
694 #define pkgSTATE_HoldReInstReq 3
695 </example>
696 </sect1>
697
698 <sect1>Definitions for Package::CurrentState
699 <p>
700 <example>
701 #define pkgSTATE_NotInstalled 0
702 #define pkgSTATE_UnPacked 1
703 #define pkgSTATE_HalfConfigured 2
704 #define pkgSTATE_UnInstalled 3
705 #define pkgSTATE_HalfInstalled 4
706 #define pkgSTATE_ConfigFiles 5
707 #define pkgSTATE_Installed 6
708 </example>
709 </sect1>
710
711 <sect1>Definitions for Package::Flags
712 <p>
713 <example>
714 #define pkgFLAG_Auto (1 << 0)
715 #define pkgFLAG_New (1 << 1)
716 #define pkgFLAG_Obsolete (1 << 2)
717 #define pkgFLAG_Essential (1 << 3)
718 #define pkgFLAG_ImmediateConf (1 << 4)
719 </example>
720 </sect1>
721
722 <sect1>Definitions for Version::Priority
723 <p>
724 Zero is used for unparsable or absent Priority fields.
725 <example>
726 #define pkgPRIO_Important 1
727 #define pkgPRIO_Required 2
728 #define pkgPRIO_Standard 3
729 #define pkgPRIO_Optional 4
730 #define pkgPRIO_Extra 5
731 </example>
732 </sect1>
733
734 <sect1>Definitions for PackageFile::Flags
735 <p>
736 <example>
737 #define pkgFLAG_NotSource (1 << 0)
738 </example>
739 </sect1>
740
741 <!-- }}} -->
742
743 <chapt>Notes on the Generator
744 <!-- Notes on the Generator {{{ -->
745 <!-- ===================================================================== -->
746 <p>
747 The pkgCache::MergePackageFile function is currently the only generator of
748 the cache file. It implements a conversion from the normal textual package
749 file into the cache file.
750
751 <p>
752 The generator assumes any package declaration with a
753 Status: line is a 'Status of the package' type of package declaration.
754 A Package with a Target-Version field should also really have a status field.
755 The processing of a Target-Version field can create a place-holder Version
756 structure that is empty to refer to the specified version (See Version
757 for info on what a empty Version looks like). The Target-Version syntax
758 allows the specification of a specific version and a target distribution.
759
760 <p>
761 Different section names on different versions is supported, but I
762 do not expect to use it. To simplify the GUI it will mearly use the section
763 in the Package structure. This should be okay as I hope sections do not change
764 much.
765
766 <p>
767 The generator goes through a number of post processing steps after producing
768 a disk file. It sorts all of the version lists to be in descending order
769 and then generates the reverse dependency lists for all of the packages.
770 ID numbers and count values are also generated in the post processing step.
771
772 <p>
773 It is possible to extend many of the structures in the cache with extra data.
774 This is done by using the ID member. ID will be a unique number from 0 to
775 Header->??Count. For example
776 <example>
777 struct MyPkgData;
778 MyPkgData *Data = new MyPkgData[Header->PackageCount];
779 Data[Package->ID]->Item = 0;
780 </example>
781 This provides a one way reference between package structures and user data. To
782 get a two way reference would require a member inside the MyPkgData structure.
783
784 <p>
785 The generators use of free space pools tend to make the package file quite
786 large, and quite full of blank space. This could be fixed with sparse files.
787
788 <!-- }}} -->
789
790 <chapt>Future Directions
791 <!-- Future Directions {{{ -->
792 <!-- ===================================================================== -->
793 <p>
794 Some good directions to take the cache file is into a cache directory that
795 contains many associated caches that cache other important bits of
796 information. (/var/cache/apt, FHS2)
797
798 <p>
799 Caching of the info/*.list is an excellent place to start, by generating all
800 the list files into a tree structure and reverse linking them to the package
801 structures in the main cache file major speed gains in dpkg might be achived.
802
803 <!-- }}} -->
804
805 </book>