Back to index

lightning-sunbird  0.9+nobinonly
nsConflictSet.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is Mozilla Communicator client code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Chris Waterson <waterson@netscape.com>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "nsConflictSet.h"
00040 #include "nsTemplateRule.h"
00041 
00042 #ifdef PR_LOGGING
00043 PRLogModule* nsConflictSet::gLog;
00044 #endif
00045 
00046 // Allocation operations for the cluster table
00047 PLHashAllocOps nsConflictSet::gClusterAllocOps = {
00048     AllocClusterTable, FreeClusterTable, AllocClusterEntry, FreeClusterEntry };
00049 
00050 // Allocation operations for the support table
00051 PLHashAllocOps nsConflictSet::gSupportAllocOps = {
00052     AllocSupportTable, FreeSupportTable, AllocSupportEntry, FreeSupportEntry };
00053 
00054 // Allocation operations for the binding table
00055 PLHashAllocOps nsConflictSet::gBindingAllocOps = {
00056     AllocBindingTable, FreeBindingTable, AllocBindingEntry, FreeBindingEntry };
00057 
00058 
00059 nsresult
00060 nsConflictSet::Init()
00061 {
00062 #ifdef PR_LOGGING
00063     if (! gLog)
00064         gLog = PR_NewLogModule("nsConflictSet");
00065 #endif
00066 
00067     static const size_t kBucketSizes[] = {
00068         sizeof(ClusterEntry),
00069         sizeof(SupportEntry),
00070         sizeof(BindingEntry),
00071     };
00072 
00073     static const PRInt32 kNumBuckets = sizeof(kBucketSizes) / sizeof(size_t);
00074 
00075     static const PRInt32 kNumResourceElements = 64;
00076 
00077     // Per news://news.mozilla.org/39BEC105.5090206%40netscape.com
00078     static const PRInt32 kInitialSize = 256;
00079 
00080     mPool.Init("nsConflictSet", kBucketSizes, kNumBuckets, kInitialSize);
00081 
00082     mClusters =
00083         PL_NewHashTable(kNumResourceElements /* XXXwaterson we need a way to give a hint? */,
00084                         nsClusterKey::HashClusterKey,
00085                         nsClusterKey::CompareClusterKeys,
00086                         PL_CompareValues,
00087                         &gClusterAllocOps,
00088                         &mPool);
00089 
00090     mSupport =
00091         PL_NewHashTable(kNumResourceElements, /* XXXwaterson need hint */
00092                         HashMemoryElement,
00093                         CompareMemoryElements,
00094                         PL_CompareValues,
00095                         &gSupportAllocOps,
00096                         &mPool);
00097 
00098     mBindingDependencies =
00099         PL_NewHashTable(kNumResourceElements /* XXX arbitrary */,
00100                         HashBindingElement,
00101                         CompareBindingElements,
00102                         PL_CompareValues,
00103                         &gBindingAllocOps,
00104                         &mPool);
00105 
00106     return NS_OK;
00107 }
00108 
00109 
00110 nsresult
00111 nsConflictSet::Destroy()
00112 {
00113     PL_HashTableDestroy(mSupport);
00114     PL_HashTableDestroy(mClusters);
00115     PL_HashTableDestroy(mBindingDependencies);
00116     return NS_OK;
00117 }
00118 
00119 nsresult
00120 nsConflictSet::Add(nsTemplateMatch* aMatch)
00121 {
00122     // Add a match to the conflict set. This involves adding it to
00123     // the cluster table, the support table, and the binding table.
00124 
00125     // add the match to a table indexed by instantiation key
00126     {
00127         nsClusterKey key(aMatch->mInstantiation, aMatch->mRule);
00128 
00129         PLHashNumber hash = key.Hash();
00130         PLHashEntry** hep = PL_HashTableRawLookup(mClusters, hash, &key);
00131 
00132         MatchCluster* cluster;
00133 
00134         if (hep && *hep) {
00135             cluster = NS_REINTERPRET_CAST(MatchCluster*, (*hep)->value);
00136         }
00137         else {
00138             PLHashEntry* he = PL_HashTableRawAdd(mClusters, hep, hash, &key, nsnull);
00139             if (! he)
00140                 return NS_ERROR_OUT_OF_MEMORY;
00141 
00142             ClusterEntry* entry = NS_REINTERPRET_CAST(ClusterEntry*, he);
00143 
00144             // Fixup the key in the hashentry to point to the value
00145             // that the specially-allocated entry contains (rather
00146             // than the value on the stack). Do the same for its
00147             // value.
00148             entry->mHashEntry.key   = &entry->mKey;
00149             entry->mHashEntry.value = cluster = &entry->mCluster;
00150         }
00151 
00152         nsTemplateMatchRefSet& set = cluster->mMatches;
00153         if (! set.Contains(aMatch))
00154             set.Add(aMatch);
00155     }
00156 
00157 
00158     // Add the match to a table indexed by supporting MemoryElement
00159     {
00160         MemoryElementSet::ConstIterator last = aMatch->mInstantiation.mSupport.Last();
00161         for (MemoryElementSet::ConstIterator element = aMatch->mInstantiation.mSupport.First(); element != last; ++element) {
00162             PLHashNumber hash = element->Hash();
00163             PLHashEntry** hep = PL_HashTableRawLookup(mSupport, hash, element.operator->());
00164 
00165             nsTemplateMatchRefSet* set;
00166 
00167             if (hep && *hep) {
00168                 set = NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
00169             }
00170             else {
00171                 PLHashEntry* he = PL_HashTableRawAdd(mSupport, hep, hash, element.operator->(), nsnull);
00172 
00173                 SupportEntry* entry = NS_REINTERPRET_CAST(SupportEntry*, he);
00174                 if (! entry)
00175                     return NS_ERROR_OUT_OF_MEMORY;
00176 
00177                 // Fixup the key and value.
00178                 entry->mHashEntry.key   = entry->mElement;
00179                 entry->mHashEntry.value = &entry->mMatchSet;
00180 
00181                 set = &entry->mMatchSet;
00182             }
00183 
00184             if (! set->Contains(aMatch)) {
00185                 set->Add(aMatch);
00186                 aMatch->AddRef();
00187             }
00188         }
00189     }
00190 
00191     // Add the match to a table indexed by bound MemoryElement
00192     nsResourceSet::ConstIterator last = aMatch->mBindingDependencies.Last();
00193     for (nsResourceSet::ConstIterator dep = aMatch->mBindingDependencies.First(); dep != last; ++dep)
00194         AddBindingDependency(aMatch, *dep);
00195 
00196     return NS_OK;
00197 }
00198 
00199 
00200 nsConflictSet::MatchCluster*
00201 nsConflictSet::GetMatchesForClusterKey(const nsClusterKey& aKey)
00202 {
00203     // Retrieve all the matches in a cluster
00204     return NS_STATIC_CAST(MatchCluster*, PL_HashTableLookup(mClusters, &aKey));
00205 }
00206 
00207 
00208 nsTemplateMatch*
00209 nsConflictSet::GetMatchWithHighestPriority(const MatchCluster* aMatchCluster) const
00210 {
00211     // Find the rule with the "highest priority"; i.e., the rule with
00212     // the lowest value for GetPriority().
00213     //
00214     // XXX if people start writing more than a few matches, we should
00215     // rewrite this to maintain the matches in sorted order, and then
00216     // just pluck the match off the top of the list.
00217     nsTemplateMatch* result = nsnull;
00218     PRInt32 max = PRInt32(PR_BIT(31) - 1);
00219 
00220     const nsTemplateMatchRefSet& set = aMatchCluster->mMatches;
00221     nsTemplateMatchRefSet::ConstIterator last = set.Last();
00222 
00223     for (nsTemplateMatchRefSet::ConstIterator match = set.First(); match != last; ++match) {
00224         PRInt32 priority = match->mRule->GetPriority();
00225         if (priority < max) {
00226             result = NS_CONST_CAST(nsTemplateMatch*, match.operator->());
00227             max = priority;
00228         }
00229     }
00230 
00231     return result;
00232 }
00233 
00234 const nsTemplateMatchRefSet*
00235 nsConflictSet::GetMatchesWithBindingDependency(nsIRDFResource* aResource)
00236 {
00237     // Retrieve all the matches whose bindings depend on the specified resource
00238     return NS_STATIC_CAST(nsTemplateMatchRefSet*, PL_HashTableLookup(mBindingDependencies, aResource));
00239 }
00240 
00241 
00242 void
00243 nsConflictSet::Remove(const MemoryElement& aMemoryElement,
00244                       nsTemplateMatchSet& aNewMatches,
00245                       nsTemplateMatchSet& aRetractedMatches)
00246 {
00247     // Use the memory-element-to-match map to figure out what matches
00248     // will be affected.
00249     PLHashEntry** hep = PL_HashTableRawLookup(mSupport, aMemoryElement.Hash(), &aMemoryElement);
00250 
00251     if (!hep || !*hep)
00252         return;
00253 
00254     // 'set' gets the set of all matches containing the first binding.
00255     nsTemplateMatchRefSet* set =
00256         NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
00257 
00258     // We'll iterate through these matches, only paying attention to
00259     // matches that strictly contain the MemoryElement we're about to
00260     // remove.
00261     nsTemplateMatchRefSet::ConstIterator last = set->Last();
00262     for (nsTemplateMatchRefSet::ConstIterator match = set->First(); match != last; ++match) {
00263         // Note the retraction, so we can compute new matches, later.
00264         aRetractedMatches.Add(match.operator->());
00265 
00266         // Keep the bindings table in sync, as well. Since this match
00267         // is getting nuked, we need to nuke its bindings as well.
00268         nsResourceSet::ConstIterator last = match->mBindingDependencies.Last();
00269         for (nsResourceSet::ConstIterator dep = match->mBindingDependencies.First(); dep != last; ++dep)
00270             RemoveBindingDependency(match.operator->(), *dep);
00271     }
00272 
00273     // Unhash it
00274     PL_HashTableRawRemove(mSupport, hep, *hep);
00275 
00276     // Update the key-to-match map, and see if any new rules have been
00277     // fired as a result of the retraction.
00278     ComputeNewMatches(aNewMatches, aRetractedMatches);
00279 }
00280 
00281 nsresult
00282 nsConflictSet::AddBindingDependency(nsTemplateMatch* aMatch, nsIRDFResource* aResource)
00283 {
00284     // Note a match's dependency on a source resource
00285     PLHashNumber hash = HashBindingElement(aResource);
00286     PLHashEntry** hep = PL_HashTableRawLookup(mBindingDependencies, hash, aResource);
00287 
00288     nsTemplateMatchRefSet* set;
00289 
00290     if (hep && *hep) {
00291         set = NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
00292     }
00293     else {
00294         PLHashEntry* he = PL_HashTableRawAdd(mBindingDependencies, hep, hash, aResource, nsnull);
00295 
00296         BindingEntry* entry = NS_REINTERPRET_CAST(BindingEntry*, he);
00297         if (! entry)
00298             return NS_ERROR_OUT_OF_MEMORY;
00299 
00300         // Fixup the value.
00301         entry->mHashEntry.value = set = &entry->mMatchSet;
00302         
00303     }
00304 
00305     if (! set->Contains(aMatch))
00306         set->Add(aMatch);
00307 
00308     return NS_OK;
00309 }
00310 
00311 nsresult
00312 nsConflictSet::RemoveBindingDependency(nsTemplateMatch* aMatch, nsIRDFResource* aResource)
00313 {
00314     // Remove a match's dependency on a source resource
00315     PLHashNumber hash = HashBindingElement(aResource);
00316     PLHashEntry** hep = PL_HashTableRawLookup(mBindingDependencies, hash, aResource);
00317 
00318     if (hep && *hep) {
00319         nsTemplateMatchRefSet* set = NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
00320 
00321         set->Remove(aMatch);
00322 
00323         if (set->Empty())
00324             PL_HashTableRawRemove(mBindingDependencies, hep, *hep);
00325     }
00326 
00327     return NS_OK;
00328 }
00329 
00330 nsresult
00331 nsConflictSet::ComputeNewMatches(nsTemplateMatchSet& aNewMatches,
00332                                  nsTemplateMatchSet& aRetractedMatches)
00333 {
00334     // Given a set of just-retracted matches, compute the set of new
00335     // matches that have been revealed, updating the key-to-match map
00336     // as we go.
00337     nsTemplateMatchSet::ConstIterator last = aRetractedMatches.Last();
00338     for (nsTemplateMatchSet::ConstIterator retraction = aRetractedMatches.First();
00339          retraction != last;
00340          ++retraction) {
00341         nsClusterKey key(retraction->mInstantiation, retraction->mRule);
00342         PLHashEntry** hep = PL_HashTableRawLookup(mClusters, key.Hash(), &key);
00343 
00344         // XXXwaterson I'd managed to convince myself that this was really
00345         // okay, but now I can't remember why.
00346         //NS_ASSERTION(hep && *hep, "mClusters corrupted");
00347         if (!hep || !*hep)
00348             continue;
00349 
00350         MatchCluster* cluster = NS_REINTERPRET_CAST(MatchCluster*, (*hep)->value);
00351         nsTemplateMatchRefSet& set = cluster->mMatches;
00352 
00353         nsTemplateMatchRefSet::ConstIterator last = set.Last();
00354         for (nsTemplateMatchRefSet::ConstIterator match = set.First(); match != last; ++match) {
00355             if (match->mRule == retraction->mRule) {
00356                 set.Remove(match.operator->()); // N.B., iterator no longer valid!
00357 
00358                 // See if we've revealed another rule that's applicable
00359                 nsTemplateMatch* newmatch =
00360                     GetMatchWithHighestPriority(cluster);
00361 
00362                 if (newmatch)
00363                     aNewMatches.Add(newmatch);
00364 
00365                 break;
00366             }
00367         }
00368 
00369         if (set.Empty())
00370             PL_HashTableRawRemove(mClusters, hep, *hep);
00371     }
00372 
00373     return NS_OK;
00374 }
00375 
00376 
00377 void
00378 nsConflictSet::Clear()
00379 {
00380     Destroy();
00381     Init();
00382 }
00383 
00384 PLHashNumber PR_CALLBACK
00385 nsConflictSet::HashMemoryElement(const void* aMemoryElement)
00386 {
00387     const MemoryElement* element =
00388         NS_STATIC_CAST(const MemoryElement*, aMemoryElement);
00389 
00390     return element->Hash();
00391 }
00392 
00393 PRIntn PR_CALLBACK
00394 nsConflictSet::CompareMemoryElements(const void* aLeft, const void* aRight)
00395 {
00396     const MemoryElement* left =
00397         NS_STATIC_CAST(const MemoryElement*, aLeft);
00398 
00399     const MemoryElement* right =
00400         NS_STATIC_CAST(const MemoryElement*, aRight);
00401 
00402     return *left == *right;
00403 }
00404 
00405 //----------------------------------------------------------------------
00406 //
00407 
00408 void
00409 nsConflictSet::SupportEntry::Destroy(nsFixedSizeAllocator& aPool, SupportEntry* aEntry)
00410 {
00411     // We need to Release() the matches here, because this is where
00412     // we've got access to the pool from which they were
00413     // allocated. Since SupportEntry's dtor is protected, nobody else
00414     // can be creating SupportEntry objects (e.g., on the stack).
00415     nsTemplateMatchRefSet::ConstIterator last = aEntry->mMatchSet.Last();
00416     for (nsTemplateMatchRefSet::ConstIterator iter = aEntry->mMatchSet.First();
00417          iter != last;
00418          ++iter)
00419         iter->Release(aPool);
00420 
00421     aEntry->~SupportEntry();
00422     aPool.Free(aEntry, sizeof(*aEntry));
00423 }