apt-pkg/pkgcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: pkgcache.cc,v 1.23 1999/02/23 06:46:24 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 = 2;
  47    MinorVersion = 3;
  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
 181 // Bases for iterator classes                                           /*{{{*/
 182 void pkgCache::VerIterator::_dummy() {}
 183 void pkgCache::DepIterator::_dummy() {}
 184 void pkgCache::PrvIterator::_dummy() {}
 185                                                                         /*}}}*/
 186 // PkgIterator::operator ++ - Postfix incr                              /*{{{*/
 187 // ---------------------------------------------------------------------
 188 /* This will advance to the next logical package in the hash table. */
 189 void pkgCache::PkgIterator::operator ++(int)
 190 {
 191    // Follow the current links
 192    if (Pkg != Owner->PkgP)
 193       Pkg = Owner->PkgP + Pkg->NextPackage;
 194
 195    // Follow the hash table
 196    while (Pkg == Owner->PkgP && HashIndex < (signed)_count(Owner->HeaderP->HashTable))
 197    {
 198       HashIndex++;
 199       Pkg = Owner->PkgP + Owner->HeaderP->HashTable[HashIndex];
 200    }
 201 };
 202                                                                         /*}}}*/
 203 // PkgIterator::State - Check the State of the package                  /*{{{*/
 204 // ---------------------------------------------------------------------
 205 /* By this we mean if it is either cleanly installed or cleanly removed. */
 206 pkgCache::PkgIterator::OkState pkgCache::PkgIterator::State() const
 207 {
 208    if (Pkg->InstState == pkgCache::State::ReInstReq ||
 209        Pkg->InstState == pkgCache::State::HoldReInstReq)
 210       return NeedsUnpack;
 211
 212    if (Pkg->CurrentState == pkgCache::State::UnPacked ||
 213        Pkg->CurrentState == pkgCache::State::HalfConfigured)
 214       return NeedsConfigure;
 215
 216    if (Pkg->CurrentState == pkgCache::State::UnInstalled ||
 217        Pkg->CurrentState == pkgCache::State::HalfInstalled ||
 218        Pkg->InstState != pkgCache::State::Ok)
 219       return NeedsUnpack;
 220
 221    return NeedsNothing;
 222 }
 223                                                                         /*}}}*/
 224 // DepIterator::IsCritical - Returns true if the dep is important       /*{{{*/
 225 // ---------------------------------------------------------------------
 226 /* Currently critical deps are defined as depends, predepends and
 227    conflicts. */
 228 bool pkgCache::DepIterator::IsCritical()
 229 {
 230    if (Dep->Type == pkgCache::Dep::Conflicts ||
 231        Dep->Type == pkgCache::Dep::Depends ||
 232        Dep->Type == pkgCache::Dep::PreDepends)
 233       return true;
 234    return false;
 235 }
 236                                                                         /*}}}*/
 237 // DepIterator::SmartTargetPkg - Resolve dep target pointers w/provides /*{{{*/
 238 // ---------------------------------------------------------------------
 239 /* This intellegently looks at dep target packages and tries to figure
 240    out which package should be used. This is needed to nicely handle
 241    provide mapping. If the target package has no other providing packages
 242    then it returned. Otherwise the providing list is looked at to
 243    see if there is one one unique providing package if so it is returned.
 244    Otherwise true is returned and the target package is set. The return
 245    result indicates whether the node should be expandable */
 246 bool pkgCache::DepIterator::SmartTargetPkg(PkgIterator &Result)
 247 {
 248    Result = TargetPkg();
 249
 250    // No provides at all
 251    if (Result->ProvidesList == 0)
 252       return false;
 253
 254    // There is the Base package and the providing ones which is at least 2
 255    if (Result->VersionList != 0)
 256       return true;
 257
 258    /* We have to skip over indirect provisions of the package that
 259       owns the dependency. For instance, if libc5-dev depends on the
 260       virtual package libc-dev which is provided by libc5-dev and libc6-dev
 261       we must ignore libc5-dev when considering the provides list. */
 262    PrvIterator PStart = Result.ProvidesList();
 263    for (; PStart.end() != true && PStart.OwnerPkg() == ParentPkg(); PStart++);
 264
 265    // Nothing but indirect self provides
 266    if (PStart.end() == true)
 267       return false;
 268
 269    // Check for single packages in the provides list
 270    PrvIterator P = PStart;
 271    for (; P.end() != true; P++)
 272    {
 273       // Skip over self provides
 274       if (P.OwnerPkg() == ParentPkg())
 275          continue;
 276       if (PStart.OwnerPkg() != P.OwnerPkg())
 277          break;
 278    }
 279
 280    // Check for non dups
 281    if (P.end() != true)
 282       return true;
 283    Result = PStart.OwnerPkg();
 284    return false;
 285 }
 286                                                                         /*}}}*/
 287 // DepIterator::AllTargets - Returns the set of all possible targets    /*{{{*/
 288 // ---------------------------------------------------------------------
 289 /* This is a more usefull version of TargetPkg() that follows versioned
 290    provides. It includes every possible package-version that could satisfy
 291    the dependency. The last item in the list has a 0. The resulting pointer
 292    must be delete [] 'd */
 293 pkgCache::Version **pkgCache::DepIterator::AllTargets()
 294 {
 295    Version **Res = 0;
 296    unsigned long Size =0;
 297    while (1)
 298    {
 299       Version **End = Res;
 300       PkgIterator DPkg = TargetPkg();
 301
 302       // Walk along the actual package providing versions
 303       for (VerIterator I = DPkg.VersionList(); I.end() == false; I++)
 304       {
 305          if (pkgCheckDep(TargetVer(),I.VerStr(),Dep->CompareOp) == false)
 306             continue;
 307
 308          if (Dep->Type == pkgCache::Dep::Conflicts &&
 309              ParentPkg() == I.ParentPkg())
 310             continue;
 311
 312          Size++;
 313          if (Res != 0)
 314             *End++ = I;
 315       }
 316
 317       // Follow all provides
 318       for (PrvIterator I = DPkg.ProvidesList(); I.end() == false; I++)
 319       {
 320          if (pkgCheckDep(TargetVer(),I.ProvideVersion(),Dep->CompareOp) == false)
 321             continue;
 322
 323          if (Dep->Type == pkgCache::Dep::Conflicts &&
 324              ParentPkg() == I.OwnerPkg())
 325             continue;
 326
 327          Size++;
 328          if (Res != 0)
 329             *End++ = I.OwnerVer();
 330       }
 331
 332       // Do it again and write it into the array
 333       if (Res == 0)
 334       {
 335          Res = new Version *[Size+1];
 336          Size = 0;
 337       }
 338       else
 339       {
 340          *End = 0;
 341          break;
 342       }
 343    }
 344
 345    return Res;
 346 }
 347                                                                         /*}}}*/
 348 // DepIterator::CompType - Return a string describing the compare type  /*{{{*/
 349 // ---------------------------------------------------------------------
 350 /* This returns a string representation of the dependency compare
 351    type */
 352 const char *pkgCache::DepIterator::CompType()
 353 {
 354    const char *Ops[] = {"","<=",">=","<",">","=","!="};
 355    if ((unsigned)(Dep->CompareOp & 0xF) < 7)
 356       return Ops[Dep->CompareOp & 0xF];
 357    return "";
 358 }
 359                                                                         /*}}}*/
 360 // DepIterator::DepType - Return a string describing the dep type       /*{{{*/
 361 // ---------------------------------------------------------------------
 362 /* */
 363 const char *pkgCache::DepIterator::DepType()
 364 {
 365    const char *Types[] = {"","Depends","PreDepends","Suggests",
 366                           "Recommends","Conflicts","Replaces"};
 367    if (Dep->Type < 7)
 368       return Types[Dep->Type];
 369    return "";
 370 }
 371                                                                         /*}}}*/
 372 // DepIterator::GlobOr - Compute an OR group                            /*{{{*/
 373 // ---------------------------------------------------------------------
 374 /* This Takes an iterator, iterates past the current dependency grouping
 375    and returns Start and End so that so End is the final element
 376    in the group, if End == Start then D is End++ and End is the
 377    dependency D was pointing to. Use in loops to iterate sensibly. */
 378 void pkgCache::DepIterator::GlobOr(DepIterator &Start,DepIterator &End)
 379 {
 380    // Compute a single dependency element (glob or)
 381    Start = *this;
 382    End = *this;
 383    for (bool LastOR = true; end() == false && LastOR == true;)
 384    {
 385       LastOR = (Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 386       (*this)++;
 387       if (LastOR == true)
 388          End = (*this);
 389    }
 390 }
 391                                                                         /*}}}*/
 392 // VerIterator::CompareVer - Fast version compare for same pkgs         /*{{{*/
 393 // ---------------------------------------------------------------------
 394 /* This just looks over the version list to see if B is listed before A. In
 395    most cases this will return in under 4 checks, ver lists are short. */
 396 int pkgCache::VerIterator::CompareVer(const VerIterator &B) const
 397 {
 398    // Check if they are equal
 399    if (*this == B)
 400       return 0;
 401    if (end() == true)
 402       return -1;
 403    if (B.end() == true)
 404       return 1;
 405
 406    /* Start at A and look for B. If B is found then A > B otherwise
 407       B was before A so A < B */
 408    VerIterator I = *this;
 409    for (;I.end() == false; I++)
 410       if (I == B)
 411          return 1;
 412    return -1;
 413 }
 414                                                                         /*}}}*/
 415 // VerIterator::Downloadable - Checks if the version is downloadable    /*{{{*/
 416 // ---------------------------------------------------------------------
 417 /* */
 418 bool pkgCache::VerIterator::Downloadable() const
 419 {
 420    VerFileIterator Files = FileList();
 421    for (; Files.end() == false; Files++)
 422       if ((Files.File()->Flags & pkgCache::Flag::NotSource) != pkgCache::Flag::NotSource)
 423          return true;
 424    return false;
 425 }
 426                                                                         /*}}}*/
 427 // VerIterator::PriorityType - Return a string describing the priority  /*{{{*/
 428 // ---------------------------------------------------------------------
 429 /* */
 430 const char *pkgCache::VerIterator::PriorityType()
 431 {
 432    const char *Types[] = {"","Important","Required","Standard",
 433                           "Optional","Extra"};
 434    if (Ver->Priority < 6)
 435       return Types[Ver->Priority];
 436    return "";
 437 }
 438                                                                         /*}}}*/
 439 // VerIterator::Automatic - Check if this version is 'automatic'        /*{{{*/
 440 // ---------------------------------------------------------------------
 441 /* This checks to see if any of the versions files are not NotAutomatic.
 442    True if this version is selectable for automatic installation. */
 443 bool pkgCache::VerIterator::Automatic() const
 444 {
 445    VerFileIterator Files = FileList();
 446    for (; Files.end() == false; Files++)
 447       if ((Files.File()->Flags & pkgCache::Flag::NotAutomatic) != pkgCache::Flag::NotAutomatic)
 448          return true;
 449    return false;
 450 }
 451                                                                         /*}}}*/
 452 // VerIterator::NewestFile - Return the newest file version relation    /*{{{*/
 453 // ---------------------------------------------------------------------
 454 /* This looks at the version numbers associated with all of the sources
 455    this version is in and returns the highest.*/
 456 pkgCache::VerFileIterator pkgCache::VerIterator::NewestFile() const
 457 {
 458    VerFileIterator Files = FileList();
 459    VerFileIterator Highest = Files;
 460    for (; Files.end() == false; Files++)
 461    {
 462       if (pkgVersionCompare(Files.File().Version(),Highest.File().Version()) > 0)
 463          Highest = Files;
 464    }
 465
 466    return Highest;
 467 }
 468                                                                         /*}}}*/
 469 // PkgFileIterator::IsOk - Checks if the cache is in sync with the file /*{{{*/
 470 // ---------------------------------------------------------------------
 471 /* This stats the file and compares its stats with the ones that were
 472    stored during generation. Date checks should probably also be
 473    included here. */
 474 bool pkgCache::PkgFileIterator::IsOk()
 475 {
 476    struct stat Buf;
 477    if (stat(FileName(),&Buf) != 0)
 478       return false;
 479
 480    if (Buf.st_size != (signed)File->Size || Buf.st_mtime != File->mtime)
 481       return false;
 482
 483    return true;
 484 }
 485                                                                         /*}}}*/