Back to index

lightning-sunbird  0.9+nobinonly
nsTemplateMatchSet.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 "nscore.h"
00040 #include "nsTemplateMatchSet.h"
00041 #include "nsTemplateRule.h"
00042 
00043 #ifdef DEBUG_waterson
00044 #define NSTEMPLATEMATCHREFSET_METER // collect stats about match set sizes
00045 #endif
00046 
00047 //----------------------------------------------------------------------
00048 //
00049 // nsTemplateMatchSet
00050 //
00051 
00052 nsTemplateMatchSet::~nsTemplateMatchSet()
00053 {
00054     while (mHead) {
00055         Element* doomed = mHead;
00056         mHead = mHead->mNext;
00057         doomed->mMatch->Release(mPool);
00058         delete doomed;
00059     }
00060 
00061     MOZ_COUNT_DTOR(nsTemplateMatchSet);
00062 }
00063 
00064 //----------------------------------------------------------------------
00065 //
00066 // nsTemplateMatchRefSet
00067 //
00068 
00069 PLDHashTableOps nsTemplateMatchRefSet::gOps = {
00070     PL_DHashAllocTable,
00071     PL_DHashFreeTable,
00072     PL_DHashGetKeyStub,
00073     HashEntry,
00074     MatchEntry,
00075     PL_DHashMoveEntryStub,
00076     PL_DHashClearEntryStub,
00077     PL_DHashFinalizeStub
00078 };
00079 
00080 PLDHashNumber PR_CALLBACK
00081 nsTemplateMatchRefSet::HashEntry(PLDHashTable* aTable, const void* aKey)
00082 {
00083     const nsTemplateMatch* match = NS_STATIC_CAST(const nsTemplateMatch*, aKey);
00084     return PLDHashNumber(Instantiation::Hash(&(match->mInstantiation)))
00085         ^ (PLDHashNumber(NS_PTR_TO_INT32(match->mRule)) >> 2);
00086 }
00087 
00088 PRBool PR_CALLBACK
00089 nsTemplateMatchRefSet::MatchEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aHdr, const void* aKey)
00090 {
00091     const Entry* entry = NS_REINTERPRET_CAST(const Entry*, aHdr);
00092     const nsTemplateMatch* left  = entry->mMatch;
00093     const nsTemplateMatch* right = NS_STATIC_CAST(const nsTemplateMatch*, aKey);
00094     return *left == *right;
00095 }
00096 
00097 #ifdef NSTEMPLATEMATCHREFSET_METER
00098 #include "nsVoidArray.h"
00099 static PRInt32 gCount;
00100 static nsVoidArray gCountDistribution;
00101 #endif
00102 
00103 void
00104 nsTemplateMatchRefSet::Init()
00105 {
00106 #ifdef NSTEMPLATEMATCHREFSET_METER
00107     ++gCount;
00108 #endif
00109     mStorageElements.mInlineMatches.mCount = 0;
00110 }
00111 
00112 void
00113 nsTemplateMatchRefSet::Finish()
00114 {
00115 #ifdef NSTEMPLATEMATCHREFSET_METER
00116     {
00117         PRInt32 entries = mStorageElements.mInlineMatches.mCount <= kMaxInlineMatches
00118             ? PRInt32(mStorageElements.mInlineMatches.mCount)
00119             : mStorageElements.mTable.entryCount;
00120 
00121         PRInt32 count = (entries < gCountDistribution.Count())
00122             ? PRInt32(gCountDistribution[entries])
00123             : 0;
00124 
00125         gCountDistribution.ReplaceElementAt((void*) ++count, entries);
00126 
00127         --gCount;
00128         if (gCount == 0) {
00129             printf("nsTemplateMatchRefSet distribution\n");
00130             for (PRInt32 i = gCountDistribution.Count() - 1; i >= 0; --i)
00131                 printf("%d: %d\n", i, PRInt32(gCountDistribution[i]));
00132         }
00133     }
00134 #endif
00135 
00136     if (mStorageElements.mInlineMatches.mCount > kMaxInlineMatches)
00137         // It's a hashtable, so finish the table properly
00138         PL_DHashTableFinish(&mStorageElements.mTable);
00139 
00140     mStorageElements.mInlineMatches.mCount = 0;
00141 }
00142 
00143 void
00144 nsTemplateMatchRefSet::CopyFrom(const nsTemplateMatchRefSet& aSet)
00145 {
00146     ConstIterator last = aSet.Last();
00147     for (ConstIterator iter = aSet.First(); iter != last; ++iter)
00148         Add(iter.operator->());
00149 }
00150 
00151 PRBool
00152 nsTemplateMatchRefSet::Empty() const
00153 {
00154     PRUint32 count = mStorageElements.mInlineMatches.mCount;
00155     if (count <= kMaxInlineMatches)
00156         return count == 0;
00157 
00158     return mStorageElements.mTable.entryCount == 0;
00159 }
00160 
00161 PRBool
00162 nsTemplateMatchRefSet::Contains(const nsTemplateMatch* aMatch) const
00163 {
00164     PRUint32 count = mStorageElements.mInlineMatches.mCount;
00165     if (count <= kMaxInlineMatches) {
00166         while (PRInt32(--count) >= 0) {
00167             if (*(mStorageElements.mInlineMatches.mEntries[count]) == *aMatch)
00168                 return PR_TRUE;
00169         }
00170 
00171         return PR_FALSE;
00172     }
00173 
00174     PLDHashEntryHdr* hdr =
00175         PL_DHashTableOperate(NS_CONST_CAST(PLDHashTable*, &mStorageElements.mTable), aMatch,
00176                              PL_DHASH_LOOKUP);
00177 
00178     return PL_DHASH_ENTRY_IS_BUSY(hdr);
00179 }
00180 
00181 PRBool
00182 nsTemplateMatchRefSet::Add(const nsTemplateMatch* aMatch)
00183 {
00184     // Cast away const, we assume shared ownership.
00185     nsTemplateMatch* match = NS_CONST_CAST(nsTemplateMatch*, aMatch);
00186 
00187     PRUint32 count = mStorageElements.mInlineMatches.mCount;
00188     if (count < kMaxInlineMatches) {
00189         // There's still room in the inline matches.
00190 
00191         // Check for duplicates
00192         for (PRInt32 i = PRInt32(count) - 1; i >= 0; --i) {
00193             if (*(mStorageElements.mInlineMatches.mEntries[i]) == *aMatch)
00194                 return PR_FALSE;
00195         }
00196 
00197         // Nope. Add it!
00198         mStorageElements.mInlineMatches.mEntries[count] = match;
00199 
00200         ++mStorageElements.mInlineMatches.mCount;
00201         return PR_TRUE;
00202     }
00203 
00204     if (count == kMaxInlineMatches) {
00205         // No room left in inline matches. Fault, and convert to
00206         // hashtable.
00207         nsTemplateMatch* temp[kMaxInlineMatches];
00208         PRInt32 i;
00209 
00210         // Copy pointers to a safe place
00211         for (i = count - 1; i >= 0; --i)
00212             temp[i] = mStorageElements.mInlineMatches.mEntries[i];
00213 
00214         // Clobber the union; we'll treat it as a hashtable now.
00215         if (!PL_DHashTableInit(&mStorageElements.mTable, &gOps, nsnull,
00216                                sizeof(Entry), PL_DHASH_MIN_SIZE)) {
00217             for (i = count - 1; i >= 0; --i)
00218                 mStorageElements.mInlineMatches.mEntries[i] = temp[i];
00219             return PR_FALSE;
00220         }
00221 
00222         // Now that we've table-ized this thing, mCount better be a
00223         // big freaking number, since it's sharing space with a
00224         // pointer to the PLDHashTable's ops.
00225         NS_ASSERTION(mStorageElements.mInlineMatches.mCount > kMaxInlineMatches,
00226                      "wow, I thought it'd be bigger than _that_");
00227 
00228         // Copy the pointers into the hashtable.
00229         for (i = count - 1; i >= 0; --i)
00230             AddToTable(temp[i]);
00231     }
00232 
00233     return AddToTable(match);
00234 }
00235 
00236 PRBool
00237 nsTemplateMatchRefSet::AddToTable(nsTemplateMatch* aMatch)
00238 {
00239     PLDHashEntryHdr* hdr =
00240         PL_DHashTableOperate(&mStorageElements.mTable, aMatch, PL_DHASH_ADD);
00241 
00242     if (hdr) {
00243         Entry* entry = NS_REINTERPRET_CAST(Entry*, hdr);
00244 
00245         if (! entry->mMatch) {
00246             entry->mMatch = aMatch;
00247             return PR_TRUE;
00248         }
00249     }
00250 
00251     return PR_FALSE;
00252 }
00253 
00254 PRBool
00255 nsTemplateMatchRefSet::Remove(const nsTemplateMatch* aMatch)
00256 {
00257     PRBool found = PR_FALSE;
00258 
00259     PRUint32 count = mStorageElements.mInlineMatches.mCount;
00260     if (count <= kMaxInlineMatches) {
00261         nsTemplateMatch** last;
00262 
00263         for (PRUint32 i = 0; i < count; ++i) {
00264             nsTemplateMatch** entry = &mStorageElements.mInlineMatches.mEntries[i];
00265             nsTemplateMatch* match = *entry;
00266 
00267             if (*match == *aMatch) {
00268                 found = PR_TRUE;
00269             }
00270             else if (found)
00271                 *last = match;
00272 
00273             last = entry;
00274         }
00275 
00276         if (found)
00277             --mStorageElements.mInlineMatches.mCount;
00278     }
00279     else {
00280         PLDHashEntryHdr* hdr =
00281             PL_DHashTableOperate(&mStorageElements.mTable, aMatch, PL_DHASH_LOOKUP);
00282 
00283         found = PL_DHASH_ENTRY_IS_BUSY(hdr);
00284 
00285         if (found)
00286             // Remove the match. N.B., we never demote back to a list.
00287             PL_DHashTableOperate(&mStorageElements.mTable, aMatch, PL_DHASH_REMOVE);
00288     }
00289 
00290     return found;
00291 }
00292 
00293 //----------------------------------------------------------------------
00294 //
00295 // ConstIterator
00296 //
00297 
00298 #define ENTRY_IS_LIVE(entry) (PL_DHASH_ENTRY_IS_BUSY(&((entry)->mHdr)) && (entry)->mMatch)
00299 
00300 nsTemplateMatchRefSet::ConstIterator
00301 nsTemplateMatchRefSet::First() const
00302 {
00303     if (mStorageElements.mInlineMatches.mCount <= kMaxInlineMatches)
00304         // XXX C-style cast to avoid gcc-2.7.2.3. bustage
00305         return ConstIterator(this, (nsTemplateMatch**) mStorageElements.mInlineMatches.mEntries);
00306 
00307     Entry* entry = NS_REINTERPRET_CAST(Entry*, mStorageElements.mTable.entryStore);
00308     Entry* limit = entry + PL_DHASH_TABLE_SIZE(&mStorageElements.mTable);
00309     for ( ; entry < limit; ++entry) {
00310         if (ENTRY_IS_LIVE(entry))
00311             break;
00312     }
00313 
00314     return ConstIterator(this, entry);
00315 }
00316 
00317 nsTemplateMatchRefSet::ConstIterator
00318 nsTemplateMatchRefSet::Last() const
00319 {
00320     PRUint32 count = mStorageElements.mInlineMatches.mCount;
00321     if (count <= kMaxInlineMatches) {
00322         // XXX C-style cast to avoid gcc-2.7.2.3 bustage
00323         nsTemplateMatch** first = (nsTemplateMatch**) mStorageElements.mInlineMatches.mEntries;
00324         nsTemplateMatch** limit = first + count;
00325         return ConstIterator(this, limit);
00326     }
00327 
00328     Entry* limit = NS_REINTERPRET_CAST(Entry*, mStorageElements.mTable.entryStore);
00329     limit += PL_DHASH_TABLE_SIZE(&mStorageElements.mTable);
00330     return ConstIterator(this, limit);
00331 }
00332 
00333 void
00334 nsTemplateMatchRefSet::ConstIterator::Next()
00335 {
00336     if (mSet->mStorageElements.mInlineMatches.mCount <= kMaxInlineMatches)
00337         ++mInlineEntry;
00338     else {
00339         const PLDHashTable& table = mSet->mStorageElements.mTable;
00340         Entry* limit = NS_REINTERPRET_CAST(Entry*, table.entryStore);
00341         limit += PL_DHASH_TABLE_SIZE(&table);
00342         while (++mTableEntry < limit) {
00343             if (ENTRY_IS_LIVE(mTableEntry))
00344                 break;
00345         }
00346     }
00347 }
00348 
00349 void
00350 nsTemplateMatchRefSet::ConstIterator::Prev()
00351 {
00352     if (mSet->mStorageElements.mInlineMatches.mCount <= kMaxInlineMatches)
00353         --mInlineEntry;
00354     else {
00355         const PLDHashTable& table = mSet->mStorageElements.mTable;
00356         Entry* limit = NS_REINTERPRET_CAST(Entry*, table.entryStore);
00357         while (--mTableEntry > limit) {
00358             if (ENTRY_IS_LIVE(mTableEntry))
00359                 break;
00360         }
00361     }
00362 }
00363 
00364 PRBool
00365 nsTemplateMatchRefSet::ConstIterator::operator==(const ConstIterator& aConstIterator) const
00366 {
00367     if (mSet != aConstIterator.mSet)
00368         return PR_FALSE;
00369 
00370     PRUint32 count = mSet->mStorageElements.mInlineMatches.mCount;
00371     if (count <= kMaxInlineMatches)
00372         return mInlineEntry == aConstIterator.mInlineEntry;
00373 
00374     return mTableEntry == aConstIterator.mTableEntry;
00375 }