apt-pkg/pkgcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: pkgcache.cc,v 1.31 1999/12/10 23:40:29 jgg Exp $
   4 /* ######################################################################
   5
   6    Package Cache - Accessor code for the cache
   7
   8    Please see doc/apt-pkg/cache.sgml for a more detailed description of
   9    this format. Also be sure to keep that file up-to-date!!
  10
  11    This is the general utility functions for cache managment. They provide
  12    a complete set of accessor functions for the cache. The cacheiterators
  13    header contains the STL-like iterators that can be used to easially
  14    navigate the cache as well as seemlessly dereference the mmap'd
  15    indexes. Use these always.
  16
  17    The main class provides for ways to get package indexes and some
  18    general lookup functions to start the iterators.
  19
  20    ##################################################################### */
  21                                                                         /*}}}*/
  22 // Include Files                                                        /*{{{*/
  23 #ifdef __GNUG__
  24 #pragma implementation "apt-pkg/pkgcache.h"
  25 #pragma implementation "apt-pkg/cacheiterators.h"
  26 #endif
  27 #include <apt-pkg/pkgcache.h>
  28 #include <apt-pkg/version.h>
  29 #include <apt-pkg/error.h>
  30 #include <apt-pkg/strutl.h>
  31
  32 #include <string>
  33 #include <sys/stat.h>
  34 #include <unistd.h>
  35
  36 #include <system.h>
  37
  38                                                                         /*}}}*/
  39
  40 // Cache::Header::Header - Constructor                                  /*{{{*/
  41 // ---------------------------------------------------------------------
  42 /* Simply initialize the header */
  43 pkgCache::Header::Header()
  44 {
  45    Signature = 0x98FE76DC;
  46
  47    /* Whenever the structures change the major version should be bumped,
  48       whenever the generator changes the minor version should be bumped. */
  49    MajorVersion = 3;
  50    MinorVersion = 5;
  51    Dirty = true;
  52
  53    HeaderSz = sizeof(pkgCache::Header);
  54    PackageSz = sizeof(pkgCache::Package);
  55    PackageFileSz = sizeof(pkgCache::PackageFile);
  56    VersionSz = sizeof(pkgCache::Version);
  57    DependencySz = sizeof(pkgCache::Dependency);
  58    ProvidesSz = sizeof(pkgCache::Provides);
  59    VerFileSz = sizeof(pkgCache::VerFile);
  60
  61    PackageCount = 0;
  62    VersionCount = 0;
  63    DependsCount = 0;
  64    PackageFileCount = 0;
  65    VerFileCount = 0;
  66    ProvidesCount = 0;
  67    MaxVerFileSize = 0;
  68
  69    FileList = 0;
  70    StringList = 0;
  71    memset(HashTable,0,sizeof(HashTable));
  72    memset(Pools,0,sizeof(Pools));
  73 }
  74                                                                         /*}}}*/
  75 // Cache::Header::CheckSizes - Check if the two headers have same *sz   /*{{{*/
  76 // ---------------------------------------------------------------------
  77 /* */
  78 bool pkgCache::Header::CheckSizes(Header &Against) const
  79 {
  80    if (HeaderSz == Against.HeaderSz &&
  81        PackageSz == Against.PackageSz &&
  82        PackageFileSz == Against.PackageFileSz &&
  83        VersionSz == Against.VersionSz &&
  84        DependencySz == Against.DependencySz &&
  85        VerFileSz == Against.VerFileSz &&
  86        ProvidesSz == Against.ProvidesSz)
  87       return true;
  88    return false;
  89 }
  90                                                                         /*}}}*/
  91
  92 // Cache::pkgCache - Constructor                                        /*{{{*/
  93 // ---------------------------------------------------------------------
  94 /* */
  95 pkgCache::pkgCache(MMap &Map) : Map(Map)
  96 {
  97    ReMap();
  98 }
  99                                                                         /*}}}*/
 100 // Cache::ReMap - Reopen the cache file                                 /*{{{*/
 101 // ---------------------------------------------------------------------
 102 /* If the file is already closed then this will open it open it. */
 103 bool pkgCache::ReMap()
 104 {
 105    // Apply the typecasts.
 106    HeaderP = (Header *)Map.Data();
 107    PkgP = (Package *)Map.Data();
 108    VerFileP = (VerFile *)Map.Data();
 109    PkgFileP = (PackageFile *)Map.Data();
 110    VerP = (Version *)Map.Data();
 111    ProvideP = (Provides *)Map.Data();
 112    DepP = (Dependency *)Map.Data();
 113    StringItemP = (StringItem *)Map.Data();
 114    StrP = (char *)Map.Data();
 115
 116    if (Map.Size() == 0)
 117       return false;
 118
 119    // Check the header
 120    Header DefHeader;
 121    if (HeaderP->Signature != DefHeader.Signature ||
 122        HeaderP->Dirty == true)
 123       return _error->Error("The package cache file is corrupted");
 124
 125    if (HeaderP->MajorVersion != DefHeader.MajorVersion ||
 126        HeaderP->MinorVersion != DefHeader.MinorVersion ||
 127        HeaderP->CheckSizes(DefHeader) == false)
 128       return _error->Error("The package cache file is an incompatible version");
 129
 130    return true;
 131 }
 132                                                                         /*}}}*/
 133 // Cache::Hash - Hash a string                                          /*{{{*/
 134 // ---------------------------------------------------------------------
 135 /* This is used to generate the hash entries for the HashTable. With my
 136    package list from bo this function gets 94% table usage on a 512 item
 137    table (480 used items) */
 138 unsigned long pkgCache::sHash(string Str) const
 139 {
 140    unsigned long Hash = 0;
 141    for (const char *I = Str.begin(); I != Str.end(); I++)
 142       Hash = 5*Hash + tolower(*I);
 143    return Hash % _count(HeaderP->HashTable);
 144 }
 145
 146 unsigned long pkgCache::sHash(const char *Str) const
 147 {
 148    unsigned long Hash = 0;
 149    for (const char *I = Str; *I != 0; I++)
 150       Hash = 5*Hash + tolower(*I);
 151    return Hash % _count(HeaderP->HashTable);
 152 }
 153
 154                                                                         /*}}}*/
 155 // Cache::FindPkg - Locate a package by name                            /*{{{*/
 156 // ---------------------------------------------------------------------
 157 /* Returns 0 on error, pointer to the package otherwise */
 158 pkgCache::PkgIterator pkgCache::FindPkg(string Name)
 159 {
 160    // Look at the hash bucket
 161    Package *Pkg = PkgP + HeaderP->HashTable[Hash(Name)];
 162    for (; Pkg != PkgP; Pkg = PkgP + Pkg->NextPackage)
 163    {
 164       if (Pkg->Name != 0 && StrP[Pkg->Name] == Name[0] &&
 165           stringcasecmp(Name.begin(),Name.end(),StrP + Pkg->Name) == 0)
 166          return PkgIterator(*this,Pkg);
 167    }
 168    return PkgIterator(*this,0);
 169 }
 170                                                                         /*}}}*/
 171 // Cache::Priority - Convert a priority value to a string               /*{{{*/
 172 // ---------------------------------------------------------------------
 173 /* */
 174 const char *pkgCache::Priority(unsigned char Prio)
 175 {
 176    const char *Mapping[] = {0,"important","required","standard","optional","extra"};
 177    if (Prio < _count(Mapping))
 178       return Mapping[Prio];
 179    return 0;
 180 }
 181                                                                         /*}}}*/
 182 // Cache::GetCandidateVer - Returns the Candidate install version       /*{{{*/
 183 // ---------------------------------------------------------------------
 184 /* The default just returns the highest available version that is not
 185    a source and automatic */
 186 pkgCache::VerIterator pkgCache::GetCandidateVer(PkgIterator Pkg,
 187                                                 bool AllowCurrent)
 188 {
 189    /* Not source/not automatic versions cannot be a candidate version
 190       unless they are already installed */
 191    VerIterator Last(*this,0);
 192
 193    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 194    {
 195       if (Pkg.CurrentVer() == I && AllowCurrent == true)
 196          return I;
 197
 198       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 199       {
 200          if ((J.File()->Flags & Flag::NotSource) != 0)
 201             continue;
 202
 203          /* Stash the highest version of a not-automatic source, we use it
 204             if there is nothing better */
 205          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 206          {
 207             if (Last.end() == true)
 208                Last = I;
 209             continue;
 210          }
 211
 212          return I;
 213       }
 214    }
 215
 216    return Last;
 217 }
 218                                                                         /*}}}*/
 219
 220 // Bases for iterator classes                                           /*{{{*/
 221 void pkgCache::VerIterator::_dummy() {}
 222 void pkgCache::DepIterator::_dummy() {}
 223 void pkgCache::PrvIterator::_dummy() {}
 224                                                                         /*}}}*/
 225 // PkgIterator::operator ++ - Postfix incr                              /*{{{*/
 226 // ---------------------------------------------------------------------
 227 /* This will advance to the next logical package in the hash table. */
 228 void pkgCache::PkgIterator::operator ++(int)
 229 {
 230    // Follow the current links
 231    if (Pkg != Owner->PkgP)
 232       Pkg = Owner->PkgP + Pkg->NextPackage;
 233
 234    // Follow the hash table
 235    while (Pkg == Owner->PkgP && HashIndex < (signed)_count(Owner->HeaderP->HashTable))
 236    {
 237       HashIndex++;
 238       Pkg = Owner->PkgP + Owner->HeaderP->HashTable[HashIndex];
 239    }
 240 };
 241                                                                         /*}}}*/
 242 // PkgIterator::State - Check the State of the package                  /*{{{*/
 243 // ---------------------------------------------------------------------
 244 /* By this we mean if it is either cleanly installed or cleanly removed. */
 245 pkgCache::PkgIterator::OkState pkgCache::PkgIterator::State() const
 246 {
 247    if (Pkg->InstState == pkgCache::State::ReInstReq ||
 248        Pkg->InstState == pkgCache::State::HoldReInstReq)
 249       return NeedsUnpack;
 250
 251    if (Pkg->CurrentState == pkgCache::State::UnPacked ||
 252        Pkg->CurrentState == pkgCache::State::HalfConfigured)
 253       return NeedsConfigure;
 254
 255    if (Pkg->CurrentState == pkgCache::State::HalfInstalled ||
 256        Pkg->InstState != pkgCache::State::Ok)
 257       return NeedsUnpack;
 258
 259    return NeedsNothing;
 260 }
 261                                                                         /*}}}*/
 262 // DepIterator::IsCritical - Returns true if the dep is important       /*{{{*/
 263 // ---------------------------------------------------------------------
 264 /* Currently critical deps are defined as depends, predepends and
 265    conflicts. */
 266 bool pkgCache::DepIterator::IsCritical()
 267 {
 268    if (Dep->Type == pkgCache::Dep::Conflicts ||
 269        Dep->Type == pkgCache::Dep::Depends ||
 270        Dep->Type == pkgCache::Dep::PreDepends)
 271       return true;
 272    return false;
 273 }
 274                                                                         /*}}}*/
 275 // DepIterator::SmartTargetPkg - Resolve dep target pointers w/provides /*{{{*/
 276 // ---------------------------------------------------------------------
 277 /* This intellegently looks at dep target packages and tries to figure
 278    out which package should be used. This is needed to nicely handle
 279    provide mapping. If the target package has no other providing packages
 280    then it returned. Otherwise the providing list is looked at to
 281    see if there is one one unique providing package if so it is returned.
 282    Otherwise true is returned and the target package is set. The return
 283    result indicates whether the node should be expandable */
 284 bool pkgCache::DepIterator::SmartTargetPkg(PkgIterator &Result)
 285 {
 286    Result = TargetPkg();
 287
 288    // No provides at all
 289    if (Result->ProvidesList == 0)
 290       return false;
 291
 292    // There is the Base package and the providing ones which is at least 2
 293    if (Result->VersionList != 0)
 294       return true;
 295
 296    /* We have to skip over indirect provisions of the package that
 297       owns the dependency. For instance, if libc5-dev depends on the
 298       virtual package libc-dev which is provided by libc5-dev and libc6-dev
 299       we must ignore libc5-dev when considering the provides list. */
 300    PrvIterator PStart = Result.ProvidesList();
 301    for (; PStart.end() != true && PStart.OwnerPkg() == ParentPkg(); PStart++);
 302
 303    // Nothing but indirect self provides
 304    if (PStart.end() == true)
 305       return false;
 306
 307    // Check for single packages in the provides list
 308    PrvIterator P = PStart;
 309    for (; P.end() != true; P++)
 310    {
 311       // Skip over self provides
 312       if (P.OwnerPkg() == ParentPkg())
 313          continue;
 314       if (PStart.OwnerPkg() != P.OwnerPkg())
 315          break;
 316    }
 317
 318    // Check for non dups
 319    if (P.end() != true)
 320       return true;
 321    Result = PStart.OwnerPkg();
 322    return false;
 323 }
 324                                                                         /*}}}*/
 325 // DepIterator::AllTargets - Returns the set of all possible targets    /*{{{*/
 326 // ---------------------------------------------------------------------
 327 /* This is a more usefull version of TargetPkg() that follows versioned
 328    provides. It includes every possible package-version that could satisfy
 329    the dependency. The last item in the list has a 0. The resulting pointer
 330    must be delete [] 'd */
 331 pkgCache::Version **pkgCache::DepIterator::AllTargets()
 332 {
 333    Version **Res = 0;
 334    unsigned long Size =0;
 335    while (1)
 336    {
 337       Version **End = Res;
 338       PkgIterator DPkg = TargetPkg();
 339
 340       // Walk along the actual package providing versions
 341       for (VerIterator I = DPkg.VersionList(); I.end() == false; I++)
 342       {
 343          if (pkgCheckDep(TargetVer(),I.VerStr(),Dep->CompareOp) == false)
 344             continue;
 345
 346          if (Dep->Type == pkgCache::Dep::Conflicts &&
 347              ParentPkg() == I.ParentPkg())
 348             continue;
 349
 350          Size++;
 351          if (Res != 0)
 352             *End++ = I;
 353       }
 354
 355       // Follow all provides
 356       for (PrvIterator I = DPkg.ProvidesList(); I.end() == false; I++)
 357       {
 358          if (pkgCheckDep(TargetVer(),I.ProvideVersion(),Dep->CompareOp) == false)
 359             continue;
 360
 361          if (Dep->Type == pkgCache::Dep::Conflicts &&
 362              ParentPkg() == I.OwnerPkg())
 363             continue;
 364
 365          Size++;
 366          if (Res != 0)
 367             *End++ = I.OwnerVer();
 368       }
 369
 370       // Do it again and write it into the array
 371       if (Res == 0)
 372       {
 373          Res = new Version *[Size+1];
 374          Size = 0;
 375       }
 376       else
 377       {
 378          *End = 0;
 379          break;
 380       }
 381    }
 382
 383    return Res;
 384 }
 385                                                                         /*}}}*/
 386 // DepIterator::CompType - Return a string describing the compare type  /*{{{*/
 387 // ---------------------------------------------------------------------
 388 /* This returns a string representation of the dependency compare
 389    type */
 390 const char *pkgCache::DepIterator::CompType()
 391 {
 392    const char *Ops[] = {"","<=",">=","<",">","=","!="};
 393    if ((unsigned)(Dep->CompareOp & 0xF) < 7)
 394       return Ops[Dep->CompareOp & 0xF];
 395    return "";
 396 }
 397                                                                         /*}}}*/
 398 // DepIterator::DepType - Return a string describing the dep type       /*{{{*/
 399 // ---------------------------------------------------------------------
 400 /* */
 401 const char *pkgCache::DepIterator::DepType()
 402 {
 403    const char *Types[] = {"","Depends","PreDepends","Suggests",
 404                           "Recommends","Conflicts","Replaces"};
 405    if (Dep->Type < 7)
 406       return Types[Dep->Type];
 407    return "";
 408 }
 409                                                                         /*}}}*/
 410 // DepIterator::GlobOr - Compute an OR group                            /*{{{*/
 411 // ---------------------------------------------------------------------
 412 /* This Takes an iterator, iterates past the current dependency grouping
 413    and returns Start and End so that so End is the final element
 414    in the group, if End == Start then D is End++ and End is the
 415    dependency D was pointing to. Use in loops to iterate sensibly. */
 416 void pkgCache::DepIterator::GlobOr(DepIterator &Start,DepIterator &End)
 417 {
 418    // Compute a single dependency element (glob or)
 419    Start = *this;
 420    End = *this;
 421    for (bool LastOR = true; end() == false && LastOR == true;)
 422    {
 423       LastOR = (Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 424       (*this)++;
 425       if (LastOR == true)
 426          End = (*this);
 427    }
 428 }
 429                                                                         /*}}}*/
 430 // VerIterator::CompareVer - Fast version compare for same pkgs         /*{{{*/
 431 // ---------------------------------------------------------------------
 432 /* This just looks over the version list to see if B is listed before A. In
 433    most cases this will return in under 4 checks, ver lists are short. */
 434 int pkgCache::VerIterator::CompareVer(const VerIterator &B) const
 435 {
 436    // Check if they are equal
 437    if (*this == B)
 438       return 0;
 439    if (end() == true)
 440       return -1;
 441    if (B.end() == true)
 442       return 1;
 443
 444    /* Start at A and look for B. If B is found then A > B otherwise
 445       B was before A so A < B */
 446    VerIterator I = *this;
 447    for (;I.end() == false; I++)
 448       if (I == B)
 449          return 1;
 450    return -1;
 451 }
 452                                                                         /*}}}*/
 453 // VerIterator::Downloadable - Checks if the version is downloadable    /*{{{*/
 454 // ---------------------------------------------------------------------
 455 /* */
 456 bool pkgCache::VerIterator::Downloadable() const
 457 {
 458    VerFileIterator Files = FileList();
 459    for (; Files.end() == false; Files++)
 460       if ((Files.File()->Flags & pkgCache::Flag::NotSource) != pkgCache::Flag::NotSource)
 461          return true;
 462    return false;
 463 }
 464                                                                         /*}}}*/
 465 // VerIterator::PriorityType - Return a string describing the priority  /*{{{*/
 466 // ---------------------------------------------------------------------
 467 /* */
 468 const char *pkgCache::VerIterator::PriorityType()
 469 {
 470    const char *Types[] = {"","Important","Required","Standard",
 471                           "Optional","Extra"};
 472    if (Ver->Priority < 6)
 473       return Types[Ver->Priority];
 474    return "";
 475 }
 476                                                                         /*}}}*/
 477 // VerIterator::Automatic - Check if this version is 'automatic'        /*{{{*/
 478 // ---------------------------------------------------------------------
 479 /* This checks to see if any of the versions files are not NotAutomatic.
 480    True if this version is selectable for automatic installation. */
 481 bool pkgCache::VerIterator::Automatic() const
 482 {
 483    VerFileIterator Files = FileList();
 484    for (; Files.end() == false; Files++)
 485       if ((Files.File()->Flags & pkgCache::Flag::NotAutomatic) != pkgCache::Flag::NotAutomatic)
 486          return true;
 487    return false;
 488 }
 489                                                                         /*}}}*/
 490 // VerIterator::NewestFile - Return the newest file version relation    /*{{{*/
 491 // ---------------------------------------------------------------------
 492 /* This looks at the version numbers associated with all of the sources
 493    this version is in and returns the highest.*/
 494 pkgCache::VerFileIterator pkgCache::VerIterator::NewestFile() const
 495 {
 496    VerFileIterator Files = FileList();
 497    VerFileIterator Highest = Files;
 498    for (; Files.end() == false; Files++)
 499    {
 500       if (pkgVersionCompare(Files.File().Version(),Highest.File().Version()) > 0)
 501          Highest = Files;
 502    }
 503
 504    return Highest;
 505 }
 506                                                                         /*}}}*/
 507 // PkgFileIterator::IsOk - Checks if the cache is in sync with the file /*{{{*/
 508 // ---------------------------------------------------------------------
 509 /* This stats the file and compares its stats with the ones that were
 510    stored during generation. Date checks should probably also be
 511    included here. */
 512 bool pkgCache::PkgFileIterator::IsOk()
 513 {
 514    struct stat Buf;
 515    if (stat(FileName(),&Buf) != 0)
 516       return false;
 517
 518    if (Buf.st_size != (signed)File->Size || Buf.st_mtime != File->mtime)
 519       return false;
 520
 521    return true;
 522 }
 523                                                                         /*}}}*/