apt-pkg/pkgcache.cc

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