src/common/ConstCapacityArray.h

/*
 * Copyright (c) 2014 - 2019 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 || 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 (size_t 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 (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 - 2019 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 \|\| 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 (size_t 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 (size_t 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	size_t find(const T& value) const {
149	for (size_t 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[](size_t 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[](size_t index) const {
189	return m_data[index];
190	}
191
192	private:
193	T* __restrict const m_data;
194	ssize_t m_capacity;
195	ssize_t m_size;
196	};
197
198	} // namespace LinuxSampler
199
200	#endif // LS_CONSTCAPACITYARRAY_H