summaryrefslogtreecommitdiff
path: root/apt-inst/filelist.cc
diff options
context:
space:
mode:
authorJulian Andres Klode <julian.klode@canonical.com>2019-05-06 13:42:03 +0200
committerJulian Andres Klode <julian.klode@canonical.com>2019-05-06 13:42:03 +0200
commitdb36c35a351a76825ae00628b74c160bc418683c (patch)
treeb0f31e19e45775f9a0880c0d4801e87077696036 /apt-inst/filelist.cc
parent7f0508ecc442705ac9fcbc3c2b5ac74ead18fff8 (diff)
parent6089a4b17c61ef30b2efc00e270b0907f51f352a (diff)
Merge branch 'pu/merge-libraries'
Diffstat (limited to 'apt-inst/filelist.cc')
-rw-r--r--apt-inst/filelist.cc586
1 files changed, 0 insertions, 586 deletions
diff --git a/apt-inst/filelist.cc b/apt-inst/filelist.cc
deleted file mode 100644
index 44b97d054..000000000
--- a/apt-inst/filelist.cc
+++ /dev/null
@@ -1,586 +0,0 @@
-// -*- mode: cpp; mode: fold -*-
-// Description /*{{{*/
-/* ######################################################################
-
- File Listing - Manages a Cache of File -> Package names.
-
- Diversions add some significant complexity to the system. To keep
- storage space down in the very special case of a diverted file no
- extra bytes are allocated in the Node structure. Instead a diversion
- is inserted directly into the hash table and its flag bit set. Every
- lookup for that filename will always return the diversion.
-
- The hash buckets are stored in sorted form, with diversions having
- the highest sort order. Identical files are assigned the same file
- pointer, thus after a search all of the nodes owning that file can be
- found by iterating down the bucket.
-
- Re-updates of diversions (another extremely special case) are done by
- marking all diversions as untouched, then loading the entire diversion
- list again, touching each diversion and then finally going back and
- releasing all untouched diversions. It is assumed that the diversion
- table will always be quite small and be a very irregular case.
-
- Diversions that are user-installed are represented by a package with
- an empty name string.
-
- Conf files are handled like diversions by changing the meaning of the
- Pointer field to point to a conf file entry - again to reduce over
- head for a special case.
-
- ##################################################################### */
- /*}}}*/
-// Include Files /*{{{*/
-#include <config.h>
-
-#include <apt-pkg/error.h>
-#include <apt-pkg/filelist.h>
-#include <apt-pkg/mmap.h>
-#include <apt-pkg/strutl.h>
-
-#include <iostream>
-#include <string.h>
-#include <apti18n.h>
- /*}}}*/
-
-using namespace std;
-
-// FlCache::Header::Header - Constructor /*{{{*/
-// ---------------------------------------------------------------------
-/* Initialize the header variables. These are the defaults used when
- creating new caches */
-pkgFLCache::Header::Header()
-{
- Signature = 0xEA3F1295;
-
- /* Whenever the structures change the major version should be bumped,
- whenever the generator changes the minor version should be bumped. */
- MajorVersion = 1;
- MinorVersion = 0;
- Dirty = true;
-
- HeaderSz = sizeof(pkgFLCache::Header);
- NodeSz = sizeof(pkgFLCache::Node);
- DirSz = sizeof(pkgFLCache::Directory);
- PackageSz = sizeof(pkgFLCache::Package);
- DiversionSz = sizeof(pkgFLCache::Diversion);
- ConfFileSz = sizeof(pkgFLCache::ConfFile);
-
- NodeCount = 0;
- DirCount = 0;
- PackageCount = 0;
- DiversionCount = 0;
- ConfFileCount = 0;
- HashSize = 1 << 14;
-
- FileHash = 0;
- DirTree = 0;
- Packages = 0;
- Diversions = 0;
- UniqNodes = 0;
- memset(Pools,0,sizeof(Pools));
-}
- /*}}}*/
-// FLCache::Header::CheckSizes - Check if the two headers have same *sz /*{{{*/
-// ---------------------------------------------------------------------
-/* Compare to make sure we are matching versions */
-APT_PURE bool pkgFLCache::Header::CheckSizes(Header &Against) const
-{
- if (HeaderSz == Against.HeaderSz &&
- NodeSz == Against.NodeSz &&
- DirSz == Against.DirSz &&
- DiversionSz == Against.DiversionSz &&
- PackageSz == Against.PackageSz &&
- ConfFileSz == Against.ConfFileSz)
- return true;
- return false;
-}
- /*}}}*/
-
-// FLCache::pkgFLCache - Constructor /*{{{*/
-// ---------------------------------------------------------------------
-/* If this is a new cache then a new header and hash table are instantaited
- otherwise the existing ones are mearly attached */
-pkgFLCache::pkgFLCache(DynamicMMap &Map) : Map(Map)
-{
- if (_error->PendingError() == true)
- return;
-
- LastTreeLookup = 0;
- LastLookupSize = 0;
-
- // Apply the typecasts
- HeaderP = (Header *)Map.Data();
- NodeP = (Node *)Map.Data();
- DirP = (Directory *)Map.Data();
- DiverP = (Diversion *)Map.Data();
- PkgP = (Package *)Map.Data();
- ConfP = (ConfFile *)Map.Data();
- StrP = (char *)Map.Data();
- AnyP = (unsigned char *)Map.Data();
-
- // New mapping, create the basic cache structures
- if (Map.Size() == 0)
- {
- Map.RawAllocate(sizeof(pkgFLCache::Header));
- *HeaderP = pkgFLCache::Header();
- HeaderP->FileHash = Map.RawAllocate(sizeof(pkgFLCache::Node)*HeaderP->HashSize,
- sizeof(pkgFLCache::Node))/sizeof(pkgFLCache::Node);
- }
-
- FileHash = NodeP + HeaderP->FileHash;
-
- // Setup the dynamic map manager
- HeaderP->Dirty = true;
- Map.Sync(0,sizeof(pkgFLCache::Header));
- Map.UsePools(*HeaderP->Pools,sizeof(HeaderP->Pools)/sizeof(HeaderP->Pools[0]));
-}
- /*}}}*/
-// FLCache::TreeLookup - Perform a lookup in a generic tree /*{{{*/
-// ---------------------------------------------------------------------
-/* This is a simple generic tree lookup. The first three entries of
- the Directory structure are used as a template, but any other similar
- structure could be used in it's place. */
-map_ptrloc pkgFLCache::TreeLookup(map_ptrloc *Base,const char *Text,
- const char *TextEnd,unsigned long Size,
- unsigned int *Count,bool Insert)
-{
- pkgFLCache::Directory *Dir;
-
- // Check our last entry cache
- if (LastTreeLookup != 0 && LastLookupSize == Size)
- {
- Dir = (pkgFLCache::Directory *)(AnyP + LastTreeLookup*Size);
- if (stringcmp(Text,TextEnd,StrP + Dir->Name) == 0)
- return LastTreeLookup;
- }
-
- while (1)
- {
- // Allocate a new one
- if (*Base == 0)
- {
- if (Insert == false)
- return 0;
-
- *Base = Map.Allocate(Size);
- if (*Base == 0)
- return 0;
-
- (*Count)++;
- Dir = (pkgFLCache::Directory *)(AnyP + *Base*Size);
- Dir->Name = Map.WriteString(Text,TextEnd - Text);
- LastTreeLookup = *Base;
- LastLookupSize = Size;
- return *Base;
- }
-
- // Compare this node
- Dir = (pkgFLCache::Directory *)(AnyP + *Base*Size);
- int Res = stringcmp(Text,TextEnd,StrP + Dir->Name);
- if (Res == 0)
- {
- LastTreeLookup = *Base;
- LastLookupSize = Size;
- return *Base;
- }
-
- if (Res > 0)
- Base = &Dir->Left;
- if (Res < 0)
- Base = &Dir->Right;
- }
-}
- /*}}}*/
-// FLCache::PrintTree - Print out a tree /*{{{*/
-// ---------------------------------------------------------------------
-/* This is a simple generic tree dumper, meant for debugging. */
-void pkgFLCache::PrintTree(map_ptrloc Base,unsigned long Size)
-{
- if (Base == 0)
- return;
-
- pkgFLCache::Directory *Dir = (pkgFLCache::Directory *)(AnyP + Base*Size);
- PrintTree(Dir->Left,Size);
- cout << (StrP + Dir->Name) << endl;
- PrintTree(Dir->Right,Size);
-}
- /*}}}*/
-// FLCache::GetPkg - Get a package pointer /*{{{*/
-// ---------------------------------------------------------------------
-/* Locate a package by name in it's tree, this is just a wrapper for
- TreeLookup */
-pkgFLCache::PkgIterator pkgFLCache::GetPkg(const char *Name,const char *NameEnd,
- bool Insert)
-{
- if (NameEnd == 0)
- NameEnd = Name + strlen(Name);
-
- map_ptrloc Pos = TreeLookup(&HeaderP->Packages,Name,NameEnd,
- sizeof(pkgFLCache::Package),
- &HeaderP->PackageCount,Insert);
- if (Pos == 0)
- return pkgFLCache::PkgIterator();
- return pkgFLCache::PkgIterator(*this,PkgP + Pos);
-}
- /*}}}*/
-// FLCache::GetNode - Get the node associated with the filename /*{{{*/
-// ---------------------------------------------------------------------
-/* Lookup a node in the hash table. If Insert is true then a new node is
- always inserted. The hash table can have multiple instances of a
- single name available. A search returns the first. It is important
- that additions for the same name insert after the first entry of
- the name group. */
-pkgFLCache::NodeIterator pkgFLCache::GetNode(const char *Name,
- const char *NameEnd,
- map_ptrloc Loc,
- bool Insert,bool Divert)
-{
- // Split the name into file and directory, hashing as it is copied
- const char *File = Name;
- unsigned long HashPos = 0;
- for (const char *I = Name; I < NameEnd; I++)
- {
- HashPos = 1637*HashPos + *I;
- if (*I == '/')
- File = I;
- }
-
- // Search for it
- Node *Hash = NodeP + HeaderP->FileHash + (HashPos % HeaderP->HashSize);
- int Res = 0;
- map_ptrloc FilePtr = 0;
- while (Hash->Pointer != 0)
- {
- // Compare
- Res = stringcmp(File+1,NameEnd,StrP + Hash->File);
- if (Res == 0)
- Res = stringcmp(Name,File,StrP + DirP[Hash->Dir].Name);
-
- // Diversion?
- if (Res == 0 && Insert == true)
- {
- /* Dir and File match exactly, we need to reuse the file name
- when we link it in */
- FilePtr = Hash->File;
- Res = Divert - ((Hash->Flags & Node::Diversion) == Node::Diversion);
- }
-
- // Is a match
- if (Res == 0)
- {
- if (Insert == false)
- return NodeIterator(*this,Hash);
-
- // Only one diversion per name!
- if (Divert == true)
- return NodeIterator(*this,Hash);
- break;
- }
-
- // Out of sort order
- if (Res > 0)
- break;
-
- if (Hash->Next != 0)
- Hash = NodeP + Hash->Next;
- else
- break;
- }
-
- // Fail, not found
- if (Insert == false)
- return NodeIterator(*this);
-
- // Find a directory node
- map_ptrloc Dir = TreeLookup(&HeaderP->DirTree,Name,File,
- sizeof(pkgFLCache::Directory),
- &HeaderP->DirCount,true);
- if (Dir == 0)
- return NodeIterator(*this);
-
- // Allocate a new node
- if (Hash->Pointer != 0)
- {
- // Overwrite or append
- if (Res > 0)
- {
- Node *Next = NodeP + Map.Allocate(sizeof(*Hash));
- if (Next == NodeP)
- return NodeIterator(*this);
- *Next = *Hash;
- Hash->Next = Next - NodeP;
- }
- else
- {
- unsigned long NewNext = Map.Allocate(sizeof(*Hash));
- if (NewNext == 0)
- return NodeIterator(*this);
- NodeP[NewNext].Next = Hash->Next;
- Hash->Next = NewNext;
- Hash = NodeP + Hash->Next;
- }
- }
-
- // Insert into the new item
- Hash->Dir = Dir;
- Hash->Pointer = Loc;
- Hash->Flags = 0;
- if (Divert == true)
- Hash->Flags |= Node::Diversion;
-
- if (FilePtr != 0)
- Hash->File = FilePtr;
- else
- {
- HeaderP->UniqNodes++;
- Hash->File = Map.WriteString(File+1,NameEnd - File-1);
- }
-
- // Link the node to the package list
- if (Divert == false && Loc == 0)
- {
- Hash->Next = PkgP[Loc].Files;
- PkgP[Loc].Files = Hash - NodeP;
- }
-
- HeaderP->NodeCount++;
- return NodeIterator(*this,Hash);
-}
- /*}}}*/
-// FLCache::HashNode - Return the hash bucket for the node /*{{{*/
-// ---------------------------------------------------------------------
-/* This is one of two hashing functions. The other is inlined into the
- GetNode routine. */
-APT_PURE pkgFLCache::Node *pkgFLCache::HashNode(NodeIterator const &Nde)
-{
- // Hash the node
- unsigned long HashPos = 0;
- for (const char *I = Nde.DirN(); *I != 0; I++)
- HashPos = 1637*HashPos + *I;
- HashPos = 1637*HashPos + '/';
- for (const char *I = Nde.File(); *I != 0; I++)
- HashPos = 1637*HashPos + *I;
- return NodeP + HeaderP->FileHash + (HashPos % HeaderP->HashSize);
-}
- /*}}}*/
-// FLCache::DropNode - Drop a node from the hash table /*{{{*/
-// ---------------------------------------------------------------------
-/* This erases a node from the hash table. Note that this does not unlink
- the node from the package linked list. */
-void pkgFLCache::DropNode(map_ptrloc N)
-{
- if (N == 0)
- return;
-
- NodeIterator Nde(*this,NodeP + N);
-
- if (Nde->NextPkg != 0)
- _error->Warning(_("DropNode called on still linked node"));
-
- // Locate it in the hash table
- Node *Last = 0;
- Node *Hash = HashNode(Nde);
- while (Hash->Pointer != 0)
- {
- // Got it
- if (Hash == Nde)
- {
- // Top of the bucket..
- if (Last == 0)
- {
- Hash->Pointer = 0;
- if (Hash->Next == 0)
- return;
- *Hash = NodeP[Hash->Next];
- // Release Hash->Next
- return;
- }
- Last->Next = Hash->Next;
- // Release Hash
- return;
- }
-
- Last = Hash;
- if (Hash->Next != 0)
- Hash = NodeP + Hash->Next;
- else
- break;
- }
-
- _error->Error(_("Failed to locate the hash element!"));
-}
- /*}}}*/
-// FLCache::BeginDiverLoad - Start reading new diversions /*{{{*/
-// ---------------------------------------------------------------------
-/* Tag all the diversions as untouched */
-void pkgFLCache::BeginDiverLoad()
-{
- for (DiverIterator I = DiverBegin(); I.end() == false; I++)
- I->Flags = 0;
-}
- /*}}}*/
-// FLCache::FinishDiverLoad - Finish up a new diversion load /*{{{*/
-// ---------------------------------------------------------------------
-/* This drops any untouched diversions. In effect removing any diversions
- that where not loaded (ie missing from the diversion file) */
-void pkgFLCache::FinishDiverLoad()
-{
- map_ptrloc *Cur = &HeaderP->Diversions;
- while (*Cur != 0)
- {
- Diversion *Div = DiverP + *Cur;
- if ((Div->Flags & Diversion::Touched) == Diversion::Touched)
- {
- Cur = &Div->Next;
- continue;
- }
-
- // Purge!
- DropNode(Div->DivertTo);
- DropNode(Div->DivertFrom);
- *Cur = Div->Next;
- }
-}
- /*}}}*/
-// FLCache::AddDiversion - Add a new diversion /*{{{*/
-// ---------------------------------------------------------------------
-/* Add a new diversion to the diverion tables and make sure that it is
- unique and non-chaining. */
-bool pkgFLCache::AddDiversion(PkgIterator const &Owner,
- const char *From,const char *To)
-{
- /* Locate the two hash nodes we are going to manipulate. If there
- are pre-existing diversions then they will be returned */
- NodeIterator FromN = GetNode(From,From+strlen(From),0,true,true);
- NodeIterator ToN = GetNode(To,To+strlen(To),0,true,true);
- if (FromN.end() == true || ToN.end() == true)
- return _error->Error(_("Failed to allocate diversion"));
-
- // Should never happen
- if ((FromN->Flags & Node::Diversion) != Node::Diversion ||
- (ToN->Flags & Node::Diversion) != Node::Diversion)
- return _error->Error(_("Internal error in AddDiversion"));
-
- // Now, try to reclaim an existing diversion..
- map_ptrloc Diver = 0;
- if (FromN->Pointer != 0)
- Diver = FromN->Pointer;
-
- /* Make sure from and to point to the same diversion, if they don't
- then we are trying to intermix diversions - very bad */
- if (ToN->Pointer != 0 && ToN->Pointer != Diver)
- {
- // It could be that the other diversion is no longer in use
- if ((DiverP[ToN->Pointer].Flags & Diversion::Touched) == Diversion::Touched)
- return _error->Error(_("Trying to overwrite a diversion, %s -> %s and %s/%s"),
- From,To,ToN.File(),ToN.Dir().Name());
-
- // We can erase it.
- Diversion *Div = DiverP + ToN->Pointer;
- ToN->Pointer = 0;
-
- if (Div->DivertTo == ToN.Offset())
- Div->DivertTo = 0;
- if (Div->DivertFrom == ToN.Offset())
- Div->DivertFrom = 0;
-
- // This diversion will be cleaned up by FinishDiverLoad
- }
-
- // Allocate a new diversion
- if (Diver == 0)
- {
- Diver = Map.Allocate(sizeof(Diversion));
- if (Diver == 0)
- return false;
- DiverP[Diver].Next = HeaderP->Diversions;
- HeaderP->Diversions = Diver;
- HeaderP->DiversionCount++;
- }
-
- // Can only have one diversion of the same files
- Diversion *Div = DiverP + Diver;
- if ((Div->Flags & Diversion::Touched) == Diversion::Touched)
- return _error->Error(_("Double add of diversion %s -> %s"),From,To);
-
- // Setup the From/To links
- if (Div->DivertFrom != FromN.Offset() && Div->DivertFrom != ToN.Offset())
- DropNode(Div->DivertFrom);
- Div->DivertFrom = FromN.Offset();
- if (Div->DivertTo != FromN.Offset() && Div->DivertTo != ToN.Offset())
- DropNode(Div->DivertTo);
- Div->DivertTo = ToN.Offset();
-
- // Link it to the two nodes
- FromN->Pointer = Diver;
- ToN->Pointer = Diver;
-
- // And the package
- Div->OwnerPkg = Owner.Offset();
- Div->Flags |= Diversion::Touched;
-
- return true;
-}
- /*}}}*/
-// FLCache::AddConfFile - Add a new configuration file /*{{{*/
-// ---------------------------------------------------------------------
-/* This simply adds a new conf file node to the hash table. This is only
- used by the status file reader. It associates a hash with each conf
- file entry that exists in the status file and the list file for
- the proper package. Duplicate conf files (across packages) are left
- up to other routines to deal with. */
-bool pkgFLCache::AddConfFile(const char *Name,const char *NameEnd,
- PkgIterator const &Owner,
- const unsigned char *Sum)
-{
- NodeIterator Nde = GetNode(Name,NameEnd,0,false,false);
- if (Nde.end() == true)
- return true;
-
- unsigned long File = Nde->File;
- for (; Nde->File == File && Nde.end() == false; Nde++)
- {
- if (Nde.RealPackage() != Owner)
- continue;
-
- if ((Nde->Flags & Node::ConfFile) == Node::ConfFile)
- return _error->Error(_("Duplicate conf file %s/%s"),Nde.DirN(),Nde.File());
-
- // Allocate a new conf file structure
- map_ptrloc Conf = Map.Allocate(sizeof(ConfFile));
- if (Conf == 0)
- return false;
- ConfP[Conf].OwnerPkg = Owner.Offset();
- memcpy(ConfP[Conf].MD5,Sum,sizeof(ConfP[Conf].MD5));
-
- Nde->Pointer = Conf;
- Nde->Flags |= Node::ConfFile;
- return true;
- }
-
- /* This means the conf file has been replaced, but the entry in the
- status file was not updated */
- return true;
-}
- /*}}}*/
-
-// NodeIterator::RealPackage - Return the package for this node /*{{{*/
-// ---------------------------------------------------------------------
-/* Since the package pointer is indirected in all sorts of interesting ways
- this is used to get a pointer to the owning package */
-APT_PURE pkgFLCache::Package *pkgFLCache::NodeIterator::RealPackage() const
-{
- if (Nde->Pointer == 0)
- return 0;
-
- if ((Nde->Flags & Node::ConfFile) == Node::ConfFile)
- return Owner->PkgP + Owner->ConfP[Nde->Pointer].OwnerPkg;
-
- // Diversions are ignored
- if ((Nde->Flags & Node::Diversion) == Node::Diversion)
- return 0;
-
- return Owner->PkgP + Nde->Pointer;
-}
- /*}}}*/