// Copyright 2020 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef LIB_FIDL_CPP_INTERNAL_BITSET_H_
#define LIB_FIDL_CPP_INTERNAL_BITSET_H_

#include <cstddef>
#include <cstdint>

namespace fidl {
namespace internal {

// BitSet used to track field presence in HLCPP tables.
template <size_t N>
class BitSet final {
  static const size_t RoundUpN = (N + 63ull) & ~63ull;
  static const size_t StorageSize = RoundUpN / 64ull;

  static inline size_t StorageIndex(size_t index) { return index / 64ull; }
  static inline uint64_t BitMask(size_t index) { return 1ull << (index % 64ull); }

  // Return the index of the most significant bit set or -1 if none are set.
  static inline int64_t MaxBitSet(uint64_t input) {
    // __builtin_clzll is undefined for an input of 0.
    if (input == 0) {
      return -1;
    }
    return 63ll - __builtin_clzll(input);
  }

 public:
  BitSet() noexcept = default;
  BitSet(const BitSet& other) noexcept = default;
  BitSet& operator=(const BitSet& other) noexcept = default;

  template <size_t Index>
  inline bool IsSet() const noexcept {
    static_assert(Index < N, "index exceeds BitSet size");
    return (storage_[StorageIndex(Index)] & BitMask(Index)) != 0;
  }

  template <size_t Index>
  inline void Set() noexcept {
    static_assert(Index < N, "index exceeds BitSet size");
    storage_[StorageIndex(Index)] |= BitMask(Index);
  }

  template <size_t Index>
  inline void Clear() noexcept {
    static_assert(Index < N, "index exceeds BitSet size");
    storage_[StorageIndex(Index)] &= ~BitMask(Index);
  }

  bool IsEmpty() const noexcept {
    uint64_t cum_union = 0ull;
    for (size_t i = 0; i < StorageSize; i++) {
      cum_union |= storage_[i];
    }
    return cum_union == 0ull;
  }

  int64_t MaxSetIndex() const noexcept {
    static_assert(StorageSize >= 1, "storage size expected to be at least 1");
    for (int64_t i = StorageSize - 1; i >= 1; i--) {
      uint64_t val = storage_[i];
      if (val != 0) {
        return 64ll * i + MaxBitSet(val);
      }
    }
    return MaxBitSet(storage_[0]);
  }

 private:
  uint64_t storage_[StorageSize] = {};
};

// Specialization to avoid compile errors due to 0-sized array.
template <>
class BitSet<0> {
 public:
  BitSet() noexcept = default;
  BitSet(const BitSet& other) noexcept = default;
  BitSet& operator=(const BitSet& other) noexcept = default;

  bool IsEmpty() const noexcept { return true; }

  int64_t MaxSetIndex() const noexcept { return -1; }
};

}  // namespace internal
}  // namespace fidl

#endif  // LIB_FIDL_CPP_INTERNAL_BITSET_H_