blob: a149bf95a3cf769bbb199e878c975311f318506a (
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
|
/* -*- 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;
};
} // namespace a11y
} // namespace mozilla
#endif
|
