src/common/ConstCapacityArray.h

/*
 * Copyright (c) 2014 - 2021 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(ssize_t 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 size_t 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 size_t 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(size_t index, size_t count = 1) {
            if (index >= m_size)
                return;
            // special case: no elements behind the removed elements, so nothing
            // to move
            if (index + count >= m_size) {
                m_size = index;
                return;
            }
            // don't use memmove() here! Since it is not RT safe with all libc
            // implementations and on all architectures
            const size_t n = m_size - index - count;
            for (size_t i = 0; i < n; ++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 (size_t 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
         */
        size_t find(const T& value) const {
            for (size_t 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[](size_t 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[](size_t index) const {
            return m_data[index];
        }

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

} // namespace LinuxSampler

#endif // LS_CONSTCAPACITYARRAY_H
1	/*
2	* Copyright (c) 2014 - 2021 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(ssize_t 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 size_t 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 size_t 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(size_t index, size_t count = 1) {
119	if (index >= m_size)
120	return;
121	// special case: no elements behind the removed elements, so nothing
122	// to move
123	if (index + count >= m_size) {
124	m_size = index;
125	return;
126	}
127	// don't use memmove() here! Since it is not RT safe with all libc
128	// implementations and on all architectures
129	const size_t n = m_size - index - count;
130	for (size_t i = 0; i < n; ++i)
131	m_data[index + i] = m_data[index + i + count];
132	m_size -= count;
133	}
134
135	/**
136	* Returns true in case there is an element with given @a value in this
137	* array
138	*
139	* @param value - value to be searched for
140	*/
141	bool contains(const T& value) const {
142	for (size_t i = 0; i < m_size; ++i)
143	if (m_data[i] == value) return true;
144	return false;
145	}
146
147	/**
148	* Searches the array for an element with given index, if found it
149	* returns the element's index, if no such element was found an invalid
150	* index will be returned instead.
151	*
152	* @param value - value to be searched for
153	* @returns index of found element
154	*/
155	size_t find(const T& value) const {
156	for (size_t i = 0; i < m_size; ++i)
157	if (m_data[i] == value) return i;
158	return -1;
159	}
160
161	/**
162	* Remove all elements from the array. Size of array will be zero after
163	* this call.
164	*
165	* Access time is always constant with Theta(1).
166	*
167	* This method is guaranteed to be real-time safe.
168	*/
169	inline void clear() {
170	m_size = 0;
171	}
172
173	/**
174	* Access element at position @a index (for read/write access).
175	*
176	* Access time is always constant with Theta(1).
177	*
178	* This method is guaranteed to be real-time safe.
179	*
180	* @param index - position of array to access
181	*/
182	inline T& operator[](size_t index) {
183	return m_data[index];
184	}
185
186	/**
187	* Access element at position @a index (for read only access).
188	*
189	* Access time is always constant with Theta(1).
190	*
191	* This method is guaranteed to be real-time safe.
192	*
193	* @param index - position of array to access
194	*/
195	inline const T& operator[](size_t index) const {
196	return m_data[index];
197	}
198
199	private:
200	T* __restrict const m_data;
201	ssize_t m_capacity;
202	ssize_t m_size;
203	};
204
205	} // namespace LinuxSampler
206
207	#endif // LS_CONSTCAPACITYARRAY_H