1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/ds/nsStaticNameTable.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,236 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + *
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/* Class to manage lookup of static names in a table. */
1.11 +
1.12 +#include "nsCRT.h"
1.13 +
1.14 +#include "nscore.h"
1.15 +#include "mozilla/HashFunctions.h"
1.16 +#include "nsISupportsImpl.h"
1.17 +
1.18 +#define PL_ARENA_CONST_ALIGN_MASK 3
1.19 +#include "nsStaticNameTable.h"
1.20 +
1.21 +using namespace mozilla;
1.22 +
1.23 +struct NameTableKey
1.24 +{
1.25 + NameTableKey(const nsAFlatCString* aKeyStr)
1.26 + : mIsUnichar(false)
1.27 + {
1.28 + mKeyStr.m1b = aKeyStr;
1.29 + }
1.30 +
1.31 + NameTableKey(const nsAFlatString* aKeyStr)
1.32 + : mIsUnichar(true)
1.33 + {
1.34 + mKeyStr.m2b = aKeyStr;
1.35 + }
1.36 +
1.37 + bool mIsUnichar;
1.38 + union {
1.39 + const nsAFlatCString* m1b;
1.40 + const nsAFlatString* m2b;
1.41 + } mKeyStr;
1.42 +};
1.43 +
1.44 +struct NameTableEntry : public PLDHashEntryHdr
1.45 +{
1.46 + // no ownership here!
1.47 + const nsAFlatCString* mString;
1.48 + int32_t mIndex;
1.49 +};
1.50 +
1.51 +static bool
1.52 +matchNameKeysCaseInsensitive(PLDHashTable*, const PLDHashEntryHdr* aHdr,
1.53 + const void* key)
1.54 +{
1.55 + const NameTableEntry* entry =
1.56 + static_cast<const NameTableEntry *>(aHdr);
1.57 + const NameTableKey *keyValue = static_cast<const NameTableKey*>(key);
1.58 +
1.59 + const nsAFlatCString* entryKey = entry->mString;
1.60 +
1.61 + if (keyValue->mIsUnichar) {
1.62 + return keyValue->mKeyStr.m2b->
1.63 + LowerCaseEqualsASCII(entryKey->get(), entryKey->Length());
1.64 + }
1.65 +
1.66 + return keyValue->mKeyStr.m1b->
1.67 + LowerCaseEqualsASCII(entryKey->get(), entryKey->Length());
1.68 +}
1.69 +
1.70 +/*
1.71 + * caseInsensitiveHashKey is just like PL_DHashStringKey except it
1.72 + * uses (*s & ~0x20) instead of simply *s. This means that "aFOO" and
1.73 + * "afoo" and "aFoo" will all hash to the same thing. It also means
1.74 + * that some strings that aren't case-insensensitively equal will hash
1.75 + * to the same value, but it's just a hash function so it doesn't
1.76 + * matter.
1.77 + */
1.78 +static PLDHashNumber
1.79 +caseInsensitiveStringHashKey(PLDHashTable *table, const void *key)
1.80 +{
1.81 + PLDHashNumber h = 0;
1.82 + const NameTableKey* tableKey = static_cast<const NameTableKey*>(key);
1.83 + if (tableKey->mIsUnichar) {
1.84 + for (const char16_t* s = tableKey->mKeyStr.m2b->get();
1.85 + *s != '\0';
1.86 + s++)
1.87 + h = AddToHash(h, *s & ~0x20);
1.88 + } else {
1.89 + for (const unsigned char* s =
1.90 + reinterpret_cast<const unsigned char*>
1.91 + (tableKey->mKeyStr.m1b->get());
1.92 + *s != '\0';
1.93 + s++)
1.94 + h = AddToHash(h, *s & ~0x20);
1.95 + }
1.96 + return h;
1.97 +}
1.98 +
1.99 +static const struct PLDHashTableOps nametable_CaseInsensitiveHashTableOps = {
1.100 + PL_DHashAllocTable,
1.101 + PL_DHashFreeTable,
1.102 + caseInsensitiveStringHashKey,
1.103 + matchNameKeysCaseInsensitive,
1.104 + PL_DHashMoveEntryStub,
1.105 + PL_DHashClearEntryStub,
1.106 + PL_DHashFinalizeStub,
1.107 + nullptr,
1.108 +};
1.109 +
1.110 +nsStaticCaseInsensitiveNameTable::nsStaticCaseInsensitiveNameTable()
1.111 + : mNameArray(nullptr), mNullStr("")
1.112 +{
1.113 + MOZ_COUNT_CTOR(nsStaticCaseInsensitiveNameTable);
1.114 + mNameTable.ops = nullptr;
1.115 +}
1.116 +
1.117 +nsStaticCaseInsensitiveNameTable::~nsStaticCaseInsensitiveNameTable()
1.118 +{
1.119 + if (mNameArray) {
1.120 + // manually call the destructor on placement-new'ed objects
1.121 + for (uint32_t index = 0; index < mNameTable.entryCount; index++) {
1.122 + mNameArray[index].~nsDependentCString();
1.123 + }
1.124 + nsMemory::Free((void*)mNameArray);
1.125 + }
1.126 + if (mNameTable.ops)
1.127 + PL_DHashTableFinish(&mNameTable);
1.128 + MOZ_COUNT_DTOR(nsStaticCaseInsensitiveNameTable);
1.129 +}
1.130 +
1.131 +bool
1.132 +nsStaticCaseInsensitiveNameTable::Init(const char* const aNames[], int32_t Count)
1.133 +{
1.134 + NS_ASSERTION(!mNameArray, "double Init");
1.135 + NS_ASSERTION(!mNameTable.ops, "double Init");
1.136 + NS_ASSERTION(aNames, "null name table");
1.137 + NS_ASSERTION(Count, "0 count");
1.138 +
1.139 + mNameArray = (nsDependentCString*)
1.140 + nsMemory::Alloc(Count * sizeof(nsDependentCString));
1.141 + if (!mNameArray)
1.142 + return false;
1.143 +
1.144 + if (!PL_DHashTableInit(&mNameTable, &nametable_CaseInsensitiveHashTableOps,
1.145 + nullptr, sizeof(NameTableEntry), Count,
1.146 + fallible_t())) {
1.147 + mNameTable.ops = nullptr;
1.148 + return false;
1.149 + }
1.150 +
1.151 + for (int32_t index = 0; index < Count; ++index) {
1.152 + const char* raw = aNames[index];
1.153 +#ifdef DEBUG
1.154 + {
1.155 + // verify invariants of contents
1.156 + nsAutoCString temp1(raw);
1.157 + nsDependentCString temp2(raw);
1.158 + ToLowerCase(temp1);
1.159 + NS_ASSERTION(temp1.Equals(temp2), "upper case char in table");
1.160 + NS_ASSERTION(nsCRT::IsAscii(raw),
1.161 + "non-ascii string in table -- "
1.162 + "case-insensitive matching won't work right");
1.163 + }
1.164 +#endif
1.165 + // use placement-new to initialize the string object
1.166 + nsDependentCString* strPtr = &mNameArray[index];
1.167 + new (strPtr) nsDependentCString(raw);
1.168 +
1.169 + NameTableKey key(strPtr);
1.170 +
1.171 + NameTableEntry *entry =
1.172 + static_cast<NameTableEntry*>
1.173 + (PL_DHashTableOperate(&mNameTable, &key,
1.174 + PL_DHASH_ADD));
1.175 +
1.176 + if (!entry) continue;
1.177 +
1.178 + NS_ASSERTION(entry->mString == 0, "Entry already exists!");
1.179 +
1.180 + entry->mString = strPtr; // not owned!
1.181 + entry->mIndex = index;
1.182 + }
1.183 +#ifdef DEBUG
1.184 + PL_DHashMarkTableImmutable(&mNameTable);
1.185 +#endif
1.186 + return true;
1.187 +}
1.188 +
1.189 +int32_t
1.190 +nsStaticCaseInsensitiveNameTable::Lookup(const nsACString& aName)
1.191 +{
1.192 + NS_ASSERTION(mNameArray, "not inited");
1.193 + NS_ASSERTION(mNameTable.ops, "not inited");
1.194 +
1.195 + const nsAFlatCString& str = PromiseFlatCString(aName);
1.196 +
1.197 + NameTableKey key(&str);
1.198 + NameTableEntry *entry =
1.199 + static_cast<NameTableEntry*>
1.200 + (PL_DHashTableOperate(&mNameTable, &key,
1.201 + PL_DHASH_LOOKUP));
1.202 +
1.203 + if (PL_DHASH_ENTRY_IS_FREE(entry))
1.204 + return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
1.205 +
1.206 + return entry->mIndex;
1.207 +}
1.208 +
1.209 +int32_t
1.210 +nsStaticCaseInsensitiveNameTable::Lookup(const nsAString& aName)
1.211 +{
1.212 + NS_ASSERTION(mNameArray, "not inited");
1.213 + NS_ASSERTION(mNameTable.ops, "not inited");
1.214 +
1.215 + const nsAFlatString& str = PromiseFlatString(aName);
1.216 +
1.217 + NameTableKey key(&str);
1.218 + NameTableEntry *entry =
1.219 + static_cast<NameTableEntry*>
1.220 + (PL_DHashTableOperate(&mNameTable, &key,
1.221 + PL_DHASH_LOOKUP));
1.222 +
1.223 + if (PL_DHASH_ENTRY_IS_FREE(entry))
1.224 + return nsStaticCaseInsensitiveNameTable::NOT_FOUND;
1.225 +
1.226 + return entry->mIndex;
1.227 +}
1.228 +
1.229 +const nsAFlatCString&
1.230 +nsStaticCaseInsensitiveNameTable::GetStringValue(int32_t index)
1.231 +{
1.232 + NS_ASSERTION(mNameArray, "not inited");
1.233 + NS_ASSERTION(mNameTable.ops, "not inited");
1.234 +
1.235 + if ((NOT_FOUND < index) && ((uint32_t)index < mNameTable.entryCount)) {
1.236 + return mNameArray[index];
1.237 + }
1.238 + return mNullStr;
1.239 +}
