/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * 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/. */

#ifndef jit_BitSet_h
#define jit_BitSet_h

#include "IonAllocPolicy.h"

namespace js {
namespace jit {

// Provides constant time set insertion and removal, and fast linear
// set operations such as intersection, difference, and union.
// N.B. All set operations must be performed on sets with the same maximum.
class BitSet : private TempObject
{
  public:
    static size_t RawLengthForBits(size_t bits) {
        return 1 + bits / (8 * sizeof(uint32_t));
    }

  private:
    BitSet(unsigned int max) :
        max_(max),
        bits_(NULL) {}

    unsigned int max_;
    uint32_t *bits_;

    static inline uint32_t bitForValue(unsigned int value) {
        return 1l << (uint32_t)(value % (8 * sizeof(uint32_t)));
    }

    static inline unsigned int wordForValue(unsigned int value) {
        return value / (8 * sizeof(uint32_t));
    }

    inline unsigned int numWords() const {
        return RawLengthForBits(max_);
    }

    bool init();

  public:
    class Iterator;

    static BitSet *New(unsigned int max);

    unsigned int getMax() const {
        return max_;
    }

    // O(1): Check if this set contains the given value.
    bool contains(unsigned int value) const {
        JS_ASSERT(bits_);
        JS_ASSERT(value <= max_);

        return !!(bits_[wordForValue(value)] & bitForValue(value));
    }

    // O(max): Check if this set contains any value.
    bool empty() const;

    // O(1): Insert the given value into this set.
    void insert(unsigned int value) {
        JS_ASSERT(bits_);
        JS_ASSERT(value <= max_);

        bits_[wordForValue(value)] |= bitForValue(value);
    }

    // O(max): Insert every element of the given set into this set.
    void insertAll(const BitSet *other);

    // O(1): Remove the given value from this set.
    void remove(unsigned int value) {
        JS_ASSERT(bits_);
        JS_ASSERT(value <= max_);

        bits_[wordForValue(value)] &= ~bitForValue(value);
    }

    // O(max): Remove the every element of the given set from this set.
    void removeAll(const BitSet *other);

    // O(max): Intersect this set with the given set.
    void intersect(const BitSet *other);

    // O(max): Intersect this set with the given set; return whether the
    // intersection caused the set to change.
    bool fixedPointIntersect(const BitSet *other);

    // O(max): Does inplace complement of the set.
    void complement();

    // O(max): Clear this set.
    void clear();

    uint32_t *raw() const {
        return bits_;
    }
    size_t rawLength() const {
        return numWords();
    }
};

class BitSet::Iterator
{
  private:
    BitSet &set_;
    unsigned index_;
    unsigned word_;
    uint32_t value_;

  public:
    Iterator(BitSet &set) :
      set_(set),
      index_(0),
      word_(0),
      value_(set.bits_[0])
    {
        if (!set_.contains(index_))
            (*this)++;
    }

    inline bool more() const {
        return word_ < set_.numWords();
    }
    inline operator bool() const {
        return more();
    }

    inline Iterator& operator++(int dummy) {
        JS_ASSERT(more());
        JS_ASSERT(index_ <= set_.max_);

        index_++;
        value_ >>= 1;

        // Skip words containing only zeros.
        while (value_ == 0) {
            word_++;
            if (!more())
                return *this;

            index_ = word_ * sizeof(value_) * 8;
            value_ = set_.bits_[word_];
        }

        // The result of js_bitscan_ctz32 is undefined if the input is 0.
        JS_ASSERT(value_ != 0);

        int numZeros = js_bitscan_ctz32(value_);
        index_ += numZeros;
        value_ >>= numZeros;

        JS_ASSERT_IF(index_ <= set_.max_, set_.contains(index_));
        return *this;
    }

    unsigned int operator *() {
        JS_ASSERT(index_ <= set_.max_);
        return index_;
    }
};

}
}

#endif /* jit_BitSet_h */