accessible/base/IDSet.h

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