michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  *
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* Class to manage lookup of static names in a table. */
michael@0: 
michael@0: #include "nsCRT.h"
michael@0: 
michael@0: #include "nscore.h"
michael@0: #include "mozilla/HashFunctions.h"
michael@0: #include "nsISupportsImpl.h"
michael@0: 
michael@0: #define PL_ARENA_CONST_ALIGN_MASK 3
michael@0: #include "nsStaticNameTable.h"
michael@0: 
michael@0: using namespace mozilla;
michael@0: 
michael@0: struct NameTableKey
michael@0: {
michael@0:     NameTableKey(const nsAFlatCString* aKeyStr)
michael@0:         : mIsUnichar(false)
michael@0:     {
michael@0:         mKeyStr.m1b = aKeyStr;
michael@0:     }
michael@0: 
michael@0:     NameTableKey(const nsAFlatString* aKeyStr)
michael@0:         : mIsUnichar(true)
michael@0:     {
michael@0:         mKeyStr.m2b = aKeyStr;
michael@0:     }
michael@0: 
michael@0:     bool mIsUnichar;
michael@0:     union {
michael@0:         const nsAFlatCString* m1b;
michael@0:         const nsAFlatString* m2b;
michael@0:     } mKeyStr;
michael@0: };
michael@0: 
michael@0: struct NameTableEntry : public PLDHashEntryHdr
michael@0: {
michael@0:     // no ownership here!
michael@0:     const nsAFlatCString* mString;
michael@0:     int32_t mIndex;
michael@0: };
michael@0: 
michael@0: static bool
michael@0: matchNameKeysCaseInsensitive(PLDHashTable*, const PLDHashEntryHdr* aHdr,
michael@0:                              const void* key)
michael@0: {
michael@0:     const NameTableEntry* entry =
michael@0:         static_cast<const NameTableEntry *>(aHdr);
michael@0:     const NameTableKey *keyValue = static_cast<const NameTableKey*>(key);
michael@0: 
michael@0:     const nsAFlatCString* entryKey = entry->mString;
michael@0: 
michael@0:     if (keyValue->mIsUnichar) {
michael@0:         return keyValue->mKeyStr.m2b->
michael@0:             LowerCaseEqualsASCII(entryKey->get(), entryKey->Length());
michael@0:     }
michael@0: 
michael@0:     return keyValue->mKeyStr.m1b->
michael@0:         LowerCaseEqualsASCII(entryKey->get(), entryKey->Length());
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * caseInsensitiveHashKey is just like PL_DHashStringKey except it
michael@0:  * uses (*s & ~0x20) instead of simply *s.  This means that "aFOO" and
michael@0:  * "afoo" and "aFoo" will all hash to the same thing.  It also means
michael@0:  * that some strings that aren't case-insensensitively equal will hash
michael@0:  * to the same value, but it's just a hash function so it doesn't
michael@0:  * matter.
michael@0:  */
michael@0: static PLDHashNumber
michael@0: caseInsensitiveStringHashKey(PLDHashTable *table, const void *key)
michael@0: {
michael@0:     PLDHashNumber h = 0;
michael@0:     const NameTableKey* tableKey = static_cast<const NameTableKey*>(key);
michael@0:     if (tableKey->mIsUnichar) {
michael@0:         for (const char16_t* s = tableKey->mKeyStr.m2b->get();
michael@0:              *s != '\0';
michael@0:              s++)
michael@0:             h = AddToHash(h, *s & ~0x20);
michael@0:     } else {
michael@0:         for (const unsigned char* s =
michael@0:                  reinterpret_cast<const unsigned char*>
michael@0:                                  (tableKey->mKeyStr.m1b->get());
michael@0:              *s != '\0';
michael@0:              s++)
michael@0:             h = AddToHash(h, *s & ~0x20);
michael@0:     }
michael@0:     return h;
michael@0: }
michael@0: 
michael@0: static const struct PLDHashTableOps nametable_CaseInsensitiveHashTableOps = {
michael@0:     PL_DHashAllocTable,
michael@0:     PL_DHashFreeTable,
michael@0:     caseInsensitiveStringHashKey,
michael@0:     matchNameKeysCaseInsensitive,
michael@0:     PL_DHashMoveEntryStub,
michael@0:     PL_DHashClearEntryStub,
michael@0:     PL_DHashFinalizeStub,
michael@0:     nullptr,
michael@0: };
michael@0: 
michael@0: nsStaticCaseInsensitiveNameTable::nsStaticCaseInsensitiveNameTable()
michael@0:   : mNameArray(nullptr), mNullStr("")
michael@0: {
michael@0:     MOZ_COUNT_CTOR(nsStaticCaseInsensitiveNameTable);
michael@0:     mNameTable.ops = nullptr;
michael@0: }
michael@0: 
michael@0: nsStaticCaseInsensitiveNameTable::~nsStaticCaseInsensitiveNameTable()
michael@0: {
michael@0:     if (mNameArray) {
michael@0:         // manually call the destructor on placement-new'ed objects
michael@0:         for (uint32_t index = 0; index < mNameTable.entryCount; index++) {
michael@0:             mNameArray[index].~nsDependentCString();
michael@0:         }
michael@0:         nsMemory::Free((void*)mNameArray);
michael@0:     }
michael@0:     if (mNameTable.ops)
michael@0:         PL_DHashTableFinish(&mNameTable);
michael@0:     MOZ_COUNT_DTOR(nsStaticCaseInsensitiveNameTable);
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsStaticCaseInsensitiveNameTable::Init(const char* const aNames[], int32_t Count)
michael@0: {
michael@0:     NS_ASSERTION(!mNameArray, "double Init");
michael@0:     NS_ASSERTION(!mNameTable.ops, "double Init");
michael@0:     NS_ASSERTION(aNames, "null name table");
michael@0:     NS_ASSERTION(Count, "0 count");
michael@0: 
michael@0:     mNameArray = (nsDependentCString*)
michael@0:                    nsMemory::Alloc(Count * sizeof(nsDependentCString));
michael@0:     if (!mNameArray)
michael@0:         return false;
michael@0: 
michael@0:     if (!PL_DHashTableInit(&mNameTable, &nametable_CaseInsensitiveHashTableOps,
michael@0:                            nullptr, sizeof(NameTableEntry), Count,
michael@0:                            fallible_t())) {
michael@0:         mNameTable.ops = nullptr;
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     for (int32_t index = 0; index < Count; ++index) {
michael@0:         const char* raw = aNames[index];
michael@0: #ifdef DEBUG
michael@0:         {
michael@0:             // verify invariants of contents
michael@0:             nsAutoCString temp1(raw);
michael@0:             nsDependentCString temp2(raw);
michael@0:             ToLowerCase(temp1);
michael@0:             NS_ASSERTION(temp1.Equals(temp2), "upper case char in table");
michael@0:             NS_ASSERTION(nsCRT::IsAscii(raw),
michael@0:                          "non-ascii string in table -- "
michael@0:                          "case-insensitive matching won't work right");
michael@0:         }
michael@0: #endif
michael@0:         // use placement-new to initialize the string object
michael@0:         nsDependentCString* strPtr = &mNameArray[index];
michael@0:         new (strPtr) nsDependentCString(raw);
michael@0: 
michael@0:         NameTableKey key(strPtr);
michael@0: 
michael@0:         NameTableEntry *entry =
michael@0:           static_cast<NameTableEntry*>
michael@0:                      (PL_DHashTableOperate(&mNameTable, &key,
michael@0:                                               PL_DHASH_ADD));
michael@0: 
michael@0:         if (!entry) continue;
michael@0: 
michael@0:         NS_ASSERTION(entry->mString == 0, "Entry already exists!");
michael@0: 
michael@0:         entry->mString = strPtr;      // not owned!
michael@0:         entry->mIndex = index;
michael@0:     }
michael@0: #ifdef DEBUG
michael@0:     PL_DHashMarkTableImmutable(&mNameTable);
michael@0: #endif
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: int32_t
michael@0: nsStaticCaseInsensitiveNameTable::Lookup(const nsACString& aName)
michael@0: {
michael@0:     NS_ASSERTION(mNameArray, "not inited");
michael@0:     NS_ASSERTION(mNameTable.ops, "not inited");
michael@0: 
michael@0:     const nsAFlatCString& str = PromiseFlatCString(aName);
michael@0: 
michael@0:     NameTableKey key(&str);
michael@0:     NameTableEntry *entry =
michael@0:         static_cast<NameTableEntry*>
michael@0:                    (PL_DHashTableOperate(&mNameTable, &key,
michael@0:                                             PL_DHASH_LOOKUP));
michael@0: 
michael@0:     if (PL_DHASH_ENTRY_IS_FREE(entry))
michael@0:         return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
michael@0: 
michael@0:     return entry->mIndex;
michael@0: }
michael@0: 
michael@0: int32_t
michael@0: nsStaticCaseInsensitiveNameTable::Lookup(const nsAString& aName)
michael@0: {
michael@0:     NS_ASSERTION(mNameArray, "not inited");
michael@0:     NS_ASSERTION(mNameTable.ops, "not inited");
michael@0: 
michael@0:     const nsAFlatString& str = PromiseFlatString(aName);
michael@0: 
michael@0:     NameTableKey key(&str);
michael@0:     NameTableEntry *entry =
michael@0:         static_cast<NameTableEntry*>
michael@0:                    (PL_DHashTableOperate(&mNameTable, &key,
michael@0:                                             PL_DHASH_LOOKUP));
michael@0: 
michael@0:     if (PL_DHASH_ENTRY_IS_FREE(entry))
michael@0:         return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
michael@0: 
michael@0:     return entry->mIndex;
michael@0: }
michael@0: 
michael@0: const nsAFlatCString& 
michael@0: nsStaticCaseInsensitiveNameTable::GetStringValue(int32_t index)
michael@0: {
michael@0:     NS_ASSERTION(mNameArray, "not inited");
michael@0:     NS_ASSERTION(mNameTable.ops, "not inited");
michael@0: 
michael@0:     if ((NOT_FOUND < index) && ((uint32_t)index < mNameTable.entryCount)) {
michael@0:         return mNameArray[index];
michael@0:     }
michael@0:     return mNullStr;
michael@0: }