blob: 3c3ed74c3b9743acf792f0fad167756963215988 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
/* -*- 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/. */
/**
* A class to generate unique IDs in the range [ - 2^31, 0 )
*/
#ifndef MOZILLA_A11Y_IDSet_h_
#define MOZILLA_A11Y_IDSet_h_
#include "mozilla/Attributes.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/SplayTree.h"
namespace mozilla {
namespace a11y {
/**
* On windows an accessible's id must be a negative 32 bit integer. It is
* important to support recycling arbitrary IDs because accessibles can be
* created and destroyed at any time in the life of a page. IDSet provides 2
* operations: generate an ID in the range (0, mMaxId], and release an ID so
* it can be allocated again. Allocated ID are tracked by a sparse bitmap
* implemented with a splay tree. Nodes in the tree are keyed by the upper N
* bits of the ID, and the node contains a bitmap tracking the allocation of
* 2^(ceil(log2(mMaxId)) - N) IDs.
*
* Note that negation is handled by MsaaIdGenerator as it performs additional
* decoration on the ID generated by IDSet.
* @see mozilla::a11y::MsaaIdGenerator
*/
class IDSet
{
public:
constexpr explicit IDSet(const uint32_t aMaxIdBits)
: mBitSet()
, mIdx(0)
, mMaxId((1UL << aMaxIdBits) - 1UL)
, mMaxIdx(mMaxId / bitsPerElt)
{
}
/**
* Return a new unique id.
*/
uint32_t GetID()
{
uint32_t idx = mIdx;
while (true) {
BitSetElt* elt = mBitSet.findOrInsert(BitSetElt(idx));
if (elt->mBitvec[0] != UINT64_MAX) {
uint32_t i = CountTrailingZeroes64(~elt->mBitvec[0]);
elt->mBitvec[0] |= (1ull << i);
mIdx = idx;
return (elt->mIdx * bitsPerElt + i);
}
if (elt->mBitvec[1] != UINT64_MAX) {
uint32_t i = CountTrailingZeroes64(~elt->mBitvec[1]);
elt->mBitvec[1] |= (1ull << i);
mIdx = idx;
return (elt->mIdx * bitsPerElt + bitsPerWord + i);
}
idx++;
if (idx > mMaxIdx) {
idx = 0;
}
if (idx == mIdx) {
MOZ_CRASH("used up all the available ids");
}
}
}
/**
* Free a no longer required id so it may be allocated again.
*/
void ReleaseID(uint32_t aID)
{
MOZ_ASSERT(aID < mMaxId);
uint32_t idx = aID / bitsPerElt;
mIdx = idx;
BitSetElt* elt = mBitSet.find(BitSetElt(idx));
MOZ_ASSERT(elt);
uint32_t vecIdx = (aID % bitsPerElt) / bitsPerWord;
elt->mBitvec[vecIdx] &= ~(1ull << (aID % bitsPerWord));
if (elt->mBitvec[0] == 0 && elt->mBitvec[1] == 0) {
delete mBitSet.remove(*elt);
}
}
private:
static const unsigned int wordsPerElt = 2;
static const unsigned int bitsPerWord = 64;
static const unsigned int bitsPerElt = wordsPerElt * bitsPerWord;
struct BitSetElt : mozilla::SplayTreeNode<BitSetElt>
{
explicit BitSetElt(uint32_t aIdx) :
mIdx(aIdx)
{ mBitvec[0] = mBitvec[1] = 0; }
uint64_t mBitvec[wordsPerElt];
uint32_t mIdx;
static int compare(const BitSetElt& a, const BitSetElt& b)
{
if (a.mIdx == b.mIdx) {
return 0;
}
if (a.mIdx < b.mIdx) {
return -1;
}
return 1;
}
};
SplayTree<BitSetElt, BitSetElt> mBitSet;
uint32_t mIdx;
const uint32_t mMaxId;
const uint32_t mMaxIdx;
};
}
}
#endif
|
