Back to index

lightning-sunbird  0.9+nobinonly
nsInMemoryDataSource.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is mozilla.org code.
00017  *
00018  * The Initial Developer of the Original Code is
00019  * Netscape Communications Corporation.
00020  * Portions created by the Initial Developer are Copyright (C) 1998
00021  * the Initial Developer. All Rights Reserved.
00022  *
00023  * Contributor(s):
00024  *   Chris Waterson         <waterson@netscape.com>
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either of the GNU General Public License Version 2 or later (the "GPL"),
00028  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK *****
00039  *
00040  *
00041  * This Original Code has been modified by IBM Corporation.
00042  * Modifications made by IBM described herein are
00043  * Copyright (c) International Business Machines
00044  * Corporation, 2000
00045  *
00046  * Modifications to Mozilla code or documentation
00047  * identified per MPL Section 3.3
00048  *
00049  * Date         Modified by     Description of modification
00050  * 03/27/2000   IBM Corp.       Added PR_CALLBACK for Optlink
00051  *                               use in OS2
00052  */
00053 
00054 /*
00055 
00056   Implementation for an in-memory RDF data store.
00057 
00058   TO DO
00059 
00060   1) Instrument this code to gather space and time performance
00061      characteristics.
00062 
00063   2) Optimize lookups for datasources which have a small number
00064      of properties + fanning out to a large number of targets.
00065 
00066   3) Complete implementation of thread-safety; specifically, make
00067      assertions be reference counted objects (so that a cursor can
00068      still refer to an assertion that gets removed from the graph).
00069 
00070  */
00071 
00072 #include "nsAgg.h"
00073 #include "nsCOMPtr.h"
00074 #include "nscore.h"
00075 #include "nsIOutputStream.h"
00076 #include "nsIRDFDataSource.h"
00077 #include "nsIRDFLiteral.h"
00078 #include "nsIRDFNode.h"
00079 #include "nsIRDFObserver.h"
00080 #include "nsIRDFInMemoryDataSource.h"
00081 #include "nsIRDFPropagatableDataSource.h"
00082 #include "nsIRDFPurgeableDataSource.h"
00083 #include "nsIRDFService.h"
00084 #include "nsIServiceManager.h"
00085 #include "nsISupportsArray.h"
00086 #include "nsCOMArray.h"
00087 #include "nsEnumeratorUtils.h"
00088 #include "nsVoidArray.h"  // XXX introduces dependency on raptorbase
00089 #include "nsCRT.h"
00090 #include "nsRDFCID.h"
00091 #include "nsRDFBaseDataSources.h"
00092 #include "nsString.h"
00093 #include "nsReadableUtils.h"
00094 #include "nsXPIDLString.h"
00095 #include "nsFixedSizeAllocator.h"
00096 #include "rdfutil.h"
00097 #include "pldhash.h"
00098 #include "plstr.h"
00099 #include "prlog.h"
00100 #include "rdf.h"
00101 
00102 #include "rdfIDataSource.h"
00103 #include "rdfITripleVisitor.h"
00104 
00105 #ifdef PR_LOGGING
00106 static PRLogModuleInfo* gLog = nsnull;
00107 #endif
00108 
00109 
00110 // This struct is used as the slot value in the forward and reverse
00111 // arcs hash tables.
00112 //
00113 // Assertion objects are reference counted, because each Assertion's
00114 // ownership is shared between the datasource and any enumerators that
00115 // are currently iterating over the datasource.
00116 //
00117 class Assertion 
00118 {
00119 public:
00120     static Assertion*
00121     Create(nsFixedSizeAllocator& aAllocator,
00122            nsIRDFResource* aSource,
00123            nsIRDFResource* aProperty,
00124            nsIRDFNode* aTarget,
00125            PRBool aTruthValue) {
00126         void* place = aAllocator.Alloc(sizeof(Assertion));
00127         return place
00128             ? ::new (place) Assertion(aSource, aProperty, aTarget, aTruthValue)
00129             : nsnull; }
00130     static Assertion*
00131     Create(nsFixedSizeAllocator& aAllocator, nsIRDFResource* aSource) {
00132         void* place = aAllocator.Alloc(sizeof(Assertion));
00133         return place
00134             ? ::new (place) Assertion(aSource)
00135             : nsnull; }
00136 
00137     static void
00138     Destroy(nsFixedSizeAllocator& aAllocator, Assertion* aAssertion) {
00139         if (aAssertion->mHashEntry && aAssertion->u.hash.mPropertyHash) {
00140             PL_DHashTableEnumerate(aAssertion->u.hash.mPropertyHash,
00141                 DeletePropertyHashEntry, &aAllocator);
00142             PL_DHashTableDestroy(aAssertion->u.hash.mPropertyHash);
00143             aAssertion->u.hash.mPropertyHash = nsnull;
00144         }
00145         aAssertion->~Assertion();
00146         aAllocator.Free(aAssertion, sizeof(*aAssertion)); }
00147 
00148     static PLDHashOperator PR_CALLBACK
00149     DeletePropertyHashEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00150                            PRUint32 aNumber, void* aArg);
00151 
00152     Assertion(nsIRDFResource* aSource,      // normal assertion
00153               nsIRDFResource* aProperty,
00154               nsIRDFNode* aTarget,
00155               PRBool aTruthValue);
00156     Assertion(nsIRDFResource* aSource);     // PLDHashTable assertion variant
00157 
00158     ~Assertion();
00159 
00160     void AddRef() {
00161         if (mRefCnt == PR_UINT16_MAX) {
00162             NS_WARNING("refcount overflow, leaking Assertion");
00163             return;
00164         }
00165         ++mRefCnt;
00166     }
00167 
00168     void Release(nsFixedSizeAllocator& aAllocator) {
00169         if (mRefCnt == PR_UINT16_MAX) {
00170             NS_WARNING("refcount overflow, leaking Assertion");
00171             return;
00172         }
00173         if (--mRefCnt == 0)
00174             Destroy(aAllocator, this);
00175     }
00176 
00177     // For nsIRDFPurgeableDataSource
00178     inline  void    Mark()      { u.as.mMarked = PR_TRUE; }
00179     inline  PRBool  IsMarked()  { return u.as.mMarked; }
00180     inline  void    Unmark()    { u.as.mMarked = PR_FALSE; }
00181 
00182     // public for now, because I'm too lazy to go thru and clean this up.
00183 
00184     // These are shared between hash/as (see the union below)
00185     nsIRDFResource*         mSource;
00186     Assertion*              mNext;
00187 
00188     union
00189     {
00190         struct hash
00191         {
00192             PLDHashTable*   mPropertyHash; 
00193         } hash;
00194         struct as
00195         {
00196             nsIRDFResource* mProperty;
00197             nsIRDFNode*     mTarget;
00198             Assertion*      mInvNext;
00199             // make sure PRPackedBool are final elements
00200             PRPackedBool    mTruthValue;
00201             PRPackedBool    mMarked;
00202         } as;
00203     } u;
00204 
00205     // also shared between hash/as (see the union above)
00206     // but placed after union definition to ensure that
00207     // all 32-bit entries are long aligned
00208     PRUint16                    mRefCnt;
00209     PRPackedBool                mHashEntry;
00210 
00211 private:
00212     // Hide so that only Create() and Destroy() can be used to
00213     // allocate and deallocate from the heap
00214     static void* operator new(size_t) CPP_THROW_NEW { return 0; }
00215     static void operator delete(void*, size_t) {}
00216 };
00217 
00218 
00219 struct Entry {
00220     PLDHashEntryHdr mHdr;
00221     nsIRDFNode*     mNode;
00222     Assertion*      mAssertions;
00223 };
00224 
00225 
00226 Assertion::Assertion(nsIRDFResource* aSource)
00227     : mSource(aSource),
00228       mNext(nsnull),
00229       mRefCnt(0),
00230       mHashEntry(PR_TRUE)
00231 {
00232     MOZ_COUNT_CTOR(RDF_Assertion);
00233 
00234     NS_ADDREF(mSource);
00235 
00236     u.hash.mPropertyHash = PL_NewDHashTable(PL_DHashGetStubOps(),
00237                       nsnull, sizeof(Entry), PL_DHASH_MIN_SIZE);
00238 }
00239 
00240 Assertion::Assertion(nsIRDFResource* aSource,
00241                      nsIRDFResource* aProperty,
00242                      nsIRDFNode* aTarget,
00243                      PRBool aTruthValue)
00244     : mSource(aSource),
00245       mNext(nsnull),
00246       mRefCnt(0),
00247       mHashEntry(PR_FALSE)
00248 {
00249     MOZ_COUNT_CTOR(RDF_Assertion);
00250 
00251     u.as.mProperty = aProperty;
00252     u.as.mTarget = aTarget;
00253 
00254     NS_ADDREF(mSource);
00255     NS_ADDREF(u.as.mProperty);
00256     NS_ADDREF(u.as.mTarget);
00257 
00258     u.as.mInvNext = nsnull;
00259     u.as.mTruthValue = aTruthValue;
00260     u.as.mMarked = PR_FALSE;
00261 }
00262 
00263 Assertion::~Assertion()
00264 {
00265     MOZ_COUNT_DTOR(RDF_Assertion);
00266 #ifdef DEBUG_REFS
00267     --gInstanceCount;
00268     fprintf(stdout, "%d - RDF: Assertion\n", gInstanceCount);
00269 #endif
00270 
00271     NS_RELEASE(mSource);
00272     if (!mHashEntry)
00273     {
00274         NS_RELEASE(u.as.mProperty);
00275         NS_RELEASE(u.as.mTarget);
00276     }
00277 }
00278 
00279 PLDHashOperator PR_CALLBACK
00280 Assertion::DeletePropertyHashEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00281                                            PRUint32 aNumber, void* aArg)
00282 {
00283     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
00284     nsFixedSizeAllocator* allocator = NS_STATIC_CAST(nsFixedSizeAllocator*, aArg);
00285 
00286     Assertion* as = entry->mAssertions;
00287     while (as) {
00288         Assertion* doomed = as;
00289         as = as->mNext;
00290 
00291         // Unlink, and release the datasource's reference.
00292         doomed->mNext = doomed->u.as.mInvNext = nsnull;
00293         doomed->Release(*allocator);
00294     }
00295     return PL_DHASH_NEXT;
00296 }
00297 
00298 
00299 
00301 // InMemoryDataSource
00302 class InMemoryArcsEnumeratorImpl;
00303 class InMemoryAssertionEnumeratorImpl;
00304 class InMemoryResourceEnumeratorImpl;
00305 
00306 class InMemoryDataSource : public nsIRDFDataSource,
00307                            public nsIRDFInMemoryDataSource,
00308                            public nsIRDFPropagatableDataSource,
00309                            public nsIRDFPurgeableDataSource,
00310                            public rdfIDataSource
00311 {
00312 protected:
00313     nsFixedSizeAllocator mAllocator;
00314 
00315     // These hash tables are keyed on pointers to nsIRDFResource
00316     // objects (the nsIRDFService ensures that there is only ever one
00317     // nsIRDFResource object per unique URI). The value of an entry is
00318     // an Assertion struct, which is a linked list of (subject
00319     // predicate object) triples.
00320     PLDHashTable mForwardArcs; 
00321     PLDHashTable mReverseArcs; 
00322 
00323     nsCOMArray<nsIRDFObserver> mObservers;  
00324     PRUint32                   mNumObservers;
00325 
00326     // VisitFoo needs to block writes, [Un]Assert only allowed
00327     // during mReadCount == 0
00328     PRUint32 mReadCount;
00329 
00330     static PLDHashOperator PR_CALLBACK
00331     DeleteForwardArcsEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00332                            PRUint32 aNumber, void* aArg);
00333 
00334     static PLDHashOperator PR_CALLBACK
00335     ResourceEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00336                        PRUint32 aNumber, void* aArg);
00337 
00338     friend class InMemoryArcsEnumeratorImpl;
00339     friend class InMemoryAssertionEnumeratorImpl;
00340     friend class InMemoryResourceEnumeratorImpl; // b/c it needs to enumerate mForwardArcs
00341 
00342     // Thread-safe writer implementation methods.
00343     nsresult
00344     LockedAssert(nsIRDFResource* source, 
00345                  nsIRDFResource* property, 
00346                  nsIRDFNode* target,
00347                  PRBool tv);
00348 
00349     nsresult
00350     LockedUnassert(nsIRDFResource* source,
00351                    nsIRDFResource* property,
00352                    nsIRDFNode* target);
00353 
00354     InMemoryDataSource(nsISupports* aOuter);
00355     virtual ~InMemoryDataSource();
00356     nsresult Init();
00357 
00358     friend NS_IMETHODIMP
00359     NS_NewRDFInMemoryDataSource(nsISupports* aOuter, const nsIID& aIID, void** aResult);
00360 
00361 public:
00362     NS_DECL_AGGREGATED
00363 
00364     // nsIRDFDataSource methods
00365     NS_DECL_NSIRDFDATASOURCE
00366 
00367     // nsIRDFInMemoryDataSource methods
00368     NS_DECL_NSIRDFINMEMORYDATASOURCE
00369 
00370     // nsIRDFPropagatableDataSource methods
00371     NS_DECL_NSIRDFPROPAGATABLEDATASOURCE
00372 
00373     // nsIRDFPurgeableDataSource methods
00374     NS_DECL_NSIRDFPURGEABLEDATASOURCE
00375 
00376     // rdfIDataSource methods
00377     NS_DECL_RDFIDATASOURCE
00378 
00379 protected:
00380     static PLDHashOperator PR_CALLBACK
00381     SweepForwardArcsEntries(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00382                             PRUint32 aNumber, void* aArg);
00383 
00384 public:
00385     // Implementation methods
00386     Assertion*
00387     GetForwardArcs(nsIRDFResource* u) {
00388         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mForwardArcs, u, PL_DHASH_LOOKUP);
00389         return PL_DHASH_ENTRY_IS_BUSY(hdr)
00390             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
00391             : nsnull; }
00392 
00393     Assertion*
00394     GetReverseArcs(nsIRDFNode* v) {
00395         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mReverseArcs, v, PL_DHASH_LOOKUP);
00396         return PL_DHASH_ENTRY_IS_BUSY(hdr)
00397             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
00398             : nsnull; }
00399 
00400     void
00401     SetForwardArcs(nsIRDFResource* u, Assertion* as) {
00402         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mForwardArcs, u,
00403                                                     as ? PL_DHASH_ADD : PL_DHASH_REMOVE);
00404         if (as && hdr) {
00405             Entry* entry = NS_REINTERPRET_CAST(Entry*, hdr);
00406             entry->mNode = u;
00407             entry->mAssertions = as;
00408         } }
00409 
00410     void
00411     SetReverseArcs(nsIRDFNode* v, Assertion* as) {
00412         PLDHashEntryHdr* hdr = PL_DHashTableOperate(&mReverseArcs, v,
00413                                                     as ? PL_DHASH_ADD : PL_DHASH_REMOVE);
00414         if (as && hdr) {
00415             Entry* entry = NS_REINTERPRET_CAST(Entry*, hdr);
00416             entry->mNode = v;
00417             entry->mAssertions = as;
00418         } }
00419 
00420 #ifdef PR_LOGGING
00421     void
00422     LogOperation(const char* aOperation,
00423                  nsIRDFResource* asource,
00424                  nsIRDFResource* aProperty,
00425                  nsIRDFNode* aTarget,
00426                  PRBool aTruthValue = PR_TRUE);
00427 #endif
00428 
00429     PRBool  mPropagateChanges;
00430 };
00431 
00432 //----------------------------------------------------------------------
00433 //
00434 // InMemoryAssertionEnumeratorImpl
00435 //
00436 
00440 class InMemoryAssertionEnumeratorImpl : public nsISimpleEnumerator
00441 {
00442 private:
00443     InMemoryDataSource* mDataSource;
00444     nsIRDFResource* mSource;
00445     nsIRDFResource* mProperty;
00446     nsIRDFNode*     mTarget;
00447     nsIRDFNode*     mValue;
00448     PRInt32         mCount;
00449     PRBool          mTruthValue;
00450     Assertion*      mNextAssertion;
00451     nsCOMPtr<nsISupportsArray> mHashArcs;
00452 
00453     // Hide so that only Create() and Destroy() can be used to
00454     // allocate and deallocate from the heap
00455     static void* operator new(size_t) CPP_THROW_NEW { return 0; }
00456     static void operator delete(void*, size_t) {}
00457 
00458     InMemoryAssertionEnumeratorImpl(InMemoryDataSource* aDataSource,
00459                                     nsIRDFResource* aSource,
00460                                     nsIRDFResource* aProperty,
00461                                     nsIRDFNode* aTarget,
00462                                     PRBool aTruthValue);
00463 
00464     virtual ~InMemoryAssertionEnumeratorImpl();
00465 
00466 public:
00467     static InMemoryAssertionEnumeratorImpl*
00468     Create(InMemoryDataSource* aDataSource,
00469            nsIRDFResource* aSource,
00470            nsIRDFResource* aProperty,
00471            nsIRDFNode* aTarget,
00472            PRBool aTruthValue) {
00473         void* place = aDataSource->mAllocator.Alloc(sizeof(InMemoryAssertionEnumeratorImpl));
00474         return place
00475             ? ::new (place) InMemoryAssertionEnumeratorImpl(aDataSource,
00476                                                             aSource, aProperty, aTarget,
00477                                                             aTruthValue)
00478             : nsnull; }
00479 
00480     static void
00481     Destroy(InMemoryAssertionEnumeratorImpl* aEnumerator) {
00482         // Keep the datasource alive for the duration of the stack
00483         // frame so its allocator stays valid.
00484         nsCOMPtr<nsIRDFDataSource> kungFuDeathGrip = aEnumerator->mDataSource;
00485 
00486         // Grab the pool from the datasource; since we keep the
00487         // datasource alive, this has to be safe.
00488         nsFixedSizeAllocator& pool = aEnumerator->mDataSource->mAllocator;
00489         aEnumerator->~InMemoryAssertionEnumeratorImpl();
00490         pool.Free(aEnumerator, sizeof(*aEnumerator)); }
00491 
00492     // nsISupports interface
00493     NS_DECL_ISUPPORTS
00494    
00495     // nsISimpleEnumerator interface
00496     NS_DECL_NSISIMPLEENUMERATOR
00497 };
00498 
00500 
00501 
00502 InMemoryAssertionEnumeratorImpl::InMemoryAssertionEnumeratorImpl(
00503                  InMemoryDataSource* aDataSource,
00504                  nsIRDFResource* aSource,
00505                  nsIRDFResource* aProperty,
00506                  nsIRDFNode* aTarget,
00507                  PRBool aTruthValue)
00508     : mDataSource(aDataSource),
00509       mSource(aSource),
00510       mProperty(aProperty),
00511       mTarget(aTarget),
00512       mValue(nsnull),
00513       mCount(0),
00514       mTruthValue(aTruthValue),
00515       mNextAssertion(nsnull)
00516 {
00517     NS_ADDREF(mDataSource);
00518     NS_IF_ADDREF(mSource);
00519     NS_ADDREF(mProperty);
00520     NS_IF_ADDREF(mTarget);
00521 
00522     if (mSource) {
00523         mNextAssertion = mDataSource->GetForwardArcs(mSource);
00524 
00525         if (mNextAssertion && mNextAssertion->mHashEntry) {
00526             // its our magical HASH_ENTRY forward hash for assertions
00527             PLDHashEntryHdr* hdr = PL_DHashTableOperate(mNextAssertion->u.hash.mPropertyHash,
00528                 aProperty, PL_DHASH_LOOKUP);
00529             mNextAssertion = PL_DHASH_ENTRY_IS_BUSY(hdr)
00530                 ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
00531                 : nsnull;
00532         }
00533     }
00534     else {
00535         mNextAssertion = mDataSource->GetReverseArcs(mTarget);
00536     }
00537 
00538     // Add an owning reference from the enumerator
00539     if (mNextAssertion)
00540         mNextAssertion->AddRef();
00541 }
00542 
00543 InMemoryAssertionEnumeratorImpl::~InMemoryAssertionEnumeratorImpl()
00544 {
00545 #ifdef DEBUG_REFS
00546     --gInstanceCount;
00547     fprintf(stdout, "%d - RDF: InMemoryAssertionEnumeratorImpl\n", gInstanceCount);
00548 #endif
00549 
00550     if (mNextAssertion)
00551         mNextAssertion->Release(mDataSource->mAllocator);
00552 
00553     NS_IF_RELEASE(mDataSource);
00554     NS_IF_RELEASE(mSource);
00555     NS_IF_RELEASE(mProperty);
00556     NS_IF_RELEASE(mTarget);
00557     NS_IF_RELEASE(mValue);
00558 }
00559 
00560 NS_IMPL_ADDREF(InMemoryAssertionEnumeratorImpl)
00561 NS_IMPL_RELEASE_WITH_DESTROY(InMemoryAssertionEnumeratorImpl, Destroy(this))
00562 NS_IMPL_QUERY_INTERFACE1(InMemoryAssertionEnumeratorImpl, nsISimpleEnumerator)
00563 
00564 NS_IMETHODIMP
00565 InMemoryAssertionEnumeratorImpl::HasMoreElements(PRBool* aResult)
00566 {
00567     if (mValue) {
00568         *aResult = PR_TRUE;
00569         return NS_OK;
00570     }
00571 
00572     while (mNextAssertion) {
00573         PRBool foundIt = PR_FALSE;
00574         if ((mProperty == mNextAssertion->u.as.mProperty) &&
00575             (mTruthValue == mNextAssertion->u.as.mTruthValue)) {
00576             if (mSource) {
00577                 mValue = mNextAssertion->u.as.mTarget;
00578                 NS_ADDREF(mValue);
00579             }
00580             else {
00581                 mValue = mNextAssertion->mSource;
00582                 NS_ADDREF(mValue);
00583             }
00584             foundIt = PR_TRUE;
00585         }
00586 
00587         // Remember the last assertion we were holding on to
00588         Assertion* as = mNextAssertion;
00589 
00590         // iterate
00591         mNextAssertion = (mSource) ? mNextAssertion->mNext : mNextAssertion->u.as.mInvNext;
00592 
00593         // grab an owning reference from the enumerator to the next assertion
00594         if (mNextAssertion)
00595             mNextAssertion->AddRef();
00596 
00597         // ...and release the reference from the enumerator to the old one.
00598         as->Release(mDataSource->mAllocator);
00599 
00600         if (foundIt) {
00601             *aResult = PR_TRUE;
00602             return NS_OK;
00603         }
00604     }
00605 
00606     *aResult = PR_FALSE;
00607     return NS_OK;
00608 }
00609 
00610 
00611 NS_IMETHODIMP
00612 InMemoryAssertionEnumeratorImpl::GetNext(nsISupports** aResult)
00613 {
00614     nsresult rv;
00615 
00616     PRBool hasMore;
00617     rv = HasMoreElements(&hasMore);
00618     if (NS_FAILED(rv)) return rv;
00619 
00620     if (! hasMore)
00621         return NS_ERROR_UNEXPECTED;
00622 
00623     // Don't AddRef: we "transfer" ownership to the caller
00624     *aResult = mValue;
00625     mValue = nsnull;
00626 
00627     return NS_OK;
00628 }
00629 
00631 //
00632 
00641 class InMemoryArcsEnumeratorImpl : public nsISimpleEnumerator
00642 {
00643 private:
00644     // Hide so that only Create() and Destroy() can be used to
00645     // allocate and deallocate from the heap
00646     static void* operator new(size_t) CPP_THROW_NEW { return 0; }
00647     static void operator delete(void*, size_t) {}
00648 
00649     InMemoryDataSource* mDataSource;
00650     nsIRDFResource*     mSource;
00651     nsIRDFNode*         mTarget;
00652     nsAutoVoidArray     mAlreadyReturned;
00653     nsIRDFResource*     mCurrent;
00654     Assertion*          mAssertion;
00655     nsCOMPtr<nsISupportsArray> mHashArcs;
00656 
00657     InMemoryArcsEnumeratorImpl(InMemoryDataSource* aDataSource,
00658                                nsIRDFResource* aSource,
00659                                nsIRDFNode* aTarget);
00660 
00661     virtual ~InMemoryArcsEnumeratorImpl();
00662 
00663     static PLDHashOperator PR_CALLBACK
00664     ArcEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00665                        PRUint32 aNumber, void* aArg);
00666 
00667 public:
00668     // nsISupports interface
00669     NS_DECL_ISUPPORTS
00670 
00671     // nsISimpleEnumerator interface
00672     NS_DECL_NSISIMPLEENUMERATOR
00673 
00674     static InMemoryArcsEnumeratorImpl*
00675     Create(InMemoryDataSource* aDataSource,
00676            nsIRDFResource* aSource,
00677            nsIRDFNode* aTarget) {
00678         void* place = aDataSource->mAllocator.Alloc(sizeof(InMemoryArcsEnumeratorImpl));
00679         return place
00680             ? ::new (place) InMemoryArcsEnumeratorImpl(aDataSource, aSource, aTarget)
00681             : nsnull; }
00682 
00683     static void
00684     Destroy(InMemoryArcsEnumeratorImpl* aEnumerator) {
00685         // Keep the datasource alive for the duration of the stack
00686         // frame so its allocator stays valid.
00687         nsCOMPtr<nsIRDFDataSource> kungFuDeathGrip = aEnumerator->mDataSource;
00688 
00689         // Grab the pool from the datasource; since we keep the
00690         // datasource alive, this has to be safe.
00691         nsFixedSizeAllocator& pool = aEnumerator->mDataSource->mAllocator;
00692         aEnumerator->~InMemoryArcsEnumeratorImpl();
00693         pool.Free(aEnumerator, sizeof(*aEnumerator)); }
00694 };
00695 
00696 
00697 PLDHashOperator PR_CALLBACK
00698 InMemoryArcsEnumeratorImpl::ArcEnumerator(PLDHashTable* aTable,
00699                                        PLDHashEntryHdr* aHdr,
00700                                        PRUint32 aNumber, void* aArg)
00701 {
00702     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
00703     nsISupportsArray* resources = NS_STATIC_CAST(nsISupportsArray*, aArg);
00704 
00705     resources->AppendElement(entry->mNode);
00706     return PL_DHASH_NEXT;
00707 }
00708 
00709 
00710 InMemoryArcsEnumeratorImpl::InMemoryArcsEnumeratorImpl(InMemoryDataSource* aDataSource,
00711                                                        nsIRDFResource* aSource,
00712                                                        nsIRDFNode* aTarget)
00713     : mDataSource(aDataSource),
00714       mSource(aSource),
00715       mTarget(aTarget),
00716       mCurrent(nsnull)
00717 {
00718     NS_ADDREF(mDataSource);
00719     NS_IF_ADDREF(mSource);
00720     NS_IF_ADDREF(mTarget);
00721 
00722     if (mSource) {
00723         // cast okay because it's a closed system
00724         mAssertion = mDataSource->GetForwardArcs(mSource);
00725 
00726         if (mAssertion && mAssertion->mHashEntry) {
00727             // its our magical HASH_ENTRY forward hash for assertions
00728             nsresult rv = NS_NewISupportsArray(getter_AddRefs(mHashArcs));
00729             if (NS_SUCCEEDED(rv)) {
00730                 PL_DHashTableEnumerate(mAssertion->u.hash.mPropertyHash,
00731                     ArcEnumerator, mHashArcs.get());
00732             }
00733             mAssertion = nsnull;
00734         }
00735     }
00736     else {
00737         mAssertion = mDataSource->GetReverseArcs(mTarget);
00738     }
00739 }
00740 
00741 InMemoryArcsEnumeratorImpl::~InMemoryArcsEnumeratorImpl()
00742 {
00743 #ifdef DEBUG_REFS
00744     --gInstanceCount;
00745     fprintf(stdout, "%d - RDF: InMemoryArcsEnumeratorImpl\n", gInstanceCount);
00746 #endif
00747 
00748     NS_RELEASE(mDataSource);
00749     NS_IF_RELEASE(mSource);
00750     NS_IF_RELEASE(mTarget);
00751     NS_IF_RELEASE(mCurrent);
00752 
00753     for (PRInt32 i = mAlreadyReturned.Count() - 1; i >= 0; --i) {
00754         nsIRDFResource* resource = (nsIRDFResource*) mAlreadyReturned[i];
00755         NS_RELEASE(resource);
00756     }
00757 }
00758 
00759 NS_IMPL_ADDREF(InMemoryArcsEnumeratorImpl)
00760 NS_IMPL_RELEASE_WITH_DESTROY(InMemoryArcsEnumeratorImpl, Destroy(this))
00761 NS_IMPL_QUERY_INTERFACE1(InMemoryArcsEnumeratorImpl, nsISimpleEnumerator)
00762 
00763 NS_IMETHODIMP
00764 InMemoryArcsEnumeratorImpl::HasMoreElements(PRBool* aResult)
00765 {
00766     NS_PRECONDITION(aResult != nsnull, "null ptr");
00767     if (! aResult)
00768         return NS_ERROR_NULL_POINTER;
00769 
00770     if (mCurrent) {
00771         *aResult = PR_TRUE;
00772         return NS_OK;
00773     }
00774 
00775     if (mHashArcs) {
00776         PRUint32    itemCount;
00777         nsresult    rv;
00778         if (NS_FAILED(rv = mHashArcs->Count(&itemCount)))   return(rv);
00779         if (itemCount > 0) {
00780             --itemCount;
00781             mCurrent = NS_STATIC_CAST(nsIRDFResource *,
00782                                       mHashArcs->ElementAt(itemCount));
00783             mHashArcs->RemoveElementAt(itemCount);
00784             *aResult = PR_TRUE;
00785             return NS_OK;
00786         }
00787     }
00788     else
00789         while (mAssertion) {
00790             nsIRDFResource* next = mAssertion->u.as.mProperty;
00791 
00792             // "next" is the property arc we are tentatively going to return
00793             // in a subsequent GetNext() call.  It is important to do two
00794             // things, however, before that can happen:
00795             //   1) Make sure it's not an arc we've already returned.
00796             //   2) Make sure that |mAssertion| is not left pointing to
00797             //      another assertion that has the same property as this one.
00798             // The first is a practical concern; the second a defense against
00799             // an obscure crash and other erratic behavior.  To ensure the
00800             // second condition, skip down the chain until we find the next 
00801             // assertion with a property that doesn't match the current one.
00802             // (All these assertions would be skipped via mAlreadyReturned
00803             // checks anyways; this is even a bit faster.)
00804 
00805             do {
00806                 mAssertion = (mSource ? mAssertion->mNext :
00807                         mAssertion->u.as.mInvNext);
00808             }
00809             while (mAssertion && (next == mAssertion->u.as.mProperty));
00810 
00811             PRBool alreadyReturned = PR_FALSE;
00812             for (PRInt32 i = mAlreadyReturned.Count() - 1; i >= 0; --i) {
00813                 if (mAlreadyReturned[i] == next) {
00814                     alreadyReturned = PR_TRUE;
00815                     break;
00816                 }
00817             }
00818 
00819             if (! alreadyReturned) {
00820                 mCurrent = next;
00821                 NS_ADDREF(mCurrent);
00822                 *aResult = PR_TRUE;
00823                 return NS_OK;
00824             }
00825         }
00826 
00827     *aResult = PR_FALSE;
00828     return NS_OK;
00829 }
00830 
00831 
00832 NS_IMETHODIMP
00833 InMemoryArcsEnumeratorImpl::GetNext(nsISupports** aResult)
00834 {
00835     nsresult rv;
00836 
00837     PRBool hasMore;
00838     rv = HasMoreElements(&hasMore);
00839     if (NS_FAILED(rv)) return rv;
00840 
00841     if (! hasMore)
00842         return NS_ERROR_UNEXPECTED;
00843 
00844     // Add this to the set of things we've already returned so that we
00845     // can ensure uniqueness
00846     NS_ADDREF(mCurrent);
00847     mAlreadyReturned.AppendElement(mCurrent);
00848 
00849     // Don't AddRef: we "transfer" ownership to the caller
00850     *aResult = mCurrent;
00851     mCurrent = nsnull;
00852 
00853     return NS_OK;
00854 }
00855 
00856 
00858 // InMemoryDataSource
00859 
00860 NS_IMETHODIMP
00861 NS_NewRDFInMemoryDataSource(nsISupports* aOuter, const nsIID& aIID, void** aResult)
00862 {
00863     NS_PRECONDITION(aResult != nsnull, "null ptr");
00864     if (! aResult)
00865         return NS_ERROR_NULL_POINTER;
00866     *aResult = nsnull;
00867 
00868     if (aOuter && !aIID.Equals(NS_GET_IID(nsISupports))) {
00869         NS_ERROR("aggregation requires nsISupports");
00870         return NS_ERROR_ILLEGAL_VALUE;
00871     }
00872 
00873     InMemoryDataSource* datasource = new InMemoryDataSource(aOuter);
00874     if (! datasource)
00875         return NS_ERROR_OUT_OF_MEMORY;
00876     NS_ADDREF(datasource);
00877 
00878     nsresult rv = datasource->Init();
00879     if (NS_SUCCEEDED(rv)) {
00880         datasource->fAggregated.AddRef();
00881         rv = datasource->AggregatedQueryInterface(aIID, aResult); // This'll AddRef()
00882         datasource->fAggregated.Release();
00883     }
00884 
00885     NS_RELEASE(datasource);
00886     return rv;
00887 }
00888 
00889 
00890 InMemoryDataSource::InMemoryDataSource(nsISupports* aOuter)
00891     : mNumObservers(0), mReadCount(0)
00892 {
00893     NS_INIT_AGGREGATED(aOuter);
00894 
00895     static const size_t kBucketSizes[] = {
00896         sizeof(Assertion),
00897         sizeof(Entry),
00898         sizeof(InMemoryArcsEnumeratorImpl),
00899         sizeof(InMemoryAssertionEnumeratorImpl) };
00900 
00901     static const PRInt32 kNumBuckets = sizeof(kBucketSizes) / sizeof(size_t);
00902 
00903     // Per news://news.mozilla.org/39BEC105.5090206%40netscape.com
00904     static const PRInt32 kInitialSize = 1024;
00905 
00906     mAllocator.Init("nsInMemoryDataSource", kBucketSizes, kNumBuckets, kInitialSize);
00907 
00908     mForwardArcs.ops = nsnull;
00909     mReverseArcs.ops = nsnull;
00910     mPropagateChanges = PR_TRUE;
00911 }
00912 
00913 
00914 nsresult
00915 InMemoryDataSource::Init()
00916 {
00917     if (!PL_DHashTableInit(&mForwardArcs,
00918                            PL_DHashGetStubOps(),
00919                            nsnull,
00920                            sizeof(Entry),
00921                            PL_DHASH_MIN_SIZE)) {
00922         mForwardArcs.ops = nsnull;
00923         return NS_ERROR_OUT_OF_MEMORY;
00924     }
00925     if (!PL_DHashTableInit(&mReverseArcs,
00926                            PL_DHashGetStubOps(),
00927                            nsnull,
00928                            sizeof(Entry),
00929                            PL_DHASH_MIN_SIZE)) {
00930         mReverseArcs.ops = nsnull;
00931         return NS_ERROR_OUT_OF_MEMORY;
00932     }
00933 
00934 #ifdef PR_LOGGING
00935     if (! gLog)
00936         gLog = PR_NewLogModule("InMemoryDataSource");
00937 #endif
00938 
00939     return NS_OK;
00940 }
00941 
00942 
00943 InMemoryDataSource::~InMemoryDataSource()
00944 {
00945 #ifdef DEBUG_REFS
00946     --gInstanceCount;
00947     fprintf(stdout, "%d - RDF: InMemoryDataSource\n", gInstanceCount);
00948 #endif
00949 
00950     if (mForwardArcs.ops) {
00951         // This'll release all of the Assertion objects that are
00952         // associated with this data source. We only need to do this
00953         // for the forward arcs, because the reverse arcs table
00954         // indexes the exact same set of resources.
00955         PL_DHashTableEnumerate(&mForwardArcs, DeleteForwardArcsEntry, &mAllocator);
00956         PL_DHashTableFinish(&mForwardArcs);
00957     }
00958     if (mReverseArcs.ops)
00959         PL_DHashTableFinish(&mReverseArcs);
00960 
00961     PR_LOG(gLog, PR_LOG_NOTICE,
00962            ("InMemoryDataSource(%p): destroyed.", this));
00963 
00964 }
00965 
00966 PLDHashOperator PR_CALLBACK
00967 InMemoryDataSource::DeleteForwardArcsEntry(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
00968                                            PRUint32 aNumber, void* aArg)
00969 {
00970     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
00971     nsFixedSizeAllocator* allocator = NS_STATIC_CAST(nsFixedSizeAllocator*, aArg);
00972 
00973     Assertion* as = entry->mAssertions;
00974     while (as) {
00975         Assertion* doomed = as;
00976         as = as->mNext;
00977 
00978         // Unlink, and release the datasource's reference.
00979         doomed->mNext = doomed->u.as.mInvNext = nsnull;
00980         doomed->Release(*allocator);
00981     }
00982     return PL_DHASH_NEXT;
00983 }
00984 
00985 
00987 
00988 NS_IMPL_AGGREGATED(InMemoryDataSource)
00989 
00990 NS_IMETHODIMP
00991 InMemoryDataSource::AggregatedQueryInterface(REFNSIID aIID, void** aResult)
00992 {
00993     NS_PRECONDITION(aResult != nsnull, "null ptr");
00994     if (! aResult)
00995         return NS_ERROR_NULL_POINTER;
00996 
00997     if (aIID.Equals(NS_GET_IID(nsISupports))) {
00998         *aResult = NS_STATIC_CAST(nsISupports*, &fAggregated);
00999     }
01000     else if (aIID.Equals(NS_GET_IID(nsIRDFDataSource))) {
01001         *aResult = NS_STATIC_CAST(nsIRDFDataSource*, this);
01002     }
01003     else if (aIID.Equals(NS_GET_IID(nsIRDFInMemoryDataSource))) {
01004         *aResult = NS_STATIC_CAST(nsIRDFInMemoryDataSource*, this);
01005     }
01006     else if (aIID.Equals(NS_GET_IID(nsIRDFPropagatableDataSource))) {
01007         *aResult = NS_STATIC_CAST(nsIRDFPropagatableDataSource*, this);
01008     }
01009     else if (aIID.Equals(NS_GET_IID(nsIRDFPurgeableDataSource))) {
01010         *aResult = NS_STATIC_CAST(nsIRDFPurgeableDataSource*, this);
01011     }
01012     else if (aIID.Equals(NS_GET_IID(rdfIDataSource))) {
01013         *aResult = NS_STATIC_CAST(rdfIDataSource*, this);
01014     }
01015     else {
01016         *aResult = nsnull;
01017         return NS_NOINTERFACE;
01018     }
01019 
01020     NS_ADDREF(NS_STATIC_CAST(nsISupports*, *aResult));
01021     return NS_OK;
01022 }
01023 
01024 
01026 
01027 
01028 #ifdef PR_LOGGING
01029 void
01030 InMemoryDataSource::LogOperation(const char* aOperation,
01031                                  nsIRDFResource* aSource,
01032                                  nsIRDFResource* aProperty,
01033                                  nsIRDFNode* aTarget,
01034                                  PRBool aTruthValue)
01035 {
01036     if (! PR_LOG_TEST(gLog, PR_LOG_NOTICE))
01037         return;
01038 
01039     nsXPIDLCString uri;
01040     aSource->GetValue(getter_Copies(uri));
01041     PR_LogPrint
01042            ("InMemoryDataSource(%p): %s", this, aOperation);
01043 
01044     PR_LogPrint
01045            ("  [(%p)%s]--", aSource, (const char*) uri);
01046 
01047     aProperty->GetValue(getter_Copies(uri));
01048 
01049     char tv = (aTruthValue ? '-' : '!');
01050     PR_LogPrint
01051            ("  --%c[(%p)%s]--", tv, aProperty, (const char*) uri);
01052 
01053     nsCOMPtr<nsIRDFResource> resource;
01054     nsCOMPtr<nsIRDFLiteral> literal;
01055 
01056     if ((resource = do_QueryInterface(aTarget)) != nsnull) {
01057         resource->GetValue(getter_Copies(uri));
01058         PR_LogPrint
01059            ("  -->[(%p)%s]", aTarget, (const char*) uri);
01060     }
01061     else if ((literal = do_QueryInterface(aTarget)) != nsnull) {
01062         nsXPIDLString value;
01063         literal->GetValue(getter_Copies(value));
01064         nsAutoString valueStr(value);
01065         char* valueCStr = ToNewCString(valueStr);
01066 
01067         PR_LogPrint
01068            ("  -->(\"%s\")\n", valueCStr);
01069 
01070         NS_Free(valueCStr);
01071     }
01072     else {
01073         PR_LogPrint
01074            ("  -->(unknown-type)\n");
01075     }
01076 }
01077 #endif
01078 
01079 
01080 NS_IMETHODIMP
01081 InMemoryDataSource::GetURI(char* *uri)
01082 {
01083     NS_PRECONDITION(uri != nsnull, "null ptr");
01084     if (! uri)
01085         return NS_ERROR_NULL_POINTER;
01086 
01087     *uri = nsnull;
01088     return NS_OK;
01089 }
01090 
01091 NS_IMETHODIMP
01092 InMemoryDataSource::GetSource(nsIRDFResource* property,
01093                               nsIRDFNode* target,
01094                               PRBool tv,
01095                               nsIRDFResource** source)
01096 {
01097     NS_PRECONDITION(source != nsnull, "null ptr");
01098     if (! source)
01099         return NS_ERROR_NULL_POINTER;
01100 
01101     NS_PRECONDITION(property != nsnull, "null ptr");
01102     if (! property)
01103         return NS_ERROR_NULL_POINTER;
01104 
01105     NS_PRECONDITION(target != nsnull, "null ptr");
01106     if (! target)
01107         return NS_ERROR_NULL_POINTER;
01108 
01109     for (Assertion* as = GetReverseArcs(target); as; as = as->u.as.mInvNext) {
01110         if ((property == as->u.as.mProperty) && (tv == as->u.as.mTruthValue)) {
01111             *source = as->mSource;
01112             NS_ADDREF(*source);
01113             return NS_OK;
01114         }
01115     }
01116     *source = nsnull;
01117     return NS_RDF_NO_VALUE;
01118 }
01119 
01120 NS_IMETHODIMP
01121 InMemoryDataSource::GetTarget(nsIRDFResource* source,
01122                               nsIRDFResource* property,
01123                               PRBool tv,
01124                               nsIRDFNode** target)
01125 {
01126     NS_PRECONDITION(source != nsnull, "null ptr");
01127     if (! source)
01128         return NS_ERROR_NULL_POINTER;
01129 
01130     NS_PRECONDITION(property != nsnull, "null ptr");
01131     if (! property)
01132         return NS_ERROR_NULL_POINTER;
01133 
01134     NS_PRECONDITION(target != nsnull, "null ptr");
01135     if (! target)
01136         return NS_ERROR_NULL_POINTER;
01137 
01138     Assertion *as = GetForwardArcs(source);
01139     if (as && as->mHashEntry) {
01140         PLDHashEntryHdr* hdr = PL_DHashTableOperate(as->u.hash.mPropertyHash, property, PL_DHASH_LOOKUP);
01141         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
01142             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01143             : nsnull;
01144         while (val) {
01145             if (tv == val->u.as.mTruthValue) {
01146                 *target = val->u.as.mTarget;
01147                 NS_IF_ADDREF(*target);
01148                 return NS_OK;
01149             }
01150             val = val->mNext;
01151         }
01152     }
01153     else
01154     for (; as != nsnull; as = as->mNext) {
01155         if ((property == as->u.as.mProperty) && (tv == (as->u.as.mTruthValue))) {
01156             *target = as->u.as.mTarget;
01157             NS_ADDREF(*target);
01158             return NS_OK;
01159         }
01160     }
01161 
01162     // If we get here, then there was no target with for the specified
01163     // property & truth value.
01164     *target = nsnull;
01165     return NS_RDF_NO_VALUE;
01166 }
01167 
01168 NS_IMETHODIMP
01169 InMemoryDataSource::HasAssertion(nsIRDFResource* source,
01170                                  nsIRDFResource* property,
01171                                  nsIRDFNode* target,
01172                                  PRBool tv,
01173                                  PRBool* hasAssertion)
01174 {
01175     if (! source)
01176         return NS_ERROR_NULL_POINTER;
01177 
01178     if (! property)
01179         return NS_ERROR_NULL_POINTER;
01180 
01181     if (! target)
01182         return NS_ERROR_NULL_POINTER;
01183 
01184     Assertion *as = GetForwardArcs(source);
01185     if (as && as->mHashEntry) {
01186         PLDHashEntryHdr* hdr = PL_DHashTableOperate(as->u.hash.mPropertyHash, property, PL_DHASH_LOOKUP);
01187         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
01188             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01189             : nsnull;
01190         while (val) {
01191             if ((val->u.as.mTarget == target) && (tv == (val->u.as.mTruthValue))) {
01192                 *hasAssertion = PR_TRUE;
01193                 return NS_OK;
01194             }
01195             val = val->mNext;
01196         }
01197     }
01198     else
01199     for (; as != nsnull; as = as->mNext) {
01200         // check target first as its most unique
01201         if (target != as->u.as.mTarget)
01202             continue;
01203 
01204         if (property != as->u.as.mProperty)
01205             continue;
01206 
01207         if (tv != (as->u.as.mTruthValue))
01208             continue;
01209 
01210         // found it!
01211         *hasAssertion = PR_TRUE;
01212         return NS_OK;
01213     }
01214 
01215     // If we get here, we couldn't find the assertion
01216     *hasAssertion = PR_FALSE;
01217     return NS_OK;
01218 }
01219 
01220 NS_IMETHODIMP
01221 InMemoryDataSource::GetSources(nsIRDFResource* aProperty,
01222                                nsIRDFNode* aTarget,
01223                                PRBool aTruthValue,
01224                                nsISimpleEnumerator** aResult)
01225 {
01226     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01227     if (! aProperty)
01228         return NS_ERROR_NULL_POINTER;
01229 
01230     NS_PRECONDITION(aTarget != nsnull, "null ptr");
01231     if (! aTarget)
01232         return NS_ERROR_NULL_POINTER;
01233 
01234     NS_PRECONDITION(aResult != nsnull, "null ptr");
01235     if (! aResult)
01236         return NS_ERROR_NULL_POINTER;
01237 
01238     InMemoryAssertionEnumeratorImpl* result =
01239         InMemoryAssertionEnumeratorImpl::Create(this, nsnull, aProperty,
01240                                                   aTarget, aTruthValue);
01241 
01242     if (! result)
01243         return NS_ERROR_OUT_OF_MEMORY;
01244 
01245     NS_ADDREF(result);
01246     *aResult = result;
01247 
01248     return NS_OK;
01249 }
01250 
01251 NS_IMETHODIMP
01252 InMemoryDataSource::GetTargets(nsIRDFResource* aSource,
01253                                nsIRDFResource* aProperty,
01254                                PRBool aTruthValue,
01255                                nsISimpleEnumerator** aResult)
01256 {
01257     NS_PRECONDITION(aSource != nsnull, "null ptr");
01258     if (! aSource)
01259         return NS_ERROR_NULL_POINTER;
01260     
01261     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01262     if (! aProperty)
01263         return NS_ERROR_NULL_POINTER;
01264 
01265     NS_PRECONDITION(aResult != nsnull, "null ptr");
01266     if (! aResult)
01267         return NS_ERROR_NULL_POINTER;
01268 
01269     InMemoryAssertionEnumeratorImpl* result =
01270         InMemoryAssertionEnumeratorImpl::Create(this, aSource, aProperty,
01271                                                 nsnull, aTruthValue);
01272 
01273     if (! result)
01274         return NS_ERROR_OUT_OF_MEMORY;
01275 
01276     NS_ADDREF(result);
01277     *aResult = result;
01278 
01279     return NS_OK;
01280 }
01281 
01282 
01283 nsresult
01284 InMemoryDataSource::LockedAssert(nsIRDFResource* aSource,
01285                                  nsIRDFResource* aProperty,
01286                                  nsIRDFNode* aTarget,
01287                                  PRBool aTruthValue)
01288 {
01289 #ifdef PR_LOGGING
01290     LogOperation("ASSERT", aSource, aProperty, aTarget, aTruthValue);
01291 #endif
01292 
01293     Assertion* next = GetForwardArcs(aSource);
01294     Assertion* prev = next;
01295     Assertion* as = nsnull;
01296 
01297     PRBool  haveHash = (next) ? next->mHashEntry : PR_FALSE;
01298     if (haveHash) {
01299         PLDHashEntryHdr* hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash, aProperty, PL_DHASH_LOOKUP);
01300         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
01301             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01302             : nsnull;
01303         while (val) {
01304             if (val->u.as.mTarget == aTarget) {
01305                 // Wow, we already had the assertion. Make sure that the
01306                 // truth values are correct and bail.
01307                 val->u.as.mTruthValue = aTruthValue;
01308                 return NS_OK;
01309             }
01310             val = val->mNext;
01311         }
01312     }
01313     else
01314     {
01315         while (next) {
01316             // check target first as its most unique
01317             if (aTarget == next->u.as.mTarget) {
01318                 if (aProperty == next->u.as.mProperty) {
01319                     // Wow, we already had the assertion. Make sure that the
01320                     // truth values are correct and bail.
01321                     next->u.as.mTruthValue = aTruthValue;
01322                     return NS_OK;
01323                 }
01324             }
01325 
01326             prev = next;
01327             next = next->mNext;
01328         }
01329     }
01330 
01331     as = Assertion::Create(mAllocator, aSource, aProperty, aTarget, aTruthValue);
01332     if (! as)
01333         return NS_ERROR_OUT_OF_MEMORY;
01334 
01335     // Add the datasource's owning reference.
01336     as->AddRef();
01337 
01338     if (haveHash)
01339     {
01340         PLDHashEntryHdr* hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash,
01341             aProperty, PL_DHASH_LOOKUP);
01342         Assertion *asRef = PL_DHASH_ENTRY_IS_BUSY(hdr)
01343             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01344             : nsnull;
01345         if (asRef)
01346         {
01347             as->mNext = asRef->mNext;
01348             asRef->mNext = as;
01349         }
01350         else
01351         {
01352             hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash,
01353                                             aProperty, PL_DHASH_ADD);
01354             if (hdr)
01355             {
01356                 Entry* entry = NS_REINTERPRET_CAST(Entry*, hdr);
01357                 entry->mNode = aProperty;
01358                 entry->mAssertions = as;
01359             }
01360         }
01361     }
01362     else
01363     {
01364         // Link it in to the "forward arcs" table
01365         if (!prev) {
01366             SetForwardArcs(aSource, as);
01367         } else {
01368             prev->mNext = as;
01369         }
01370     }
01371 
01372     // Link it in to the "reverse arcs" table
01373 
01374     next = GetReverseArcs(aTarget);
01375     as->u.as.mInvNext = next;
01376     next = as;
01377     SetReverseArcs(aTarget, next);
01378 
01379     return NS_OK;
01380 }
01381 
01382 NS_IMETHODIMP
01383 InMemoryDataSource::Assert(nsIRDFResource* aSource,
01384                            nsIRDFResource* aProperty, 
01385                            nsIRDFNode* aTarget,
01386                            PRBool aTruthValue) 
01387 {
01388     NS_PRECONDITION(aSource != nsnull, "null ptr");
01389     if (! aSource)
01390         return NS_ERROR_NULL_POINTER;
01391 
01392     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01393     if (! aProperty)
01394         return NS_ERROR_NULL_POINTER;
01395 
01396     NS_PRECONDITION(aTarget != nsnull, "null ptr");
01397     if (! aTarget)
01398         return NS_ERROR_NULL_POINTER;
01399 
01400     if (mReadCount) {
01401         NS_WARNING("Writing to InMemoryDataSource during read\n");
01402         return NS_RDF_ASSERTION_REJECTED;
01403     }
01404 
01405     nsresult rv;
01406     rv = LockedAssert(aSource, aProperty, aTarget, aTruthValue);
01407     if (NS_FAILED(rv)) return rv;
01408 
01409     // notify observers
01410     for (PRInt32 i = (PRInt32)mNumObservers - 1; mPropagateChanges && i >= 0; --i) {
01411         nsIRDFObserver* obs = mObservers[i];
01412 
01413         // XXX this should never happen, but it does, and we can't figure out why.
01414         NS_ASSERTION(obs, "observer array corrupted!");
01415         if (! obs)
01416           continue;
01417 
01418         obs->OnAssert(this, aSource, aProperty, aTarget);
01419         // XXX ignore return value?
01420     }
01421 
01422     return NS_RDF_ASSERTION_ACCEPTED;
01423 }
01424 
01425 
01426 nsresult
01427 InMemoryDataSource::LockedUnassert(nsIRDFResource* aSource,
01428                                    nsIRDFResource* aProperty,
01429                                    nsIRDFNode* aTarget)
01430 {
01431 #ifdef PR_LOGGING
01432     LogOperation("UNASSERT", aSource, aProperty, aTarget);
01433 #endif
01434 
01435     Assertion* next = GetForwardArcs(aSource);
01436     Assertion* prev = next;
01437     Assertion* root = next;
01438     Assertion* as = nsnull;
01439     
01440     PRBool  haveHash = (next) ? next->mHashEntry : PR_FALSE;
01441     if (haveHash) {
01442         PLDHashEntryHdr* hdr = PL_DHashTableOperate(next->u.hash.mPropertyHash,
01443             aProperty, PL_DHASH_LOOKUP);
01444         prev = next = PL_DHASH_ENTRY_IS_BUSY(hdr)
01445             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01446             : nsnull;
01447         PRBool first = PR_TRUE;
01448         while (next) {
01449             if (aTarget == next->u.as.mTarget) {
01450                 break;
01451             }
01452             first = PR_FALSE;
01453             prev = next;
01454             next = next->mNext;
01455         }
01456         // We don't even have the assertion, so just bail.
01457         if (!next)
01458             return NS_OK;
01459 
01460         as = next;
01461 
01462         if (first) {
01463             PL_DHashTableRawRemove(root->u.hash.mPropertyHash, hdr);
01464 
01465             if (next && next->mNext) {
01466                 PLDHashEntryHdr* hdr = PL_DHashTableOperate(root->u.hash.mPropertyHash,
01467                                      aProperty, PL_DHASH_ADD);
01468                 if (hdr) {
01469                     Entry* entry = NS_REINTERPRET_CAST(Entry*, hdr);
01470                     entry->mNode = aProperty;
01471                     entry->mAssertions = next->mNext;
01472                 }
01473             }
01474             else {
01475                 // If this second-level hash empties out, clean it up.
01476                 if (!root->u.hash.mPropertyHash->entryCount) {
01477                     Assertion::Destroy(mAllocator, root);
01478                     SetForwardArcs(aSource, nsnull);
01479                 }
01480             }
01481         }
01482         else {
01483             prev->mNext = next->mNext;
01484         }
01485     }
01486     else
01487     {
01488         while (next) {
01489             // check target first as its most unique
01490             if (aTarget == next->u.as.mTarget) {
01491                 if (aProperty == next->u.as.mProperty) {
01492                     if (prev == next) {
01493                         SetForwardArcs(aSource, next->mNext);
01494                     } else {
01495                         prev->mNext = next->mNext;
01496                     }
01497                     as = next;
01498                     break;
01499                 }
01500             }
01501 
01502             prev = next;
01503             next = next->mNext;
01504         }
01505     }
01506     // We don't even have the assertion, so just bail.
01507     if (!as)
01508         return NS_OK;
01509 
01510 #ifdef DEBUG
01511     PRBool foundReverseArc = PR_FALSE;
01512 #endif
01513 
01514     next = prev = GetReverseArcs(aTarget);
01515     while (next) {
01516         if (next == as) {
01517             if (prev == next) {
01518                 SetReverseArcs(aTarget, next->u.as.mInvNext);
01519             } else {
01520                 prev->u.as.mInvNext = next->u.as.mInvNext;
01521             }
01522 #ifdef DEBUG
01523             foundReverseArc = PR_TRUE;
01524 #endif
01525             break;
01526         }
01527         prev = next;
01528         next = next->u.as.mInvNext;
01529     }
01530 
01531 #ifdef DEBUG
01532     NS_ASSERTION(foundReverseArc, "in-memory db corrupted: unable to find reverse arc");
01533 #endif
01534 
01535     // Unlink, and release the datasource's reference
01536     as->mNext = as->u.as.mInvNext = nsnull;
01537     as->Release(mAllocator);
01538 
01539     return NS_OK;
01540 }
01541 
01542 NS_IMETHODIMP
01543 InMemoryDataSource::Unassert(nsIRDFResource* aSource,
01544                              nsIRDFResource* aProperty,
01545                              nsIRDFNode* aTarget)
01546 {
01547     NS_PRECONDITION(aSource != nsnull, "null ptr");
01548     if (! aSource)
01549         return NS_ERROR_NULL_POINTER;
01550 
01551     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01552     if (! aProperty)
01553         return NS_ERROR_NULL_POINTER;
01554 
01555     NS_PRECONDITION(aTarget != nsnull, "null ptr");
01556     if (! aTarget)
01557         return NS_ERROR_NULL_POINTER;
01558 
01559     if (mReadCount) {
01560         NS_WARNING("Writing to InMemoryDataSource during read\n");
01561         return NS_RDF_ASSERTION_REJECTED;
01562     }
01563 
01564     nsresult rv;
01565 
01566     rv = LockedUnassert(aSource, aProperty, aTarget);
01567     if (NS_FAILED(rv)) return rv;
01568 
01569     // Notify the world
01570     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
01571         nsIRDFObserver* obs = mObservers[i];
01572 
01573         // XXX this should never happen, but it does, and we can't figure out why.
01574         NS_ASSERTION(obs, "observer array corrupted!");
01575         if (! obs)
01576           continue;
01577 
01578         obs->OnUnassert(this, aSource, aProperty, aTarget);
01579         // XXX ignore return value?
01580     }
01581 
01582     return NS_RDF_ASSERTION_ACCEPTED;
01583 }
01584 
01585 
01586 NS_IMETHODIMP
01587 InMemoryDataSource::Change(nsIRDFResource* aSource,
01588                            nsIRDFResource* aProperty,
01589                            nsIRDFNode* aOldTarget,
01590                            nsIRDFNode* aNewTarget)
01591 {
01592     NS_PRECONDITION(aSource != nsnull, "null ptr");
01593     if (! aSource)
01594         return NS_ERROR_NULL_POINTER;
01595 
01596     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01597     if (! aProperty)
01598         return NS_ERROR_NULL_POINTER;
01599 
01600     NS_PRECONDITION(aOldTarget != nsnull, "null ptr");
01601     if (! aOldTarget)
01602         return NS_ERROR_NULL_POINTER;
01603 
01604     NS_PRECONDITION(aNewTarget != nsnull, "null ptr");
01605     if (! aNewTarget)
01606         return NS_ERROR_NULL_POINTER;
01607 
01608     if (mReadCount) {
01609         NS_WARNING("Writing to InMemoryDataSource during read\n");
01610         return NS_RDF_ASSERTION_REJECTED;
01611     }
01612 
01613     nsresult rv;
01614 
01615     // XXX We can implement LockedChange() if we decide that this
01616     // is a performance bottleneck.
01617 
01618     rv = LockedUnassert(aSource, aProperty, aOldTarget);
01619     if (NS_FAILED(rv)) return rv;
01620 
01621     rv = LockedAssert(aSource, aProperty, aNewTarget, PR_TRUE);
01622     if (NS_FAILED(rv)) return rv;
01623 
01624     // Notify the world
01625     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
01626         nsIRDFObserver* obs = mObservers[i];
01627 
01628         // XXX this should never happen, but it does, and we can't figure out why.
01629         NS_ASSERTION(obs, "observer array corrupted!");
01630         if (! obs)
01631           continue;
01632 
01633         obs->OnChange(this, aSource, aProperty, aOldTarget, aNewTarget);
01634         // XXX ignore return value?
01635     }
01636 
01637     return NS_RDF_ASSERTION_ACCEPTED;
01638 }
01639 
01640 
01641 NS_IMETHODIMP
01642 InMemoryDataSource::Move(nsIRDFResource* aOldSource,
01643                          nsIRDFResource* aNewSource,
01644                          nsIRDFResource* aProperty,
01645                          nsIRDFNode* aTarget)
01646 {
01647     NS_PRECONDITION(aOldSource != nsnull, "null ptr");
01648     if (! aOldSource)
01649         return NS_ERROR_NULL_POINTER;
01650 
01651     NS_PRECONDITION(aNewSource != nsnull, "null ptr");
01652     if (! aNewSource)
01653         return NS_ERROR_NULL_POINTER;
01654 
01655     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01656     if (! aProperty)
01657         return NS_ERROR_NULL_POINTER;
01658 
01659     NS_PRECONDITION(aTarget != nsnull, "null ptr");
01660     if (! aTarget)
01661         return NS_ERROR_NULL_POINTER;
01662 
01663     if (mReadCount) {
01664         NS_WARNING("Writing to InMemoryDataSource during read\n");
01665         return NS_RDF_ASSERTION_REJECTED;
01666     }
01667 
01668     nsresult rv;
01669 
01670     // XXX We can implement LockedMove() if we decide that this
01671     // is a performance bottleneck.
01672 
01673     rv = LockedUnassert(aOldSource, aProperty, aTarget);
01674     if (NS_FAILED(rv)) return rv;
01675 
01676     rv = LockedAssert(aNewSource, aProperty, aTarget, PR_TRUE);
01677     if (NS_FAILED(rv)) return rv;
01678 
01679     // Notify the world
01680     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
01681         nsIRDFObserver* obs = mObservers[i];
01682 
01683         // XXX this should never happen, but it does, and we can't figure out why.
01684         NS_ASSERTION(obs, "observer array corrupted!");
01685         if (! obs)
01686           continue;
01687 
01688         obs->OnMove(this, aOldSource, aNewSource, aProperty, aTarget);
01689         // XXX ignore return value?
01690     }
01691 
01692     return NS_RDF_ASSERTION_ACCEPTED;
01693 }
01694 
01695 
01696 NS_IMETHODIMP
01697 InMemoryDataSource::AddObserver(nsIRDFObserver* aObserver)
01698 {
01699     NS_PRECONDITION(aObserver != nsnull, "null ptr");
01700     if (! aObserver)
01701         return NS_ERROR_NULL_POINTER;
01702 
01703     mObservers.AppendObject(aObserver);
01704     mNumObservers = mObservers.Count();
01705 
01706     return NS_OK;
01707 }
01708 
01709 NS_IMETHODIMP
01710 InMemoryDataSource::RemoveObserver(nsIRDFObserver* aObserver)
01711 {
01712     NS_PRECONDITION(aObserver != nsnull, "null ptr");
01713     if (! aObserver)
01714         return NS_ERROR_NULL_POINTER;
01715 
01716     mObservers.RemoveObject(aObserver);
01717     // note: use Count() instead of just decrementing
01718     // in case aObserver wasn't in list, for example
01719     mNumObservers = mObservers.Count();
01720 
01721     return NS_OK;
01722 }
01723 
01724 NS_IMETHODIMP 
01725 InMemoryDataSource::HasArcIn(nsIRDFNode *aNode, nsIRDFResource *aArc, PRBool *result)
01726 {
01727     Assertion* ass = GetReverseArcs(aNode);
01728     while (ass) {
01729         nsIRDFResource* elbow = ass->u.as.mProperty;
01730         if (elbow == aArc) {
01731             *result = PR_TRUE;
01732             return NS_OK;
01733         }
01734         ass = ass->u.as.mInvNext;
01735     }
01736     *result = PR_FALSE;
01737     return NS_OK;
01738 }
01739 
01740 NS_IMETHODIMP 
01741 InMemoryDataSource::HasArcOut(nsIRDFResource *aSource, nsIRDFResource *aArc, PRBool *result)
01742 {
01743     Assertion* ass = GetForwardArcs(aSource);
01744     if (ass && ass->mHashEntry) {
01745         PLDHashEntryHdr* hdr = PL_DHashTableOperate(ass->u.hash.mPropertyHash,
01746             aArc, PL_DHASH_LOOKUP);
01747         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
01748             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01749             : nsnull;
01750         if (val) {
01751             *result = PR_TRUE;
01752             return NS_OK;
01753         }
01754         ass = ass->mNext;
01755     }
01756     while (ass) {
01757         nsIRDFResource* elbow = ass->u.as.mProperty;
01758         if (elbow == aArc) {
01759             *result = PR_TRUE;
01760             return NS_OK;
01761         }
01762         ass = ass->mNext;
01763     }
01764     *result = PR_FALSE;
01765     return NS_OK;
01766 }
01767 
01768 NS_IMETHODIMP
01769 InMemoryDataSource::ArcLabelsIn(nsIRDFNode* aTarget, nsISimpleEnumerator** aResult)
01770 {
01771     NS_PRECONDITION(aTarget != nsnull, "null ptr");
01772     if (! aTarget)
01773         return NS_ERROR_NULL_POINTER;
01774 
01775     InMemoryArcsEnumeratorImpl* result =
01776         InMemoryArcsEnumeratorImpl::Create(this, nsnull, aTarget);
01777 
01778     if (! result)
01779         return NS_ERROR_OUT_OF_MEMORY;
01780 
01781     NS_ADDREF(result);
01782     *aResult = result;
01783 
01784     return NS_OK;
01785 }
01786 
01787 NS_IMETHODIMP
01788 InMemoryDataSource::ArcLabelsOut(nsIRDFResource* aSource, nsISimpleEnumerator** aResult)
01789 {
01790     NS_PRECONDITION(aSource != nsnull, "null ptr");
01791     if (! aSource)
01792         return NS_ERROR_NULL_POINTER;
01793 
01794     InMemoryArcsEnumeratorImpl* result =
01795         InMemoryArcsEnumeratorImpl::Create(this, aSource, nsnull);
01796 
01797     if (! result)
01798         return NS_ERROR_OUT_OF_MEMORY;
01799 
01800     NS_ADDREF(result);
01801     *aResult = result;
01802 
01803     return NS_OK;
01804 }
01805 
01806 PLDHashOperator PR_CALLBACK
01807 InMemoryDataSource::ResourceEnumerator(PLDHashTable* aTable,
01808                                        PLDHashEntryHdr* aHdr,
01809                                        PRUint32 aNumber, void* aArg)
01810 {
01811     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
01812     nsISupportsArray* resources = NS_STATIC_CAST(nsISupportsArray*, aArg);
01813 
01814     resources->AppendElement(entry->mNode);
01815     return PL_DHASH_NEXT;
01816 }
01817 
01818 
01819 NS_IMETHODIMP
01820 InMemoryDataSource::GetAllResources(nsISimpleEnumerator** aResult)
01821 {
01822     nsresult rv;
01823 
01824     nsCOMPtr<nsISupportsArray> values;
01825     rv = NS_NewISupportsArray(getter_AddRefs(values));
01826     if (NS_FAILED(rv)) return rv;
01827 
01828     // Enumerate all of our entries into an nsISupportsArray.
01829     PL_DHashTableEnumerate(&mForwardArcs, ResourceEnumerator, values.get());
01830 
01831     *aResult = new nsArrayEnumerator(values);
01832     if (! *aResult)
01833         return NS_ERROR_OUT_OF_MEMORY;
01834 
01835     NS_ADDREF(*aResult);
01836     return NS_OK;
01837 }
01838 
01839 NS_IMETHODIMP
01840 InMemoryDataSource::GetAllCmds(nsIRDFResource* source,
01841                                nsISimpleEnumerator/*<nsIRDFResource>*/** commands)
01842 {
01843     return(NS_NewEmptyEnumerator(commands));
01844 }
01845 
01846 NS_IMETHODIMP
01847 InMemoryDataSource::IsCommandEnabled(nsISupportsArray/*<nsIRDFResource>*/* aSources,
01848                                      nsIRDFResource*   aCommand,
01849                                      nsISupportsArray/*<nsIRDFResource>*/* aArguments,
01850                                      PRBool* aResult)
01851 {
01852     *aResult = PR_FALSE;
01853     return NS_OK;
01854 }
01855 
01856 NS_IMETHODIMP
01857 InMemoryDataSource::DoCommand(nsISupportsArray/*<nsIRDFResource>*/* aSources,
01858                               nsIRDFResource*   aCommand,
01859                               nsISupportsArray/*<nsIRDFResource>*/* aArguments)
01860 {
01861     return NS_OK;
01862 }
01863 
01864 NS_IMETHODIMP
01865 InMemoryDataSource::BeginUpdateBatch()
01866 {
01867     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
01868         nsIRDFObserver* obs = mObservers[i];
01869         obs->OnBeginUpdateBatch(this);
01870     }
01871     return NS_OK;
01872 }
01873 
01874 NS_IMETHODIMP
01875 InMemoryDataSource::EndUpdateBatch()
01876 {
01877     for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
01878         nsIRDFObserver* obs = mObservers[i];
01879         obs->OnEndUpdateBatch(this);
01880     }
01881     return NS_OK;
01882 }
01883 
01884 
01885 
01887 // nsIRDFInMemoryDataSource methods
01888 
01889 NS_IMETHODIMP
01890 InMemoryDataSource::EnsureFastContainment(nsIRDFResource* aSource)
01891 {
01892     Assertion *as = GetForwardArcs(aSource);
01893     PRBool  haveHash = (as) ? as->mHashEntry : PR_FALSE;
01894     
01895     // if its already a hash, then nothing to do
01896     if (haveHash)   return(NS_OK);
01897 
01898     // convert aSource in forward hash into a hash
01899     Assertion *hashAssertion = Assertion::Create(mAllocator, aSource);
01900     NS_ASSERTION(hashAssertion, "unable to Assertion::Create");
01901     if (!hashAssertion) return(NS_ERROR_OUT_OF_MEMORY);
01902 
01903     // Add the datasource's owning reference.
01904     hashAssertion->AddRef();
01905 
01906     register Assertion *first = GetForwardArcs(aSource);
01907     SetForwardArcs(aSource, hashAssertion);
01908 
01909     // mutate references of existing forward assertions into this hash
01910     PLDHashTable *table = hashAssertion->u.hash.mPropertyHash;
01911     Assertion *nextRef;
01912     while(first) {
01913         nextRef = first->mNext;
01914         nsIRDFResource *prop = first->u.as.mProperty;
01915 
01916         PLDHashEntryHdr* hdr = PL_DHashTableOperate(table,
01917             prop, PL_DHASH_LOOKUP);
01918         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
01919             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01920             : nsnull;
01921         if (val) {
01922             first->mNext = val->mNext;
01923             val->mNext = first;
01924         }
01925         else {
01926             PLDHashEntryHdr* hdr = PL_DHashTableOperate(table,
01927                                             prop, PL_DHASH_ADD);
01928             if (hdr) {
01929                 Entry* entry = NS_REINTERPRET_CAST(Entry*, hdr);
01930                 entry->mNode = prop;
01931                 entry->mAssertions = first;
01932                 first->mNext = nsnull;
01933             }
01934         }
01935         first = nextRef;
01936     }
01937     return(NS_OK);
01938 }
01939 
01940 
01942 // nsIRDFPropagatableDataSource methods
01943 NS_IMETHODIMP
01944 InMemoryDataSource::GetPropagateChanges(PRBool* aPropagateChanges)
01945 {
01946     *aPropagateChanges = mPropagateChanges;
01947     return NS_OK;
01948 }
01949 
01950 NS_IMETHODIMP
01951 InMemoryDataSource::SetPropagateChanges(PRBool aPropagateChanges)
01952 {
01953     mPropagateChanges = aPropagateChanges;
01954     return NS_OK;
01955 }
01956 
01957 
01959 // nsIRDFPurgeableDataSource methods
01960 
01961 NS_IMETHODIMP
01962 InMemoryDataSource::Mark(nsIRDFResource* aSource,
01963                          nsIRDFResource* aProperty,
01964                          nsIRDFNode* aTarget,
01965                          PRBool aTruthValue,
01966                          PRBool* aDidMark)
01967 {
01968     NS_PRECONDITION(aSource != nsnull, "null ptr");
01969     if (! aSource)
01970         return NS_ERROR_NULL_POINTER;
01971 
01972     NS_PRECONDITION(aProperty != nsnull, "null ptr");
01973     if (! aProperty)
01974         return NS_ERROR_NULL_POINTER;
01975 
01976     NS_PRECONDITION(aTarget != nsnull, "null ptr");
01977     if (! aTarget)
01978         return NS_ERROR_NULL_POINTER;
01979 
01980     Assertion *as = GetForwardArcs(aSource);
01981     if (as && as->mHashEntry) {
01982         PLDHashEntryHdr* hdr = PL_DHashTableOperate(as->u.hash.mPropertyHash,
01983             aProperty, PL_DHASH_LOOKUP);
01984         Assertion* val = PL_DHASH_ENTRY_IS_BUSY(hdr)
01985             ? NS_REINTERPRET_CAST(Entry*, hdr)->mAssertions
01986             : nsnull;
01987         while (val) {
01988             if ((val->u.as.mTarget == aTarget) &&
01989                 (aTruthValue == (val->u.as.mTruthValue))) {
01990 
01991                 // found it! so mark it.
01992                 as->Mark();
01993                 *aDidMark = PR_TRUE;
01994 
01995 #ifdef PR_LOGGING
01996                 LogOperation("MARK", aSource, aProperty, aTarget, aTruthValue);
01997 #endif
01998 
01999                 return NS_OK;
02000             }
02001             val = val->mNext;
02002         }
02003     }
02004     else for (; as != nsnull; as = as->mNext) {
02005         // check target first as its most unique
02006         if (aTarget != as->u.as.mTarget)
02007             continue;
02008 
02009         if (aProperty != as->u.as.mProperty)
02010             continue;
02011 
02012         if (aTruthValue != (as->u.as.mTruthValue))
02013             continue;
02014 
02015         // found it! so mark it.
02016         as->Mark();
02017         *aDidMark = PR_TRUE;
02018 
02019 #ifdef PR_LOGGING
02020         LogOperation("MARK", aSource, aProperty, aTarget, aTruthValue);
02021 #endif
02022 
02023         return NS_OK;
02024     }
02025 
02026     // If we get here, we couldn't find the assertion
02027     *aDidMark = PR_FALSE;
02028     return NS_OK;
02029 }
02030 
02031 
02032 struct SweepInfo {
02033     Assertion* mUnassertList;
02034     PLDHashTable* mReverseArcs;
02035     nsFixedSizeAllocator* mAllocator;
02036 };
02037 
02038 NS_IMETHODIMP
02039 InMemoryDataSource::Sweep()
02040 {
02041     SweepInfo info = { nsnull, &mReverseArcs, &mAllocator};
02042 
02043     // Remove all the assertions, but don't notify anyone.
02044     PL_DHashTableEnumerate(&mForwardArcs, SweepForwardArcsEntries, &info);
02045 
02046     // Now do the notification.
02047     Assertion* as = info.mUnassertList;
02048     while (as) {
02049 #ifdef PR_LOGGING
02050         LogOperation("SWEEP", as->mSource, as->u.as.mProperty, as->u.as.mTarget, as->u.as.mTruthValue);
02051 #endif
02052         if (!(as->mHashEntry))
02053         {
02054             for (PRInt32 i = PRInt32(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
02055                 nsIRDFObserver* obs = mObservers[i];
02056                 // XXXbz other loops over mObservers null-check |obs| here!
02057                 obs->OnUnassert(this, as->mSource, as->u.as.mProperty, as->u.as.mTarget);
02058                 // XXX ignore return value?
02059             }
02060         }
02061 
02062         Assertion* doomed = as;
02063         as = as->mNext;
02064 
02065         // Unlink, and release the datasource's reference
02066         doomed->mNext = doomed->u.as.mInvNext = nsnull;
02067         doomed->Release(mAllocator);
02068     }
02069 
02070     return NS_OK;
02071 }
02072 
02073 
02074 PLDHashOperator PR_CALLBACK
02075 InMemoryDataSource::SweepForwardArcsEntries(PLDHashTable* aTable,
02076                                             PLDHashEntryHdr* aHdr,
02077                                             PRUint32 aNumber, void* aArg)
02078 {
02079     PLDHashOperator result = PL_DHASH_NEXT;
02080     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
02081     SweepInfo* info = NS_STATIC_CAST(SweepInfo*, aArg);
02082 
02083     Assertion* as = entry->mAssertions;
02084     if (as && (as->mHashEntry))
02085     {
02086         // Stuff in sub-hashes must be swept recursively (max depth: 1)
02087         PL_DHashTableEnumerate(as->u.hash.mPropertyHash, 
02088                                SweepForwardArcsEntries, info);
02089 
02090         // If the sub-hash is now empty, clean it up.
02091         if (!as->u.hash.mPropertyHash->entryCount) {
02092             Assertion::Destroy(*info->mAllocator, as);
02093             result = PL_DHASH_REMOVE;
02094         }
02095 
02096         return result;
02097     }
02098 
02099     Assertion* prev = nsnull;
02100     while (as) {
02101         if (as->IsMarked()) {
02102             prev = as;
02103             as->Unmark();
02104             as = as->mNext;
02105         }
02106         else {
02107             // remove from the list of assertions in the datasource
02108             Assertion* next = as->mNext;
02109             if (prev) {
02110                 prev->mNext = next;
02111             }
02112             else {
02113                 // it's the first one. update the hashtable entry.
02114                 entry->mAssertions = next;
02115             }
02116 
02117             // remove from the reverse arcs
02118             PLDHashEntryHdr* hdr =
02119                 PL_DHashTableOperate(info->mReverseArcs, as->u.as.mTarget, PL_DHASH_LOOKUP);
02120             NS_ASSERTION(PL_DHASH_ENTRY_IS_BUSY(hdr), "no assertion in reverse arcs");
02121 
02122             Entry* rentry = NS_REINTERPRET_CAST(Entry*, hdr);
02123             Assertion* ras = rentry->mAssertions;
02124             Assertion* rprev = nsnull;
02125             while (ras) {
02126                 if (ras == as) {
02127                     if (rprev) {
02128                         rprev->u.as.mInvNext = ras->u.as.mInvNext;
02129                     }
02130                     else {
02131                         // it's the first one. update the hashtable entry.
02132                         rentry->mAssertions = ras->u.as.mInvNext;
02133                     }
02134                     as->u.as.mInvNext = nsnull; // for my sanity.
02135                     break;
02136                 }
02137                 rprev = ras;
02138                 ras = ras->u.as.mInvNext;
02139             }
02140 
02141             // Wow, it was the _only_ one. Unhash it.
02142             if (! rentry->mAssertions)
02143             {
02144                 PL_DHashTableRawRemove(info->mReverseArcs, hdr);
02145             }
02146 
02147             // add to the list of assertions to unassert
02148             as->mNext = info->mUnassertList;
02149             info->mUnassertList = as;
02150 
02151             // Advance to the next assertion
02152             as = next;
02153         }
02154     }
02155 
02156     // if no more assertions exist for this resource, then unhash it.
02157     if (! entry->mAssertions)
02158         result = PL_DHASH_REMOVE;
02159 
02160     return result;
02161 }
02162 
02164 // rdfIDataSource methods
02165 
02166 class VisitorClosure
02167 {
02168 public:
02169     VisitorClosure(rdfITripleVisitor* aVisitor) :
02170         mVisitor(aVisitor),
02171         mRv(NS_OK)
02172     {};
02173     rdfITripleVisitor* mVisitor;
02174     nsresult mRv;
02175 };
02176 
02177 PLDHashOperator PR_CALLBACK
02178 SubjectEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
02179                   PRUint32 aNumber, void* aArg) {
02180     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
02181     VisitorClosure* closure = NS_STATIC_CAST(VisitorClosure*, aArg);
02182 
02183     nsresult rv;
02184     nsCOMPtr<nsIRDFNode> subject = do_QueryInterface(entry->mNode, &rv);
02185     NS_ENSURE_SUCCESS(rv, PL_DHASH_NEXT);
02186 
02187     closure->mRv = closure->mVisitor->Visit(subject, nsnull, nsnull, PR_TRUE);
02188     if (NS_FAILED(closure->mRv) || closure->mRv == NS_RDF_STOP_VISIT)
02189         return PL_DHASH_STOP;
02190 
02191     return PL_DHASH_NEXT;
02192 }
02193 
02194 NS_IMETHODIMP
02195 InMemoryDataSource::VisitAllSubjects(rdfITripleVisitor *aVisitor)
02196 {
02197     // Lock datasource against writes
02198     ++mReadCount;
02199 
02200     // Enumerate all of our entries into an nsISupportsArray.
02201     VisitorClosure cls(aVisitor);
02202     PL_DHashTableEnumerate(&mForwardArcs, SubjectEnumerator, &cls);
02203 
02204     // Unlock datasource
02205     --mReadCount;
02206 
02207     return cls.mRv;
02208 } 
02209 
02210 class TriplesInnerClosure
02211 {
02212 public:
02213     TriplesInnerClosure(nsIRDFNode* aSubject, VisitorClosure* aClosure) :
02214         mSubject(aSubject), mOuter(aClosure) {};
02215     nsIRDFNode* mSubject;
02216     VisitorClosure* mOuter;
02217 };
02218 
02219 PLDHashOperator PR_CALLBACK
02220 TriplesInnerEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
02221                   PRUint32 aNumber, void* aArg) {
02222     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
02223     Assertion* assertion = entry->mAssertions;
02224     TriplesInnerClosure* closure = 
02225         NS_STATIC_CAST(TriplesInnerClosure*, aArg);
02226     while (assertion) {
02227         NS_ASSERTION(!assertion->mHashEntry, "shouldn't have to hashes");
02228         VisitorClosure* cls = closure->mOuter;
02229         cls->mRv = cls->mVisitor->Visit(closure->mSubject,
02230                                         assertion->u.as.mProperty,
02231                                         assertion->u.as.mTarget,
02232                                         assertion->u.as.mTruthValue);
02233         if (NS_FAILED(cls->mRv) || cls->mRv == NS_RDF_STOP_VISIT) {
02234             return PL_DHASH_STOP;
02235         }
02236         assertion = assertion->mNext;
02237     }
02238     return PL_DHASH_NEXT;
02239 }
02240 PLDHashOperator PR_CALLBACK
02241 TriplesEnumerator(PLDHashTable* aTable, PLDHashEntryHdr* aHdr,
02242                   PRUint32 aNumber, void* aArg) {
02243     Entry* entry = NS_REINTERPRET_CAST(Entry*, aHdr);
02244     VisitorClosure* closure = NS_STATIC_CAST(VisitorClosure*, aArg);
02245 
02246     nsresult rv;
02247     nsCOMPtr<nsIRDFNode> subject = do_QueryInterface(entry->mNode, &rv);
02248     NS_ENSURE_SUCCESS(rv, PL_DHASH_NEXT);
02249 
02250     if (entry->mAssertions->mHashEntry) {
02251         TriplesInnerClosure cls(subject, closure);
02252         PL_DHashTableEnumerate(entry->mAssertions->u.hash.mPropertyHash,
02253                                TriplesInnerEnumerator, &cls);
02254         if (NS_FAILED(closure->mRv)) {
02255             return PL_DHASH_STOP;
02256         }
02257         return PL_DHASH_NEXT;
02258     }
02259     Assertion* assertion = entry->mAssertions;
02260     while (assertion) {
02261         NS_ASSERTION(!assertion->mHashEntry, "shouldn't have to hashes");
02262         closure->mRv = closure->mVisitor->Visit(subject,
02263                                                 assertion->u.as.mProperty,
02264                                                 assertion->u.as.mTarget,
02265                                                 assertion->u.as.mTruthValue);
02266         if (NS_FAILED(closure->mRv) || closure->mRv == NS_RDF_STOP_VISIT) {
02267             return PL_DHASH_STOP;
02268         }
02269         assertion = assertion->mNext;
02270     }
02271     return PL_DHASH_NEXT;
02272 }
02273 NS_IMETHODIMP
02274 InMemoryDataSource::VisitAllTriples(rdfITripleVisitor *aVisitor)
02275 {
02276     // Lock datasource against writes
02277     ++mReadCount;
02278 
02279     // Enumerate all of our entries into an nsISupportsArray.
02280     VisitorClosure cls(aVisitor);
02281     PL_DHashTableEnumerate(&mForwardArcs, TriplesEnumerator, &cls);
02282 
02283     // Unlock datasource
02284     --mReadCount;
02285 
02286     return cls.mRv;
02287 } 
02288 
02290