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	schoenebeck	2630	/*
2	schoenebeck	3847	* Copyright (c) 2014 - 2021 Christian Schoenebeck
3	schoenebeck	2630	*
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	schoenebeck	3557	ConstCapacityArray(ssize_t capacity) :
45	schoenebeck	2630	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	schoenebeck	3557	inline size_t size() const {
67	schoenebeck	2630	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	schoenebeck	3557	inline size_t capacity() const {
80	schoenebeck	2630	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	schoenebeck	3557	inline void remove(size_t index, size_t count = 1) {
119	schoenebeck	3847	if (index >= m_size)
120	schoenebeck	2630	return;
121	schoenebeck	3847	// 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	schoenebeck	2630	// don't use memmove() here! Since it is not RT safe with all libc
128			// implementations and on all architectures
129	schoenebeck	3847	const size_t n = m_size - index - count;
130			for (size_t i = 0; i < n; ++i)
131	schoenebeck	2630	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	schoenebeck	3557	for (size_t i = 0; i < m_size; ++i)
143	schoenebeck	2630	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	schoenebeck	3557	size_t find(const T& value) const {
156			for (size_t i = 0; i < m_size; ++i)
157	schoenebeck	2630	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	schoenebeck	3557	inline T& operator[](size_t index) {
183	schoenebeck	2630	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	schoenebeck	3557	inline const T& operator[](size_t index) const {
196	schoenebeck	2630	return m_data[index];
197			}
198
199			private:
200			T* __restrict const m_data;
201	schoenebeck	3557	ssize_t m_capacity;
202			ssize_t m_size;
203	schoenebeck	2630	};
204
205			} // namespace LinuxSampler
206
207			#endif // LS_CONSTCAPACITYARRAY_H