// Licensed to the Apache Software Foundation (ASF) under one

// or more contributor license agreements.  See the NOTICE file

// distributed with this work for additional information

// regarding copyright ownership.  The ASF licenses this file

// to you under the Apache License, Version 2.0 (the

// "License"); you may not use this file except in compliance

// with the License.  You may obtain a copy of the License at

//

//   http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing,

// software distributed under the License is distributed on an

// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY

// KIND, either express or implied.  See the License for the

// specific language governing permissions and limitations

// under the License.

// Date: Tue Feb 25 23:43:39 CST 2014

// Provide functions to get/set bits of an integral array. These functions

// are not threadsafe because operations on different bits may modify a same

// integer.

#ifndef BUTIL_BIT_ARRAY_H

#define BUTIL_BIT_ARRAY_H

#include <stdint.h>

namespace butil {

#define BIT_ARRAY_LEN(nbit) (((nbit) + 63 ) / 64 * 8)

// Create an array with at least |nbit| bits. The array is not cleared.

inline uint64_t* bit_array_malloc(size_t nbit) {

    if (!nbit) {

        return NULL;

    }

    return (uint64_t*)malloc(BIT_ARRAY_LEN(nbit)/*different from /8*/);

}

inline void bit_array_free(uint64_t* array) {

    free(array);

}

// Set bit 0 ~ nbit-1 of |array| to be 0

inline void bit_array_clear(uint64_t* array, size_t nbit) {

    const size_t off = (nbit >> 6);

    memset(array, 0, off * 8);

    const size_t last = (off << 6);

    if (last != nbit) {

        array[off] &= ~((((uint64_t)1) << (nbit - last)) - 1);

    }

}

// Set i-th bit (from left, counting from 0) of |array| to be 1

inline void bit_array_set(uint64_t* array, size_t i) {

    const size_t off = (i >> 6);

    array[off] |= (((uint64_t)1) << (i - (off << 6)));

}

// Set i-th bit (from left, counting from 0) of |array| to be 0

inline void bit_array_unset(uint64_t* array, size_t i) {

    const size_t off = (i >> 6);

    array[off] &= ~(((uint64_t)1) << (i - (off << 6)));

}

// Get i-th bit (from left, counting from 0) of |array|

inline uint64_t bit_array_get(const uint64_t* array, size_t i) {

    const size_t off = (i >> 6);

    return (array[off] & (((uint64_t)1) << (i - (off << 6))));

}

// Find index of first 1-bit from bit |begin| to |end| in |array|.

// Returns |end| if all bits are 0.

// This function is of O(nbit) complexity.

inline size_t bit_array_first1(const uint64_t* array, size_t begin, size_t end) {

    size_t off1 = (begin >> 6);

    const size_t first = (off1 << 6);

    if (first != begin) {

        const uint64_t v =

            array[off1] & ~((((uint64_t)1) << (begin - first)) - 1);

        if (v) {

            return std::min(first + __builtin_ctzl(v), end);

        }

        ++off1;

    }

    const size_t off2 = (end >> 6);

    for (size_t i = off1; i < off2; ++i) {

        if (array[i]) {

            return i * 64 + __builtin_ctzl(array[i]);

        }

    }

    const size_t last = (off2 << 6);

    if (last != end && array[off2]) {

        return std::min(last + __builtin_ctzl(array[off2]), end);

    }

    return end;

}

}  // end namespace butil

#endif  // BUTIL_BIT_ARRAY_H