Join with aliencode

Author: jgg
Date: 2001-02-20 07:03:16 GMT
Join with aliencode

1 files changed, 588 insertions, 0 deletions

diff --git a/apt-inst/filelist.cc b/apt-inst/filelist.cc
new file mode 100644
index 000000000..211fc935e
--- /dev/null
+++ b/apt-inst/filelist.cc
@@ -0,0 +1,588 @@
+// -*- mode: cpp; mode: fold -*-
+// Description								/*{{{*/
+// $Id: filelist.cc,v 1.2 2001/02/20 07:03:16 jgg Exp $
+/* ######################################################################
+
+   File Listing - Manages a Cache of File -> Package names.
+
+   Diversions add some signficant 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 higest 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							/*{{{*/
+#ifdef __GNUG__
+#pragma implementation "apt-pkg/filelist.h"
+#endif
+
+#include <apt-pkg/filelist.h>
+#include <apt-pkg/mmap.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/strutl.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <iostream>
+									/*}}}*/
+
+// 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 */
+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, ment 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. */
+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 dont
+      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 */
+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;
+}
+									/*}}}*/