rdf/base/src/nsInMemoryDataSource.cpp

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