apt-pkg/pkgcache.cc

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