xpcom/ds/nsStaticNameTable.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla Communicator client code, released
  17  * March 31, 1998.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 1998
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 /* Class to manage lookup of static names in a table. */
  41
  42 #include "nsCRT.h"
  43
  44 #include "nscore.h"
  45 #include "nsString.h"
  46 #include "nsReadableUtils.h"
  47 #include "prbit.h"
  48
  49 #define PL_ARENA_CONST_ALIGN_MASK 3
  50 #include "nsStaticNameTable.h"
  51
  52 struct NameTableKey
  53 {
  54     NameTableKey(const nsAFlatCString* aKeyStr)
  55         : mIsUnichar(PR_FALSE)
  56     {
  57         mKeyStr.m1b = aKeyStr;
  58     }
  59
  60     NameTableKey(const nsAFlatString* aKeyStr)
  61         : mIsUnichar(PR_TRUE)
  62     {
  63         mKeyStr.m2b = aKeyStr;
  64     }
  65
  66     PRBool mIsUnichar;
  67     union {
  68         const nsAFlatCString* m1b;
  69         const nsAFlatString* m2b;
  70     } mKeyStr;
  71 };
  72
  73 struct NameTableEntry : public PLDHashEntryHdr
  74 {
  75     // no ownership here!
  76     const nsAFlatCString* mString;
  77     PRInt32 mIndex;
  78 };
  79
  80 static PRBool
  81 matchNameKeysCaseInsensitive(PLDHashTable*, const PLDHashEntryHdr* aHdr,
  82                              const void* key)
  83 {
  84     const NameTableEntry* entry =
  85         static_cast<const NameTableEntry *>(aHdr);
  86     const NameTableKey *keyValue = static_cast<const NameTableKey*>(key);
  87
  88     const nsAFlatCString* entryKey = entry->mString;
  89
  90     if (keyValue->mIsUnichar) {
  91         return keyValue->mKeyStr.m2b->
  92             LowerCaseEqualsASCII(entryKey->get(), entryKey->Length());
  93     }
  94
  95     return keyValue->mKeyStr.m1b->
  96         LowerCaseEqualsASCII(entryKey->get(), entryKey->Length());
  97 }
  98
  99 /*
 100  * caseInsensitiveHashKey is just like PL_DHashStringKey except it
 101  * uses (*s & ~0x20) instead of simply *s.  This means that "aFOO" and
 102  * "afoo" and "aFoo" will all hash to the same thing.  It also means
 103  * that some strings that aren't case-insensensitively equal will hash
 104  * to the same value, but it's just a hash function so it doesn't
 105  * matter.
 106  */
 107 static PLDHashNumber
 108 caseInsensitiveStringHashKey(PLDHashTable *table, const void *key)
 109 {
 110     PLDHashNumber h = 0;
 111     const NameTableKey* tableKey = static_cast<const NameTableKey*>(key);
 112     if (tableKey->mIsUnichar) {
 113         for (const PRUnichar* s = tableKey->mKeyStr.m2b->get();
 114              *s != '\0';
 115              s++)
 116             h = PR_ROTATE_LEFT32(h, 4) ^ (*s & ~0x20);
 117     } else {
 118         for (const unsigned char* s =
 119                  reinterpret_cast<const unsigned char*>
 120                                  (tableKey->mKeyStr.m1b->get());
 121              *s != '\0';
 122              s++)
 123             h = PR_ROTATE_LEFT32(h, 4) ^ (*s & ~0x20);
 124     }
 125     return h;
 126 }
 127
 128 static const struct PLDHashTableOps nametable_CaseInsensitiveHashTableOps = {
 129     PL_DHashAllocTable,
 130     PL_DHashFreeTable,
 131     caseInsensitiveStringHashKey,
 132     matchNameKeysCaseInsensitive,
 133     PL_DHashMoveEntryStub,
 134     PL_DHashClearEntryStub,
 135     PL_DHashFinalizeStub,
 136     nsnull,
 137 };
 138
 139 nsStaticCaseInsensitiveNameTable::nsStaticCaseInsensitiveNameTable()
 140   : mNameArray(nsnull), mNullStr("")
 141 {
 142     MOZ_COUNT_CTOR(nsStaticCaseInsensitiveNameTable);
 143     mNameTable.ops = nsnull;
 144 }
 145
 146 nsStaticCaseInsensitiveNameTable::~nsStaticCaseInsensitiveNameTable()
 147 {
 148     if (mNameArray) {
 149         // manually call the destructor on placement-new'ed objects
 150         for (PRUint32 index = 0; index < mNameTable.entryCount; index++) {
 151             mNameArray[index].~nsDependentCString();
 152         }
 153         nsMemory::Free((void*)mNameArray);
 154     }
 155     if (mNameTable.ops)
 156         PL_DHashTableFinish(&mNameTable);
 157     MOZ_COUNT_DTOR(nsStaticCaseInsensitiveNameTable);
 158 }
 159
 160 PRBool
 161 nsStaticCaseInsensitiveNameTable::Init(const char* const aNames[], PRInt32 Count)
 162 {
 163     NS_ASSERTION(!mNameArray, "double Init");
 164     NS_ASSERTION(!mNameTable.ops, "double Init");
 165     NS_ASSERTION(aNames, "null name table");
 166     NS_ASSERTION(Count, "0 count");
 167
 168     mNameArray = (nsDependentCString*)
 169                    nsMemory::Alloc(Count * sizeof(nsDependentCString));
 170     if (!mNameArray)
 171         return PR_FALSE;
 172
 173     if (!PL_DHashTableInit(&mNameTable,
 174                            &nametable_CaseInsensitiveHashTableOps,
 175                            nsnull, sizeof(NameTableEntry), Count)) {
 176         mNameTable.ops = nsnull;
 177         return PR_FALSE;
 178     }
 179
 180     for (PRInt32 index = 0; index < Count; ++index) {
 181         const char* raw = aNames[index];
 182 #ifdef DEBUG
 183         {
 184             // verify invariants of contents
 185             nsCAutoString temp1(raw);
 186             nsDependentCString temp2(raw);
 187             ToLowerCase(temp1);
 188             NS_ASSERTION(temp1.Equals(temp2), "upper case char in table");
 189             NS_ASSERTION(nsCRT::IsAscii(raw),
 190                          "non-ascii string in table -- "
 191                          "case-insensitive matching won't work right");
 192         }
 193 #endif
 194         // use placement-new to initialize the string object
 195         nsDependentCString* strPtr = &mNameArray[index];
 196         new (strPtr) nsDependentCString(raw);
 197
 198         NameTableKey key(strPtr);
 199
 200         NameTableEntry *entry =
 201           static_cast<NameTableEntry*>
 202                      (PL_DHashTableOperate(&mNameTable, &key,
 203                                               PL_DHASH_ADD));
 204
 205         if (!entry) continue;
 206
 207         NS_ASSERTION(entry->mString == 0, "Entry already exists!");
 208
 209         entry->mString = strPtr;      // not owned!
 210         entry->mIndex = index;
 211     }
 212     return PR_TRUE;
 213 }
 214
 215 PRInt32
 216 nsStaticCaseInsensitiveNameTable::Lookup(const nsACString& aName)
 217 {
 218     NS_ASSERTION(mNameArray, "not inited");
 219     NS_ASSERTION(mNameTable.ops, "not inited");
 220
 221     const nsAFlatCString& str = PromiseFlatCString(aName);
 222
 223     NameTableKey key(&str);
 224     NameTableEntry *entry =
 225         static_cast<NameTableEntry*>
 226                    (PL_DHashTableOperate(&mNameTable, &key,
 227                                             PL_DHASH_LOOKUP));
 228
 229     if (PL_DHASH_ENTRY_IS_FREE(entry))
 230         return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
 231
 232     return entry->mIndex;
 233 }
 234
 235 PRInt32
 236 nsStaticCaseInsensitiveNameTable::Lookup(const nsAString& aName)
 237 {
 238     NS_ASSERTION(mNameArray, "not inited");
 239     NS_ASSERTION(mNameTable.ops, "not inited");
 240
 241     const nsAFlatString& str = PromiseFlatString(aName);
 242
 243     NameTableKey key(&str);
 244     NameTableEntry *entry =
 245         static_cast<NameTableEntry*>
 246                    (PL_DHashTableOperate(&mNameTable, &key,
 247                                             PL_DHASH_LOOKUP));
 248
 249     if (PL_DHASH_ENTRY_IS_FREE(entry))
 250         return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
 251
 252     return entry->mIndex;
 253 }
 254
 255 const nsAFlatCString&
 256 nsStaticCaseInsensitiveNameTable::GetStringValue(PRInt32 index)
 257 {
 258     NS_ASSERTION(mNameArray, "not inited");
 259     NS_ASSERTION(mNameTable.ops, "not inited");
 260
 261     if ((NOT_FOUND < index) && ((PRUint32)index < mNameTable.entryCount)) {
 262         return mNameArray[index];
 263     }
 264     return mNullStr;
 265 }