array.h

/* -*- mode: C; c-basic-offset: 4; intent-tabs-mode: nil -*-
 *
 * Sifteo SDK
 *
 * Copyright <c> 2012 Sifteo, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#pragma once
#ifdef NOT_USERSPACE
#   error This is a userspace-only header, not allowed by the current build.
#endif

#include <sifteo/memory.h>
#include <sifteo/macros.h>

namespace Sifteo {

template <typename T, unsigned tCapacity, typename sizeT = uint32_t>
class Array {
public:

    typedef T* iterator;
    typedef const T* const_iterator;
    static const unsigned NOT_FOUND = unsigned(-1);

    Array() {
        clear();
    }

    static unsigned capacity() {
        return tCapacity;
    }

    unsigned count() const {
        return numItems;
    }

    void setCount(unsigned c) {
        ASSERT(c <= tCapacity);
        numItems = c;
    }

    bool empty() const {
        return count() == 0;
    }

    const T& operator[](unsigned index) const {
        ASSERT(index < count());
        return items[index];
    }

    const T& operator[](int index) const {
        ASSERT(0 <= index && index < (int)count());
        return items[index];
    }

    T& operator[](unsigned index) {
        ASSERT(index < count());
        return items[index];
    }

    T& operator[](int index) {
        ASSERT(0 <= index && index < (int)count());
        return items[index];
    }

    T& append(const T &newItem) {
        return push_back(newItem);
    }

    T& append() {
        return push_back();
    }

    T& push_back(const T &newItem) {
        ASSERT(count() < tCapacity);
        T &item = items[numItems++];
        item = newItem;
        return item;
    }

    T& push_back() {
        ASSERT(count() < tCapacity);
        return items[numItems++];
    }

    T pop_back() {
        ASSERT(count() > 0);
        numItems--;
        return items[numItems];
    }

    void pop_back(T* outValue) {
        ASSERT(outValue != 0);
        ASSERT(count() > 0);
        numItems--;
        *outValue = items[numItems];
    }
    
    void clear() {
        numItems = 0;
    }

    void erase(unsigned index) {
        // allow a.erase(a.find()) without checking for not-found.
        if (index == NOT_FOUND)
            return;

        erase(items + index);
    }

    void erase(iterator item) {
        ASSERT(item >= begin() && item < end());
        iterator next = item + 1;
        memcpy((uint8_t*)item, (uint8_t*)next, (uint8_t*)end() - (uint8_t*)next);
        numItems--;
    }

    void erase_tail() {
        ASSERT(count() > 0);
        numItems--;
    }
    
    iterator begin() {
        return &items[0];
    }

    iterator end() {
        return &items[count()];
    }

    unsigned find(T itemToFind)
    {
        int index = 0;
        for (iterator I=begin(), E=end(); I != E; ++I, ++index) {
            if (*I == itemToFind)
                return index;
        }
        return NOT_FOUND;
    }

private:
    T items[tCapacity];
    sizeT numItems;
};


template <unsigned tSize>
class BitArray
{
    static unsigned clz(uint32_t word) {
        return __builtin_clz(word);
    }

    static uint32_t lz(unsigned bit) {
        return 0x80000000 >> bit;
    }

    // Return a range of bits from 'bit' to 31.
    static uint32_t range(int bit) {
        if (bit <= 0) return 0xffffffff;
        if (bit >= 32) return 0;
        return 0xffffffff >> bit;
    }

public:
    uint32_t words[(tSize + 31) / 32];
  
    static unsigned size() {
        return tSize;
    }

    void mark(unsigned index)
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        ASSERT(index < tSize);
        if (NUM_WORDS > 1) {
            unsigned word = index >> 5;
            unsigned bit = index & 31;
            words[word] |= lz(bit);
        } else {
            words[0] |= lz(index);
        }
    }

    void clear(unsigned index)
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        ASSERT(index < tSize);
        if (NUM_WORDS > 1) {
            unsigned word = index >> 5;
            unsigned bit = index & 31;
            words[word] &= ~lz(bit);
        } else {
            words[0] &= ~lz(index);
        }
    }

    void mark()
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;
        const unsigned NUM_FULL_WORDS = tSize / 32;
        const unsigned REMAINDER_BITS = tSize & 31;

        STATIC_ASSERT(NUM_FULL_WORDS + 1 == NUM_WORDS ||
                      NUM_FULL_WORDS == NUM_WORDS);

        // Set fully-utilized words only
        _SYS_memset32(words, -1, NUM_FULL_WORDS);

        if (NUM_FULL_WORDS != NUM_WORDS) {
            // Set only bits < tSize in the last word.
            uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
            words[NUM_FULL_WORDS] = mask;
        }
    }

    void clear()
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;
        _SYS_memset32(words, 0, NUM_WORDS);
    }

    bool test(unsigned index) const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        ASSERT(index < tSize);
        if (NUM_WORDS > 1) {
            unsigned word = index >> 5;
            unsigned bit = index & 31;
            return (words[word] & lz(bit)) != 0;
        } else {
            return (words[0] & lz(index)) != 0;
        }
    }

    bool empty() const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        if (NUM_WORDS > 1) {
            #pragma clang diagnostic push
            #pragma clang diagnostic ignored "-Wtautological-compare"
            for (unsigned w = 0; w < NUM_WORDS; w++)
                if (words[w])
                    return false;
            return true;
            #pragma clang diagnostic pop
        } else if (NUM_WORDS == 1) {
            return words[0] == 0;
        } else {
            return true;
        }
    }

    unsigned count() const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        if (NUM_WORDS > 1) {
            #pragma clang diagnostic push
            #pragma clang diagnostic ignored "-Wtautological-compare"
            unsigned c = 0;
            for (unsigned w = 0; w < NUM_WORDS; w++)
                c += __builtin_popcount(words[w]);
            return c;
            #pragma clang diagnostic pop
        } else if (NUM_WORDS == 1) {
            return __builtin_popcount(words[0]);
        } else {
            return 0;
        }
    }

    bool findFirst(unsigned &index) const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        if (NUM_WORDS > 1) {
            #pragma clang diagnostic push
            #pragma clang diagnostic ignored "-Wtautological-compare"
            for (unsigned w = 0; w < NUM_WORDS; w++) {
                uint32_t v = words[w];
                if (v) {
                    index = (w << 5) | clz(v);
                    ASSERT(index < tSize);
                    return true;
                }
            }
            #pragma clang diagnostic pop
        } else if (NUM_WORDS == 1) {
            uint32_t v = words[0];
            if (v) {
                index = clz(v);
                ASSERT(index < tSize);
                return true;
            }
        }
        return false;
    }

    bool clearFirst(unsigned &index)
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        if (NUM_WORDS > 1) {
            #pragma clang diagnostic push
            #pragma clang diagnostic ignored "-Wtautological-compare"
            for (unsigned w = 0; w < NUM_WORDS; w++) {
                uint32_t v = words[w];
                if (v) {
                    unsigned bit = clz(v);
                    words[w] ^= lz(bit);
                    index = (w << 5) | bit;
                    ASSERT(index < tSize);
                    return true;
                }
            }
            #pragma clang diagnostic pop
        } else if (NUM_WORDS == 1) {
            uint32_t v = words[0];
            if (v) {
                unsigned bit = clz(v);
                words[0] ^= lz(bit);
                index = bit;
                ASSERT(index < tSize);
                return true;
            }
        }
        return false;
    }

    bool clearN(unsigned &index, unsigned n)
    {
        for (unsigned i : *this) {
            if (n--)
                continue;

            clear(i);
            index = i;
            return true;
        }
        return false;
    }

    struct iterator {
        unsigned index;
        BitArray<tSize> remaining;

        bool operator == (const iterator& other) const {
            return index == other.index;
        }

        bool operator != (const iterator& other) const {
            return index != other.index;
        }

        unsigned operator* () const {
            return index;
        }

        const iterator& operator++ () {
            if (!remaining.clearFirst(index))
                index = unsigned(-1);
            return *this;
        }
    };

    iterator begin() const {
        iterator i;
        i.remaining = *this;
        return ++i;
    }

    iterator end() const {
        iterator i;
        i.index = unsigned(-1);
        return i;
    }

    BitArray() {
        clear();
    }

    explicit BitArray(unsigned index) {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        ASSERT(index < tSize);
        if (NUM_WORDS > 1) {
            #pragma clang diagnostic push
            #pragma clang diagnostic ignored "-Wtautological-compare"
            for (unsigned w = 0; w < NUM_WORDS; w++) {
                words[w] = (w == (index >> 5)) ? lz(index & 31) : 0;
            }
            #pragma clang diagnostic pop
        } else {
            words[0] = lz(index);
        }
    }

    explicit BitArray(unsigned begin, unsigned end) {
        const unsigned NUM_WORDS = (tSize + 31) / 32;

        ASSERT(begin < tSize);
        ASSERT(end <= tSize);
        ASSERT(begin <= end);

        if (NUM_WORDS > 1) {
            #pragma clang diagnostic push
            #pragma clang diagnostic ignored "-Wtautological-compare"
            for (unsigned w = 0; w < NUM_WORDS; w++) {
                int offset = w << 5;
                words[w] = range(begin - offset) & ~range(end - offset);
            }
            #pragma clang diagnostic pop
        } else {
            words[0] = range(begin) & ~range(end);
        }
    }

    BitArray<tSize> operator & (const BitArray<tSize> &other) const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;
        BitArray<tSize> result;
        #pragma clang diagnostic push
        #pragma clang diagnostic ignored "-Wtautological-compare"
        for (unsigned w = 0; w < NUM_WORDS; w++)
            result.words[w] = words[w] & other.words[w];
        #pragma clang diagnostic pop
        return result;
    }

    BitArray<tSize> operator | (const BitArray<tSize> &other) const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;
        BitArray<tSize> result;
        #pragma clang diagnostic push
        #pragma clang diagnostic ignored "-Wtautological-compare"
        for (unsigned w = 0; w < NUM_WORDS; w++)
            result.words[w] = words[w] | other.words[w];
        #pragma clang diagnostic pop
        return result;
    }

    BitArray<tSize> operator ^ (const BitArray<tSize> &other) const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;
        BitArray<tSize> result;
        #pragma clang diagnostic push
        #pragma clang diagnostic ignored "-Wtautological-compare"
        for (unsigned w = 0; w < NUM_WORDS; w++)
            result.words[w] = words[w] ^ other.words[w];
        #pragma clang diagnostic pop
        return result;
    }

    BitArray<tSize> operator ~ () const
    {
        const unsigned NUM_WORDS = (tSize + 31) / 32;
        const unsigned NUM_FULL_WORDS = tSize / 32;
        const unsigned REMAINDER_BITS = tSize & 31;
        BitArray<tSize> result;

        STATIC_ASSERT(NUM_FULL_WORDS + 1 == NUM_WORDS ||
                      NUM_FULL_WORDS == NUM_WORDS);

        // Trivial inversion for fully-utilized words
        #pragma clang diagnostic push
        #pragma clang diagnostic ignored "-Wtautological-compare"
        for (unsigned w = 0; w < NUM_FULL_WORDS; w++)
            result.words[w] = ~words[w];
        #pragma clang diagnostic pop

        if (NUM_FULL_WORDS != NUM_WORDS) {
            // Set only bits < tSize in the last word.
            uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
            result.words[NUM_FULL_WORDS] = mask & ~words[NUM_FULL_WORDS];
        }

        return result;
    }
};


};  // namespace Sifteo