Back to index

lightning-sunbird  0.9+nobinonly
nsElementMap.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 /*
00040 
00041    Maps IDs to elements.
00042 
00043 
00044    To turn on logging for this module, set:
00045 
00046      NS_PR_LOG_MODULES nsElementMap:5
00047 
00048  */
00049 
00050 #include "nsCOMPtr.h"
00051 #include "nsCRT.h"
00052 #include "nsElementMap.h"
00053 #include "nsISupportsArray.h"
00054 #include "nsString.h"
00055 #include "nsIAtom.h"
00056 #include "nsReadableUtils.h"
00057 #include "prlog.h"
00058 
00059 #ifdef PR_LOGGING
00060 static PRLogModuleInfo* gMapLog;
00061 #endif
00062 
00063 static void* PR_CALLBACK AllocTable(void* aPool, PRSize aSize)
00064 {
00065     return new char[aSize];
00066 }
00067 
00068 static void PR_CALLBACK FreeTable(void* aPool, void* aItem)
00069 {
00070     delete[] NS_STATIC_CAST(char*, aItem);
00071 }
00072 
00073 static PLHashEntry* PR_CALLBACK AllocEntry(void* aPool, const void* aKey)
00074 {
00075     nsFixedSizeAllocator* pool = NS_STATIC_CAST(nsFixedSizeAllocator*, aPool);
00076     PLHashEntry* entry = NS_STATIC_CAST(PLHashEntry*, pool->Alloc(sizeof(PLHashEntry)));
00077     return entry;
00078 }
00079 
00080 static void PR_CALLBACK FreeEntry(void* aPool, PLHashEntry* aEntry, PRUintn aFlag) 
00081 {
00082     nsFixedSizeAllocator* pool = NS_STATIC_CAST(nsFixedSizeAllocator*, aPool);
00083     if (aFlag == HT_FREE_ENTRY)
00084         pool->Free(aEntry, sizeof(PLHashEntry));
00085 }
00086 
00087 PLHashAllocOps nsElementMap::gAllocOps = {
00088     AllocTable, FreeTable, AllocEntry, FreeEntry };
00089 
00090 
00091 nsElementMap::nsElementMap()
00092 {
00093     MOZ_COUNT_CTOR(nsElementMap);
00094 
00095     // Create a table for mapping IDs to elements in the content tree.
00096     static const size_t kBucketSizes[] = {
00097         sizeof(PLHashEntry), sizeof(ContentListItem)
00098     };
00099 
00100     static const PRInt32 kNumBuckets = sizeof(kBucketSizes) / sizeof(size_t);
00101 
00102     static const PRInt32 kInitialNumElements = 64;
00103 
00104     // Per news://news.mozilla.org/39BEC105.5090206%40netscape.com
00105     static const PRInt32 kInitialPoolSize = 512;
00106 
00107     mPool.Init("nsElementMap", kBucketSizes, kNumBuckets, kInitialPoolSize);
00108 
00109     mMap = PL_NewHashTable(kInitialNumElements,
00110                            Hash,
00111                            Compare,
00112                            PL_CompareValues,
00113                            &gAllocOps,
00114                            &mPool);
00115 
00116     NS_ASSERTION(mMap != nsnull, "could not create hash table for resources");
00117 
00118 #ifdef PR_LOGGING
00119     if (! gMapLog)
00120         gMapLog = PR_NewLogModule("nsElementMap");
00121 
00122 
00123     PR_LOG(gMapLog, PR_LOG_NOTICE,
00124            ("xulelemap(%p) created", this));
00125 #endif
00126 }
00127 
00128 nsElementMap::~nsElementMap()
00129 {
00130     MOZ_COUNT_DTOR(nsElementMap);
00131 
00132     if (mMap) {
00133         PL_HashTableEnumerateEntries(mMap, ReleaseContentList, this);
00134         PL_HashTableDestroy(mMap);
00135     }
00136 
00137     PR_LOG(gMapLog, PR_LOG_NOTICE,
00138            ("xulelemap(%p) destroyed", this));
00139 }
00140 
00141 
00142 PRIntn
00143 nsElementMap::ReleaseContentList(PLHashEntry* aHashEntry, PRIntn aIndex, void* aClosure)
00144 {
00145     nsElementMap* self = NS_STATIC_CAST(nsElementMap*, aClosure);
00146 
00147     PRUnichar* id =
00148         NS_REINTERPRET_CAST(PRUnichar*, NS_CONST_CAST(void*, aHashEntry->key));
00149 
00150     nsMemory::Free(id);
00151         
00152     ContentListItem* head =
00153         NS_REINTERPRET_CAST(ContentListItem*, aHashEntry->value);
00154 
00155     while (head) {
00156         ContentListItem* doomed = head;
00157         head = head->mNext;
00158         ContentListItem::Destroy(self->mPool, doomed);
00159     }
00160 
00161     return HT_ENUMERATE_NEXT;
00162 }
00163 
00164 
00165 nsresult
00166 nsElementMap::Add(const nsAString& aID, nsIContent* aContent)
00167 {
00168     NS_PRECONDITION(mMap != nsnull, "not initialized");
00169     if (! mMap)
00170         return NS_ERROR_NOT_INITIALIZED;
00171 
00172     const nsPromiseFlatString& flatID = PromiseFlatString(aID);
00173     const PRUnichar *id = flatID.get();
00174 
00175     ContentListItem* head =
00176         NS_STATIC_CAST(ContentListItem*, PL_HashTableLookup(mMap, id));
00177 
00178     if (! head) {
00179         head = ContentListItem::Create(mPool, aContent);
00180         if (! head)
00181             return NS_ERROR_OUT_OF_MEMORY;
00182 
00183         PRUnichar* key = ToNewUnicode(aID);
00184         if (! key)
00185             return NS_ERROR_OUT_OF_MEMORY;
00186 
00187         PL_HashTableAdd(mMap, key, head);
00188     }
00189     else {
00190         while (1) {
00191             if (head->mContent.get() == aContent) {
00192                 // This can happen if an element that was created via
00193                 // frame construction code is then "appended" to the
00194                 // content model with aNotify == PR_TRUE. If you see
00195                 // this warning, it's an indication that you're
00196                 // unnecessarily notifying the frame system, and
00197                 // potentially causing unnecessary reflow.
00198                 //NS_ERROR("element was already in the map");
00199 #ifdef PR_LOGGING
00200                 if (PR_LOG_TEST(gMapLog, PR_LOG_NOTICE)) {
00201                     const char *tagname;
00202                     aContent->Tag()->GetUTF8String(&tagname);
00203 
00204                     nsCAutoString aidC; 
00205                     aidC.AssignWithConversion(id, aID.Length());
00206                     PR_LOG(gMapLog, PR_LOG_NOTICE,
00207                            ("xulelemap(%p) dup    %s[%p] <-- %s\n",
00208                             this,
00209                             tagname,
00210                             aContent,
00211                             aidC.get()));
00212                 }
00213 #endif
00214 
00215                 return NS_OK;
00216             }
00217             if (! head->mNext)
00218                 break;
00219 
00220             head = head->mNext;
00221         }
00222 
00223         head->mNext = nsElementMap::ContentListItem::Create(mPool, aContent);
00224         if (! head->mNext)
00225             return NS_ERROR_OUT_OF_MEMORY;
00226     }
00227 
00228 #ifdef PR_LOGGING
00229     if (PR_LOG_TEST(gMapLog, PR_LOG_NOTICE)) {
00230         const char *tagname;
00231         aContent->Tag()->GetUTF8String(&tagname);
00232 
00233         nsCAutoString aidC; 
00234         aidC.AssignWithConversion(id, aID.Length());
00235         PR_LOG(gMapLog, PR_LOG_NOTICE,
00236                ("xulelemap(%p) add    %s[%p] <-- %s\n",
00237                 this,
00238                 tagname,
00239                 aContent,
00240                 aidC.get()));
00241     }
00242 #endif
00243 
00244     return NS_OK;
00245 }
00246 
00247 
00248 nsresult
00249 nsElementMap::Remove(const nsAString& aID, nsIContent* aContent)
00250 {
00251     NS_PRECONDITION(mMap != nsnull, "not initialized");
00252     if (! mMap)
00253         return NS_ERROR_NOT_INITIALIZED;
00254 
00255     const nsPromiseFlatString& flatID = PromiseFlatString(aID);
00256     const PRUnichar *id = flatID.get();
00257 
00258 #ifdef PR_LOGGING
00259     if (PR_LOG_TEST(gMapLog, PR_LOG_NOTICE)) {
00260         const char *tagname;
00261         aContent->Tag()->GetUTF8String(&tagname);
00262 
00263         nsCAutoString aidC; 
00264         aidC.AssignWithConversion(id);
00265         PR_LOG(gMapLog, PR_LOG_NOTICE,
00266                ("xulelemap(%p) remove  %s[%p] <-- %s\n",
00267                 this,
00268                 tagname,
00269                 aContent,
00270                 aidC.get()));
00271     }
00272 #endif
00273 
00274     PLHashEntry** hep = PL_HashTableRawLookup(mMap,
00275                                               Hash(id),
00276                                               id);
00277 
00278     // XXX Don't comment out this assert: if you get here, something
00279     // has gone dreadfully, horribly wrong. Curse. Scream. File a bug
00280     // against waterson@netscape.com.
00281     NS_ASSERTION(hep != nsnull && *hep != nsnull, "attempt to remove an element that was never added");
00282     if (!hep || !*hep)
00283         return NS_OK;
00284 
00285     ContentListItem* head = NS_REINTERPRET_CAST(ContentListItem*, (*hep)->value);
00286 
00287     if (head->mContent.get() == aContent) {
00288         ContentListItem* next = head->mNext;
00289         if (next) {
00290             (*hep)->value = next;
00291         }
00292         else {
00293             // It was the last reference in the table
00294             PRUnichar* key = NS_REINTERPRET_CAST(PRUnichar*, NS_CONST_CAST(void*, (*hep)->key));
00295             PL_HashTableRawRemove(mMap, hep, *hep);
00296             nsMemory::Free(key);
00297         }
00298         ContentListItem::Destroy(mPool, head);
00299     }
00300     else {
00301         ContentListItem* item = head->mNext;
00302         while (item) {
00303             if (item->mContent.get() == aContent) {
00304                 head->mNext = item->mNext;
00305                 ContentListItem::Destroy(mPool, item);
00306                 break;
00307             }
00308             head = item;
00309             item = item->mNext;
00310         }
00311     }
00312 
00313     return NS_OK;
00314 }
00315 
00316 
00317 
00318 nsresult
00319 nsElementMap::Find(const nsAString& aID, nsISupportsArray* aResults)
00320 {
00321     NS_PRECONDITION(mMap != nsnull, "not initialized");
00322     if (! mMap)
00323         return NS_ERROR_NOT_INITIALIZED;
00324 
00325     aResults->Clear();
00326     ContentListItem* item =
00327         NS_REINTERPRET_CAST(ContentListItem*, PL_HashTableLookup(mMap, (const PRUnichar *)PromiseFlatString(aID).get()));
00328 
00329     while (item) {
00330         aResults->AppendElement(item->mContent);
00331         item = item->mNext;
00332     }
00333     return NS_OK;
00334 }
00335 
00336 
00337 nsresult
00338 nsElementMap::FindFirst(const nsAString& aID, nsIContent** aResult)
00339 {
00340     NS_PRECONDITION(mMap != nsnull, "not initialized");
00341     if (! mMap)
00342         return NS_ERROR_NOT_INITIALIZED;
00343 
00344     ContentListItem* item =
00345         NS_REINTERPRET_CAST(ContentListItem*, PL_HashTableLookup(mMap, (const PRUnichar *)PromiseFlatString(aID).get()));
00346 
00347     if (item) {
00348         *aResult = item->mContent;
00349         NS_ADDREF(*aResult);
00350     }
00351     else {
00352         *aResult = nsnull;
00353     }
00354 
00355     return NS_OK;
00356 }
00357 
00358 nsresult
00359 nsElementMap::Enumerate(nsElementMapEnumerator aEnumerator, void* aClosure)
00360 {
00361     EnumerateClosure closure = { this, aEnumerator, aClosure };
00362     PL_HashTableEnumerateEntries(mMap, EnumerateImpl, &closure);
00363     return NS_OK;
00364 }
00365 
00366 
00367 PRIntn
00368 nsElementMap::EnumerateImpl(PLHashEntry* aHashEntry, PRIntn aIndex, void* aClosure)
00369 {
00370     // This routine will be called once for each key in the
00371     // hashtable. It will in turn call the enumerator that the user
00372     // has passed in via Enumerate() once for each element that's been
00373     // mapped to this ID.
00374     EnumerateClosure* closure = NS_REINTERPRET_CAST(EnumerateClosure*, aClosure);
00375 
00376     const PRUnichar* id =
00377         NS_REINTERPRET_CAST(const PRUnichar*, aHashEntry->key);
00378 
00379     // 'link' holds a pointer to the previous element's link field.
00380     ContentListItem** link = 
00381         NS_REINTERPRET_CAST(ContentListItem**, &aHashEntry->value);
00382 
00383     ContentListItem* item = *link;
00384 
00385     // Iterate through each content node that's been mapped to this ID
00386     while (item) {
00387         ContentListItem* current = item;
00388         item = item->mNext;
00389         PRIntn result = (*closure->mEnumerator)(id, current->mContent, closure->mClosure);
00390 
00391         if (result == HT_ENUMERATE_REMOVE) {
00392             // If the user wants to remove the current, then deal.
00393             *link = item;
00394             ContentListItem::Destroy(closure->mSelf->mPool, current);
00395 
00396             if ((! *link) && (link == NS_REINTERPRET_CAST(ContentListItem**, &aHashEntry->value))) {
00397                 // It's the last content node that was mapped to this
00398                 // ID. Unhash it.
00399                 PRUnichar* key = NS_CONST_CAST(PRUnichar*, id);
00400                 nsMemory::Free(key);
00401                 return HT_ENUMERATE_REMOVE;
00402             }
00403         }
00404         else {
00405             link = &current->mNext;
00406         }
00407     }
00408 
00409     return HT_ENUMERATE_NEXT;
00410 }
00411 
00412 
00413 PLHashNumber
00414 nsElementMap::Hash(const void* aKey)
00415 {
00416     PLHashNumber result = 0;
00417     const PRUnichar* s = NS_REINTERPRET_CAST(const PRUnichar*, aKey);
00418     while (*s != nsnull) {
00419         result = (result >> 28) ^ (result << 4) ^ *s;
00420         ++s;
00421     }
00422     return result;
00423 }
00424 
00425 
00426 PRIntn
00427 nsElementMap::Compare(const void* aLeft, const void* aRight)
00428 {
00429     return 0 == nsCRT::strcmp(NS_REINTERPRET_CAST(const PRUnichar*, aLeft),
00430                               NS_REINTERPRET_CAST(const PRUnichar*, aRight));
00431 }