prj/cam/src/object/trait.cpp

   1 /*
   2 @Copyright Looking Glass Studios, Inc.
   3 1996,1997,1998,1999,2000 Unpublished Work.
   4 */
   5
   6 // $Header: r:/t2repos/thief2/src/object/trait.cpp,v 1.16 1999/05/19 16:05:39 mahk Exp $
   7 #include <trait_.h>
   8 #include <objquery.h>
   9 #include <traisrch.h>
  10 #include <trcache.h>
  11 #include <osysbase.h>
  12 #include <config.h>
  13 #include <cfgdbg.h>
  14 #include <mprintf.h>
  15 #include <dlistsim.h>
  16 #include <dlisttem.h>
  17 #include <traitln_.h>
  18 #include <relation.h>
  19 #include <linkman.h>
  20 #include <linkbase.h>
  21
  22 // Must be last header
  23 #include <dbmem.h>
  24
  25 IMPLEMENT_UNAGGREGATABLE_SELF_DELETE(cBaseTrait,ITrait);
  26
  27 ////////////////////////////////////////////////////////////
  28 //
  29 // cUninheritedTrait
  30 //
  31
  32 STDMETHODIMP_(BOOL) cUninheritedTrait::PossessedBy(ObjID obj)
  33 {
  34    return IntrinsicTo(obj);
  35 }
  36
  37 ////////////////////////////////////////
  38
  39 STDMETHODIMP_(ObjID) cUninheritedTrait::GetDonor(ObjID )
  40 {
  41    return OBJ_NULL;
  42 }
  43
  44 ////////////////////////////////////////
  45
  46 STDMETHODIMP_(IObjectQuery*) cUninheritedTrait::GetAllDonors(ObjID obj)
  47 {
  48    if (IntrinsicTo(obj))
  49       return CreateSingleObjectQuery(obj);
  50    else
  51       return CreateEmptyObjectQuery();
  52 }
  53
  54 ////////////////////////////////////////
  55
  56 STDMETHODIMP_(IObjectQuery*) cUninheritedTrait::GetAllHeirs(ObjID , eObjConcreteness)
  57 {
  58    return CreateEmptyObjectQuery();
  59 }
  60
  61 //------------------------------------------------------------
  62 // FILTER QUERIES
  63 //
  64
  65 class cTraitFilterQuery : public cFilterObjectQuery
  66 {
  67    ITrait* Trait;
  68 protected:
  69    BOOL Filter(ObjID obj) { return Trait->IntrinsicTo(obj);};
  70
  71 public:
  72    cTraitFilterQuery(IObjectQuery* q, ITrait* trait)
  73       : cFilterObjectQuery(q),Trait(trait)
  74    {
  75       Trait->AddRef();
  76       Skip();
  77    }
  78
  79    ~cTraitFilterQuery() { SafeRelease(Trait);};
  80 };
  81
  82 ////////////////////////////////////////////////////////////
  83 //
  84 // cInheritedTrait
  85 //
  86
  87 STDMETHODIMP_(BOOL) cInheritedTrait::PossessedBy(ObjID obj)
  88 {
  89    if (IntrinsicTo(obj))
  90       return TRUE;
  91    else
  92       return GetDonor(obj) != OBJ_NULL;
  93 }
  94
  95 ////////////////////////////////////////
  96
  97 STDMETHODIMP_(ObjID) cInheritedTrait::GetDonor(ObjID obj)
  98 {
  99    ObjID result = OBJ_NULL;
 100    IObjectQuery* query = GetAllDonors(obj);
 101    if (!query->Done()) result = query->Object();
 102    if (result == obj)
 103    {
 104       query->Next();
 105       result = (query->Done()) ? OBJ_NULL :query->Object();
 106    }
 107    SafeRelease(query);
 108    return result;
 109 }
 110
 111 ////////////////////////////////////////
 112
 113 STDMETHODIMP_(IObjectQuery*) cInheritedTrait::GetAllDonors(ObjID obj)
 114 {
 115    IObjectQuery* inner = TraitMan->Query(obj,kTraitQueryAllDonors);
 116    IObjectQuery* outer = new cTraitFilterQuery(inner,this);
 117    SafeRelease(inner);
 118    return outer;
 119 }
 120
 121 ////////////////////////////////////////
 122
 123 STDMETHODIMP_(IObjectQuery*) cInheritedTrait::GetAllHeirs(ObjID obj , eObjConcreteness which)
 124 {
 125    // @TODO: make this actually stop when another donor overshadows the property
 126    IObjectQuery* inner = TraitMan->Query(obj,kTraitQueryAllDescendents);
 127    IObjectQuery* outer = new cConcretenessFilterQuery(inner,which);
 128    SafeRelease(inner);
 129    return outer;
 130 }
 131
 132
 133 ////////////////////////////////////////////////////////////
 134 //
 135 // Cached trait query
 136 //
 137 // A total rework of the depth first query
 138 //
 139
 140 //
 141 // Helper class for iterating across metaprop links
 142 //
 143
 144 class cChildren : public MetaPropLinks::cIter
 145 {
 146 public:
 147    typedef MetaPropLinks::cIter cParent;
 148    cChildren(const cParent& p)
 149       : cParent(p)
 150    {
 151    }
 152
 153    cChildren() {};
 154
 155    cChildren(ObjID obj)
 156    {
 157       MetaPropLinks* links = GetObjectMetaPropLinks(obj);
 158       if (links)
 159          *this = links->Iter();
 160    }
 161
 162    ObjID Object()
 163    {
 164       return Value().dest;
 165    }
 166
 167 };
 168
 169
 170 //
 171 // Search stack frame
 172 //
 173
 174
 175
 176 struct sStackFrame
 177 {
 178    ObjID node;
 179    BOOL intrinsic;
 180    cChildren children;
 181    ObjID donor; // current opinion of donor
 182    ObjID through; // where we get donor through
 183
 184    sStackFrame(ObjID n = OBJ_NULL,
 185                BOOL i = FALSE,
 186                IObjectQuery* c = NULL,
 187                ObjID d = OBJ_NULL,
 188                ObjID t = OBJ_NULL)
 189       : node(n),
 190         donor(d),
 191         through(t),
 192         intrinsic(i)
 193    {
 194    }
 195
 196
 197 };
 198
 199 //
 200 // Search stack
 201 //
 202
 203 class cSearchStack : public cSimpleStack<sStackFrame>
 204 {
 205
 206 };
 207
 208
 209
 210
 211 class cCachedTraitQuery : public cBaseObjectQuery
 212 {
 213    TraitID ID;
 214    cAutoIPtr<ITrait> Trait;
 215    cSearchStack Stack;
 216    BOOL do_spew;
 217    ObjID YieldMe;
 218    ObjID SkipMe;
 219
 220 #ifndef SHIP
 221 #define trSpew(x) if (do_spew) mprintf x
 222 #else
 223 #define trSpew(x)
 224 #endif
 225
 226    static IDonorCache* Cache;
 227    static ITraitManager* TraitMan;
 228
 229    typedef cBaseObjectQuery cParent;
 230
 231 protected:
 232
 233    //
 234    // Given an object, build a query of successors, using cache where possible.
 235    //
 236    BOOL Expand(sStackFrame* frame)
 237    {
 238       ObjID obj = frame->node;
 239       ObjID donor;
 240       ObjID through;
 241
 242       if (obj == SkipMe)
 243       {
 244          SkipMe = OBJ_NULL;
 245          trSpew(("Expanding past %d\n",obj));
 246       }
 247
 248       YieldMe = OBJ_NULL;
 249
 250       // Look for us in the cache
 251       if (Cache->GetDonor(obj,ID,&donor,&through))
 252       {
 253          trSpew(("Cache: %d has %d through %d\n",obj,donor,through));
 254          if (donor == OBJ_NULL)
 255          {
 256             frame->children = cChildren();
 257             return FALSE;
 258          }
 259
 260          frame->donor = donor;
 261          frame->through = through;
 262
 263          if (frame->donor != SkipMe)
 264          {
 265             YieldMe = donor;
 266             SkipMe = donor;
 267          }
 268
 269          cChildren rest(obj);
 270          // fast forward the donor query past our "through"
 271
 272          for (; !rest.Done(); rest.Next())
 273             if (rest.Object() == through)
 274                break;
 275
 276          frame->children = rest;
 277
 278          return TRUE;
 279       }
 280       else
 281       {
 282          frame->children = cChildren(obj);
 283
 284          return !frame->children.Done();
 285       }
 286    }
 287
 288
 289
 290    //
 291    // Open a stack frame for an object
 292    //
 293    void Open(ObjID obj)
 294    {
 295       sStackFrame frame(obj);
 296       frame.intrinsic = Trait->IntrinsicTo(obj);
 297       trSpew(("Opening %d intrinsic %d\n",obj,frame.intrinsic));
 298
 299       Stack.Push(frame);
 300    }
 301
 302    void PropagateDonor(const sStackFrame& finished)
 303    {
 304       // Now, set the donor of the current top, based on what we already knew.
 305       if (Stack.Top().donor == OBJ_NULL) // if we don't already know
 306       {
 307          ObjID donor = finished.donor;
 308          if (finished.intrinsic)
 309             donor = finished.node;
 310          Stack.Top().donor = donor;
 311          Stack.Top().through = finished.node;
 312       }
 313    }
 314
 315    //
 316    // Unwind the stack to the next upward branch
 317    //
 318
 319    BOOL Contract()
 320    {
 321       if (Stack.Top().node == OBJ_NULL)
 322          return FALSE;
 323
 324       while (Stack.Top().children.Done())
 325       {
 326          sStackFrame& finished = Stack.Top();
 327          // This node is finished.  Cache it.
 328
 329
 330
 331          trSpew(("Closing %d  Donor: %d through %d Intrinsic: %d\n",
 332                  finished.node,
 333                  finished.donor,
 334                  finished.through,
 335                  finished.intrinsic));
 336
 337
 338          Cache->SetDonor(finished.node,ID,finished.donor,finished.through);
 339
 340          Stack.Pop();
 341
 342          // If we hit bottom, we're done.
 343          if (Stack.Top().node == OBJ_NULL)
 344             return FALSE;
 345
 346          // propagate the donor backward
 347          PropagateDonor(finished);
 348          Stack.Top().children.Next();
 349       }
 350       return TRUE;
 351    }
 352
 353    //
 354    // Go to the next object in the search, before filtering out non-donors
 355    //
 356    void NextObj()
 357    {
 358       if (!Expand(&Stack.Top()))
 359       {
 360          if (!Contract())
 361             return;
 362       }
 363
 364       Open(Stack.Top().children.Object());
 365    }
 366
 367    void Skip()
 368    {
 369       while(!Done()
 370             && YieldMe == OBJ_NULL
 371             && !(Stack.Top().intrinsic && Stack.Top().node != SkipMe))
 372       {
 373          trSpew(("Skipping %d\n",Stack.Top().node));
 374
 375          NextObj();
 376       }
 377    }
 378
 379    // @TODO: Release these interfaces one day
 380    void GrabIFaces()
 381    {
 382       if (Cache == NULL)
 383          Cache = AppGetObj(IDonorCache);
 384
 385       if (TraitMan == NULL)
 386          TraitMan = AppGetObj(ITraitManager);
 387    }
 388
 389
 390
 391 public:
 392    cCachedTraitQuery(ObjID obj, ITrait* trait, TraitID id)
 393       : ID(id),
 394         Trait(trait),
 395         do_spew(FALSE),
 396         YieldMe(OBJ_NULL),
 397         SkipMe(OBJ_NULL)
 398    {
 399 #ifndef SHIP
 400       do_spew = config_is_defined("trait_cache_spew");
 401       trSpew(("Start %s search on %d\n",Trait->Describe()->name,obj));
 402 #endif
 403       Trait->AddRef();
 404
 405       GrabIFaces();
 406
 407       Open(obj);
 408       //      NextObj();
 409       Skip();
 410    };
 411
 412    ~cCachedTraitQuery()
 413    {
 414       while (Stack.Top().node != OBJ_NULL)
 415       {
 416          sStackFrame frame = Stack.Pop();
 417
 418          // if we got valid cache data, store it.
 419          trSpew(("Unwinding %d.  ",frame.node));
 420          if (frame.donor != OBJ_NULL) // valid donor data
 421          {
 422             trSpew(("Caching donor %d through %d",frame.donor,frame.through));
 423             Cache->SetDonor(frame.node,ID,frame.donor,frame.through);
 424          }
 425          PropagateDonor(frame);
 426          trSpew(("\n"));
 427       }
 428
 429       trSpew(("End search.\n"));
 430    };
 431
 432
 433    STDMETHOD(Next)()
 434    {
 435       NextObj();
 436       Skip();
 437       return S_OK;
 438    }
 439
 440    STDMETHOD_(BOOL,Done)() { return Stack.Top().node == OBJ_NULL;};
 441    STDMETHOD_(ObjID,Object)()
 442    {
 443       if (YieldMe != OBJ_NULL)
 444          return YieldMe;
 445       return Stack.Top().node;
 446    };
 447
 448 };
 449 #undef trSpew
 450
 451 ITraitManager* cCachedTraitQuery::TraitMan = NULL;
 452 IDonorCache* cCachedTraitQuery::Cache    = NULL;
 453
 454
 455
 456 ////////////////////////////////////////////////////////////
 457 //
 458 // cCachedTrait
 459 //
 460 //
 461
 462
 463 cCachedTrait::cCachedTrait(const sTraitDesc& desc, const sTraitPredicate& pred)
 464    : cInheritedTrait(desc,pred),
 465    pCache(AppGetObj(IDonorCache))
 466 {
 467    ID = pCache->NewTrait(&Desc);
 468
 469    ConfigSpew("trait_id_spew",("Trait %s has id %d\n",desc.name,ID));
 470
 471
 472 }
 473
 474 cCachedTrait::~cCachedTrait()
 475 {
 476    SafeRelease(pCache);
 477 }
 478
 479 //
 480 // Go ahead and do as much of the first level of the search as you
 481 // can, using the cache.  This is particularly useful in the case
 482 // of a concrete that is not in the cache
 483 //
 484 // TRUE means the out param is the donor you're looking for
 485 //
 486 // FALSE means donor is the first donor for search
 487 //
 488
 489 BOOL cCachedTrait::get_cached_donor(ObjID obj, ObjID* donor)
 490 {
 491    BOOL retval = FALSE;
 492
 493    MetaPropLinks* links = GetObjectMetaPropLinks(obj);
 494    if (!links)
 495       return FALSE;
 496
 497    MetaPropLinks::cIter iter;
 498    for (iter = links->Iter(); !iter.Done(); iter.Next())
 499    {
 500       ObjID qobj = iter.Value().dest;
 501
 502       ObjID cachedonor;
 503       ObjID through;
 504
 505       if (IntrinsicTo(qobj))
 506       {
 507          pCache->SetDonor(obj,ID,qobj,qobj);
 508          *donor = qobj;
 509          return TRUE;
 510       }
 511
 512       if (pCache->GetDonor(qobj,ID,&cachedonor,&through))
 513       {
 514          if (cachedonor == OBJ_NULL)
 515             continue;
 516          else
 517          {
 518             *donor = cachedonor;
 519             pCache->SetDonor(obj,ID,*donor,qobj);
 520             return TRUE;
 521          }
 522       }
 523
 524       *donor = qobj;
 525       return FALSE;
 526    }
 527    // we got no donors
 528    *donor = OBJ_NULL;
 529    pCache->SetDonor(obj,ID,OBJ_NULL,OBJ_NULL);
 530    return TRUE;
 531 }
 532
 533 STDMETHODIMP_(ObjID) cCachedTrait::GetDonor(ObjID obj)
 534 {
 535    // check the cache first
 536    ObjID cachedonor,through;
 537    if (pCache->GetDonor(obj,ID,&cachedonor,&through))
 538       return cachedonor;
 539
 540    // Now check the first level
 541    ObjID donor;
 542    if (get_cached_donor(obj,&donor))
 543       return donor;
 544
 545    // If that fails, do the search
 546    ObjID result = OBJ_NULL;
 547
 548    IObjectQuery* query = GetAllDonors(obj);
 549    if (!query->Done()) result = query->Object();
 550    if (result == obj)
 551    {
 552       query->Next();
 553       result = (query->Done()) ? OBJ_NULL :query->Object();
 554    }
 555    SafeRelease(query);
 556    return result;
 557 }
 558
 559 STDMETHODIMP_(IObjectQuery*) cCachedTrait::GetAllDonors(ObjID obj)
 560 {
 561    return new cCachedTraitQuery(obj,this,ID);
 562 }
 563
 564 STDMETHODIMP cCachedTrait::Touch(ObjID obj)
 565 {
 566    if (obj == OBJ_NULL)
 567       pCache->Flush(FLUSH_ALL_OBJS,ID);
 568    else
 569    {
 570       IObjectQuery* objs = TraitMan->Query(obj,kTraitQueryAllDescendents);
 571       pCache->FlushObjSet(objs,ID);
 572       SafeRelease(objs);
 573    }
 574
 575    return S_OK;
 576 }
 577
 578
 579
 580
 581
 582
 583