apt-pkg/pkgcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: pkgcache.cc,v 1.20 1998/12/07 07:26:19 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    MaxVerFileSize = 0;
  63
  64    FileList = 0;
  65    StringList = 0;
  66    memset(HashTable,0,sizeof(HashTable));
  67    memset(Pools,0,sizeof(Pools));
  68 }
  69                                                                         /*}}}*/
  70 // Cache::Header::CheckSizes - Check if the two headers have same *sz   /*{{{*/
  71 // ---------------------------------------------------------------------
  72 /* */
  73 bool pkgCache::Header::CheckSizes(Header &Against) const
  74 {
  75    if (HeaderSz == Against.HeaderSz &&
  76        PackageSz == Against.PackageSz &&
  77        PackageFileSz == Against.PackageFileSz &&
  78        VersionSz == Against.VersionSz &&
  79        DependencySz == Against.DependencySz &&
  80        VerFileSz == Against.VerFileSz &&
  81        ProvidesSz == Against.ProvidesSz)
  82       return true;
  83    return false;
  84 }
  85                                                                         /*}}}*/
  86
  87 // Cache::pkgCache - Constructor                                        /*{{{*/
  88 // ---------------------------------------------------------------------
  89 /* */
  90 pkgCache::pkgCache(MMap &Map) : Map(Map)
  91 {
  92    ReMap();
  93 }
  94                                                                         /*}}}*/
  95 // Cache::ReMap - Reopen the cache file                                 /*{{{*/
  96 // ---------------------------------------------------------------------
  97 /* If the file is already closed then this will open it open it. */
  98 bool pkgCache::ReMap()
  99 {
 100    // Apply the typecasts.
 101    HeaderP = (Header *)Map.Data();
 102    PkgP = (Package *)Map.Data();
 103    VerFileP = (VerFile *)Map.Data();
 104    PkgFileP = (PackageFile *)Map.Data();
 105    VerP = (Version *)Map.Data();
 106    ProvideP = (Provides *)Map.Data();
 107    DepP = (Dependency *)Map.Data();
 108    StringItemP = (StringItem *)Map.Data();
 109    StrP = (char *)Map.Data();
 110
 111    if (Map.Size() == 0)
 112       return false;
 113
 114    // Check the header
 115    Header DefHeader;
 116    if (HeaderP->Signature != DefHeader.Signature ||
 117        HeaderP->Dirty == true)
 118       return _error->Error("The package cache file is corrupted");
 119
 120    if (HeaderP->MajorVersion != DefHeader.MajorVersion ||
 121        HeaderP->MinorVersion != DefHeader.MinorVersion ||
 122        HeaderP->CheckSizes(DefHeader) == false)
 123       return _error->Error("The package cache file is an incompatible version");
 124
 125    return true;
 126 }
 127                                                                         /*}}}*/
 128 // Cache::Hash - Hash a string                                          /*{{{*/
 129 // ---------------------------------------------------------------------
 130 /* This is used to generate the hash entries for the HashTable. With my
 131    package list from bo this function gets 94% table usage on a 512 item
 132    table (480 used items) */
 133 unsigned long pkgCache::sHash(string Str)
 134 {
 135    unsigned long Hash = 0;
 136    for (const char *I = Str.begin(); I != Str.end(); I++)
 137       Hash += *I * ((Str.end() - I + 1));
 138    Header H;
 139    return Hash % _count(H.HashTable);
 140 }
 141
 142 unsigned long pkgCache::sHash(const char *Str)
 143 {
 144    unsigned long Hash = 0;
 145    const char *End = Str + strlen(Str);
 146    for (const char *I = Str; I != End; I++)
 147       Hash += *I * ((End - I + 1));
 148    Header H;
 149    return Hash % _count(H.HashTable);
 150 }
 151
 152                                                                         /*}}}*/
 153 // Cache::FindPkg - Locate a package by name                            /*{{{*/
 154 // ---------------------------------------------------------------------
 155 /* Returns 0 on error, pointer to the package otherwise */
 156 pkgCache::PkgIterator pkgCache::FindPkg(string Name)
 157 {
 158    // Look at the hash bucket
 159    Package *Pkg = PkgP + HeaderP->HashTable[Hash(Name)];
 160    for (; Pkg != PkgP; Pkg = PkgP + Pkg->NextPackage)
 161    {
 162       if (Pkg->Name != 0 && StrP[Pkg->Name] == Name[0] &&
 163           StrP + Pkg->Name == Name)
 164          return PkgIterator(*this,Pkg);
 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 // PkgFileIterator::IsOk - Checks if the cache is in sync with the file /*{{{*/
 440 // ---------------------------------------------------------------------
 441 /* This stats the file and compares its stats with the ones that were
 442    stored during generation. Date checks should probably also be
 443    included here. */
 444 bool pkgCache::PkgFileIterator::IsOk()
 445 {
 446    struct stat Buf;
 447    if (stat(FileName(),&Buf) != 0)
 448       return false;
 449
 450    if (Buf.st_size != (signed)File->Size || Buf.st_mtime != File->mtime)
 451       return false;
 452
 453    return true;
 454 }
 455                                                                         /*}}}*/