• file
• revisions
• annotate
• diff
• comparison
• raw

xpcom/ds/nsCheapSets.h@b8a032363ba2 (annotated)

xpcom/ds/nsCheapSets.h

Thu, 22 Jan 2015 13:21:57 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Thu, 22 Jan 2015 13:21:57 +0100

branch

TOR_BUG_9701

changeset 15

b8a032363ba2

permissions

-rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

michael@0	1	/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0	2	/* This Source Code Form is subject to the terms of the Mozilla Public
michael@0	3	* License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0	4	* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0	5
michael@0	6	#ifndef __nsCheapSets_h__
michael@0	7	#define __nsCheapSets_h__
michael@0	8
michael@0	9	#include "nsTHashtable.h"
michael@0	10	#include <stdint.h>
michael@0	11
michael@0	12	/**
michael@0	13	* A set that takes up minimal size when there are 0 or 1 entries in the set.
michael@0	14	* Use for cases where sizes of 0 and 1 are even slightly common.
michael@0	15	*/
michael@0	16	template<typename EntryType>
michael@0	17	class nsCheapSet
michael@0	18	{
michael@0	19	public:
michael@0	20	typedef typename EntryType::KeyType KeyType;
michael@0	21	typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg);
michael@0	22
michael@0	23	nsCheapSet() : mState(ZERO)
michael@0	24	{
michael@0	25	}
michael@0	26	~nsCheapSet()
michael@0	27	{
michael@0	28	switch (mState) {
michael@0	29	case ZERO:
michael@0	30	break;
michael@0	31	case ONE:
michael@0	32	GetSingleEntry()->~EntryType();
michael@0	33	break;
michael@0	34	case MANY:
michael@0	35	delete mUnion.table;
michael@0	36	break;
michael@0	37	default:
michael@0	38	NS_NOTREACHED("bogus state");
michael@0	39	break;
michael@0	40	}
michael@0	41	}
michael@0	42
michael@0	43	nsresult Put(const KeyType aVal);
michael@0	44
michael@0	45	void Remove(const KeyType aVal);
michael@0	46
michael@0	47	bool Contains(const KeyType aVal)
michael@0	48	{
michael@0	49	switch (mState) {
michael@0	50	case ZERO:
michael@0	51	return false;
michael@0	52	case ONE:
michael@0	53	return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
michael@0	54	case MANY:
michael@0	55	return !!mUnion.table->GetEntry(aVal);
michael@0	56	default:
michael@0	57	NS_NOTREACHED("bogus state");
michael@0	58	return false;
michael@0	59	}
michael@0	60	}
michael@0	61
michael@0	62	uint32_t EnumerateEntries(Enumerator enumFunc, void* userArg)
michael@0	63	{
michael@0	64	switch (mState) {
michael@0	65	case ZERO:
michael@0	66	return 0;
michael@0	67	case ONE:
michael@0	68	if (enumFunc(GetSingleEntry(), userArg) == PL_DHASH_REMOVE) {
michael@0	69	GetSingleEntry()->~EntryType();
michael@0	70	mState = ZERO;
michael@0	71	}
michael@0	72	return 1;
michael@0	73	case MANY:
michael@0	74	return mUnion.table->EnumerateEntries(enumFunc, userArg);
michael@0	75	default:
michael@0	76	NS_NOTREACHED("bogus state");
michael@0	77	return 0;
michael@0	78	}
michael@0	79	}
michael@0	80
michael@0	81	private:
michael@0	82	EntryType* GetSingleEntry()
michael@0	83	{
michael@0	84	return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
michael@0	85	}
michael@0	86
michael@0	87	enum SetState {
michael@0	88	ZERO,
michael@0	89	ONE,
michael@0	90	MANY
michael@0	91	};
michael@0	92
michael@0	93	union {
michael@0	94	nsTHashtable<EntryType> *table;
michael@0	95	char singleEntry[sizeof(EntryType)];
michael@0	96	} mUnion;
michael@0	97	enum SetState mState;
michael@0	98	};
michael@0	99
michael@0	100	template<typename EntryType>
michael@0	101	nsresult
michael@0	102	nsCheapSet<EntryType>::Put(const KeyType aVal)
michael@0	103	{
michael@0	104	switch (mState) {
michael@0	105	case ZERO:
michael@0	106	new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
michael@0	107	mState = ONE;
michael@0	108	return NS_OK;
michael@0	109	case ONE:
michael@0	110	{
michael@0	111	nsTHashtable<EntryType> *table = new nsTHashtable<EntryType>();
michael@0	112	EntryType *entry = GetSingleEntry();
michael@0	113	table->PutEntry(entry->GetKey());
michael@0	114	entry->~EntryType();
michael@0	115	mUnion.table = table;
michael@0	116	mState = MANY;
michael@0	117	}
michael@0	118	// Fall through.
michael@0	119	case MANY:
michael@0	120	mUnion.table->PutEntry(aVal);
michael@0	121	return NS_OK;
michael@0	122	default:
michael@0	123	NS_NOTREACHED("bogus state");
michael@0	124	return NS_OK;
michael@0	125	}
michael@0	126	}
michael@0	127
michael@0	128	template<typename EntryType>
michael@0	129	void
michael@0	130	nsCheapSet<EntryType>::Remove(const KeyType aVal)
michael@0	131	{
michael@0	132	switch (mState) {
michael@0	133	case ZERO:
michael@0	134	break;
michael@0	135	case ONE:
michael@0	136	if (Contains(aVal)) {
michael@0	137	GetSingleEntry()->~EntryType();
michael@0	138	mState = ZERO;
michael@0	139	}
michael@0	140	break;
michael@0	141	case MANY:
michael@0	142	mUnion.table->RemoveEntry(aVal);
michael@0	143	break;
michael@0	144	default:
michael@0	145	NS_NOTREACHED("bogus state");
michael@0	146	break;
michael@0	147	}
michael@0	148	}
michael@0	149
michael@0	150	#endif