ConstantSizeList.h

Go to the documentation of this file.

/*******************************************************************************
 *
 * Copyright (c) 2008-2010 Michael Schulze <mschulze@ivs.cs.uni-magdeburg.de>
 * All rights reserved.
 *
 *    Redistribution and use in source and binary forms, with or without
 *    modification, are permitted provided that the following conditions
 *    are met:
 *
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the
 *      distribution.
 *
 *    * Neither the name of the copyright holders nor the names of
 *      contributors may be used to endorse or promote products derived
 *      from this software without specific prior written permission.
 *
 *
 *    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 *    IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 *    TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 *    PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 *    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 *    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 *    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *    $Id$
 *
 ******************************************************************************/
#ifndef __ConstantSizeList_h__
#define __ConstantSizeList_h__

#include <stdint.h>
#include "object/Array.h"
#include "object/Uninitialized.h"

namespace object {

    template < typename T,
               unsigned int N,
               bool callDestructor = true >
    class ConstantSizeList {

            Array< Uninitialized<T>, N > content;

            enum {
                used_space = (N / 8) + ((N % 8) ? 1 : 0)
            };

            uint8_t used[used_space];

        public:
            typedef T value_type;

            typedef T* pointer;

            typedef T& reference;

            struct ConstantSizeListIterator;
            typedef ConstantSizeListIterator iterator;

            ConstantSizeList () {
                for (uint8_t i = 0;i < used_space;++i) {
                    used[i] = 0;
                }
            }

            ~ConstantSizeList () {
                if (callDestructor) {
                    iterator i = begin();
                    while (i != end()) {
                        delElement (&*i);
                        ++i;
                    }
                }
            }

        public:
            iterator begin () {
                return iterator(*this, getFirstElement());
            }

            iterator end () {
                return iterator(*this, N);
            }

            class ConstantSizeListIterator {
                    ConstantSizeList&  _storage;
                    uint8_t _currentPos;

                public:
                    typedef typename ConstantSizeList::value_type value_type;

                    typedef typename ConstantSizeList::pointer pointer;

                    typedef typename ConstantSizeList::reference reference;

                    ConstantSizeListIterator (ConstantSizeList& s, const uint8_t pos) :
                            _storage(s), _currentPos(pos) {
                    }

                    ConstantSizeListIterator operator = (const ConstantSizeListIterator& i) {
                        _storage = i._storage;
                        _currentPos = i._currentPos;
                        return ConstantSizeListIterator(_storage, _currentPos);
                    }

                    ConstantSizeListIterator operator ++ () {
                        _currentPos = _storage.getNextElement(_currentPos + 1);
                        return ConstantSizeListIterator(_storage, _currentPos);
                    }

                    ConstantSizeListIterator operator ++ (int) {
                        _currentPos = _storage.getNextElement(_currentPos + 1);
                        return ConstantSizeListIterator(_storage, _currentPos);
                    }

                    bool operator == (const ConstantSizeListIterator& i) const {
                        return _currentPos == i._currentPos;
                    }

                    bool operator != (const ConstantSizeListIterator& i) const {
                        return _currentPos != i._currentPos;
                    }

                    value_type& operator * () const {
                        return reinterpret_cast<value_type&>(_storage.content[_currentPos]);
                    }

            };

            void delElement (const T* value) {
                for (uint8_t i = 0; i < N;++i)
                    if ( value == reinterpret_cast<T*>(&content[i]) ) {
                        reinterpret_cast<T*>(&content[i])->~T();
                        used[i/8] = used[i/8] & (~(0x80 >> (i % 8)));
                        return;
                    }
            }

            T* newElement () {
                for (uint8_t i = 0;i < used_space;++i)
                    if ( used[i] != 0xff ) {
                        uint8_t mask = 0x80;
                        for (uint8_t j = 0;j < 8 ; ++j)
                            if (!(used[i] & mask)) {
                                used[i] |= mask;
                                return new(&content[(i*8+j)]) T();
                            } else
                                mask >>= 1;
                    }
                return 0;
            }

        private:

            uint8_t getFirstElement () {
                return getNextElement(0);
            }

            uint8_t getNextElement (uint8_t t) {
                uint8_t start = t % 8;
                for (uint8_t i = t / 8;i < used_space;++i) {
                    if ( used[i] ) {
                        uint8_t mask = 0x80 >> start;
                        for (uint8_t j = start;j < 8 ; ++j) {
                            if ((used[i] & mask)) {
                                return (i*8 + j);
                            } else {
                                mask >>= 1;
                            }
                        }
                        start = 0;
                    }
                }
                return N;
            }
    };

} /* namespace object */

#endif