1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_growable_array.h
29 // growable_array is backed by an embedded fixed array which can hold up to N elements, beyond this it automatically switches to a vogl::vector.
30 // This class is only a subset of vogl::vector, but its semantics closely match it.
31 // Objects in the embedded fixed array are not constructed until they are inserted/push_back'd, etc. They are guaranteed 8 byte alignment.
32 // If vogl::vector supports mixins I could add this functionality into it directly without having to duplicate code (and I could cut down on the #
33 // of member vars), but it would become much more complex.
34 // This is like llvm::SmallVector, see http://fahrenheit2539.blogspot.com/2012/06/introduction-in-depths-look-at.html
36 #ifndef VOGL_GROWABLE_ARRAY_H
37 #define VOGL_GROWABLE_ARRAY_H
39 #include "vogl_core.h"
43 template <typename T, uint N>
47 typedef T element_type;
53 inline growable_array()
59 inline growable_array(uint initial_size)
66 inline growable_array(const growable_array &other)
73 inline growable_array &operator=(const growable_array &rhs)
80 const uint rhs_size = rhs.size();
83 m_dynamic_elements = rhs.m_dynamic_elements;
86 helpers::copy_array(&fixed_element(0), rhs.get_ptr(), rhs_size);
87 m_fixed_size = rhs_size;
93 inline ~growable_array()
95 VOGL_ASSERT((m_fixed_size && m_dynamic_elements.is_empty()) || (!m_fixed_size));
96 VOGL_ASSERT((m_fixed_size && (m_dynamic_elements.get_ptr() == NULL)) || (!m_fixed_size));
98 if (VOGL_HAS_DESTRUCTOR(T))
100 scalar_type<T>::destruct_array(&fixed_element(0), m_fixed_size);
104 inline bool is_dynamic() const
106 return m_dynamic_elements.get_ptr() != NULL;
111 VOGL_ASSERT((m_fixed_size && m_dynamic_elements.is_empty() && (m_dynamic_elements.get_ptr() == NULL)) || (!m_fixed_size));
115 if (VOGL_HAS_DESTRUCTOR(T))
117 scalar_type<T>::destruct_array(&fixed_element(0), m_fixed_size);
123 m_dynamic_elements.clear();
127 inline uint size() const
129 return m_fixed_size ? m_fixed_size : m_dynamic_elements.size();
132 inline uint size_in_bytes() const
134 return size() * sizeof(T);
137 inline bool is_empty() const
142 inline uint capacity() const
144 return is_dynamic() ? m_dynamic_elements.capacity() : N;
147 inline const T *get_ptr() const
149 return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.get_ptr() : &fixed_element(0));
153 return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.get_ptr() : &fixed_element(0));
156 inline const T *begin() const
165 inline const T *end() const
167 return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.end() : &fixed_element(m_fixed_size));
171 return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.end() : &fixed_element(m_fixed_size));
174 inline const T &front() const
185 inline const T &back() const
196 inline const T &operator[](uint i) const
198 VOGL_ASSERT(i < size());
202 inline T &operator[](uint i)
204 VOGL_ASSERT(i < size());
208 inline void set_all(const T &val)
210 if (VOGL_IS_BITWISE_COPYABLE(T) && (sizeof(T) == sizeof(uint8)))
211 memset(get_ptr(), *reinterpret_cast<const uint8 *>(&val), size());
215 T *pEnd = p + size();
221 inline void resize(uint n, bool grow_hint = false)
225 m_dynamic_elements.resize(n, grow_hint);
229 if (n < m_fixed_size)
230 scalar_type<T>::destruct_array(&fixed_element(n), m_fixed_size - n);
231 else if (n > m_fixed_size)
232 scalar_type<T>::construct_array(&fixed_element(m_fixed_size), n - m_fixed_size);
237 switch_to_dynamic(n);
238 m_dynamic_elements.resize(n);
242 inline void reserve(uint n)
244 if ((n <= N) || (n <= size()))
247 switch_to_dynamic(n);
250 inline void push_back(const T &obj)
253 m_dynamic_elements.push_back(obj);
254 else if ((m_fixed_size + 1) > N)
256 switch_to_dynamic(m_fixed_size + 1);
257 m_dynamic_elements.push_back(obj);
261 scalar_type<T>::construct(&fixed_element(m_fixed_size), obj);
266 inline T *enlarge(uint n)
268 if ((m_fixed_size + n) > N)
269 switch_to_dynamic(m_fixed_size + n);
272 return m_dynamic_elements.enlarge(n);
274 T *pResult = &fixed_element(m_fixed_size);
275 scalar_type<T>::construct_array(pResult, n);
280 inline void pop_back()
283 m_dynamic_elements.pop_back();
286 VOGL_ASSERT(m_fixed_size);
290 scalar_type<T>::destruct(&fixed_element(m_fixed_size));
295 inline void insert(uint index, const T *p, uint n)
297 VOGL_ASSERT(((p + n) <= &fixed_element(0)) || (p >= &fixed_element(m_fixed_size)));
299 if ((m_fixed_size + n) > N)
300 switch_to_dynamic(m_fixed_size + n);
304 m_dynamic_elements.insert(index, p, n);
308 VOGL_ASSERT(index <= m_fixed_size);
312 const uint orig_size = m_fixed_size;
313 resize(m_fixed_size + n);
315 VOGL_ASSERT(!is_dynamic());
317 const uint num_to_move = orig_size - index;
319 if (VOGL_IS_BITWISE_COPYABLE(T))
321 // This overwrites the destination object bits, but bitwise copyable means we don't need to worry about destruction.
322 memmove(&fixed_element(0) + index + n, &fixed_element(0) + index, sizeof(T) * num_to_move);
326 const T *pSrc = &fixed_element(0) + orig_size - 1;
327 T *pDst = const_cast<T *>(pSrc) + n;
329 for (uint i = 0; i < num_to_move; i++)
331 VOGL_ASSERT((pDst - &fixed_element(0)) < (int)m_fixed_size);
336 T *pDst = &fixed_element(0) + index;
338 if (VOGL_IS_BITWISE_COPYABLE(T))
340 // This copies in the new bits, overwriting the existing objects, which is OK for copyable types that don't need destruction.
341 memcpy(pDst, p, sizeof(T) * n);
345 for (uint i = 0; i < n; i++)
347 VOGL_ASSERT((pDst - &fixed_element(0)) < (int)m_fixed_size);
353 inline void insert(uint index, const T &obj)
355 insert(index, &obj, 1);
358 // push_front() isn't going to be very fast - it's only here for usability.
359 inline void push_front(const T &obj)
364 inline growable_array &append(const growable_array &other)
366 VOGL_ASSERT(this != &other);
368 insert(size(), other.get_ptr(), other.size());
372 inline growable_array &append(const T *p, uint n)
375 insert(size(), p, n);
379 inline void erase(uint start, uint n)
383 m_dynamic_elements.erase(start, n);
387 VOGL_ASSERT((start + n) <= m_fixed_size);
388 if ((start + n) > m_fixed_size)
394 const uint num_to_move = m_fixed_size - (start + n);
396 T *pDst = &fixed_element(0) + start;
398 const T *pSrc = &fixed_element(0) + start + n;
400 if (VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T))
402 // This test is overly cautious.
403 if ((!VOGL_IS_BITWISE_COPYABLE(T)) || VOGL_HAS_DESTRUCTOR(T))
405 // Type has been marked explictly as bitwise movable, which means we can move them around but they may need to be destructed.
406 // First destroy the erased objects.
407 scalar_type<T>::destruct_array(pDst, n);
410 // Copy "down" the objects to preserve, filling in the empty slots.
411 memmove(pDst, pSrc, num_to_move * sizeof(T));
415 // Type is not bitwise copyable or movable.
416 // Move them down one at a time by using the equals operator, and destroying anything that's left over at the end.
417 T *pDst_end = pDst + num_to_move;
418 while (pDst != pDst_end)
421 scalar_type<T>::destruct_array(pDst_end, n);
427 inline void erase(uint index)
432 inline void erase_unordered(uint index)
434 VOGL_ASSERT(index < size());
436 if ((index + 1) < size())
437 (*this)[index] = back();
444 introsort(begin(), end());
447 template <typename Comp>
448 inline void sort(Comp compare_obj)
450 introsort(begin(), end(), compare_obj);
453 inline bool is_sorted() const
455 for (uint i = 1; i < size(); ++i)
456 if ((*this)[i] < (*this)[i - 1])
467 resize(static_cast<uint>(std::unique(begin(), end()) - begin()));
471 inline void reverse()
473 uint cur_size = size();
474 uint j = cur_size >> 1;
476 for (uint i = 0; i < j; i++)
477 utils::swap(p[i], p[cur_size - 1 - i]);
480 inline int find(const T &key) const
486 cur_size = m_dynamic_elements.size();
487 p = m_dynamic_elements.get_ptr();
491 cur_size = m_fixed_size;
492 p = &fixed_element(0);
495 VOGL_ASSERT(cur_size <= cINT32_MAX);
497 const T *p_end = p + cur_size;
510 return cInvalidIndex;
513 inline int find_last(const T &key) const
519 cur_size = m_dynamic_elements.size();
520 p = m_dynamic_elements.get_ptr();
524 cur_size = m_fixed_size;
525 p = &fixed_element(0);
528 VOGL_ASSERT(cur_size <= cINT32_MAX);
530 for (int i = cur_size - 1; i >= 0; --i)
534 return cInvalidIndex;
537 inline int find_sorted(const T &key) const
543 cur_size = m_dynamic_elements.size();
544 p = m_dynamic_elements.get_ptr();
548 cur_size = m_fixed_size;
549 p = &fixed_element(0);
552 VOGL_ASSERT(cur_size <= cINT32_MAX);
555 int end = cur_size - 1;
559 int mid = begin + ((end - begin) >> 1);
563 else if (key < p[mid])
569 return cInvalidIndex;
572 void swap(growable_array &rhs)
574 growable_array &lhs = *this;
579 if (lhs.is_dynamic() && !rhs.is_dynamic())
580 helpers::move_array(&lhs.fixed_element(0), &rhs.fixed_element(0), rhs.m_fixed_size);
581 else if (!lhs.is_dynamic() && rhs.is_dynamic())
582 helpers::move_array(&rhs.fixed_element(0), &lhs.fixed_element(0), lhs.m_fixed_size);
583 else if (!lhs.is_dynamic() && !rhs.is_dynamic())
585 uint common_size = math::minimum(lhs.m_fixed_size, rhs.m_fixed_size);
586 for (uint i = 0; i < common_size; i++)
587 std::swap(lhs.fixed_element(i), rhs.fixed_element(i));
589 if (lhs.m_fixed_size > rhs.m_fixed_size)
590 helpers::move_array(&rhs.fixed_element(rhs.m_fixed_size), &lhs.fixed_element(rhs.m_fixed_size), lhs.m_fixed_size - rhs.m_fixed_size);
591 else if (rhs.m_fixed_size > lhs.m_fixed_size)
592 helpers::move_array(&fixed_element(lhs.m_fixed_size), &rhs.fixed_element(lhs.m_fixed_size), rhs.m_fixed_size - lhs.m_fixed_size);
595 lhs.m_dynamic_elements.swap(rhs.m_dynamic_elements);
596 std::swap(lhs.m_fixed_size, rhs.m_fixed_size);
599 void switch_to_dynamic(uint new_capacity)
603 m_dynamic_elements.reserve(new_capacity);
607 VOGL_ASSERT((new_capacity >= m_fixed_size) && (!m_dynamic_elements.size()));
609 T *pBlock = static_cast<T *>(vogl_malloc(new_capacity * sizeof(T)));
611 if (VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T))
613 memcpy(pBlock, &fixed_element(0), size_in_bytes());
617 T *pSrc = &fixed_element(0);
618 T *pSrc_end = &fixed_element(m_fixed_size);
621 while (pSrc != pSrc_end)
623 scalar_type<T>::construct(pDst++, *pSrc);
624 scalar_type<T>::destruct(pSrc++);
628 m_dynamic_elements.grant_ownership(pBlock, m_fixed_size, new_capacity);
632 void switch_to_embedded()
634 if (!is_dynamic() || (m_dynamic_elements.size() > N))
637 uint cur_size = m_dynamic_elements.size();
638 T *pSrc = static_cast<T *>(m_dynamic_elements.assume_ownership());
642 T *pDst = &fixed_element(0);
644 if (VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T))
645 memcpy(pDst, pSrc, cur_size * sizeof(T));
648 T *pSrc_end = pSrc + cur_size;
650 while (pSrc != pSrc_end)
652 scalar_type<T>::construct(pDst++, *pSrc);
653 scalar_type<T>::destruct(pSrc++);
658 m_fixed_size = cur_size;
662 inline bool operator==(const growable_array &rhs) const
668 for (uint i = 0; i < n; i++)
669 if (!((*this)[i] == rhs[i]))
675 inline bool operator!=(const growable_array &rhs) const
677 return !(*this == rhs);
680 template <typename OtherT>
681 inline bool operator==(const OtherT &rhs) const
687 for (uint i = 0; i < n; i++)
688 if (!((*this)[i] == rhs[i]))
694 template <typename OtherT>
695 inline bool operator!=(const OtherT &rhs) const
697 return !(*this == rhs);
701 vogl::vector<T> m_dynamic_elements;
703 uint64_t m_fixed_elements[(N * sizeof(T) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
705 inline const T &fixed_element(uint i) const
707 return reinterpret_cast<const T *>(m_fixed_elements)[i];
709 inline T &fixed_element(uint i)
711 return reinterpret_cast<T *>(m_fixed_elements)[i];
717 #endif // VOGL_GROWABLE_ARRAY_H