xpcom/ds/nsStaticNameTable.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* Class to manage lookup of static names in a table. */
   8
   9 #include "nsCRT.h"
  10
  11 #include "nscore.h"
  12 #include "mozilla/HashFunctions.h"
  13 #include "nsISupportsImpl.h"
  14
  15 #define PL_ARENA_CONST_ALIGN_MASK 3
  16 #include "nsStaticNameTable.h"
  17
  18 using namespace mozilla;
  19
  20 struct NameTableKey
  21 {
  22   explicit NameTableKey(const nsAFlatCString* aKeyStr)
  23     : mIsUnichar(false)
  24   {
  25     mKeyStr.m1b = aKeyStr;
  26   }
  27
  28   explicit NameTableKey(const nsAFlatString* aKeyStr)
  29     : mIsUnichar(true)
  30   {
  31     mKeyStr.m2b = aKeyStr;
  32   }
  33
  34   bool mIsUnichar;
  35   union
  36   {
  37     const nsAFlatCString* m1b;
  38     const nsAFlatString* m2b;
  39   } mKeyStr;
  40 };
  41
  42 struct NameTableEntry : public PLDHashEntryHdr
  43 {
  44   // no ownership here!
  45   const nsAFlatCString* mString;
  46   int32_t mIndex;
  47 };
  48
  49 static bool
  50 matchNameKeysCaseInsensitive(PLDHashTable*, const PLDHashEntryHdr* aHdr,
  51                              const void* aKey)
  52 {
  53   const NameTableEntry* entry = static_cast<const NameTableEntry*>(aHdr);
  54   const NameTableKey* keyValue = static_cast<const NameTableKey*>(aKey);
  55   const nsAFlatCString* entryKey = entry->mString;
  56
  57   if (keyValue->mIsUnichar) {
  58     return keyValue->mKeyStr.m2b->LowerCaseEqualsASCII(entryKey->get(),
  59                                                        entryKey->Length());
  60   }
  61
  62   return keyValue->mKeyStr.m1b->LowerCaseEqualsASCII(entryKey->get(),
  63                                                      entryKey->Length());
  64 }
  65
  66 /*
  67  * caseInsensitiveHashKey is just like PL_DHashStringKey except it
  68  * uses (*s & ~0x20) instead of simply *s.  This means that "aFOO" and
  69  * "afoo" and "aFoo" will all hash to the same thing.  It also means
  70  * that some strings that aren't case-insensensitively equal will hash
  71  * to the same value, but it's just a hash function so it doesn't
  72  * matter.
  73  */
  74 static PLDHashNumber
  75 caseInsensitiveStringHashKey(PLDHashTable* aTable, const void* aKey)
  76 {
  77   PLDHashNumber h = 0;
  78   const NameTableKey* tableKey = static_cast<const NameTableKey*>(aKey);
  79   if (tableKey->mIsUnichar) {
  80     for (const char16_t* s = tableKey->mKeyStr.m2b->get();
  81          *s != '\0';
  82          s++) {
  83       h = AddToHash(h, *s & ~0x20);
  84     }
  85   } else {
  86     for (const unsigned char* s = reinterpret_cast<const unsigned char*>(
  87            tableKey->mKeyStr.m1b->get());
  88          *s != '\0';
  89          s++) {
  90       h = AddToHash(h, *s & ~0x20);
  91     }
  92   }
  93   return h;
  94 }
  95
  96 static const struct PLDHashTableOps nametable_CaseInsensitiveHashTableOps = {
  97   PL_DHashAllocTable,
  98   PL_DHashFreeTable,
  99   caseInsensitiveStringHashKey,
 100   matchNameKeysCaseInsensitive,
 101   PL_DHashMoveEntryStub,
 102   PL_DHashClearEntryStub,
 103   PL_DHashFinalizeStub,
 104   nullptr,
 105 };
 106
 107 nsStaticCaseInsensitiveNameTable::nsStaticCaseInsensitiveNameTable()
 108   : mNameArray(nullptr)
 109   , mNullStr("")
 110 {
 111   MOZ_COUNT_CTOR(nsStaticCaseInsensitiveNameTable);
 112   mNameTable.ops = nullptr;
 113 }
 114
 115 nsStaticCaseInsensitiveNameTable::~nsStaticCaseInsensitiveNameTable()
 116 {
 117   if (mNameArray) {
 118     // manually call the destructor on placement-new'ed objects
 119     for (uint32_t index = 0; index < mNameTable.EntryCount(); index++) {
 120       mNameArray[index].~nsDependentCString();
 121     }
 122     nsMemory::Free((void*)mNameArray);
 123   }
 124   if (mNameTable.ops) {
 125     PL_DHashTableFinish(&mNameTable);
 126   }
 127   MOZ_COUNT_DTOR(nsStaticCaseInsensitiveNameTable);
 128 }
 129
 130 bool
 131 nsStaticCaseInsensitiveNameTable::Init(const char* const aNames[],
 132                                        int32_t aLength)
 133 {
 134   NS_ASSERTION(!mNameArray, "double Init");
 135   NS_ASSERTION(!mNameTable.ops, "double Init");
 136   NS_ASSERTION(aNames, "null name table");
 137   NS_ASSERTION(aLength, "0 length");
 138
 139   mNameArray = (nsDependentCString*)
 140     nsMemory::Alloc(aLength * sizeof(nsDependentCString));
 141   if (!mNameArray) {
 142     return false;
 143   }
 144
 145   if (!PL_DHashTableInit(&mNameTable, &nametable_CaseInsensitiveHashTableOps,
 146                          nullptr, sizeof(NameTableEntry), fallible_t(),
 147                          aLength)) {
 148     mNameTable.ops = nullptr;
 149     return false;
 150   }
 151
 152   for (int32_t index = 0; index < aLength; ++index) {
 153     const char* raw = aNames[index];
 154 #ifdef DEBUG
 155     {
 156       // verify invariants of contents
 157       nsAutoCString temp1(raw);
 158       nsDependentCString temp2(raw);
 159       ToLowerCase(temp1);
 160       NS_ASSERTION(temp1.Equals(temp2), "upper case char in table");
 161       NS_ASSERTION(nsCRT::IsAscii(raw),
 162                    "non-ascii string in table -- "
 163                    "case-insensitive matching won't work right");
 164     }
 165 #endif
 166     // use placement-new to initialize the string object
 167     nsDependentCString* strPtr = &mNameArray[index];
 168     new (strPtr) nsDependentCString(raw);
 169
 170     NameTableKey key(strPtr);
 171
 172     NameTableEntry* entry =
 173       static_cast<NameTableEntry*>(PL_DHashTableOperate(&mNameTable, &key,
 174                                                         PL_DHASH_ADD));
 175     if (!entry) {
 176       continue;
 177     }
 178
 179     NS_ASSERTION(entry->mString == 0, "Entry already exists!");
 180
 181     entry->mString = strPtr;      // not owned!
 182     entry->mIndex = index;
 183   }
 184 #ifdef DEBUG
 185   PL_DHashMarkTableImmutable(&mNameTable);
 186 #endif
 187   return true;
 188 }
 189
 190 int32_t
 191 nsStaticCaseInsensitiveNameTable::Lookup(const nsACString& aName)
 192 {
 193   NS_ASSERTION(mNameArray, "not inited");
 194   NS_ASSERTION(mNameTable.ops, "not inited");
 195
 196   const nsAFlatCString& str = PromiseFlatCString(aName);
 197
 198   NameTableKey key(&str);
 199   NameTableEntry* entry =
 200     static_cast<NameTableEntry*>(PL_DHashTableOperate(&mNameTable, &key,
 201                                                       PL_DHASH_LOOKUP));
 202   if (PL_DHASH_ENTRY_IS_FREE(entry)) {
 203     return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
 204   }
 205
 206   return entry->mIndex;
 207 }
 208
 209 int32_t
 210 nsStaticCaseInsensitiveNameTable::Lookup(const nsAString& aName)
 211 {
 212   NS_ASSERTION(mNameArray, "not inited");
 213   NS_ASSERTION(mNameTable.ops, "not inited");
 214
 215   const nsAFlatString& str = PromiseFlatString(aName);
 216
 217   NameTableKey key(&str);
 218   NameTableEntry* entry =
 219     static_cast<NameTableEntry*>(PL_DHashTableOperate(&mNameTable, &key,
 220                                                       PL_DHASH_LOOKUP));
 221   if (PL_DHASH_ENTRY_IS_FREE(entry)) {
 222     return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
 223   }
 224
 225   return entry->mIndex;
 226 }
 227
 228 const nsAFlatCString&
 229 nsStaticCaseInsensitiveNameTable::GetStringValue(int32_t aIndex)
 230 {
 231   NS_ASSERTION(mNameArray, "not inited");
 232   NS_ASSERTION(mNameTable.ops, "not inited");
 233
 234   if ((NOT_FOUND < aIndex) && ((uint32_t)aIndex < mNameTable.EntryCount())) {
 235     return mNameArray[aIndex];
 236   }
 237   return mNullStr;
 238 }