summaryrefslogtreecommitdiffstats
path: root/accessible/windows/msaa/IDSet.h
diff options
context:
space:
mode:
authorMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
committerMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
commit5f8de423f190bbb79a62f804151bc24824fa32d8 (patch)
tree10027f336435511475e392454359edea8e25895d /accessible/windows/msaa/IDSet.h
parent49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff)
downloadUXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip
Add m-esr52 at 52.6.0
Diffstat (limited to 'accessible/windows/msaa/IDSet.h')
-rw-r--r--accessible/windows/msaa/IDSet.h136
1 files changed, 136 insertions, 0 deletions
diff --git a/accessible/windows/msaa/IDSet.h b/accessible/windows/msaa/IDSet.h
new file mode 100644
index 000000000..3c3ed74c3
--- /dev/null
+++ b/accessible/windows/msaa/IDSet.h
@@ -0,0 +1,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