ui/events/gesture_detection/bitset_32.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_
   6 #define UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_
   7
   8 #include "base/basictypes.h"
   9
  10 namespace ui {
  11
  12 // Port of BitSet32 from Android
  13 // * platform/system/core/include/utils/BitSet.h
  14 // * Change-Id: I9bbf41f9d2d4a2593b0e6d7d8be7e283f985bade
  15 // * Please update the Change-Id as upstream Android changes are pulled.
  16 struct BitSet32 {
  17   uint32_t value;
  18
  19   inline BitSet32() : value(0) {}
  20   explicit inline BitSet32(uint32_t value) : value(value) {}
  21
  22   // Gets the value associated with a particular bit index.
  23   static inline uint32_t value_for_bit(uint32_t n) { return 0x80000000 >> n; }
  24
  25   // Clears the bit set.
  26   inline void clear() { value = 0; }
  27
  28   // Returns the number of marked bits in the set.
  29   inline uint32_t count() const { return popcnt(value); }
  30
  31   // Returns true if the bit set does not contain any marked bits.
  32   inline bool is_empty() const { return !value; }
  33
  34   // Returns true if the bit set does not contain any unmarked bits.
  35   inline bool is_full() const { return value == 0xffffffff; }
  36
  37   // Returns true if the specified bit is marked.
  38   inline bool has_bit(uint32_t n) const {
  39     return (value & value_for_bit(n)) != 0;
  40   }
  41
  42   // Marks the specified bit.
  43   inline void mark_bit(uint32_t n) { value |= value_for_bit(n); }
  44
  45   // Clears the specified bit.
  46   inline void clear_bit(uint32_t n) { value &= ~value_for_bit(n); }
  47
  48   // Finds the first marked bit in the set.
  49   // Result is undefined if all bits are unmarked.
  50   inline uint32_t first_marked_bit() const { return clz(value); }
  51
  52   // Finds the first unmarked bit in the set.
  53   // Result is undefined if all bits are marked.
  54   inline uint32_t first_unmarked_bit() const { return clz(~value); }
  55
  56   // Finds the last marked bit in the set.
  57   // Result is undefined if all bits are unmarked.
  58   inline uint32_t last_marked_bit() const { return 31 - ctz(value); }
  59
  60   // Finds the first marked bit in the set and clears it.  Returns the bit
  61   // index.
  62   // Result is undefined if all bits are unmarked.
  63   inline uint32_t clear_first_marked_bit() {
  64     uint32_t n = first_marked_bit();
  65     clear_bit(n);
  66     return n;
  67   }
  68
  69   // Finds the first unmarked bit in the set and marks it.  Returns the bit
  70   // index.
  71   // Result is undefined if all bits are marked.
  72   inline uint32_t mark_first_unmarked_bit() {
  73     uint32_t n = first_unmarked_bit();
  74     mark_bit(n);
  75     return n;
  76   }
  77
  78   // Finds the last marked bit in the set and clears it.  Returns the bit index.
  79   // Result is undefined if all bits are unmarked.
  80   inline uint32_t clear_last_marked_bit() {
  81     uint32_t n = last_marked_bit();
  82     clear_bit(n);
  83     return n;
  84   }
  85
  86   // Gets the inde of the specified bit in the set, which is the number of
  87   // marked bits that appear before the specified bit.
  88   inline uint32_t get_index_of_bit(uint32_t n) const {
  89     return popcnt(value & ~(0xffffffffUL >> n));
  90   }
  91
  92   inline bool operator==(const BitSet32& other) const {
  93     return value == other.value;
  94   }
  95   inline bool operator!=(const BitSet32& other) const {
  96     return value != other.value;
  97   }
  98
  99  private:
 100 #if defined(COMPILER_GCC) || defined(__clang__)
 101   static inline uint32_t popcnt(uint32_t v) { return __builtin_popcount(v); }
 102   static inline uint32_t clz(uint32_t v) { return __builtin_clz(v); }
 103   static inline uint32_t ctz(uint32_t v) { return __builtin_ctz(v); }
 104 #else
 105   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
 106   static inline uint32_t popcnt(uint32_t v) {
 107     v = v - ((v >> 1) & 0x55555555);
 108     v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
 109     return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
 110   }
 111   // TODO(jdduke): Use intrinsics (BitScan{Forward,Reverse}) with MSVC.
 112   static inline uint32_t clz(uint32_t v) {
 113     v |= (v >> 1);
 114     v |= (v >> 2);
 115     v |= (v >> 4);
 116     v |= (v >> 8);
 117     v |= (v >> 16);
 118     return 32 - popcnt(v);
 119   }
 120   static inline uint32_t ctz(uint32_t v) {
 121     return popcnt((v & static_cast<uint32_t>(-static_cast<int>(v))) - 1);
 122   }
 123 #endif
 124 };
 125
 126 }  // namespace ui
 127
 128 #endif  // UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_