/src/mozilla-central/xpcom/ds/nsCheapSets.h

Source (jump to first uncovered line)
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef __nsCheapSets_h__
#define __nsCheapSets_h__

#include "nsTHashtable.h"
#include <stdint.h>

enum nsCheapSetOperator
{
  OpNext = 0,   // enumerator says continue
  OpRemove = 1, // enumerator says remove and continue
};

/**
 * A set that takes up minimal size when there are 0 or 1 entries in the set.
 * Use for cases where sizes of 0 and 1 are even slightly common.
 */
template<typename EntryType>
class nsCheapSet
{
public:
  typedef typename EntryType::KeyType KeyType;
  typedef nsCheapSetOperator (*Enumerator)(EntryType* aEntry, void* userArg);

  nsCheapSet()
    : mState(ZERO)
  {
    mUnion.table = nullptr;
  }
  ~nsCheapSet() { Clear(); }

  /**
   * Remove all entries.
   */
  void Clear()
  {
    switch (mState) {
      case ZERO:
        break;
      case ONE:
        GetSingleEntry()->~EntryType();
        break;
      case MANY:
        delete mUnion.table;
        break;
      default:
        MOZ_ASSERT_UNREACHABLE("bogus state");
        break;
    }
    mState = ZERO;
  }

  void Put(const KeyType aVal);

  void Remove(const KeyType aVal);

  bool Contains(const KeyType aVal)
  {
    switch (mState) {
      case ZERO:
        return false;
      case ONE:
        return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
      case MANY:
        return !!mUnion.table->GetEntry(aVal);
      default:
        MOZ_ASSERT_UNREACHABLE("bogus state");
        return false;
    }
  }

  uint32_t EnumerateEntries(Enumerator aEnumFunc, void* aUserArg)
  {
    switch (mState) {
      case ZERO:
        return 0;
      case ONE:
        if (aEnumFunc(GetSingleEntry(), aUserArg) == OpRemove) {
          GetSingleEntry()->~EntryType();
          mState = ZERO;
        }
        return 1;
      case MANY: {
        uint32_t n = mUnion.table->Count();
        for (auto iter = mUnion.table->Iter(); !iter.Done(); iter.Next()) {
          auto entry = static_cast<EntryType*>(iter.Get());
          if (aEnumFunc(entry, aUserArg) == OpRemove) {
            iter.Remove();
          }
        }
        return n;
      }
      default:
        MOZ_ASSERT_UNREACHABLE("bogus state");
        return 0;
    }
  }

private:
  EntryType* GetSingleEntry()
  {
    return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
  }

  enum SetState
  {
    ZERO,
    ONE,
    MANY
  };

  union
  {
    nsTHashtable<EntryType>* table;
    char singleEntry[sizeof(EntryType)];
  } mUnion;
  enum SetState mState;
};

template<typename EntryType>
void
nsCheapSet<EntryType>::Put(const KeyType aVal)
{
  switch (mState) {
    case ZERO:
      new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
      mState = ONE;
      return;
    case ONE: {
      nsTHashtable<EntryType>* table = new nsTHashtable<EntryType>();
      EntryType* entry = GetSingleEntry();
      table->PutEntry(entry->GetKey());
      entry->~EntryType();
      mUnion.table = table;
      mState = MANY;
    }
    MOZ_FALLTHROUGH;

    case MANY:
      mUnion.table->PutEntry(aVal);
      return;
    default:
      MOZ_ASSERT_UNREACHABLE("bogus state");
      return;
  }
}

template<typename EntryType>
void
nsCheapSet<EntryType>::Remove(const KeyType aVal)
{
  switch (mState) {
    case ZERO:
      break;
    case ONE:
      if (Contains(aVal)) {
        GetSingleEntry()->~EntryType();
        mState = ZERO;
      }
      break;
    case MANY:
      mUnion.table->RemoveEntry(aVal);
      break;
    default:
      MOZ_ASSERT_UNREACHABLE("bogus state");
      break;
  }
}

#endif

Line	Count	Source (jump to first uncovered line)
1		/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -- */
2		/* vim: set ts=8 sts=2 et sw=2 tw=80: */
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		#ifndef __nsCheapSets_h__
8		#define __nsCheapSets_h__
9
10		#include "nsTHashtable.h"
11		#include <stdint.h>
12
13		enum nsCheapSetOperator
14		{
15		OpNext = 0, // enumerator says continue
16		OpRemove = 1, // enumerator says remove and continue
17		};
18
19		/**
20		* A set that takes up minimal size when there are 0 or 1 entries in the set.
21		* Use for cases where sizes of 0 and 1 are even slightly common.
22		*/
23		template<typename EntryType>
24		class nsCheapSet
25		{
26		public:
27		typedef typename EntryType::KeyType KeyType;
28		typedef nsCheapSetOperator (Enumerator)(EntryType aEntry, void* userArg);
29
30		nsCheapSet()
31		: mState(ZERO)
32	0	{
33	0	mUnion.table = nullptr;
34	0	} Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::nsCheapSet() Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::nsCheapSet()
35	0	~nsCheapSet() { Clear(); } Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::~nsCheapSet() Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::~nsCheapSet()
36
37		/**
38		* Remove all entries.
39		*/
40		void Clear()
41	0	{
42	0	switch (mState) {
43	0	case ZERO:
44	0	break;
45	0	case ONE:
46	0	GetSingleEntry()->~EntryType();
47	0	break;
48	0	case MANY:
49	0	delete mUnion.table;
50	0	break;
51	0	default:
52	0	MOZ_ASSERT_UNREACHABLE("bogus state");
53	0	break;
54	0	}
55	0	mState = ZERO;
56	0	} Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::Clear() Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::Clear()
57
58		void Put(const KeyType aVal);
59
60		void Remove(const KeyType aVal);
61
62		bool Contains(const KeyType aVal)
63	0	{
64	0	switch (mState) {
65	0	case ZERO:
66	0	return false;
67	0	case ONE:
68	0	return GetSingleEntry()->KeyEquals(EntryType::KeyToPointer(aVal));
69	0	case MANY:
70	0	return !!mUnion.table->GetEntry(aVal);
71	0	default:
72	0	MOZ_ASSERT_UNREACHABLE("bogus state");
73	0	return false;
74	0	}
75	0	} Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::Contains(unsigned int const&) Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::Contains(mozilla::dom::Element*)
76
77		uint32_t EnumerateEntries(Enumerator aEnumFunc, void* aUserArg)
78	0	{
79	0	switch (mState) {
80	0	case ZERO:
81	0	return 0;
82	0	case ONE:
83	0	if (aEnumFunc(GetSingleEntry(), aUserArg) == OpRemove) {
84	0	GetSingleEntry()->~EntryType();
85	0	mState = ZERO;
86	0	}
87	0	return 1;
88	0	case MANY: {
89	0	uint32_t n = mUnion.table->Count();
90	0	for (auto iter = mUnion.table->Iter(); !iter.Done(); iter.Next()) {
91	0	auto entry = static_cast<EntryType*>(iter.Get());
92	0	if (aEnumFunc(entry, aUserArg) == OpRemove) {
93	0	iter.Remove();
94	0	}
95	0	}
96	0	return n;
97	0	}
98	0	default:
99	0	MOZ_ASSERT_UNREACHABLE("bogus state");
100	0	return 0;
101	0	}
102	0	}
103
104		private:
105		EntryType* GetSingleEntry()
106	0	{
107	0	return reinterpret_cast<EntryType*>(&mUnion.singleEntry[0]);
108	0	} Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::GetSingleEntry() Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::GetSingleEntry()
109
110		enum SetState
111		{
112		ZERO,
113		ONE,
114		MANY
115		};
116
117		union
118		{
119		nsTHashtable<EntryType>* table;
120		char singleEntry[sizeof(EntryType)];
121		} mUnion;
122		enum SetState mState;
123		};
124
125		template<typename EntryType>
126		void
127		nsCheapSet<EntryType>::Put(const KeyType aVal)
128	0	{
129	0	switch (mState) {
130	0	case ZERO:
131	0	new (GetSingleEntry()) EntryType(EntryType::KeyToPointer(aVal));
132	0	mState = ONE;
133	0	return;
134	0	case ONE: {
135	0	nsTHashtable<EntryType>* table = new nsTHashtable<EntryType>();
136	0	EntryType* entry = GetSingleEntry();
137	0	table->PutEntry(entry->GetKey());
138	0	entry->~EntryType();
139	0	mUnion.table = table;
140	0	mState = MANY;
141	0	}
142	0	MOZ_FALLTHROUGH;
143	0
144	0	case MANY:
145	0	mUnion.table->PutEntry(aVal);
146	0	return;
147	0	default:
148	0	MOZ_ASSERT_UNREACHABLE("bogus state");
149	0	return;
150	0	}
151	0	} Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::Put(unsigned int const&) Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::Put(mozilla::dom::Element*)
152
153		template<typename EntryType>
154		void
155		nsCheapSet<EntryType>::Remove(const KeyType aVal)
156	0	{
157	0	switch (mState) {
158	0	case ZERO:
159	0	break;
160	0	case ONE:
161	0	if (Contains(aVal)) {
162	0	GetSingleEntry()->~EntryType();
163	0	mState = ZERO;
164	0	}
165	0	break;
166	0	case MANY:
167	0	mUnion.table->RemoveEntry(aVal);
168	0	break;
169	0	default:
170	0	MOZ_ASSERT_UNREACHABLE("bogus state");
171	0	break;
172	0	}
173	0	} Unexecuted instantiation: nsCheapSet<nsUint32HashKey>::Remove(unsigned int const&) Unexecuted instantiation: nsCheapSet<nsPtrHashKey<mozilla::dom::Element> >::Remove(mozilla::dom::Element*)
174
175		#endif

Coverage Report

Created: 2018-09-25 14:53