apt-pkg/pkgcache.cc

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