src/common/ConstCapacityArray.h

/*
 * Copyright (c) 2014 Christian Schoenebeck
 *
 * http://www.linuxsampler.org
 *
 * This file is part of LinuxSampler and released under the same terms.
 * See README file for details.
 */

#ifndef LS_CONSTCAPACITYARRAY_H
#define LS_CONSTCAPACITYARRAY_H

#include <stdlib.h>
#include <stdint.h>

namespace LinuxSampler {

    /**
     * Very simple container with array implementation which ensures a constant
     * access time of Theta(1) on individual elements. Internally it uses a
     * consecutive, dense C array (on heap) where its capacity is defined by the
     * constructor of this class. That internal array will never be reallocated
     * during the lifetime of a ConstCapacityArray object and thus C pointers to
     * elements of this array remain always valid.
     *
     * This class has methods to add and remove elements from the array and
     * "resizing" the array. All those operations are guaranteed to be real-time
     * safe. When elements are removed from the array, members past the removed
     * element(s) will be moved towards the array start, to always ensure that
     * the array is kept dense (without any gaps).
     */
    template<typename T>
    class ConstCapacityArray {
    public:
        /**
         * Create a ConstCapacityArray with the given capacity. The initial
         * size of the array will be zero. ConstCapacityArray's size can never
         * grow larger than its capacity defined with the constructor here.
         *
         * This constructor <b>must not</b> be called in a real-time context!
         *
         * @param capacity - maximum size this object may ever grow
         */
        ConstCapacityArray(int capacity) :
            m_data(new T[capacity]), m_capacity(capacity), m_size(0) {}

        /**
         * Destructor. Frees the internal array allocated by this object.
         *
         * This destructor <b>must not</b> be called in a real-time context!
         */
        ~ConstCapacityArray() {
            if (m_data) delete [] m_data;
        }

        /**
         * Amount of elements this array currently holds. The array's size may
         * vary between 0 ... capacity() during its lifetime.
         *
         * Access time is always constant with Theta(1).
         *
         * This method is guaranteed to be real-time safe.
         *
         * @see capacity()
         */
        inline uint size() const {
            return m_size;
        }

        /**
         * Maximum size this array may ever grow to in its lifetime.
         *
         * Access time is always constant with Theta(1).
         *
         * This method is guaranteed to be real-time safe.
         *
         * @see size()
         */
        inline uint capacity() const {
            return m_capacity;
        }

        /**
         * Returns true if this array is empty.
         *
         * Access time is always constant with Theta(1).
         *
         * This method is guaranteed to be real-time safe.
         */
        inline bool empty() const {
            return !m_size;
        }

        /**
         * Add a new element to the end of the array. Size is incremented by
         * one. You cannot add more elements than capacity() reflects.
         *
         * This method is guaranteed to be real-time safe.
         *
         * @param element - value to be added as new element
         */
        inline void append(const T& element) {
            if (m_size == m_capacity) return; // max. size already exhausted
            m_data[m_size++] = element;
        }

        /**
         * Remove @a count elements from the array at position @a index.
         * Elements past the removed element(s) will be moved towards the
         * beginning of the array. So the array always remains dense (without
         * gaps).
         *
         * This method is guaranteed to be real-time safe.
         *
         * @param index - position where element(s) shall be removed
         * @param count - amount of elements to be removed
         */
        inline void remove(uint index, uint count = 1) {
            if (index >= m_size || index + count > m_size)
                return;
            // don't use memmove() here! Since it is not RT safe with all libc
            // implementations and on all architectures
            for (uint i = 0; i < count; ++i)
                m_data[index + i] = m_data[index + i + count];
            m_size -= count;
        }

        /**
         * Returns true in case there is an element with given @a value in this
         * array
         *
         * @param value - value to be searched for
         */
        bool contains(const T& value) const {
            for (uint i = 0; i < m_size; ++i)
                if (m_data[i] == value) return true;
            return false;
        }

        /**
         * Searches the array for an element with given index, if found it
         * returns the element's index, if no such element was found an invalid
         * index will be returned instead.
         *
         * @param value - value to be searched for
         * @returns index of found element
         */
        uint find(const T& value) const {
            for (uint i = 0; i < m_size; ++i)
                if (m_data[i] == value) return i;
            return -1;
        }

        /**
         * Remove all elements from the array. Size of array will be zero after
         * this call.
         *
         * Access time is always constant with Theta(1).
         *
         * This method is guaranteed to be real-time safe.
         */
        inline void clear() {
            m_size = 0;
        }

        /**
         * Access element at position @a index (for read/write access).
         *
         * Access time is always constant with Theta(1).
         *
         * This method is guaranteed to be real-time safe.
         *
         * @param index - position of array to access
         */
        inline T& operator[](uint index) {
            return m_data[index];
        }

        /**
         * Access element at position @a index (for read only access).
         *
         * Access time is always constant with Theta(1).
         *
         * This method is guaranteed to be real-time safe.
         *
         * @param index - position of array to access
         */
        inline const T& operator[](uint index) const {
            return m_data[index];
        }

    private:
        T* __restrict const m_data;
        int m_capacity;
        int m_size;
    };

} // namespace LinuxSampler

#endif // LS_CONSTCAPACITYARRAY_H
1	schoenebeck	2630	/*
2			* Copyright (c) 2014 Christian Schoenebeck
3			*
4			* http://www.linuxsampler.org
5			*
6			* This file is part of LinuxSampler and released under the same terms.
7			* See README file for details.
8			*/
9
10			#ifndef LS_CONSTCAPACITYARRAY_H
11			#define LS_CONSTCAPACITYARRAY_H
12
13			#include <stdlib.h>
14			#include <stdint.h>
15
16			namespace LinuxSampler {
17
18			/**
19			* Very simple container with array implementation which ensures a constant
20			* access time of Theta(1) on individual elements. Internally it uses a
21			* consecutive, dense C array (on heap) where its capacity is defined by the
22			* constructor of this class. That internal array will never be reallocated
23			* during the lifetime of a ConstCapacityArray object and thus C pointers to
24			* elements of this array remain always valid.
25			*
26			* This class has methods to add and remove elements from the array and
27			* "resizing" the array. All those operations are guaranteed to be real-time
28			* safe. When elements are removed from the array, members past the removed
29			* element(s) will be moved towards the array start, to always ensure that
30			* the array is kept dense (without any gaps).
31			*/
32			template<typename T>
33			class ConstCapacityArray {
34			public:
35			/**
36			* Create a ConstCapacityArray with the given capacity. The initial
37			* size of the array will be zero. ConstCapacityArray's size can never
38			* grow larger than its capacity defined with the constructor here.
39			*
40			* This constructor <b>must not</b> be called in a real-time context!
41			*
42			* @param capacity - maximum size this object may ever grow
43			*/
44			ConstCapacityArray(int capacity) :
45			m_data(new T[capacity]), m_capacity(capacity), m_size(0) {}
46
47			/**
48			* Destructor. Frees the internal array allocated by this object.
49			*
50			* This destructor <b>must not</b> be called in a real-time context!
51			*/
52			~ConstCapacityArray() {
53			if (m_data) delete [] m_data;
54			}
55
56			/**
57			* Amount of elements this array currently holds. The array's size may
58			* vary between 0 ... capacity() during its lifetime.
59			*
60			* Access time is always constant with Theta(1).
61			*
62			* This method is guaranteed to be real-time safe.
63			*
64			* @see capacity()
65			*/
66			inline uint size() const {
67			return m_size;
68			}
69
70			/**
71			* Maximum size this array may ever grow to in its lifetime.
72			*
73			* Access time is always constant with Theta(1).
74			*
75			* This method is guaranteed to be real-time safe.
76			*
77			* @see size()
78			*/
79			inline uint capacity() const {
80			return m_capacity;
81			}
82
83			/**
84			* Returns true if this array is empty.
85			*
86			* Access time is always constant with Theta(1).
87			*
88			* This method is guaranteed to be real-time safe.
89			*/
90			inline bool empty() const {
91			return !m_size;
92			}
93
94			/**
95			* Add a new element to the end of the array. Size is incremented by
96			* one. You cannot add more elements than capacity() reflects.
97			*
98			* This method is guaranteed to be real-time safe.
99			*
100			* @param element - value to be added as new element
101			*/
102			inline void append(const T& element) {
103			if (m_size == m_capacity) return; // max. size already exhausted
104			m_data[m_size++] = element;
105			}
106
107			/**
108			* Remove @a count elements from the array at position @a index.
109			* Elements past the removed element(s) will be moved towards the
110			* beginning of the array. So the array always remains dense (without
111			* gaps).
112			*
113			* This method is guaranteed to be real-time safe.
114			*
115			* @param index - position where element(s) shall be removed
116			* @param count - amount of elements to be removed
117			*/
118			inline void remove(uint index, uint count = 1) {
119			if (index >= m_size \|\| index + count > m_size)
120			return;
121			// don't use memmove() here! Since it is not RT safe with all libc
122			// implementations and on all architectures
123			for (uint i = 0; i < count; ++i)
124			m_data[index + i] = m_data[index + i + count];
125			m_size -= count;
126			}
127
128			/**
129			* Returns true in case there is an element with given @a value in this
130			* array
131			*
132			* @param value - value to be searched for
133			*/
134			bool contains(const T& value) const {
135			for (uint i = 0; i < m_size; ++i)
136			if (m_data[i] == value) return true;
137			return false;
138			}
139
140			/**
141			* Searches the array for an element with given index, if found it
142			* returns the element's index, if no such element was found an invalid
143			* index will be returned instead.
144			*
145			* @param value - value to be searched for
146			* @returns index of found element
147			*/
148			uint find(const T& value) const {
149			for (uint i = 0; i < m_size; ++i)
150			if (m_data[i] == value) return i;
151			return -1;
152			}
153
154			/**
155			* Remove all elements from the array. Size of array will be zero after
156			* this call.
157			*
158			* Access time is always constant with Theta(1).
159			*
160			* This method is guaranteed to be real-time safe.
161			*/
162			inline void clear() {
163			m_size = 0;
164			}
165
166			/**
167			* Access element at position @a index (for read/write access).
168			*
169			* Access time is always constant with Theta(1).
170			*
171			* This method is guaranteed to be real-time safe.
172			*
173			* @param index - position of array to access
174			*/
175			inline T& operator[](uint index) {
176			return m_data[index];
177			}
178
179			/**
180			* Access element at position @a index (for read only access).
181			*
182			* Access time is always constant with Theta(1).
183			*
184			* This method is guaranteed to be real-time safe.
185			*
186			* @param index - position of array to access
187			*/
188			inline const T& operator[](uint index) const {
189			return m_data[index];
190			}
191
192			private:
193			T* __restrict const m_data;
194			int m_capacity;
195			int m_size;
196			};
197
198			} // namespace LinuxSampler
199
200			#endif // LS_CONSTCAPACITYARRAY_H