/*
 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#ifndef SHARE_LIBADT_VECTSET_HPP
#define SHARE_LIBADT_VECTSET_HPP

#include "memory/allocation.hpp"

// Vector Sets

// These sets can grow or shrink, based on the initial size and the largest
// element currently in them.

//------------------------------VectorSet--------------------------------------
class VectorSet : public ResourceObj {
private:
  uint size;                    // Size of data IN LONGWORDS (32bits)
  uint32_t* data;               // The data, bit packed
  Arena *_set_arena;

  void grow(uint newsize);      // Grow vector to required bitsize

public:
  VectorSet(Arena *arena);
  ~VectorSet() {}
  void insert(uint elem);

  void clear();
  bool is_empty() const;
  int hash() const;
  void reset() {
    memset(data, 0, size*sizeof(uint32_t));
  }

  // Expose internals for speed-critical fast iterators
  uint word_size() const { return size; }

  // Fast inlined "test and set".  Replaces the idiom:
  //     if (visited.test(idx)) return;
  //     visited.set(idx);
  // With:
  //     if (visited.test_set(idx)) return;
  //
  int test_set(uint elem) {
    uint word = elem >> 5;           // Get the longword offset
    if (word >= size) {
      // Then grow; set; return 0;
      this->insert(elem);
      return 0;
    }
    uint32_t mask = 1L << (elem & 31); // Get bit mask
    uint32_t datum = data[word] & mask;// Get bit
    data[word] |= mask;              // Set bit
    return datum;                    // Return bit
  }

  // Fast inlined test
  int test(uint elem) const {
    uint word = elem >> 5;
    if (word >= size) {
      return 0;
    }
    uint32_t mask = 1L << (elem & 31);
    return data[word] & mask;
  }

  void remove(uint elem) {
    uint word = elem >> 5;
    if (word >= size) {
      return;
    }
    uint32_t mask = 1L << (elem & 31);
    data[word] &= ~mask; // Clear bit
  }

  // Fast inlined set
  void set(uint elem) {
    uint word = elem >> 5;
    if (word >= size) {
      this->insert(elem);
    } else {
      uint32_t mask = 1L << (elem & 31);
      data[word] |= mask;
    }
  }
};

#endif // SHARE_LIBADT_VECTSET_HPP