tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

IDSet.h (3520B)

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