The Tor Browser / file comparison

comparison: xpcom/ds/nsHashtable.cpp

xpcom/ds/nsHashtable.cpp

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:ae8d10f63305
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 * This Original Code has been modified by IBM Corporation.
6 * Modifications made by IBM described herein are
7 * Copyright (c) International Business Machines
8 * Corporation, 2000
9 *
10 * Modifications to Mozilla code or documentation
11 * identified per MPL Section 3.3
12 *
13 * Date Modified by Description of modification
14 * 04/20/2000 IBM Corp. Added PR_CALLBACK for Optlink use in OS2
15 */
16
17 #include <string.h>
18 #include "prlog.h"
19 #include "prlock.h"
20 #include "nsHashtable.h"
21 #include "nsIObjectInputStream.h"
22 #include "nsIObjectOutputStream.h"
23 #include "nsCRTGlue.h"
24 #include "mozilla/HashFunctions.h"
25
26 using namespace mozilla;
27
28 struct HTEntry : PLDHashEntryHdr
29 {
30 nsHashKey* key;
31 void* value;
32 };
33
34 //
35 // Key operations
36 //
37
38 static bool
39 matchKeyEntry(PLDHashTable*, const PLDHashEntryHdr* entry,
40 const void* key)
41 {
42 const HTEntry* hashEntry =
43 static_cast<const HTEntry*>(entry);
44
45 if (hashEntry->key == key)
46 return true;
47
48 const nsHashKey* otherKey = reinterpret_cast<const nsHashKey*>(key);
49 return otherKey->Equals(hashEntry->key);
50 }
51
52 static PLDHashNumber
53 hashKey(PLDHashTable* table, const void* key)
54 {
55 const nsHashKey* hashKey = static_cast<const nsHashKey*>(key);
56
57 return hashKey->HashCode();
58 }
59
60 static void
61 clearHashEntry(PLDHashTable* table, PLDHashEntryHdr* entry)
62 {
63 HTEntry* hashEntry = static_cast<HTEntry*>(entry);
64
65 // leave it up to the nsHashKey destructor to free the "value"
66 delete hashEntry->key;
67 hashEntry->key = nullptr;
68 hashEntry->value = nullptr; // probably not necessary, but for
69 // sanity's sake
70 }
71
72
73 static const PLDHashTableOps hashtableOps = {
74 PL_DHashAllocTable,
75 PL_DHashFreeTable,
76 hashKey,
77 matchKeyEntry,
78 PL_DHashMoveEntryStub,
79 clearHashEntry,
80 PL_DHashFinalizeStub,
81 nullptr,
82 };
83
84
85 //
86 // Enumerator callback
87 //
88
89 struct _HashEnumerateArgs {
90 nsHashtableEnumFunc fn;
91 void* arg;
92 };
93
94 static PLDHashOperator
95 hashEnumerate(PLDHashTable* table, PLDHashEntryHdr* hdr, uint32_t i, void *arg)
96 {
97 _HashEnumerateArgs* thunk = (_HashEnumerateArgs*)arg;
98 HTEntry* entry = static_cast<HTEntry*>(hdr);
99
100 if (thunk->fn(entry->key, entry->value, thunk->arg))
101 return PL_DHASH_NEXT;
102 return PL_DHASH_STOP;
103 }
104
105 //
106 // HashKey
107 //
108
109 nsHashKey::~nsHashKey(void)
110 {
111 MOZ_COUNT_DTOR(nsHashKey);
112 }
113
114 nsresult
115 nsHashKey::Write(nsIObjectOutputStream* aStream) const
116 {
117 NS_NOTREACHED("oops");
118 return NS_ERROR_NOT_IMPLEMENTED;
119 }
120
121 nsHashtable::nsHashtable(uint32_t aInitSize, bool aThreadSafe)
122 : mLock(nullptr), mEnumerating(false)
123 {
124 MOZ_COUNT_CTOR(nsHashtable);
125
126 bool result = PL_DHashTableInit(&mHashtable, &hashtableOps, nullptr,
127 sizeof(HTEntry), aInitSize, fallible_t());
128 NS_ASSERTION(result, "Hashtable failed to initialize");
129
130 // make sure we detect this later
131 if (!result)
132 mHashtable.ops = nullptr;
133
134 if (aThreadSafe) {
135 mLock = PR_NewLock();
136 if (mLock == nullptr) {
137 // Cannot create a lock. If running on a multiprocessing system
138 // we are sure to die.
139 PR_ASSERT(mLock != nullptr);
140 }
141 }
142 }
143
144 nsHashtable::~nsHashtable() {
145 MOZ_COUNT_DTOR(nsHashtable);
146 if (mHashtable.ops)
147 PL_DHashTableFinish(&mHashtable);
148 if (mLock) PR_DestroyLock(mLock);
149 }
150
151 bool nsHashtable::Exists(nsHashKey *aKey)
152 {
153 if (mLock) PR_Lock(mLock);
154
155 if (!mHashtable.ops) {
156 if (mLock) PR_Unlock(mLock);
157 return false;
158 }
159
160 PLDHashEntryHdr *entry =
161 PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_LOOKUP);
162
163 bool exists = PL_DHASH_ENTRY_IS_BUSY(entry);
164
165 if (mLock) PR_Unlock(mLock);
166
167 return exists;
168 }
169
170 void *nsHashtable::Put(nsHashKey *aKey, void *aData)
171 {
172 void *res = nullptr;
173
174 if (!mHashtable.ops) return nullptr;
175
176 if (mLock) PR_Lock(mLock);
177
178 // shouldn't be adding an item during enumeration
179 PR_ASSERT(!mEnumerating);
180
181 HTEntry* entry =
182 static_cast<HTEntry*>
183 (PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_ADD));
184
185 if (entry) { // don't return early, or you'll be locked!
186 if (entry->key) {
187 // existing entry, need to boot the old value
188 res = entry->value;
189 entry->value = aData;
190 } else {
191 // new entry (leave res == null)
192 entry->key = aKey->Clone();
193 entry->value = aData;
194 }
195 }
196
197 if (mLock) PR_Unlock(mLock);
198
199 return res;
200 }
201
202 void *nsHashtable::Get(nsHashKey *aKey)
203 {
204 if (!mHashtable.ops) return nullptr;
205
206 if (mLock) PR_Lock(mLock);
207
208 HTEntry* entry =
209 static_cast<HTEntry*>
210 (PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_LOOKUP));
211 void *ret = PL_DHASH_ENTRY_IS_BUSY(entry) ? entry->value : nullptr;
212
213 if (mLock) PR_Unlock(mLock);
214
215 return ret;
216 }
217
218 void *nsHashtable::Remove(nsHashKey *aKey)
219 {
220 if (!mHashtable.ops) return nullptr;
221
222 if (mLock) PR_Lock(mLock);
223
224 // shouldn't be adding an item during enumeration
225 PR_ASSERT(!mEnumerating);
226
227
228 // need to see if the entry is actually there, in order to get the
229 // old value for the result
230 HTEntry* entry =
231 static_cast<HTEntry*>
232 (PL_DHashTableOperate(&mHashtable, aKey, PL_DHASH_LOOKUP));
233 void *res;
234
235 if (PL_DHASH_ENTRY_IS_FREE(entry)) {
236 // value wasn't in the table anyway
237 res = nullptr;
238 } else {
239 res = entry->value;
240 PL_DHashTableRawRemove(&mHashtable, entry);
241 }
242
243 if (mLock) PR_Unlock(mLock);
244
245 return res;
246 }
247
248 // XXX This method was called _hashEnumerateCopy, but it didn't copy the element!
249 // I don't know how this was supposed to work since the elements are neither copied
250 // nor refcounted.
251 static PLDHashOperator
252 hashEnumerateShare(PLDHashTable *table, PLDHashEntryHdr *hdr,
253 uint32_t i, void *arg)
254 {
255 nsHashtable *newHashtable = (nsHashtable *)arg;
256 HTEntry * entry = static_cast<HTEntry*>(hdr);
257
258 newHashtable->Put(entry->key, entry->value);
259 return PL_DHASH_NEXT;
260 }
261
262 nsHashtable * nsHashtable::Clone()
263 {
264 if (!mHashtable.ops) return nullptr;
265
266 bool threadSafe = (mLock != nullptr);
267 nsHashtable *newHashTable = new nsHashtable(mHashtable.entryCount, threadSafe);
268
269 PL_DHashTableEnumerate(&mHashtable, hashEnumerateShare, newHashTable);
270 return newHashTable;
271 }
272
273 void nsHashtable::Enumerate(nsHashtableEnumFunc aEnumFunc, void* aClosure)
274 {
275 if (!mHashtable.ops) return;
276
277 bool wasEnumerating = mEnumerating;
278 mEnumerating = true;
279 _HashEnumerateArgs thunk;
280 thunk.fn = aEnumFunc;
281 thunk.arg = aClosure;
282 PL_DHashTableEnumerate(&mHashtable, hashEnumerate, &thunk);
283 mEnumerating = wasEnumerating;
284 }
285
286 static PLDHashOperator
287 hashEnumerateRemove(PLDHashTable*, PLDHashEntryHdr* hdr, uint32_t i, void *arg)
288 {
289 HTEntry* entry = static_cast<HTEntry*>(hdr);
290 _HashEnumerateArgs* thunk = (_HashEnumerateArgs*)arg;
291 if (thunk) {
292 return thunk->fn(entry->key, entry->value, thunk->arg)
293 ? PL_DHASH_REMOVE
294 : PL_DHASH_STOP;
295 }
296 return PL_DHASH_REMOVE;
297 }
298
299 void nsHashtable::Reset() {
300 Reset(nullptr);
301 }
302
303 void nsHashtable::Reset(nsHashtableEnumFunc destroyFunc, void* aClosure)
304 {
305 if (!mHashtable.ops) return;
306
307 _HashEnumerateArgs thunk, *thunkp;
308 if (!destroyFunc) {
309 thunkp = nullptr;
310 } else {
311 thunkp = &thunk;
312 thunk.fn = destroyFunc;
313 thunk.arg = aClosure;
314 }
315 PL_DHashTableEnumerate(&mHashtable, hashEnumerateRemove, thunkp);
316 }
317
318 // nsISerializable helpers
319
320 nsHashtable::nsHashtable(nsIObjectInputStream* aStream,
321 nsHashtableReadEntryFunc aReadEntryFunc,
322 nsHashtableFreeEntryFunc aFreeEntryFunc,
323 nsresult *aRetVal)
324 : mLock(nullptr),
325 mEnumerating(false)
326 {
327 MOZ_COUNT_CTOR(nsHashtable);
328
329 bool threadSafe;
330 nsresult rv = aStream->ReadBoolean(&threadSafe);
331 if (NS_SUCCEEDED(rv)) {
332 if (threadSafe) {
333 mLock = PR_NewLock();
334 if (!mLock)
335 rv = NS_ERROR_OUT_OF_MEMORY;
336 }
337
338 if (NS_SUCCEEDED(rv)) {
339 uint32_t count;
340 rv = aStream->Read32(&count);
341
342 if (NS_SUCCEEDED(rv)) {
343 bool status =
344 PL_DHashTableInit(&mHashtable, &hashtableOps,
345 nullptr, sizeof(HTEntry), count,
346 fallible_t());
347 if (!status) {
348 mHashtable.ops = nullptr;
349 rv = NS_ERROR_OUT_OF_MEMORY;
350 } else {
351 for (uint32_t i = 0; i < count; i++) {
352 nsHashKey* key;
353 void *data;
354
355 rv = aReadEntryFunc(aStream, &key, &data);
356 if (NS_SUCCEEDED(rv)) {
357 Put(key, data);
358
359 // XXXbe must we clone key? can't we hand off
360 aFreeEntryFunc(aStream, key, nullptr);
361 }
362 }
363 }
364 }
365 }
366 }
367 *aRetVal = rv;
368 }
369
370 struct WriteEntryArgs {
371 nsIObjectOutputStream* mStream;
372 nsHashtableWriteDataFunc mWriteDataFunc;
373 nsresult mRetVal;
374 };
375
376 static bool
377 WriteEntry(nsHashKey *aKey, void *aData, void* aClosure)
378 {
379 WriteEntryArgs* args = (WriteEntryArgs*) aClosure;
380 nsIObjectOutputStream* stream = args->mStream;
381
382 nsresult rv = aKey->Write(stream);
383 if (NS_SUCCEEDED(rv))
384 rv = args->mWriteDataFunc(stream, aData);
385
386 args->mRetVal = rv;
387 return true;
388 }
389
390 nsresult
391 nsHashtable::Write(nsIObjectOutputStream* aStream,
392 nsHashtableWriteDataFunc aWriteDataFunc) const
393 {
394 if (!mHashtable.ops)
395 return NS_ERROR_OUT_OF_MEMORY;
396 bool threadSafe = (mLock != nullptr);
397 nsresult rv = aStream->WriteBoolean(threadSafe);
398 if (NS_FAILED(rv)) return rv;
399
400 // Write the entry count first, so we know how many key/value pairs to read.
401 uint32_t count = mHashtable.entryCount;
402 rv = aStream->Write32(count);
403 if (NS_FAILED(rv)) return rv;
404
405 // Write all key/value pairs in the table.
406 WriteEntryArgs args = {aStream, aWriteDataFunc};
407 const_cast<nsHashtable*>(this)->Enumerate(WriteEntry, (void*) &args);
408 return args.mRetVal;
409 }
410
411 ////////////////////////////////////////////////////////////////////////////////
412
413 // Copy Constructor
414 // We need to free mStr if the object is passed with mOwnership as OWN. As the
415 // destructor here is freeing mStr in that case, mStr is NOT getting leaked here.
416
417 nsCStringKey::nsCStringKey(const nsCStringKey& aKey)
418 : mStr(aKey.mStr), mStrLen(aKey.mStrLen), mOwnership(aKey.mOwnership)
419 {
420 if (mOwnership != NEVER_OWN) {
421 uint32_t len = mStrLen * sizeof(char);
422 char* str = reinterpret_cast<char*>(nsMemory::Alloc(len + sizeof(char)));
423 if (!str) {
424 // Pray we don't dangle!
425 mOwnership = NEVER_OWN;
426 } else {
427 // Use memcpy in case there are embedded NULs.
428 memcpy(str, mStr, len);
429 str[mStrLen] = '\0';
430 mStr = str;
431 mOwnership = OWN;
432 }
433 }
434 #ifdef DEBUG
435 mKeyType = CStringKey;
436 #endif
437 MOZ_COUNT_CTOR(nsCStringKey);
438 }
439
440 nsCStringKey::nsCStringKey(const nsAFlatCString& str)
441 : mStr(const_cast<char*>(str.get())),
442 mStrLen(str.Length()),
443 mOwnership(OWN_CLONE)
444 {
445 NS_ASSERTION(mStr, "null string key");
446 #ifdef DEBUG
447 mKeyType = CStringKey;
448 #endif
449 MOZ_COUNT_CTOR(nsCStringKey);
450 }
451
452 nsCStringKey::nsCStringKey(const nsACString& str)
453 : mStr(ToNewCString(str)),
454 mStrLen(str.Length()),
455 mOwnership(OWN)
456 {
457 NS_ASSERTION(mStr, "null string key");
458 #ifdef DEBUG
459 mKeyType = CStringKey;
460 #endif
461 MOZ_COUNT_CTOR(nsCStringKey);
462 }
463
464 nsCStringKey::nsCStringKey(const char* str, int32_t strLen, Ownership own)
465 : mStr((char*)str), mStrLen(strLen), mOwnership(own)
466 {
467 NS_ASSERTION(mStr, "null string key");
468 if (mStrLen == uint32_t(-1))
469 mStrLen = strlen(str);
470 #ifdef DEBUG
471 mKeyType = CStringKey;
472 #endif
473 MOZ_COUNT_CTOR(nsCStringKey);
474 }
475
476 nsCStringKey::~nsCStringKey(void)
477 {
478 if (mOwnership == OWN)
479 nsMemory::Free(mStr);
480 MOZ_COUNT_DTOR(nsCStringKey);
481 }
482
483 uint32_t
484 nsCStringKey::HashCode(void) const
485 {
486 return HashString(mStr, mStrLen);
487 }
488
489 bool
490 nsCStringKey::Equals(const nsHashKey* aKey) const
491 {
492 NS_ASSERTION(aKey->GetKeyType() == CStringKey, "mismatched key types");
493 nsCStringKey* other = (nsCStringKey*)aKey;
494 NS_ASSERTION(mStrLen != uint32_t(-1), "never called HashCode");
495 NS_ASSERTION(other->mStrLen != uint32_t(-1), "never called HashCode");
496 if (mStrLen != other->mStrLen)
497 return false;
498 return memcmp(mStr, other->mStr, mStrLen * sizeof(char)) == 0;
499 }
500
501 nsHashKey*
502 nsCStringKey::Clone() const
503 {
504 if (mOwnership == NEVER_OWN)
505 return new nsCStringKey(mStr, mStrLen, NEVER_OWN);
506
507 // Since this might hold binary data OR a string, we ensure that the
508 // clone string is zero terminated, but don't assume that the source
509 // string was so terminated.
510
511 uint32_t len = mStrLen * sizeof(char);
512 char* str = (char*)nsMemory::Alloc(len + sizeof(char));
513 if (str == nullptr)
514 return nullptr;
515 memcpy(str, mStr, len);
516 str[len] = 0;
517 return new nsCStringKey(str, mStrLen, OWN);
518 }
519
520 nsCStringKey::nsCStringKey(nsIObjectInputStream* aStream, nsresult *aResult)
521 : mStr(nullptr), mStrLen(0), mOwnership(OWN)
522 {
523 nsAutoCString str;
524 nsresult rv = aStream->ReadCString(str);
525 mStr = ToNewCString(str);
526 if (NS_SUCCEEDED(rv))
527 mStrLen = str.Length();
528 *aResult = rv;
529 MOZ_COUNT_CTOR(nsCStringKey);
530 }
531
532 nsresult
533 nsCStringKey::Write(nsIObjectOutputStream* aStream) const
534 {
535 return aStream->WriteStringZ(mStr);
536 }
537
538 ////////////////////////////////////////////////////////////////////////////////
539 // nsObjectHashtable: an nsHashtable where the elements are C++ objects to be
540 // deleted
541
542 nsObjectHashtable::nsObjectHashtable(nsHashtableCloneElementFunc cloneElementFun,
543 void* cloneElementClosure,
544 nsHashtableEnumFunc destroyElementFun,
545 void* destroyElementClosure,
546 uint32_t aSize, bool threadSafe)
547 : nsHashtable(aSize, threadSafe),
548 mCloneElementFun(cloneElementFun),
549 mCloneElementClosure(cloneElementClosure),
550 mDestroyElementFun(destroyElementFun),
551 mDestroyElementClosure(destroyElementClosure)
552 {
553 }
554
555 nsObjectHashtable::~nsObjectHashtable()
556 {
557 Reset();
558 }
559
560
561 PLDHashOperator
562 nsObjectHashtable::CopyElement(PLDHashTable* table,
563 PLDHashEntryHdr* hdr,
564 uint32_t i, void *arg)
565 {
566 nsObjectHashtable *newHashtable = (nsObjectHashtable *)arg;
567 HTEntry *entry = static_cast<HTEntry*>(hdr);
568
569 void* newElement =
570 newHashtable->mCloneElementFun(entry->key, entry->value,
571 newHashtable->mCloneElementClosure);
572 if (newElement == nullptr)
573 return PL_DHASH_STOP;
574 newHashtable->Put(entry->key, newElement);
575 return PL_DHASH_NEXT;
576 }
577
578 nsHashtable*
579 nsObjectHashtable::Clone()
580 {
581 if (!mHashtable.ops) return nullptr;
582
583 bool threadSafe = false;
584 if (mLock)
585 threadSafe = true;
586 nsObjectHashtable* newHashTable =
587 new nsObjectHashtable(mCloneElementFun, mCloneElementClosure,
588 mDestroyElementFun, mDestroyElementClosure,
589 mHashtable.entryCount, threadSafe);
590
591 PL_DHashTableEnumerate(&mHashtable, CopyElement, newHashTable);
592 return newHashTable;
593 }
594
595 void
596 nsObjectHashtable::Reset()
597 {
598 nsHashtable::Reset(mDestroyElementFun, mDestroyElementClosure);
599 }
600
601 bool
602 nsObjectHashtable::RemoveAndDelete(nsHashKey *aKey)
603 {
604 void *value = Remove(aKey);
605 if (value && mDestroyElementFun)
606 return !!(*mDestroyElementFun)(aKey, value, mDestroyElementClosure);
607 return false;
608 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial