rdf/base/src/nsInMemoryDataSource.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   6  *
   7  *
   8  * This Original Code has been modified by IBM Corporation.
   9  * Modifications made by IBM described herein are
  10  * Copyright (c) International Business Machines
  11  * Corporation, 2000
  12  *
  13  * Modifications to Mozilla code or documentation
  14  * identified per MPL Section 3.3
  15  *
  16  * Date         Modified by     Description of modification
  17  * 03/27/2000   IBM Corp.       Added PR_CALLBACK for Optlink
  18  *                               use in OS2
  19  */
  20
  21 /*
  22
  23   Implementation for an in-memory RDF data store.
  24
  25   TO DO
  26
  27   1) Instrument this code to gather space and time performance
  28      characteristics.
  29
  30   2) Optimize lookups for datasources which have a small number
  31      of properties + fanning out to a large number of targets.
  32
  33   3) Complete implementation of thread-safety; specifically, make
  34      assertions be reference counted objects (so that a cursor can
  35      still refer to an assertion that gets removed from the graph).
  36
  37  */
  38
  39 #include "nsAgg.h"
  40 #include "nsCOMPtr.h"
  41 #include "nscore.h"
  42 #include "nsIOutputStream.h"
  43 #include "nsIRDFDataSource.h"
  44 #include "nsIRDFLiteral.h"
  45 #include "nsIRDFNode.h"
  46 #include "nsIRDFObserver.h"
  47 #include "nsIRDFInMemoryDataSource.h"
  48 #include "nsIRDFPropagatableDataSource.h"
  49 #include "nsIRDFPurgeableDataSource.h"
  50 #include "nsIRDFService.h"
  51 #include "nsIServiceManager.h"
  52 #include "nsISupportsArray.h"
  53 #include "nsCOMArray.h"
  54 #include "nsEnumeratorUtils.h"
  55 #include "nsTArray.h"
  56 #include "nsCRT.h"
  57 #include "nsRDFCID.h"
  58 #include "nsRDFBaseDataSources.h"
  59 #include "nsString.h"
  60 #include "nsReadableUtils.h"
  61 #include "nsXPIDLString.h"
  62 #include "nsFixedSizeAllocator.h"
  63 #include "rdfutil.h"
  64 #include "pldhash.h"
  65 #include "plstr.h"
  66 #include "prlog.h"
  67 #include "rdf.h"
  68
  69 #include "rdfIDataSource.h"
  70 #include "rdfITripleVisitor.h"
  71
  72 #ifdef PR_LOGGING
  73 static PRLogModuleInfo* gLog = nullptr;
  74 #endif
  75
  76
  77 // This struct is used as the slot value in the forward and reverse
  78 // arcs hash tables.
  79 //
  80 // Assertion objects are reference counted, because each Assertion's
  81 // ownership is shared between the datasource and any enumerators that
  82 // are currently iterating over the datasource.
  83 //
  84 class Assertion
  85 {
  86 public:
  87     static Assertion*
  88     Create(nsFixedSizeAllocator& aAllocator,
  89            nsIRDFResource* aSource,
  90            nsIRDFResource* aProperty,
  91            nsIRDFNode* aTarget,
  92            bool aTruthValue) {
  93         void* place = aAllocator.Alloc(sizeof(Assertion));
  94         return place
  95             ? ::new (place) Assertion(aSource, aProperty, aTarget, aTruthValue)
  96             : nullptr; }
  97     static Assertion*
  98     Create(nsFixedSizeAllocator& aAllocator, nsIRDFResource* aSource) {
  99         void* place = aAllocator.Alloc(sizeof(Assertion));
 100         return place
 101             ? ::new (place) Assertion(aSource)
 102             : nullptr; }
 103
 104     static void
 105     Destroy(nsFixedSizeAllocator& aAllocator, Assertion* aAssertion) {
 106         if (aAssertion->mHashEntry && aAssertion->u.hash.mPropertyHash) {
 107             PL_DHashTableEnumerate(aAssertion->u.hash.mPropertyHash,
 108                 DeletePropertyHashEntry, &aAllocator);
 109             PL_DHashTableDestroy(aAssertion->u.hash.mPropertyHash);
 110             aAssertion->u.hash.mPropertyHash = nullptr;
 111         }
 112         aAssertion->~Assertion();
 113         aAllocator.Free(aAssertion, sizeof(*aAssertion)); }
 114
 115     static PLDHashOperator
 116     DeletePropertyHashEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 117                            PRUint32 aNumber, void* aArg);
 118
 119     Assertion(nsIRDFResource* aSource,      // normal assertion
 120               nsIRDFResource* aProperty,
 121               nsIRDFNode* aTarget,
 122               bool aTruthValue);
 123     Assertion(nsIRDFResource* aSource);     // PLDHashTable assertion variant
 124
 125     ~Assertion();
 126
 127     void AddRef() {
 128         if (mRefCnt == PR_UINT16_MAX) {
 129             NS_WARNING("refcount overflow, leaking Assertion");
 130             return;
 131         }
 132         ++mRefCnt;
 133     }
 134
 135     void Release(nsFixedSizeAllocator& aAllocator) {
 136         if (mRefCnt == PR_UINT16_MAX) {
 137             NS_WARNING("refcount overflow, leaking Assertion");
 138             return;
 139         }
 140         if (--mRefCnt == 0)
 141             Destroy(aAllocator, this);
 142     }
 143
 144     // For nsIRDFPurgeableDataSource
 145     inline  void    Mark()      { u.as.mMarked = true; }
 146     inline  bool    IsMarked()  { return u.as.mMarked; }
 147     inline  void    Unmark()    { u.as.mMarked = false; }
 148
 149     // public for now, because I'm too lazy to go thru and clean this up.
 150
 151     // These are shared between hash/as (see the union below)
 152     nsIRDFResource*         mSource;
 153     Assertion*              mNext;
 154
 155     union
 156     {
 157         struct hash
 158         {
 159             PLDHashTable*   mPropertyHash;
 160         } hash;
 161         struct as
 162         {
 163             nsIRDFResource* mProperty;
 164             nsIRDFNode*     mTarget;
 165             Assertion*      mInvNext;
 166             // make sure bool are final elements
 167             bool            mTruthValue;
 168             bool            mMarked;
 169         } as;
 170     } u;
 171
 172     // also shared between hash/as (see the union above)
 173     // but placed after union definition to ensure that
 174     // all 32-bit entries are long aligned
 175     PRUint16                    mRefCnt;
 176     bool                        mHashEntry;
 177
 178 private:
 179     // Hide so that only Create() and Destroy() can be used to
 180     // allocate and deallocate from the heap
 181     static void* operator new(size_t) CPP_THROW_NEW { return 0; }
 182     static void operator delete(void*, size_t) {}
 183 };
 184
 185
 186 struct Entry {
 187     PLDHashEntryHdr mHdr;
 188     nsIRDFNode*     mNode;
 189     Assertion*      mAssertions;
 190 };
 191
 192
 193 Assertion::Assertion(nsIRDFResource* aSource)
 194     : mSource(aSource),
 195       mNext(nullptr),
 196       mRefCnt(0),
 197       mHashEntry(true)
 198 {
 199     MOZ_COUNT_CTOR(RDF_Assertion);
 200
 201     NS_ADDREF(mSource);
 202
 203     u.hash.mPropertyHash = PL_NewDHashTable(PL_DHashGetStubOps(),
 204                       nullptr, sizeof(Entry), PL_DHASH_MIN_SIZE);
 205 }
 206
 207 Assertion::Assertion(nsIRDFResource* aSource,
 208                      nsIRDFResource* aProperty,
 209                      nsIRDFNode* aTarget,
 210                      bool aTruthValue)
 211     : mSource(aSource),
 212       mNext(nullptr),
 213       mRefCnt(0),
 214       mHashEntry(false)
 215 {
 216     MOZ_COUNT_CTOR(RDF_Assertion);
 217
 218     u.as.mProperty = aProperty;
 219     u.as.mTarget = aTarget;
 220
 221     NS_ADDREF(mSource);
 222     NS_ADDREF(u.as.mProperty);
 223     NS_ADDREF(u.as.mTarget);
 224
 225     u.as.mInvNext = nullptr;
 226     u.as.mTruthValue = aTruthValue;
 227     u.as.mMarked = false;
 228 }
 229
 230 Assertion::~Assertion()
 231 {
 232     MOZ_COUNT_DTOR(RDF_Assertion);
 233 #ifdef DEBUG_REFS
 234     --gInstanceCount;
 235     fprintf(stdout, "%d - RDF: Assertion\n", gInstanceCount);
 236 #endif
 237
 238     NS_RELEASE(mSource);
 239     if (!mHashEntry)
 240     {
 241         NS_RELEASE(u.as.mProperty);
 242         NS_RELEASE(u.as.mTarget);
 243     }
 244 }
 245
 246 PLDHashOperator
 247 Assertion::DeletePropertyHashEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 248                                            PRUint32 aNumber, void* aArg)
 249 {
 250     Entry* entry = reinterpret_cast<Entry*>(aHdr);
 251     nsFixedSizeAllocator* allocator = static_cast<nsFixedSizeAllocator*>(aArg);
 252
 253     Assertion* as = entry->mAssertions;
 254     while (as) {
 255         Assertion* doomed = as;
 256         as = as->mNext;
 257
 258         // Unlink, and release the datasource's reference.
 259         doomed->mNext = doomed->u.as.mInvNext = nullptr;
 260         doomed->Release(*allocator);
 261     }
 262     return PL_DHASH_NEXT;
 263 }
 264
 265
 266
 267 ////////////////////////////////////////////////////////////////////////
 268 // InMemoryDataSource
 269 class InMemoryArcsEnumeratorImpl;
 270 class InMemoryAssertionEnumeratorImpl;
 271 class InMemoryResourceEnumeratorImpl;
 272
 273 class InMemoryDataSource : public nsIRDFDataSource,
 274                            public nsIRDFInMemoryDataSource,
 275                            public nsIRDFPropagatableDataSource,
 276                            public nsIRDFPurgeableDataSource,
 277                            public rdfIDataSource
 278 {
 279 protected:
 280     nsFixedSizeAllocator mAllocator;
 281
 282     // These hash tables are keyed on pointers to nsIRDFResource
 283     // objects (the nsIRDFService ensures that there is only ever one
 284     // nsIRDFResource object per unique URI). The value of an entry is
 285     // an Assertion struct, which is a linked list of (subject
 286     // predicate object) triples.
 287     PLDHashTable mForwardArcs;
 288     PLDHashTable mReverseArcs;
 289
 290     nsCOMArray<nsIRDFObserver> mObservers;
 291     PRUint32                   mNumObservers;
 292
 293     // VisitFoo needs to block writes, [Un]Assert only allowed
 294     // during mReadCount == 0
 295     PRUint32 mReadCount;
 296
 297     static PLDHashOperator
 298     DeleteForwardArcsEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 299                            PRUint32 aNumber, void* aArg);
 300
 301     static PLDHashOperator
 302     ResourceEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 303                        PRUint32 aNumber, void* aArg);
 304
 305     friend class InMemoryArcsEnumeratorImpl;
 306     friend class InMemoryAssertionEnumeratorImpl;
 307     friend class InMemoryResourceEnumeratorImpl; // b/c it needs to enumerate mForwardArcs
 308
 309     // Thread-safe writer implementation methods.
 310     nsresult
 311     LockedAssert(nsIRDFResource* source,
 312                  nsIRDFResource* property,
 313                  nsIRDFNode* target,
 314                  bool tv);
 315
 316     nsresult
 317     LockedUnassert(nsIRDFResource* source,
 318                    nsIRDFResource* property,
 319                    nsIRDFNode* target);
 320
 321     InMemoryDataSource(nsISupports* aOuter);
 322     virtual ~InMemoryDataSource();
 323     nsresult Init();
 324
 325     friend nsresult
 326     NS_NewRDFInMemoryDataSource(nsISupports* aOuter, const nsIID& aIID, void** aResult);
 327
 328 public:
 329     NS_DECL_CYCLE_COLLECTING_AGGREGATED
 330     NS_DECL_AGGREGATED_CYCLE_COLLECTION_CLASS(InMemoryDataSource)
 331
 332     // nsIRDFDataSource methods
 333     NS_DECL_NSIRDFDATASOURCE
 334
 335     // nsIRDFInMemoryDataSource methods
 336     NS_DECL_NSIRDFINMEMORYDATASOURCE
 337
 338     // nsIRDFPropagatableDataSource methods
 339     NS_DECL_NSIRDFPROPAGATABLEDATASOURCE
 340
 341     // nsIRDFPurgeableDataSource methods
 342     NS_DECL_NSIRDFPURGEABLEDATASOURCE
 343
 344     // rdfIDataSource methods
 345     NS_DECL_RDFIDATASOURCE
 346
 347 protected:
 348     static PLDHashOperator
 349     SweepForwardArcsEntries(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 350                             PRUint32 aNumber, void* aArg);
 351
 352 public:
 353     // Implementation methods
 354     Assertion*
 355     GetForwardArcs(nsIRDFResource* u) {
 356         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mForwardArcs, u, PL_DHASH_LOOKUP);
 357         return PL_DHASH_ENTRY_IS_BUSY(hdr)
 358             ? reinterpret_cast<Entry*>(hdr)->mAssertions
 359             : nullptr; }
 360
 361     Assertion*
 362     GetReverseArcs(nsIRDFNode* v) {
 363         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mReverseArcs, v, PL_DHASH_LOOKUP);
 364         return PL_DHASH_ENTRY_IS_BUSY(hdr)
 365             ? reinterpret_cast<Entry*>(hdr)->mAssertions
 366             : nullptr; }
 367
 368     void
 369     SetForwardArcs(nsIRDFResource* u, Assertion* as) {
 370         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mForwardArcs, u,
 371                                                     as ? PL_DHASH_ADD : PL_DHASH_REMOVE);
 372         if (as && hdr) {
 373             Entry* entry = reinterpret_cast<Entry*>(hdr);
 374             entry->mNode = u;
 375             entry->mAssertions = as;
 376         } }
 377
 378     void
 379     SetReverseArcs(nsIRDFNode* v, Assertion* as) {
 380         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mReverseArcs, v,
 381                                                     as ? PL_DHASH_ADD : PL_DHASH_REMOVE);
 382         if (as && hdr) {
 383             Entry* entry = reinterpret_cast<Entry*>(hdr);
 384             entry->mNode = v;
 385             entry->mAssertions = as;
 386         } }
 387
 388 #ifdef PR_LOGGING
 389     void
 390     LogOperation(const char* aOperation,
 391                  nsIRDFResource* asource,
 392                  nsIRDFResource* aProperty,
 393                  nsIRDFNode* aTarget,
 394                  bool aTruthValue = true);
 395 #endif
 396
 397     bool    mPropagateChanges;
 398 };
 399
 400 //----------------------------------------------------------------------
 401 //
 402 // InMemoryAssertionEnumeratorImpl
 403 //
 404
 405 /**
 406  * InMemoryAssertionEnumeratorImpl
 407  */
 408 class InMemoryAssertionEnumeratorImpl : public nsISimpleEnumerator
 409 {
 410 private:
 411     InMemoryDataSource* mDataSource;
 412     nsIRDFResource* mSource;
 413     nsIRDFResource* mProperty;
 414     nsIRDFNode*     mTarget;
 415     nsIRDFNode*     mValue;
 416     bool            mTruthValue;
 417     Assertion*      mNextAssertion;
 418     nsCOMPtr<nsISupportsArray> mHashArcs;
 419
 420     // Hide so that only Create() and Destroy() can be used to
 421     // allocate and deallocate from the heap
 422     static void* operator new(size_t) CPP_THROW_NEW { return 0; }
 423     static void operator delete(void*, size_t) {}
 424
 425     InMemoryAssertionEnumeratorImpl(InMemoryDataSource* aDataSource,
 426                                     nsIRDFResource* aSource,
 427                                     nsIRDFResource* aProperty,
 428                                     nsIRDFNode* aTarget,
 429                                     bool aTruthValue);
 430
 431     virtual ~InMemoryAssertionEnumeratorImpl();
 432
 433 public:
 434     static InMemoryAssertionEnumeratorImpl*
 435     Create(InMemoryDataSource* aDataSource,
 436            nsIRDFResource* aSource,
 437            nsIRDFResource* aProperty,
 438            nsIRDFNode* aTarget,
 439            bool aTruthValue) {
 440         void* place = aDataSource->mAllocator.Alloc(sizeof(InMemoryAssertionEnumeratorImpl));
 441         return place
 442             ? ::new (place) InMemoryAssertionEnumeratorImpl(aDataSource,
 443                                                             aSource, aProperty, aTarget,
 444                                                             aTruthValue)
 445             : nullptr; }
 446
 447     static void
 448     Destroy(InMemoryAssertionEnumeratorImpl* aEnumerator) {
 449         // Keep the datasource alive for the duration of the stack
 450         // frame so its allocator stays valid.
 451         nsCOMPtr<nsIRDFDataSource> kungFuDeathGrip = aEnumerator->mDataSource;
 452
 453         // Grab the pool from the datasource; since we keep the
 454         // datasource alive, this has to be safe.
 455         nsFixedSizeAllocator& pool = aEnumerator->mDataSource->mAllocator;
 456         aEnumerator->~InMemoryAssertionEnumeratorImpl();
 457         pool.Free(aEnumerator, sizeof(*aEnumerator)); }
 458
 459     // nsISupports interface
 460     NS_DECL_ISUPPORTS
 461
 462     // nsISimpleEnumerator interface
 463     NS_DECL_NSISIMPLEENUMERATOR
 464 };
 465
 466 ////////////////////////////////////////////////////////////////////////
 467
 468
 469 InMemoryAssertionEnumeratorImpl::InMemoryAssertionEnumeratorImpl(
 470                  InMemoryDataSource* aDataSource,
 471                  nsIRDFResource* aSource,
 472                  nsIRDFResource* aProperty,
 473                  nsIRDFNode* aTarget,
 474                  bool aTruthValue)
 475     : mDataSource(aDataSource),
 476       mSource(aSource),
 477       mProperty(aProperty),
 478       mTarget(aTarget),
 479       mValue(nullptr),
 480       mTruthValue(aTruthValue),
 481       mNextAssertion(nullptr)
 482 {
 483     NS_ADDREF(mDataSource);
 484     NS_IF_ADDREF(mSource);
 485     NS_ADDREF(mProperty);
 486     NS_IF_ADDREF(mTarget);
 487
 488     if (mSource) {
 489         mNextAssertion = mDataSource->GetForwardArcs(mSource);
 490
 491         if (mNextAssertion && mNextAssertion->mHashEntry) {
 492             // its our magical HASH_ENTRY forward hash for assertions
 493             PLDHashEntryHdr* hdr = PL_DHashTableOperate(mNextAssertion->u.hash.mPropertyHash,
 494                 aProperty, PL_DHASH_LOOKUP);
 495             mNextAssertion = PL_DHASH_ENTRY_IS_BUSY(hdr)
 496                 ? reinterpret_cast<Entry*>(hdr)->mAssertions
 497                 : nullptr;
 498         }
 499     }
 500     else {
 501         mNextAssertion = mDataSource->GetReverseArcs(mTarget);
 502     }
 503
 504     // Add an owning reference from the enumerator
 505     if (mNextAssertion)
 506         mNextAssertion->AddRef();
 507 }
 508
 509 InMemoryAssertionEnumeratorImpl::~InMemoryAssertionEnumeratorImpl()
 510 {
 511 #ifdef DEBUG_REFS
 512     --gInstanceCount;
 513     fprintf(stdout, "%d - RDF: InMemoryAssertionEnumeratorImpl\n", gInstanceCount);
 514 #endif
 515
 516     if (mNextAssertion)
 517         mNextAssertion->Release(mDataSource->mAllocator);
 518
 519     NS_IF_RELEASE(mDataSource);
 520     NS_IF_RELEASE(mSource);
 521     NS_IF_RELEASE(mProperty);
 522     NS_IF_RELEASE(mTarget);
 523     NS_IF_RELEASE(mValue);
 524 }
 525
 526 NS_IMPL_ADDREF(InMemoryAssertionEnumeratorImpl)
 527 NS_IMPL_RELEASE_WITH_DESTROY(InMemoryAssertionEnumeratorImpl, Destroy(this))
 528 NS_IMPL_QUERY_INTERFACE1(InMemoryAssertionEnumeratorImpl, nsISimpleEnumerator)
 529
 530 NS_IMETHODIMP
 531 InMemoryAssertionEnumeratorImpl::HasMoreElements(bool* aResult)
 532 {
 533     if (mValue) {
 534         *aResult = true;
 535         return NS_OK;
 536     }
 537
 538     while (mNextAssertion) {
 539         bool foundIt = false;
 540         if ((mProperty == mNextAssertion->u.as.mProperty) &&
 541             (mTruthValue == mNextAssertion->u.as.mTruthValue)) {
 542             if (mSource) {
 543                 mValue = mNextAssertion->u.as.mTarget;
 544                 NS_ADDREF(mValue);
 545             }
 546             else {
 547                 mValue = mNextAssertion->mSource;
 548                 NS_ADDREF(mValue);
 549             }
 550             foundIt = true;
 551         }
 552
 553         // Remember the last assertion we were holding on to
 554         Assertion* as = mNextAssertion;
 555
 556         // iterate
 557         mNextAssertion = (mSource) ? mNextAssertion->mNext : mNextAssertion->u.as.mInvNext;
 558
 559         // grab an owning reference from the enumerator to the next assertion
 560         if (mNextAssertion)
 561             mNextAssertion->AddRef();
 562
 563         // ...and release the reference from the enumerator to the old one.
 564         as->Release(mDataSource->mAllocator);
 565
 566         if (foundIt) {
 567             *aResult = true;
 568             return NS_OK;
 569         }
 570     }
 571
 572     *aResult = false;
 573     return NS_OK;
 574 }
 575
 576
 577 NS_IMETHODIMP
 578 InMemoryAssertionEnumeratorImpl::GetNext(nsISupports** aResult)
 579 {
 580     nsresult rv;
 581
 582     bool hasMore;
 583     rv = HasMoreElements(&hasMore);
 584     if (NS_FAILED(rv)) return rv;
 585
 586     if (! hasMore)
 587         return NS_ERROR_UNEXPECTED;
 588
 589     // Don't AddRef: we "transfer" ownership to the caller
 590     *aResult = mValue;
 591     mValue = nullptr;
 592
 593     return NS_OK;
 594 }
 595
 596 ////////////////////////////////////////////////////////////////////////
 597 //
 598
 599 /**
 600  * This class is a little bit bizarre in that it implements both the
 601  * <tt>nsIRDFArcsOutCursor</tt> and <tt>nsIRDFArcsInCursor</tt> interfaces.
 602  * Because the structure of the in-memory graph is pretty flexible, it's
 603  * fairly easy to parameterize this class. The only funky thing to watch
 604  * out for is the multiple inheritance clashes.
 605  */
 606
 607 class InMemoryArcsEnumeratorImpl : public nsISimpleEnumerator
 608 {
 609 private:
 610     // Hide so that only Create() and Destroy() can be used to
 611     // allocate and deallocate from the heap
 612     static void* operator new(size_t) CPP_THROW_NEW { return 0; }
 613     static void operator delete(void*, size_t) {}
 614
 615     InMemoryDataSource* mDataSource;
 616     nsIRDFResource*     mSource;
 617     nsIRDFNode*         mTarget;
 618     nsAutoTArray<nsCOMPtr<nsIRDFResource>, 8> mAlreadyReturned;
 619     nsIRDFResource*     mCurrent;
 620     Assertion*          mAssertion;
 621     nsCOMPtr<nsISupportsArray> mHashArcs;
 622
 623     InMemoryArcsEnumeratorImpl(InMemoryDataSource* aDataSource,
 624                                nsIRDFResource* aSource,
 625                                nsIRDFNode* aTarget);
 626
 627     virtual ~InMemoryArcsEnumeratorImpl();
 628
 629     static PLDHashOperator
 630     ArcEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 631                        PRUint32 aNumber, void* aArg);
 632
 633 public:
 634     // nsISupports interface
 635     NS_DECL_ISUPPORTS
 636
 637     // nsISimpleEnumerator interface
 638     NS_DECL_NSISIMPLEENUMERATOR
 639
 640     static InMemoryArcsEnumeratorImpl*
 641     Create(InMemoryDataSource* aDataSource,
 642            nsIRDFResource* aSource,
 643            nsIRDFNode* aTarget) {
 644         void* place = aDataSource->mAllocator.Alloc(sizeof(InMemoryArcsEnumeratorImpl));
 645         return place
 646             ? ::new (place) InMemoryArcsEnumeratorImpl(aDataSource, aSource, aTarget)
 647             : nullptr; }
 648
 649     static void
 650     Destroy(InMemoryArcsEnumeratorImpl* aEnumerator) {
 651         // Keep the datasource alive for the duration of the stack
 652         // frame so its allocator stays valid.
 653         nsCOMPtr<nsIRDFDataSource> kungFuDeathGrip = aEnumerator->mDataSource;
 654
 655         // Grab the pool from the datasource; since we keep the
 656         // datasource alive, this has to be safe.
 657         nsFixedSizeAllocator& pool = aEnumerator->mDataSource->mAllocator;
 658         aEnumerator->~InMemoryArcsEnumeratorImpl();
 659         pool.Free(aEnumerator, sizeof(*aEnumerator)); }
 660 };
 661
 662
 663 PLDHashOperator
 664 InMemoryArcsEnumeratorImpl::ArcEnumerator(PLDHashTable* aTable,
 665                                        PLDHashEntryHdr* aHdr,
 666                                        PRUint32 aNumber, void* aArg)
 667 {
 668     Entry* entry = reinterpret_cast<Entry*>(aHdr);
 669     nsISupportsArray* resources = static_cast<nsISupportsArray*>(aArg);
 670
 671     resources->AppendElement(entry->mNode);
 672     return PL_DHASH_NEXT;
 673 }
 674
 675
 676 InMemoryArcsEnumeratorImpl::InMemoryArcsEnumeratorImpl(InMemoryDataSource* aDataSource,
 677                                                        nsIRDFResource* aSource,
 678                                                        nsIRDFNode* aTarget)
 679     : mDataSource(aDataSource),
 680       mSource(aSource),
 681       mTarget(aTarget),
 682       mCurrent(nullptr)
 683 {
 684     NS_ADDREF(mDataSource);
 685     NS_IF_ADDREF(mSource);
 686     NS_IF_ADDREF(mTarget);
 687
 688     if (mSource) {
 689         // cast okay because it's a closed system
 690         mAssertion = mDataSource->GetForwardArcs(mSource);
 691
 692         if (mAssertion && mAssertion->mHashEntry) {
 693             // its our magical HASH_ENTRY forward hash for assertions
 694             nsresult rv = NS_NewISupportsArray(getter_AddRefs(mHashArcs));
 695             if (NS_SUCCEEDED(rv)) {
 696                 PL_DHashTableEnumerate(mAssertion->u.hash.mPropertyHash,
 697                     ArcEnumerator, mHashArcs.get());
 698             }
 699             mAssertion = nullptr;
 700         }
 701     }
 702     else {
 703         mAssertion = mDataSource->GetReverseArcs(mTarget);
 704     }
 705 }
 706
 707 InMemoryArcsEnumeratorImpl::~InMemoryArcsEnumeratorImpl()
 708 {
 709 #ifdef DEBUG_REFS
 710     --gInstanceCount;
 711     fprintf(stdout, "%d - RDF: InMemoryArcsEnumeratorImpl\n", gInstanceCount);
 712 #endif
 713
 714     NS_RELEASE(mDataSource);
 715     NS_IF_RELEASE(mSource);
 716     NS_IF_RELEASE(mTarget);
 717     NS_IF_RELEASE(mCurrent);
 718 }
 719
 720 NS_IMPL_ADDREF(InMemoryArcsEnumeratorImpl)
 721 NS_IMPL_RELEASE_WITH_DESTROY(InMemoryArcsEnumeratorImpl, Destroy(this))
 722 NS_IMPL_QUERY_INTERFACE1(InMemoryArcsEnumeratorImpl, nsISimpleEnumerator)
 723
 724 NS_IMETHODIMP
 725 InMemoryArcsEnumeratorImpl::HasMoreElements(bool* aResult)
 726 {
 727     NS_PRECONDITION(aResult != nullptr, "null ptr");
 728     if (! aResult)
 729         return NS_ERROR_NULL_POINTER;
 730
 731     if (mCurrent) {
 732         *aResult = true;
 733         return NS_OK;
 734     }
 735
 736     if (mHashArcs) {
 737         PRUint32    itemCount;
 738         nsresult    rv;
 739         if (NS_FAILED(rv = mHashArcs->Count(&itemCount)))   return(rv);
 740         if (itemCount > 0) {
 741             --itemCount;
 742             mCurrent = static_cast<nsIRDFResource *>
 743                                   (mHashArcs->ElementAt(itemCount));
 744             mHashArcs->RemoveElementAt(itemCount);
 745             *aResult = true;
 746             return NS_OK;
 747         }
 748     }
 749     else
 750         while (mAssertion) {
 751             nsIRDFResource* next = mAssertion->u.as.mProperty;
 752
 753             // "next" is the property arc we are tentatively going to return
 754             // in a subsequent GetNext() call.  It is important to do two
 755             // things, however, before that can happen:
 756             //   1) Make sure it's not an arc we've already returned.
 757             //   2) Make sure that |mAssertion| is not left pointing to
 758             //      another assertion that has the same property as this one.
 759             // The first is a practical concern; the second a defense against
 760             // an obscure crash and other erratic behavior.  To ensure the
 761             // second condition, skip down the chain until we find the next
 762             // assertion with a property that doesn't match the current one.
 763             // (All these assertions would be skipped via mAlreadyReturned
 764             // checks anyways; this is even a bit faster.)
 765
 766             do {
 767                 mAssertion = (mSource ? mAssertion->mNext :
 768                         mAssertion->u.as.mInvNext);
 769             }
 770             while (mAssertion && (next == mAssertion->u.as.mProperty));
 771
 772             bool alreadyReturned = false;
 773             for (PRInt32 i = mAlreadyReturned.Length() - 1; i >= 0; --i) {
 774                 if (mAlreadyReturned[i] == next) {
 775                     alreadyReturned = true;
 776                     break;
 777                 }
 778             }
 779
 780             if (! alreadyReturned) {
 781                 mCurrent = next;
 782                 NS_ADDREF(mCurrent);
 783                 *aResult = true;
 784                 return NS_OK;
 785             }
 786         }
 787
 788     *aResult = false;
 789     return NS_OK;
 790 }
 791
 792
 793 NS_IMETHODIMP
 794 InMemoryArcsEnumeratorImpl::GetNext(nsISupports** aResult)
 795 {
 796     nsresult rv;
 797
 798     bool hasMore;
 799     rv = HasMoreElements(&hasMore);
 800     if (NS_FAILED(rv)) return rv;
 801
 802     if (! hasMore)
 803         return NS_ERROR_UNEXPECTED;
 804
 805     // Add this to the set of things we've already returned so that we
 806     // can ensure uniqueness
 807     mAlreadyReturned.AppendElement(mCurrent);
 808
 809     // Don't AddRef: we "transfer" ownership to the caller
 810     *aResult = mCurrent;
 811     mCurrent = nullptr;
 812
 813     return NS_OK;
 814 }
 815
 816
 817 ////////////////////////////////////////////////////////////////////////
 818 // InMemoryDataSource
 819
 820 nsresult
 821 NS_NewRDFInMemoryDataSource(nsISupports* aOuter, const nsIID& aIID, void** aResult)
 822 {
 823     NS_PRECONDITION(aResult != nullptr, "null ptr");
 824     if (! aResult)
 825         return NS_ERROR_NULL_POINTER;
 826     *aResult = nullptr;
 827
 828     if (aOuter && !aIID.Equals(NS_GET_IID(nsISupports))) {
 829         NS_ERROR("aggregation requires nsISupports");
 830         return NS_ERROR_ILLEGAL_VALUE;
 831     }
 832
 833     InMemoryDataSource* datasource = new InMemoryDataSource(aOuter);
 834     if (! datasource)
 835         return NS_ERROR_OUT_OF_MEMORY;
 836     NS_ADDREF(datasource);
 837
 838     nsresult rv = datasource->Init();
 839     if (NS_SUCCEEDED(rv)) {
 840         datasource->fAggregated.AddRef();
 841         rv = datasource->AggregatedQueryInterface(aIID, aResult); // This'll AddRef()
 842         datasource->fAggregated.Release();
 843     }
 844
 845     NS_RELEASE(datasource);
 846     return rv;
 847 }
 848
 849
 850 InMemoryDataSource::InMemoryDataSource(nsISupports* aOuter)
 851     : mNumObservers(0), mReadCount(0)
 852 {
 853     NS_INIT_AGGREGATED(aOuter);
 854
 855     static const size_t kBucketSizes[] = {
 856         sizeof(Assertion),
 857         sizeof(Entry),
 858         sizeof(InMemoryArcsEnumeratorImpl),
 859         sizeof(InMemoryAssertionEnumeratorImpl) };
 860
 861     static const PRInt32 kNumBuckets = sizeof(kBucketSizes) / sizeof(size_t);
 862
 863     // Per news://news.mozilla.org/39BEC105.5090206%40netscape.com
 864     static const PRInt32 kInitialSize = 1024;
 865
 866     mAllocator.Init("nsInMemoryDataSource", kBucketSizes, kNumBuckets, kInitialSize);
 867
 868     mForwardArcs.ops = nullptr;
 869     mReverseArcs.ops = nullptr;
 870     mPropagateChanges = true;
 871 }
 872
 873
 874 nsresult
 875 InMemoryDataSource::Init()
 876 {
 877     if (!PL_DHashTableInit(&mForwardArcs,
 878                            PL_DHashGetStubOps(),
 879                            nullptr,
 880                            sizeof(Entry),
 881                            PL_DHASH_MIN_SIZE)) {
 882         mForwardArcs.ops = nullptr;
 883         return NS_ERROR_OUT_OF_MEMORY;
 884     }
 885     if (!PL_DHashTableInit(&mReverseArcs,
 886                            PL_DHashGetStubOps(),
 887                            nullptr,
 888                            sizeof(Entry),
 889                            PL_DHASH_MIN_SIZE)) {
 890         mReverseArcs.ops = nullptr;
 891         return NS_ERROR_OUT_OF_MEMORY;
 892     }
 893
 894 #ifdef PR_LOGGING
 895     if (! gLog)
 896         gLog = PR_NewLogModule("InMemoryDataSource");
 897 #endif
 898
 899     return NS_OK;
 900 }
 901
 902
 903 InMemoryDataSource::~InMemoryDataSource()
 904 {
 905 #ifdef DEBUG_REFS
 906     --gInstanceCount;
 907     fprintf(stdout, "%d - RDF: InMemoryDataSource\n", gInstanceCount);
 908 #endif
 909
 910     if (mForwardArcs.ops) {
 911         // This'll release all of the Assertion objects that are
 912         // associated with this data source. We only need to do this
 913         // for the forward arcs, because the reverse arcs table
 914         // indexes the exact same set of resources.
 915         PL_DHashTableEnumerate(&mForwardArcs, DeleteForwardArcsEntry, &mAllocator);
 916         PL_DHashTableFinish(&mForwardArcs);
 917     }
 918     if (mReverseArcs.ops)
 919         PL_DHashTableFinish(&mReverseArcs);
 920
 921     PR_LOG(gLog, PR_LOG_NOTICE,
 922            ("InMemoryDataSource(%p): destroyed.", this));
 923
 924 }
 925
 926 PLDHashOperator
 927 InMemoryDataSource::DeleteForwardArcsEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
 928                                            PRUint32 aNumber, void* aArg)
 929 {
 930     Entry* entry = reinterpret_cast<Entry*>(aHdr);
 931     nsFixedSizeAllocator* allocator = static_cast<nsFixedSizeAllocator*>(aArg);
 932
 933     Assertion* as = entry->mAssertions;
 934     while (as) {
 935         Assertion* doomed = as;
 936         as = as->mNext;
 937
 938         // Unlink, and release the datasource's reference.
 939         doomed->mNext = doomed->u.as.mInvNext = nullptr;
 940         doomed->Release(*allocator);
 941     }
 942     return PL_DHASH_NEXT;
 943 }
 944
 945
 946 ////////////////////////////////////////////////////////////////////////
 947
 948 NS_IMPL_CYCLE_COLLECTION_CLASS(InMemoryDataSource)
 949 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(InMemoryDataSource)
 950     NS_IMPL_CYCLE_COLLECTION_UNLINK_NSCOMARRAY(mObservers)
 951 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
 952 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_AGGREGATED(InMemoryDataSource)
 953     NS_IMPL_CYCLE_COLLECTION_TRAVERSE_NSCOMARRAY(mObservers)
 954 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
 955
 956 NS_IMPL_CYCLE_COLLECTING_AGGREGATED(InMemoryDataSource)
 957 NS_INTERFACE_MAP_BEGIN_AGGREGATED(InMemoryDataSource)
 958     NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION_AGGREGATED(InMemoryDataSource)
 959     NS_INTERFACE_MAP_ENTRY(nsIRDFDataSource)
 960     NS_INTERFACE_MAP_ENTRY(nsIRDFInMemoryDataSource)
 961     NS_INTERFACE_MAP_ENTRY(nsIRDFPropagatableDataSource)
 962     NS_INTERFACE_MAP_ENTRY(nsIRDFPurgeableDataSource)
 963     NS_INTERFACE_MAP_ENTRY(rdfIDataSource)
 964 NS_INTERFACE_MAP_END
 965
 966 ////////////////////////////////////////////////////////////////////////
 967
 968
 969 #ifdef PR_LOGGING
 970 void
 971 InMemoryDataSource::LogOperation(const char* aOperation,
 972                                  nsIRDFResource* aSource,
 973                                  nsIRDFResource* aProperty,
 974                                  nsIRDFNode* aTarget,
 975                                  bool aTruthValue)
 976 {
 977     if (! PR_LOG_TEST(gLog, PR_LOG_NOTICE))
 978         return;
 979
 980     nsXPIDLCString uri;
 981     aSource->GetValue(getter_Copies(uri));
 982     PR_LogPrint
 983            ("InMemoryDataSource(%p): %s", this, aOperation);
 984
 985     PR_LogPrint
 986            ("  [(%p)%s]--", aSource, (const char*) uri);
 987
 988     aProperty->GetValue(getter_Copies(uri));
 989
 990     char tv = (aTruthValue ? '-' : '!');
 991     PR_LogPrint
 992            ("  --%c[(%p)%s]--", tv, aProperty, (const char*) uri);
 993
 994     nsCOMPtr<nsIRDFResource> resource;
 995     nsCOMPtr<nsIRDFLiteral> literal;
 996
 997     if ((resource = do_QueryInterface(aTarget)) != nullptr) {
 998         resource->GetValue(getter_Copies(uri));
 999         PR_LogPrint
1000            ("  -->[(%p)%s]", aTarget, (const char*) uri);
1001     }
1002     else if ((literal = do_QueryInterface(aTarget)) != nullptr) {
1003         nsXPIDLString value;
1004         literal->GetValue(getter_Copies(value));
1005         nsAutoString valueStr(value);
1006         char* valueCStr = ToNewCString(valueStr);
1007
1008         PR_LogPrint
1009            ("  -->(\"%s\")\n", valueCStr);
1010
1011         NS_Free(valueCStr);
1012     }
1013     else {
1014         PR_LogPrint
1015            ("  -->(unknown-type)\n");
1016     }
1017 }
1018 #endif
1019
1020
1021 NS_IMETHODIMP
1022 InMemoryDataSource::GetURI(char* *uri)
1023 {
1024     NS_PRECONDITION(uri != nullptr, "null ptr");
1025     if (! uri)
1026         return NS_ERROR_NULL_POINTER;
1027
1028     *uri = nullptr;
1029     return NS_OK;
1030 }
1031
1032 NS_IMETHODIMP
1033 InMemoryDataSource::GetSource(nsIRDFResource* property,
1034                               nsIRDFNode* target,
1035                               bool tv,
1036                               nsIRDFResource** source)
1037 {
1038     NS_PRECONDITION(source != nullptr, "null ptr");
1039     if (! source)
1040         return NS_ERROR_NULL_POINTER;
1041
1042     NS_PRECONDITION(property != nullptr, "null ptr");
1043     if (! property)
1044         return NS_ERROR_NULL_POINTER;
1045
1046     NS_PRECONDITION(target != nullptr, "null ptr");
1047     if (! target)
1048         return NS_ERROR_NULL_POINTER;
1049
1050     for (Assertion* as = GetReverseArcs(target); as; as = as->u.as.mInvNext) {
1051         if ((property == as->u.as.mProperty) && (tv == as->u.as.mTruthValue)) {
1052             *source = as->mSource;
1053             NS_ADDREF(*source);
1054             return NS_OK;
1055         }
1056     }
1057     *source = nullptr;
1058     return NS_RDF_NO_VALUE;
1059 }
1060
1061 NS_IMETHODIMP
1062 InMemoryDataSource::GetTarget(nsIRDFResource* source,
1063                               nsIRDFResource* property,
1064                               bool tv,
1065                               nsIRDFNode** target)
1066 {
1067     NS_PRECONDITION(source != nullptr, "null ptr");
1068     if (! source)
1069         return NS_ERROR_NULL_POINTER;
1070
1071     NS_PRECONDITION(property != nullptr, "null ptr");
1072     if (! property)
1073         return NS_ERROR_NULL_POINTER;
1074
1075     NS_PRECONDITION(target != nullptr, "null ptr");
1076     if (! target)
1077         return NS_ERROR_NULL_POINTER;
1078
1079     Assertion *as = GetForwardArcs(source);
1080     if (as && as->mHashEntry) {
1081         PLDHashEntryHdr* hdr = PL_DHashTableOperate(as->u.hash.mPropertyHash, property, PL_DHASH_LOOKUP);
1082         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
1083             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1084             : nullptr;
1085         while (val) {
1086             if (tv == val->u.as.mTruthValue) {
1087                 *target = val->u.as.mTarget;
1088                 NS_IF_ADDREF(*target);
1089                 return NS_OK;
1090             }
1091             val = val->mNext;
1092         }
1093     }
1094     else
1095     for (; as != nullptr; as = as->mNext) {
1096         if ((property == as->u.as.mProperty) && (tv == (as->u.as.mTruthValue))) {
1097             *target = as->u.as.mTarget;
1098             NS_ADDREF(*target);
1099             return NS_OK;
1100         }
1101     }
1102
1103     // If we get here, then there was no target with for the specified
1104     // property & truth value.
1105     *target = nullptr;
1106     return NS_RDF_NO_VALUE;
1107 }
1108
1109 NS_IMETHODIMP
1110 InMemoryDataSource::HasAssertion(nsIRDFResource* source,
1111                                  nsIRDFResource* property,
1112                                  nsIRDFNode* target,
1113                                  bool tv,
1114                                  bool* hasAssertion)
1115 {
1116     if (! source)
1117         return NS_ERROR_NULL_POINTER;
1118
1119     if (! property)
1120         return NS_ERROR_NULL_POINTER;
1121
1122     if (! target)
1123         return NS_ERROR_NULL_POINTER;
1124
1125     Assertion *as = GetForwardArcs(source);
1126     if (as && as->mHashEntry) {
1127         PLDHashEntryHdr* hdr = PL_DHashTableOperate(as->u.hash.mPropertyHash, property, PL_DHASH_LOOKUP);
1128         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
1129             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1130             : nullptr;
1131         while (val) {
1132             if ((val->u.as.mTarget == target) && (tv == (val->u.as.mTruthValue))) {
1133                 *hasAssertion = true;
1134                 return NS_OK;
1135             }
1136             val = val->mNext;
1137         }
1138     }
1139     else
1140     for (; as != nullptr; as = as->mNext) {
1141         // check target first as its most unique
1142         if (target != as->u.as.mTarget)
1143             continue;
1144
1145         if (property != as->u.as.mProperty)
1146             continue;
1147
1148         if (tv != (as->u.as.mTruthValue))
1149             continue;
1150
1151         // found it!
1152         *hasAssertion = true;
1153         return NS_OK;
1154     }
1155
1156     // If we get here, we couldn't find the assertion
1157     *hasAssertion = false;
1158     return NS_OK;
1159 }
1160
1161 NS_IMETHODIMP
1162 InMemoryDataSource::GetSources(nsIRDFResource* aProperty,
1163                                nsIRDFNode* aTarget,
1164                                bool aTruthValue,
1165                                nsISimpleEnumerator** aResult)
1166 {
1167     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1168     if (! aProperty)
1169         return NS_ERROR_NULL_POINTER;
1170
1171     NS_PRECONDITION(aTarget != nullptr, "null ptr");
1172     if (! aTarget)
1173         return NS_ERROR_NULL_POINTER;
1174
1175     NS_PRECONDITION(aResult != nullptr, "null ptr");
1176     if (! aResult)
1177         return NS_ERROR_NULL_POINTER;
1178
1179     InMemoryAssertionEnumeratorImpl* result =
1180         InMemoryAssertionEnumeratorImpl::Create(this, nullptr, aProperty,
1181                                                   aTarget, aTruthValue);
1182
1183     if (! result)
1184         return NS_ERROR_OUT_OF_MEMORY;
1185
1186     NS_ADDREF(result);
1187     *aResult = result;
1188
1189     return NS_OK;
1190 }
1191
1192 NS_IMETHODIMP
1193 InMemoryDataSource::GetTargets(nsIRDFResource* aSource,
1194                                nsIRDFResource* aProperty,
1195                                bool aTruthValue,
1196                                nsISimpleEnumerator** aResult)
1197 {
1198     NS_PRECONDITION(aSource != nullptr, "null ptr");
1199     if (! aSource)
1200         return NS_ERROR_NULL_POINTER;
1201
1202     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1203     if (! aProperty)
1204         return NS_ERROR_NULL_POINTER;
1205
1206     NS_PRECONDITION(aResult != nullptr, "null ptr");
1207     if (! aResult)
1208         return NS_ERROR_NULL_POINTER;
1209
1210     InMemoryAssertionEnumeratorImpl* result =
1211         InMemoryAssertionEnumeratorImpl::Create(this, aSource, aProperty,
1212                                                 nullptr, aTruthValue);
1213
1214     if (! result)
1215         return NS_ERROR_OUT_OF_MEMORY;
1216
1217     NS_ADDREF(result);
1218     *aResult = result;
1219
1220     return NS_OK;
1221 }
1222
1223
1224 nsresult
1225 InMemoryDataSource::LockedAssert(nsIRDFResource* aSource,
1226                                  nsIRDFResource* aProperty,
1227                                  nsIRDFNode* aTarget,
1228                                  bool aTruthValue)
1229 {
1230 #ifdef PR_LOGGING
1231     LogOperation("ASSERT", aSource, aProperty, aTarget, aTruthValue);
1232 #endif
1233
1234     Assertion* next = GetForwardArcs(aSource);
1235     Assertion* prev = next;
1236     Assertion* as = nullptr;
1237
1238     bool    haveHash = (next) ? next->mHashEntry : false;
1239     if (haveHash) {
1240         PLDHashEntryHdr* hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash, aProperty, PL_DHASH_LOOKUP);
1241         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
1242             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1243             : nullptr;
1244         while (val) {
1245             if (val->u.as.mTarget == aTarget) {
1246                 // Wow, we already had the assertion. Make sure that the
1247                 // truth values are correct and bail.
1248                 val->u.as.mTruthValue = aTruthValue;
1249                 return NS_OK;
1250             }
1251             val = val->mNext;
1252         }
1253     }
1254     else
1255     {
1256         while (next) {
1257             // check target first as its most unique
1258             if (aTarget == next->u.as.mTarget) {
1259                 if (aProperty == next->u.as.mProperty) {
1260                     // Wow, we already had the assertion. Make sure that the
1261                     // truth values are correct and bail.
1262                     next->u.as.mTruthValue = aTruthValue;
1263                     return NS_OK;
1264                 }
1265             }
1266
1267             prev = next;
1268             next = next->mNext;
1269         }
1270     }
1271
1272     as = Assertion::Create(mAllocator, aSource, aProperty, aTarget, aTruthValue);
1273     if (! as)
1274         return NS_ERROR_OUT_OF_MEMORY;
1275
1276     // Add the datasource's owning reference.
1277     as->AddRef();
1278
1279     if (haveHash)
1280     {
1281         PLDHashEntryHdr* hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash,
1282             aProperty, PL_DHASH_LOOKUP);
1283         Assertion *asRef = PL_DHASH_ENTRY_IS_BUSY(hdr)
1284             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1285             : nullptr;
1286         if (asRef)
1287         {
1288             as->mNext = asRef->mNext;
1289             asRef->mNext = as;
1290         }
1291         else
1292         {
1293             hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash,
1294                                             aProperty, PL_DHASH_ADD);
1295             if (hdr)
1296             {
1297                 Entry* entry = reinterpret_cast<Entry*>(hdr);
1298                 entry->mNode = aProperty;
1299                 entry->mAssertions = as;
1300             }
1301         }
1302     }
1303     else
1304     {
1305         // Link it in to the "forward arcs" table
1306         if (!prev) {
1307             SetForwardArcs(aSource, as);
1308         } else {
1309             prev->mNext = as;
1310         }
1311     }
1312
1313     // Link it in to the "reverse arcs" table
1314
1315     next = GetReverseArcs(aTarget);
1316     as->u.as.mInvNext = next;
1317     next = as;
1318     SetReverseArcs(aTarget, next);
1319
1320     return NS_OK;
1321 }
1322
1323 NS_IMETHODIMP
1324 InMemoryDataSource::Assert(nsIRDFResource* aSource,
1325                            nsIRDFResource* aProperty,
1326                            nsIRDFNode* aTarget,
1327                            bool aTruthValue)
1328 {
1329     NS_PRECONDITION(aSource != nullptr, "null ptr");
1330     if (! aSource)
1331         return NS_ERROR_NULL_POINTER;
1332
1333     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1334     if (! aProperty)
1335         return NS_ERROR_NULL_POINTER;
1336
1337     NS_PRECONDITION(aTarget != nullptr, "null ptr");
1338     if (! aTarget)
1339         return NS_ERROR_NULL_POINTER;
1340
1341     if (mReadCount) {
1342         NS_WARNING("Writing to InMemoryDataSource during read\n");
1343         return NS_RDF_ASSERTION_REJECTED;
1344     }
1345
1346     nsresult rv;
1347     rv = LockedAssert(aSource, aProperty, aTarget, aTruthValue);
1348     if (NS_FAILED(rv)) return rv;
1349
1350     // notify observers
1351     for (PRInt32 i = (PRInt32)mNumObservers - 1; mPropagateChanges && i >= 0; --i) {
1352         nsIRDFObserver* obs = mObservers[i];
1353
1354         // XXX this should never happen, but it does, and we can't figure out why.
1355         NS_ASSERTION(obs, "observer array corrupted!");
1356         if (! obs)
1357           continue;
1358
1359         obs->OnAssert(this, aSource, aProperty, aTarget);
1360         // XXX ignore return value?
1361     }
1362
1363     return NS_RDF_ASSERTION_ACCEPTED;
1364 }
1365
1366
1367 nsresult
1368 InMemoryDataSource::LockedUnassert(nsIRDFResource* aSource,
1369                                    nsIRDFResource* aProperty,
1370                                    nsIRDFNode* aTarget)
1371 {
1372 #ifdef PR_LOGGING
1373     LogOperation("UNASSERT", aSource, aProperty, aTarget);
1374 #endif
1375
1376     Assertion* next = GetForwardArcs(aSource);
1377     Assertion* prev = next;
1378     Assertion* root = next;
1379     Assertion* as = nullptr;
1380
1381     bool    haveHash = (next) ? next->mHashEntry : false;
1382     if (haveHash) {
1383         PLDHashEntryHdr* hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash,
1384             aProperty, PL_DHASH_LOOKUP);
1385         prev = next = PL_DHASH_ENTRY_IS_BUSY(hdr)
1386             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1387             : nullptr;
1388         bool first = true;
1389         while (next) {
1390             if (aTarget == next->u.as.mTarget) {
1391                 break;
1392             }
1393             first = false;
1394             prev = next;
1395             next = next->mNext;
1396         }
1397         // We don't even have the assertion, so just bail.
1398         if (!next)
1399             return NS_OK;
1400
1401         as = next;
1402
1403         if (first) {
1404             PL_DHashTableRawRemove(root->u.hash.mPropertyHash, hdr);
1405
1406             if (next && next->mNext) {
1407                 PLDHashEntryHdr* hdr = PL_DHashTableOperate(root->u.hash.mPropertyHash,
1408                                      aProperty, PL_DHASH_ADD);
1409                 if (hdr) {
1410                     Entry* entry = reinterpret_cast<Entry*>(hdr);
1411                     entry->mNode = aProperty;
1412                     entry->mAssertions = next->mNext;
1413                 }
1414             }
1415             else {
1416                 // If this second-level hash empties out, clean it up.
1417                 if (!root->u.hash.mPropertyHash->entryCount) {
1418                     Assertion::Destroy(mAllocator, root);
1419                     SetForwardArcs(aSource, nullptr);
1420                 }
1421             }
1422         }
1423         else {
1424             prev->mNext = next->mNext;
1425         }
1426     }
1427     else
1428     {
1429         while (next) {
1430             // check target first as its most unique
1431             if (aTarget == next->u.as.mTarget) {
1432                 if (aProperty == next->u.as.mProperty) {
1433                     if (prev == next) {
1434                         SetForwardArcs(aSource, next->mNext);
1435                     } else {
1436                         prev->mNext = next->mNext;
1437                     }
1438                     as = next;
1439                     break;
1440                 }
1441             }
1442
1443             prev = next;
1444             next = next->mNext;
1445         }
1446     }
1447     // We don't even have the assertion, so just bail.
1448     if (!as)
1449         return NS_OK;
1450
1451 #ifdef DEBUG
1452     bool foundReverseArc = false;
1453 #endif
1454
1455     next = prev = GetReverseArcs(aTarget);
1456     while (next) {
1457         if (next == as) {
1458             if (prev == next) {
1459                 SetReverseArcs(aTarget, next->u.as.mInvNext);
1460             } else {
1461                 prev->u.as.mInvNext = next->u.as.mInvNext;
1462             }
1463 #ifdef DEBUG
1464             foundReverseArc = true;
1465 #endif
1466             break;
1467         }
1468         prev = next;
1469         next = next->u.as.mInvNext;
1470     }
1471
1472 #ifdef DEBUG
1473     NS_ASSERTION(foundReverseArc, "in-memory db corrupted: unable to find reverse arc");
1474 #endif
1475
1476     // Unlink, and release the datasource's reference
1477     as->mNext = as->u.as.mInvNext = nullptr;
1478     as->Release(mAllocator);
1479
1480     return NS_OK;
1481 }
1482
1483 NS_IMETHODIMP
1484 InMemoryDataSource::Unassert(nsIRDFResource* aSource,
1485                              nsIRDFResource* aProperty,
1486                              nsIRDFNode* aTarget)
1487 {
1488     NS_PRECONDITION(aSource != nullptr, "null ptr");
1489     if (! aSource)
1490         return NS_ERROR_NULL_POINTER;
1491
1492     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1493     if (! aProperty)
1494         return NS_ERROR_NULL_POINTER;
1495
1496     NS_PRECONDITION(aTarget != nullptr, "null ptr");
1497     if (! aTarget)
1498         return NS_ERROR_NULL_POINTER;
1499
1500     if (mReadCount) {
1501         NS_WARNING("Writing to InMemoryDataSource during read\n");
1502         return NS_RDF_ASSERTION_REJECTED;
1503     }
1504
1505     nsresult rv;
1506
1507     rv = LockedUnassert(aSource, aProperty, aTarget);
1508     if (NS_FAILED(rv)) return rv;
1509
1510     // Notify the world
1511     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
1512         nsIRDFObserver* obs = mObservers[i];
1513
1514         // XXX this should never happen, but it does, and we can't figure out why.
1515         NS_ASSERTION(obs, "observer array corrupted!");
1516         if (! obs)
1517           continue;
1518
1519         obs->OnUnassert(this, aSource, aProperty, aTarget);
1520         // XXX ignore return value?
1521     }
1522
1523     return NS_RDF_ASSERTION_ACCEPTED;
1524 }
1525
1526
1527 NS_IMETHODIMP
1528 InMemoryDataSource::Change(nsIRDFResource* aSource,
1529                            nsIRDFResource* aProperty,
1530                            nsIRDFNode* aOldTarget,
1531                            nsIRDFNode* aNewTarget)
1532 {
1533     NS_PRECONDITION(aSource != nullptr, "null ptr");
1534     if (! aSource)
1535         return NS_ERROR_NULL_POINTER;
1536
1537     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1538     if (! aProperty)
1539         return NS_ERROR_NULL_POINTER;
1540
1541     NS_PRECONDITION(aOldTarget != nullptr, "null ptr");
1542     if (! aOldTarget)
1543         return NS_ERROR_NULL_POINTER;
1544
1545     NS_PRECONDITION(aNewTarget != nullptr, "null ptr");
1546     if (! aNewTarget)
1547         return NS_ERROR_NULL_POINTER;
1548
1549     if (mReadCount) {
1550         NS_WARNING("Writing to InMemoryDataSource during read\n");
1551         return NS_RDF_ASSERTION_REJECTED;
1552     }
1553
1554     nsresult rv;
1555
1556     // XXX We can implement LockedChange() if we decide that this
1557     // is a performance bottleneck.
1558
1559     rv = LockedUnassert(aSource, aProperty, aOldTarget);
1560     if (NS_FAILED(rv)) return rv;
1561
1562     rv = LockedAssert(aSource, aProperty, aNewTarget, true);
1563     if (NS_FAILED(rv)) return rv;
1564
1565     // Notify the world
1566     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
1567         nsIRDFObserver* obs = mObservers[i];
1568
1569         // XXX this should never happen, but it does, and we can't figure out why.
1570         NS_ASSERTION(obs, "observer array corrupted!");
1571         if (! obs)
1572           continue;
1573
1574         obs->OnChange(this, aSource, aProperty, aOldTarget, aNewTarget);
1575         // XXX ignore return value?
1576     }
1577
1578     return NS_RDF_ASSERTION_ACCEPTED;
1579 }
1580
1581
1582 NS_IMETHODIMP
1583 InMemoryDataSource::Move(nsIRDFResource* aOldSource,
1584                          nsIRDFResource* aNewSource,
1585                          nsIRDFResource* aProperty,
1586                          nsIRDFNode* aTarget)
1587 {
1588     NS_PRECONDITION(aOldSource != nullptr, "null ptr");
1589     if (! aOldSource)
1590         return NS_ERROR_NULL_POINTER;
1591
1592     NS_PRECONDITION(aNewSource != nullptr, "null ptr");
1593     if (! aNewSource)
1594         return NS_ERROR_NULL_POINTER;
1595
1596     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1597     if (! aProperty)
1598         return NS_ERROR_NULL_POINTER;
1599
1600     NS_PRECONDITION(aTarget != nullptr, "null ptr");
1601     if (! aTarget)
1602         return NS_ERROR_NULL_POINTER;
1603
1604     if (mReadCount) {
1605         NS_WARNING("Writing to InMemoryDataSource during read\n");
1606         return NS_RDF_ASSERTION_REJECTED;
1607     }
1608
1609     nsresult rv;
1610
1611     // XXX We can implement LockedMove() if we decide that this
1612     // is a performance bottleneck.
1613
1614     rv = LockedUnassert(aOldSource, aProperty, aTarget);
1615     if (NS_FAILED(rv)) return rv;
1616
1617     rv = LockedAssert(aNewSource, aProperty, aTarget, true);
1618     if (NS_FAILED(rv)) return rv;
1619
1620     // Notify the world
1621     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
1622         nsIRDFObserver* obs = mObservers[i];
1623
1624         // XXX this should never happen, but it does, and we can't figure out why.
1625         NS_ASSERTION(obs, "observer array corrupted!");
1626         if (! obs)
1627           continue;
1628
1629         obs->OnMove(this, aOldSource, aNewSource, aProperty, aTarget);
1630         // XXX ignore return value?
1631     }
1632
1633     return NS_RDF_ASSERTION_ACCEPTED;
1634 }
1635
1636
1637 NS_IMETHODIMP
1638 InMemoryDataSource::AddObserver(nsIRDFObserver* aObserver)
1639 {
1640     NS_PRECONDITION(aObserver != nullptr, "null ptr");
1641     if (! aObserver)
1642         return NS_ERROR_NULL_POINTER;
1643
1644     mObservers.AppendObject(aObserver);
1645     mNumObservers = mObservers.Count();
1646
1647     return NS_OK;
1648 }
1649
1650 NS_IMETHODIMP
1651 InMemoryDataSource::RemoveObserver(nsIRDFObserver* aObserver)
1652 {
1653     NS_PRECONDITION(aObserver != nullptr, "null ptr");
1654     if (! aObserver)
1655         return NS_ERROR_NULL_POINTER;
1656
1657     mObservers.RemoveObject(aObserver);
1658     // note: use Count() instead of just decrementing
1659     // in case aObserver wasn't in list, for example
1660     mNumObservers = mObservers.Count();
1661
1662     return NS_OK;
1663 }
1664
1665 NS_IMETHODIMP
1666 InMemoryDataSource::HasArcIn(nsIRDFNode *aNode, nsIRDFResource *aArc, bool *result)
1667 {
1668     Assertion* ass = GetReverseArcs(aNode);
1669     while (ass) {
1670         nsIRDFResource* elbow = ass->u.as.mProperty;
1671         if (elbow == aArc) {
1672             *result = true;
1673             return NS_OK;
1674         }
1675         ass = ass->u.as.mInvNext;
1676     }
1677     *result = false;
1678     return NS_OK;
1679 }
1680
1681 NS_IMETHODIMP
1682 InMemoryDataSource::HasArcOut(nsIRDFResource *aSource, nsIRDFResource *aArc, bool *result)
1683 {
1684     Assertion* ass = GetForwardArcs(aSource);
1685     if (ass && ass->mHashEntry) {
1686         PLDHashEntryHdr* hdr = PL_DHashTableOperate(ass->u.hash.mPropertyHash,
1687             aArc, PL_DHASH_LOOKUP);
1688         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
1689             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1690             : nullptr;
1691         if (val) {
1692             *result = true;
1693             return NS_OK;
1694         }
1695         ass = ass->mNext;
1696     }
1697     while (ass) {
1698         nsIRDFResource* elbow = ass->u.as.mProperty;
1699         if (elbow == aArc) {
1700             *result = true;
1701             return NS_OK;
1702         }
1703         ass = ass->mNext;
1704     }
1705     *result = false;
1706     return NS_OK;
1707 }
1708
1709 NS_IMETHODIMP
1710 InMemoryDataSource::ArcLabelsIn(nsIRDFNode* aTarget, nsISimpleEnumerator** aResult)
1711 {
1712     NS_PRECONDITION(aTarget != nullptr, "null ptr");
1713     if (! aTarget)
1714         return NS_ERROR_NULL_POINTER;
1715
1716     InMemoryArcsEnumeratorImpl* result =
1717         InMemoryArcsEnumeratorImpl::Create(this, nullptr, aTarget);
1718
1719     if (! result)
1720         return NS_ERROR_OUT_OF_MEMORY;
1721
1722     NS_ADDREF(result);
1723     *aResult = result;
1724
1725     return NS_OK;
1726 }
1727
1728 NS_IMETHODIMP
1729 InMemoryDataSource::ArcLabelsOut(nsIRDFResource* aSource, nsISimpleEnumerator** aResult)
1730 {
1731     NS_PRECONDITION(aSource != nullptr, "null ptr");
1732     if (! aSource)
1733         return NS_ERROR_NULL_POINTER;
1734
1735     InMemoryArcsEnumeratorImpl* result =
1736         InMemoryArcsEnumeratorImpl::Create(this, aSource, nullptr);
1737
1738     if (! result)
1739         return NS_ERROR_OUT_OF_MEMORY;
1740
1741     NS_ADDREF(result);
1742     *aResult = result;
1743
1744     return NS_OK;
1745 }
1746
1747 PLDHashOperator
1748 InMemoryDataSource::ResourceEnumerator(PLDHashTable* aTable,
1749                                        PLDHashEntryHdr* aHdr,
1750                                        PRUint32 aNumber, void* aArg)
1751 {
1752     Entry* entry = reinterpret_cast<Entry*>(aHdr);
1753     nsISupportsArray* resources = static_cast<nsISupportsArray*>(aArg);
1754
1755     resources->AppendElement(entry->mNode);
1756     return PL_DHASH_NEXT;
1757 }
1758
1759
1760 NS_IMETHODIMP
1761 InMemoryDataSource::GetAllResources(nsISimpleEnumerator** aResult)
1762 {
1763     nsresult rv;
1764
1765     nsCOMPtr<nsISupportsArray> values;
1766     rv = NS_NewISupportsArray(getter_AddRefs(values));
1767     if (NS_FAILED(rv)) return rv;
1768
1769     // Enumerate all of our entries into an nsISupportsArray.
1770     PL_DHashTableEnumerate(&mForwardArcs, ResourceEnumerator, values.get());
1771
1772     return NS_NewArrayEnumerator(aResult, values);
1773 }
1774
1775 NS_IMETHODIMP
1776 InMemoryDataSource::GetAllCmds(nsIRDFResource* source,
1777                                nsISimpleEnumerator/*<nsIRDFResource>*/** commands)
1778 {
1779     return(NS_NewEmptyEnumerator(commands));
1780 }
1781
1782 NS_IMETHODIMP
1783 InMemoryDataSource::IsCommandEnabled(nsISupportsArray/*<nsIRDFResource>*/* aSources,
1784                                      nsIRDFResource*   aCommand,
1785                                      nsISupportsArray/*<nsIRDFResource>*/* aArguments,
1786                                      bool* aResult)
1787 {
1788     *aResult = false;
1789     return NS_OK;
1790 }
1791
1792 NS_IMETHODIMP
1793 InMemoryDataSource::DoCommand(nsISupportsArray/*<nsIRDFResource>*/* aSources,
1794                               nsIRDFResource*   aCommand,
1795                               nsISupportsArray/*<nsIRDFResource>*/* aArguments)
1796 {
1797     return NS_OK;
1798 }
1799
1800 NS_IMETHODIMP
1801 InMemoryDataSource::BeginUpdateBatch()
1802 {
1803     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
1804         nsIRDFObserver* obs = mObservers[i];
1805         obs->OnBeginUpdateBatch(this);
1806     }
1807     return NS_OK;
1808 }
1809
1810 NS_IMETHODIMP
1811 InMemoryDataSource::EndUpdateBatch()
1812 {
1813     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
1814         nsIRDFObserver* obs = mObservers[i];
1815         obs->OnEndUpdateBatch(this);
1816     }
1817     return NS_OK;
1818 }
1819
1820
1821
1822 ////////////////////////////////////////////////////////////////////////
1823 // nsIRDFInMemoryDataSource methods
1824
1825 NS_IMETHODIMP
1826 InMemoryDataSource::EnsureFastContainment(nsIRDFResource* aSource)
1827 {
1828     Assertion *as = GetForwardArcs(aSource);
1829     bool    haveHash = (as) ? as->mHashEntry : false;
1830
1831     // if its already a hash, then nothing to do
1832     if (haveHash)   return(NS_OK);
1833
1834     // convert aSource in forward hash into a hash
1835     Assertion *hashAssertion = Assertion::Create(mAllocator, aSource);
1836     NS_ASSERTION(hashAssertion, "unable to Assertion::Create");
1837     if (!hashAssertion) return(NS_ERROR_OUT_OF_MEMORY);
1838
1839     // Add the datasource's owning reference.
1840     hashAssertion->AddRef();
1841
1842     register Assertion *first = GetForwardArcs(aSource);
1843     SetForwardArcs(aSource, hashAssertion);
1844
1845     // mutate references of existing forward assertions into this hash
1846     PLDHashTable *table = hashAssertion->u.hash.mPropertyHash;
1847     Assertion *nextRef;
1848     while(first) {
1849         nextRef = first->mNext;
1850         nsIRDFResource *prop = first->u.as.mProperty;
1851
1852         PLDHashEntryHdr* hdr = PL_DHashTableOperate(table,
1853             prop, PL_DHASH_LOOKUP);
1854         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
1855             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1856             : nullptr;
1857         if (val) {
1858             first->mNext = val->mNext;
1859             val->mNext = first;
1860         }
1861         else {
1862             PLDHashEntryHdr* hdr = PL_DHashTableOperate(table,
1863                                             prop, PL_DHASH_ADD);
1864             if (hdr) {
1865                 Entry* entry = reinterpret_cast<Entry*>(hdr);
1866                 entry->mNode = prop;
1867                 entry->mAssertions = first;
1868                 first->mNext = nullptr;
1869             }
1870         }
1871         first = nextRef;
1872     }
1873     return(NS_OK);
1874 }
1875
1876
1877 ////////////////////////////////////////////////////////////////////////
1878 // nsIRDFPropagatableDataSource methods
1879 NS_IMETHODIMP
1880 InMemoryDataSource::GetPropagateChanges(bool* aPropagateChanges)
1881 {
1882     *aPropagateChanges = mPropagateChanges;
1883     return NS_OK;
1884 }
1885
1886 NS_IMETHODIMP
1887 InMemoryDataSource::SetPropagateChanges(bool aPropagateChanges)
1888 {
1889     mPropagateChanges = aPropagateChanges;
1890     return NS_OK;
1891 }
1892
1893
1894 ////////////////////////////////////////////////////////////////////////
1895 // nsIRDFPurgeableDataSource methods
1896
1897 NS_IMETHODIMP
1898 InMemoryDataSource::Mark(nsIRDFResource* aSource,
1899                          nsIRDFResource* aProperty,
1900                          nsIRDFNode* aTarget,
1901                          bool aTruthValue,
1902                          bool* aDidMark)
1903 {
1904     NS_PRECONDITION(aSource != nullptr, "null ptr");
1905     if (! aSource)
1906         return NS_ERROR_NULL_POINTER;
1907
1908     NS_PRECONDITION(aProperty != nullptr, "null ptr");
1909     if (! aProperty)
1910         return NS_ERROR_NULL_POINTER;
1911
1912     NS_PRECONDITION(aTarget != nullptr, "null ptr");
1913     if (! aTarget)
1914         return NS_ERROR_NULL_POINTER;
1915
1916     Assertion *as = GetForwardArcs(aSource);
1917     if (as && as->mHashEntry) {
1918         PLDHashEntryHdr* hdr = PL_DHashTableOperate(as->u.hash.mPropertyHash,
1919             aProperty, PL_DHASH_LOOKUP);
1920         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
1921             ? reinterpret_cast<Entry*>(hdr)->mAssertions
1922             : nullptr;
1923         while (val) {
1924             if ((val->u.as.mTarget == aTarget) &&
1925                 (aTruthValue == (val->u.as.mTruthValue))) {
1926
1927                 // found it! so mark it.
1928                 as->Mark();
1929                 *aDidMark = true;
1930
1931 #ifdef PR_LOGGING
1932                 LogOperation("MARK", aSource, aProperty, aTarget, aTruthValue);
1933 #endif
1934
1935                 return NS_OK;
1936             }
1937             val = val->mNext;
1938         }
1939     }
1940     else for (; as != nullptr; as = as->mNext) {
1941         // check target first as its most unique
1942         if (aTarget != as->u.as.mTarget)
1943             continue;
1944
1945         if (aProperty != as->u.as.mProperty)
1946             continue;
1947
1948         if (aTruthValue != (as->u.as.mTruthValue))
1949             continue;
1950
1951         // found it! so mark it.
1952         as->Mark();
1953         *aDidMark = true;
1954
1955 #ifdef PR_LOGGING
1956         LogOperation("MARK", aSource, aProperty, aTarget, aTruthValue);
1957 #endif
1958
1959         return NS_OK;
1960     }
1961
1962     // If we get here, we couldn't find the assertion
1963     *aDidMark = false;
1964     return NS_OK;
1965 }
1966
1967
1968 struct SweepInfo {
1969     Assertion* mUnassertList;
1970     PLDHashTable* mReverseArcs;
1971     nsFixedSizeAllocator* mAllocator;
1972 };
1973
1974 NS_IMETHODIMP
1975 InMemoryDataSource::Sweep()
1976 {
1977     SweepInfo info = { nullptr, &mReverseArcs, &mAllocator};
1978
1979     // Remove all the assertions, but don't notify anyone.
1980     PL_DHashTableEnumerate(&mForwardArcs, SweepForwardArcsEntries, &info);
1981
1982     // Now do the notification.
1983     Assertion* as = info.mUnassertList;
1984     while (as) {
1985 #ifdef PR_LOGGING
1986         LogOperation("SWEEP", as->mSource, as->u.as.mProperty, as->u.as.mTarget, as->u.as.mTruthValue);
1987 #endif
1988         if (!(as->mHashEntry))
1989         {
1990             for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
1991                 nsIRDFObserver* obs = mObservers[i];
1992                 // XXXbz other loops over mObservers null-check |obs| here!
1993                 obs->OnUnassert(this, as->mSource, as->u.as.mProperty, as->u.as.mTarget);
1994                 // XXX ignore return value?
1995             }
1996         }
1997
1998         Assertion* doomed = as;
1999         as = as->mNext;
2000
2001         // Unlink, and release the datasource's reference
2002         doomed->mNext = doomed->u.as.mInvNext = nullptr;
2003         doomed->Release(mAllocator);
2004     }
2005
2006     return NS_OK;
2007 }
2008
2009
2010 PLDHashOperator
2011 InMemoryDataSource::SweepForwardArcsEntries(PLDHashTable* aTable,
2012                                             PLDHashEntryHdr* aHdr,
2013                                             PRUint32 aNumber, void* aArg)
2014 {
2015     PLDHashOperator result = PL_DHASH_NEXT;
2016     Entry* entry = reinterpret_cast<Entry*>(aHdr);
2017     SweepInfo* info = static_cast<SweepInfo*>(aArg);
2018
2019     Assertion* as = entry->mAssertions;
2020     if (as && (as->mHashEntry))
2021     {
2022         // Stuff in sub-hashes must be swept recursively (max depth: 1)
2023         PL_DHashTableEnumerate(as->u.hash.mPropertyHash,
2024                                SweepForwardArcsEntries, info);
2025
2026         // If the sub-hash is now empty, clean it up.
2027         if (!as->u.hash.mPropertyHash->entryCount) {
2028             Assertion::Destroy(*info->mAllocator, as);
2029             result = PL_DHASH_REMOVE;
2030         }
2031
2032         return result;
2033     }
2034
2035     Assertion* prev = nullptr;
2036     while (as) {
2037         if (as->IsMarked()) {
2038             prev = as;
2039             as->Unmark();
2040             as = as->mNext;
2041         }
2042         else {
2043             // remove from the list of assertions in the datasource
2044             Assertion* next = as->mNext;
2045             if (prev) {
2046                 prev->mNext = next;
2047             }
2048             else {
2049                 // it's the first one. update the hashtable entry.
2050                 entry->mAssertions = next;
2051             }
2052
2053             // remove from the reverse arcs
2054             PLDHashEntryHdr* hdr =
2055                 PL_DHashTableOperate(info->mReverseArcs, as->u.as.mTarget, PL_DHASH_LOOKUP);
2056             NS_ASSERTION(PL_DHASH_ENTRY_IS_BUSY(hdr), "no assertion in reverse arcs");
2057
2058             Entry* rentry = reinterpret_cast<Entry*>(hdr);
2059             Assertion* ras = rentry->mAssertions;
2060             Assertion* rprev = nullptr;
2061             while (ras) {
2062                 if (ras == as) {
2063                     if (rprev) {
2064                         rprev->u.as.mInvNext = ras->u.as.mInvNext;
2065                     }
2066                     else {
2067                         // it's the first one. update the hashtable entry.
2068                         rentry->mAssertions = ras->u.as.mInvNext;
2069                     }
2070                     as->u.as.mInvNext = nullptr; // for my sanity.
2071                     break;
2072                 }
2073                 rprev = ras;
2074                 ras = ras->u.as.mInvNext;
2075             }
2076
2077             // Wow, it was the _only_ one. Unhash it.
2078             if (! rentry->mAssertions)
2079             {
2080                 PL_DHashTableRawRemove(info->mReverseArcs, hdr);
2081             }
2082
2083             // add to the list of assertions to unassert
2084             as->mNext = info->mUnassertList;
2085             info->mUnassertList = as;
2086
2087             // Advance to the next assertion
2088             as = next;
2089         }
2090     }
2091
2092     // if no more assertions exist for this resource, then unhash it.
2093     if (! entry->mAssertions)
2094         result = PL_DHASH_REMOVE;
2095
2096     return result;
2097 }
2098
2099 ////////////////////////////////////////////////////////////////////////
2100 // rdfIDataSource methods
2101
2102 class VisitorClosure
2103 {
2104 public:
2105     VisitorClosure(rdfITripleVisitor* aVisitor) :
2106         mVisitor(aVisitor),
2107         mRv(NS_OK)
2108     {}
2109     rdfITripleVisitor* mVisitor;
2110     nsresult mRv;
2111 };
2112
2113 PLDHashOperator
2114 SubjectEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
2115                   PRUint32 aNumber, void* aArg) {
2116     Entry* entry = reinterpret_cast<Entry*>(aHdr);
2117     VisitorClosure* closure = static_cast<VisitorClosure*>(aArg);
2118
2119     nsresult rv;
2120     nsCOMPtr<nsIRDFNode> subject = do_QueryInterface(entry->mNode, &rv);
2121     NS_ENSURE_SUCCESS(rv, PL_DHASH_NEXT);
2122
2123     closure->mRv = closure->mVisitor->Visit(subject, nullptr, nullptr, true);
2124     if (NS_FAILED(closure->mRv) || closure->mRv == NS_RDF_STOP_VISIT)
2125         return PL_DHASH_STOP;
2126
2127     return PL_DHASH_NEXT;
2128 }
2129
2130 NS_IMETHODIMP
2131 InMemoryDataSource::VisitAllSubjects(rdfITripleVisitor *aVisitor)
2132 {
2133     // Lock datasource against writes
2134     ++mReadCount;
2135
2136     // Enumerate all of our entries into an nsISupportsArray.
2137     VisitorClosure cls(aVisitor);
2138     PL_DHashTableEnumerate(&mForwardArcs, SubjectEnumerator, &cls);
2139
2140     // Unlock datasource
2141     --mReadCount;
2142
2143     return cls.mRv;
2144 }
2145
2146 class TriplesInnerClosure
2147 {
2148 public:
2149     TriplesInnerClosure(nsIRDFNode* aSubject, VisitorClosure* aClosure) :
2150         mSubject(aSubject), mOuter(aClosure) {}
2151     nsIRDFNode* mSubject;
2152     VisitorClosure* mOuter;
2153 };
2154
2155 PLDHashOperator
2156 TriplesInnerEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
2157                   PRUint32 aNumber, void* aArg) {
2158     Entry* entry = reinterpret_cast<Entry*>(aHdr);
2159     Assertion* assertion = entry->mAssertions;
2160     TriplesInnerClosure* closure =
2161         static_cast<TriplesInnerClosure*>(aArg);
2162     while (assertion) {
2163         NS_ASSERTION(!assertion->mHashEntry, "shouldn't have to hashes");
2164         VisitorClosure* cls = closure->mOuter;
2165         cls->mRv = cls->mVisitor->Visit(closure->mSubject,
2166                                         assertion->u.as.mProperty,
2167                                         assertion->u.as.mTarget,
2168                                         assertion->u.as.mTruthValue);
2169         if (NS_FAILED(cls->mRv) || cls->mRv == NS_RDF_STOP_VISIT) {
2170             return PL_DHASH_STOP;
2171         }
2172         assertion = assertion->mNext;
2173     }
2174     return PL_DHASH_NEXT;
2175 }
2176 PLDHashOperator
2177 TriplesEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
2178                   PRUint32 aNumber, void* aArg) {
2179     Entry* entry = reinterpret_cast<Entry*>(aHdr);
2180     VisitorClosure* closure = static_cast<VisitorClosure*>(aArg);
2181
2182     nsresult rv;
2183     nsCOMPtr<nsIRDFNode> subject = do_QueryInterface(entry->mNode, &rv);
2184     NS_ENSURE_SUCCESS(rv, PL_DHASH_NEXT);
2185
2186     if (entry->mAssertions->mHashEntry) {
2187         TriplesInnerClosure cls(subject, closure);
2188         PL_DHashTableEnumerate(entry->mAssertions->u.hash.mPropertyHash,
2189                                TriplesInnerEnumerator, &cls);
2190         if (NS_FAILED(closure->mRv)) {
2191             return PL_DHASH_STOP;
2192         }
2193         return PL_DHASH_NEXT;
2194     }
2195     Assertion* assertion = entry->mAssertions;
2196     while (assertion) {
2197         NS_ASSERTION(!assertion->mHashEntry, "shouldn't have to hashes");
2198         closure->mRv = closure->mVisitor->Visit(subject,
2199                                                 assertion->u.as.mProperty,
2200                                                 assertion->u.as.mTarget,
2201                                                 assertion->u.as.mTruthValue);
2202         if (NS_FAILED(closure->mRv) || closure->mRv == NS_RDF_STOP_VISIT) {
2203             return PL_DHASH_STOP;
2204         }
2205         assertion = assertion->mNext;
2206     }
2207     return PL_DHASH_NEXT;
2208 }
2209 NS_IMETHODIMP
2210 InMemoryDataSource::VisitAllTriples(rdfITripleVisitor *aVisitor)
2211 {
2212     // Lock datasource against writes
2213     ++mReadCount;
2214
2215     // Enumerate all of our entries into an nsISupportsArray.
2216     VisitorClosure cls(aVisitor);
2217     PL_DHashTableEnumerate(&mForwardArcs, TriplesEnumerator, &cls);
2218
2219     // Unlock datasource
2220     --mReadCount;
2221
2222     return cls.mRv;
2223 }
2224
2225 ////////////////////////////////////////////////////////////////////////
2226