1 // license:GPL-2.0+
2 // copyright-holders:Couriersud
3 
4 #ifndef PALLOC_H_
5 #define PALLOC_H_
6 
7 ///
8 /// \file palloc.h
9 ///
10 
11 #include "pconfig.h"
12 #include "pgsl.h"
13 #include "pgsl.h"
14 #include "pmath.h"  // FIXME: only uses lcm ... move to ptypes.
15 #include "ptypes.h"
16 
17 #include <algorithm>
18 #include <cstddef>      // for std::max_align_t (usually long long)
19 #include <memory>
20 #include <type_traits>
21 #include <utility>
22 #include <vector>
23 
24 #if defined(_WIN32) || defined(_WIN64) || defined(_MSC_VER)
25 #include <malloc.h>
26 #endif
27 
28 namespace plib {
29 
30 	//============================================================
31 	// aligned types
32 	//============================================================
33 
34 #if 0
35 #if (PUSE_ALIGNED_HINTS)
36 	template <typename T, std::size_t A>
37 	using aligned_type __attribute__((aligned(A))) = T;
38 #else
39 	template <typename T, std::size_t A>
40 	using aligned_type = T;
41 #endif
42 
43 	template <typename T, std::size_t A>
44 	using aligned_pointer = aligned_type<T, A> *;
45 
46 	template <typename T, std::size_t A>
47 	using const_aligned_pointer = const aligned_type<T, A> *;
48 
49 	template <typename T, std::size_t A>
50 	using aligned_reference = aligned_type<T, A> &;
51 
52 	template <typename T, std::size_t A>
53 	using const_aligned_reference = const aligned_type<T, A> &;
54 #endif
55 	//============================================================
56 	// Standard arena_deleter
57 	//============================================================
58 
59 	template <typename P, typename T, bool X>
60 	struct arena_deleter_base
61 	{
62 	};
63 
64 
65 	template <typename P, typename T>
66 	struct arena_deleter_base<P, T, false>
67 	{
68 		using arena_storage_type = P;
69 
70 		constexpr arena_deleter_base(arena_storage_type *a = nullptr) noexcept
71 		: m_a(a) { }
72 
73 		template<typename U, typename =
74 			   std::enable_if_t<std::is_convertible< U*, T*>::value>>
75 		arena_deleter_base(const arena_deleter_base<P, U, false> &rhs) noexcept
76 		: m_a(rhs.m_a) { }
77 
78 		void operator()(T *p) noexcept
79 		{
80 			// call destructor
81 			p->~T();
82 			m_a->deallocate(p, sizeof(T));
83 		}
84 	//private:
85 		arena_storage_type *m_a;
86 	};
87 
88 	template <typename P, typename T>
89 	struct arena_deleter_base<P, T, true>
90 	{
91 		using arena_storage_type = P;
92 
93 		constexpr arena_deleter_base(arena_storage_type *a = nullptr) noexcept
94 		{
95 			plib::unused_var(a);
96 		}
97 
98 		template<typename U, typename = typename
99 			   std::enable_if<std::is_convertible< U*, T*>::value>::type>
100 		arena_deleter_base(const arena_deleter_base<P, U, true> &rhs) noexcept
101 		{
102 			plib::unused_var(rhs);
103 		}
104 
105 		void operator()(T *p) noexcept
106 		{
107 			// call destructor
108 			p->~T();
109 			P::deallocate(p, sizeof(T));
110 		}
111 	};
112 
113 	template <typename P, typename T>
114 	struct arena_deleter : public arena_deleter_base<P, T, P::has_static_deallocator>
115 	{
116 		using base_type = arena_deleter_base<P, T, P::has_static_deallocator>;
117 		using base_type::base_type;
118 	};
119 
120 	//============================================================
121 	// owned_ptr: smart pointer with ownership information
122 	//============================================================
123 
124 	template <typename SC, typename D>
125 	class owned_ptr
126 	{
127 	public:
128 
129 		using pointer = SC *;
130 		using element_type = SC;
131 		using deleter_type = D;
132 
133 		owned_ptr()
134 		: m_ptr(nullptr), m_deleter(), m_is_owned(true) { }
135 
136 		template <typename, typename>
137 		friend class owned_ptr;
138 
139 		owned_ptr(pointer p, bool owned)
140 		: m_ptr(p), m_deleter(), m_is_owned(owned)
141 		{ }
142 
143 		owned_ptr(pointer p, bool owned, D deleter)
144 		: m_ptr(p), m_deleter(deleter), m_is_owned(owned)
145 		{ }
146 
147 
148 		owned_ptr(const owned_ptr &r) = delete;
149 		owned_ptr & operator =(owned_ptr &r) = delete;
150 
151 		template<typename DC, typename DC_D>
152 		owned_ptr & operator =(owned_ptr<DC, DC_D> &&r)  noexcept
153 		{
154 			if (m_is_owned && (m_ptr != nullptr))
155 				//delete m_ptr;
156 				m_deleter(m_ptr);
157 			m_is_owned = r.m_is_owned;
158 			m_ptr = r.m_ptr;
159 			m_deleter = r.m_deleter;
160 			r.m_is_owned = false;
161 			r.m_ptr = nullptr;
162 			return *this;
163 		}
164 
165 		owned_ptr(owned_ptr &&r) noexcept
166 		: m_ptr(r.m_ptr)
167 		, m_deleter(r.m_deleter)
168 		, m_is_owned(r.m_is_owned)
169 		{
170 			r.m_is_owned = false;
171 			r.m_ptr = nullptr;
172 		}
173 
174 		owned_ptr &operator=(owned_ptr &&r) noexcept
175 		{
176 			if (m_is_owned && (m_ptr != nullptr))
177 				//delete m_ptr;
178 				m_deleter(m_ptr);
179 			m_is_owned = r.m_is_owned;
180 			m_ptr = r.m_ptr;
181 			m_deleter = r.m_deleter;
182 			r.m_is_owned = false;
183 			r.m_ptr = nullptr;
184 			return *this;
185 		}
186 
187 		template<typename DC, typename DC_D>
188 		owned_ptr(owned_ptr<DC, DC_D> &&r) noexcept
189 		: m_ptr(static_cast<pointer >(r.get()))
190 		, m_deleter(r.m_deleter)
191 		, m_is_owned(r.is_owned())
192 		{
193 			r.release();
194 		}
195 
196 		~owned_ptr() noexcept
197 		{
198 			if (m_is_owned && (m_ptr != nullptr))
199 			{
200 				//delete m_ptr;
201 				m_deleter(m_ptr);
202 			}
203 			m_is_owned = false;
204 			m_ptr = nullptr;
205 		}
206 
207 		///
208 		/// \brief Return \c true if the stored pointer is not null.
209 		///
210 		explicit operator bool() const noexcept { return m_ptr != nullptr; }
211 
212 		pointer  release()
213 		{
214 			pointer tmp = m_ptr;
215 			m_is_owned = false;
216 			m_ptr = nullptr;
217 			return tmp;
218 		}
219 
220 		bool is_owned() const { return m_is_owned; }
221 
222 		pointer  operator ->() const noexcept { return m_ptr; }
223 		typename std::add_lvalue_reference<element_type>::type operator *() const noexcept { return *m_ptr; }
224 		pointer  get() const noexcept { return m_ptr; }
225 
226 		deleter_type& get_deleter() noexcept { return m_deleter; }
227 		const deleter_type& get_deleter() const noexcept { return m_deleter; }
228 
229 	private:
230 		pointer m_ptr;
231 		D m_deleter;
232 		bool m_is_owned;
233 	};
234 
235 	//============================================================
236 	// Arena allocator for use with containers
237 	//============================================================
238 
239 	template <class ARENA, class T, std::size_t ALIGN = alignof(T)>
240 	class arena_allocator
241 	{
242 	public:
243 		using value_type = T;
244 		using pointer = T *;
245 		static /*constexpr*/ const std::size_t align_size = ALIGN;
246 		using arena_type = ARENA;
247 
248 		static_assert(align_size >= alignof(T),
249 			"ALIGN must be greater than alignof(T) and a multiple");
250 		static_assert((align_size % alignof(T)) == 0,
251 			"ALIGN must be greater than alignof(T) and a multiple");
252 
253 		arena_allocator() noexcept
254 		: m_a(arena_type::instance())
255 		{ }
256 
257 		~arena_allocator() noexcept = default;
258 
259 		arena_allocator(const arena_allocator &) = default;
260 		arena_allocator &operator=(const arena_allocator &) = default;
261 		arena_allocator(arena_allocator &&) noexcept = default;
262 		arena_allocator &operator=(arena_allocator &&) noexcept = default;
263 
264 		explicit arena_allocator(arena_type & a) noexcept : m_a(a)
265 		{
266 		}
267 
268 		template <class U>
269 		arena_allocator(const arena_allocator<ARENA, U, ALIGN>& rhs) noexcept
270 		: m_a(rhs.m_a)
271 		{
272 		}
273 
274 		template <class U>
275 		struct rebind
276 		{
277 			using other = arena_allocator<ARENA, U, ALIGN>;
278 		};
279 
280 		pointer allocate(std::size_t n)
281 		{
282 			return reinterpret_cast<T *>(m_a.allocate(ALIGN, sizeof(T) * n)); //NOLINT
283 		}
284 
285 		void deallocate(pointer p, std::size_t n) noexcept
286 		{
287 			m_a.deallocate(p, sizeof(T) * n);
288 		}
289 
290 		template<typename U, typename... Args>
291 		void construct(U* p, Args&&... args)
292 		{
293 			// NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
294 			::new (void_ptr_cast(p)) U(std::forward<Args>(args)...);
295 		}
296 
297 		template<typename U>
298 		void destroy(U* p)
299 		{
300 			p->~U();
301 		}
302 
303 		template <class AR1, class T1, std::size_t A1, class AR2, class T2, std::size_t A2>
304 		friend bool operator==(const arena_allocator<AR1, T1, A1>& lhs, // NOLINT
305 			const arena_allocator<AR2, T2, A2>& rhs) noexcept;
306 
307 		template <class AU, class U, std::size_t A>
308 		friend class arena_allocator;
309 
310 	private:
311 		arena_type &m_a;
312 	};
313 
314 	template <class AR1, class T1, std::size_t A1, class AR2, class T2, std::size_t A2>
315 	inline bool operator==(const arena_allocator<AR1, T1, A1>& lhs,
316 		const arena_allocator<AR2, T2, A2>& rhs) noexcept
317 	{
318 		return A1 == A2 && rhs.m_a == lhs.m_a;
319 	}
320 	template <class AR1, class T1, std::size_t A1, class AR2, class T2, std::size_t A2>
321 	inline bool operator!=(const arena_allocator<AR1, T1, A1>& lhs,
322 		const arena_allocator<AR2, T2, A2>& rhs) noexcept
323 	{
324 		return !(lhs == rhs);
325 	}
326 
327 	//============================================================
328 	//  Memory allocation
329 	//============================================================
330 
331 	// MSVC has an issue with SFINAE and overloading resolution.
332 	// A discussion can be found here:
333 	//
334 	// https://stackoverflow.com/questions/31062892/overloading-on-static-in-conjunction-with-sfinae
335 	//
336 	// The previous code compiled with gcc and clang on all platforms and
337 	// compilers apart from MSVC.
338 
339 	template <typename P, bool HSD, bool HSA>
340 	struct arena_base;
341 
342 	template <typename P, bool HSD, bool HSA>
343 	struct arena_core
344 	{
345 		static constexpr const bool has_static_deallocator = HSD;
346 		static constexpr const bool has_static_allocator = HSA;
347 		using size_type = std::size_t;
348 
349 		template <class T, size_type ALIGN = alignof(T)>
350 		using allocator_type = arena_allocator<P, T, ALIGN>;
351 
352 		template <class T>
353 		using deleter_type = arena_deleter<P, T>;
354 
355 		template <typename T>
356 		using unique_ptr = std::unique_ptr<T, deleter_type<T>>;
357 
358 		template <typename T>
359 		using owned_ptr = plib::owned_ptr<T, deleter_type<T>>;
360 
361 		static inline P &instance() noexcept
362 		{
363 			static P s_arena;
364 			return s_arena;
365 		}
366 
367 		friend struct arena_base<P, HSD, HSA>;
368 	private:
369 		size_t m_stat_cur_alloc = 0;
370 		size_t m_stat_max_alloc = 0;
371 
372 	};
373 
374 	template <typename P, bool HSD, bool HSA>
375 	struct arena_base : public arena_core<P, HSD, HSA>
376 	{
377 		using base_type = arena_core<P, HSD, HSA>;
378 		using size_type = typename base_type::size_type;
379 
380 		static size_type cur_alloc() noexcept { return base_type::instance().m_stat_cur_alloc; }
381 		static size_type max_alloc() noexcept { return base_type::instance().m_stat_max_alloc; }
382 
383 		static inline void inc_alloc_stat(size_type size)
384 		{
385 			auto &i = base_type::instance();
386 			i.m_stat_cur_alloc += size;
387 			if (i.m_stat_max_alloc <i.m_stat_cur_alloc)
388 				i.m_stat_max_alloc = i.m_stat_cur_alloc;
389 		}
390 		static inline void dec_alloc_stat(size_type size)
391 		{
392 			base_type::instance().m_stat_cur_alloc -= size;
393 		}
394 	};
395 
396 	template <typename P>
397 	struct arena_base<P, false, false> : public arena_core<P, false, false>
398 	{
399 		using size_type = typename arena_core<P, false, false>::size_type;
400 
401 		size_type cur_alloc() const noexcept { return this->m_stat_cur_alloc; }
402 		size_type max_alloc() const noexcept { return this->m_stat_max_alloc; }
403 
404 		inline void inc_alloc_stat(size_type size)
405 		{
406 			this->m_stat_cur_alloc += size;
407 			if (this->m_stat_max_alloc < this->m_stat_cur_alloc)
408 				this->m_stat_max_alloc = this->m_stat_cur_alloc;
409 		}
410 		inline void dec_alloc_stat(size_type size)
411 		{
412 			this->m_stat_cur_alloc -= size;
413 		}
414 	};
415 
416 	struct aligned_arena : public arena_base<aligned_arena, true, true>
417 	{
418 		static inline gsl::owner<void *> allocate( size_t alignment, size_t size )
419 		{
420 			inc_alloc_stat(size);
421 
422 		#if (PUSE_ALIGNED_ALLOCATION)
423 		#if defined(_WIN32) || defined(_WIN64) || defined(_MSC_VER)
424 			return _aligned_malloc(size, alignment);
425 		#elif defined(__APPLE__) || defined(__ANDROID__)
426 			void* p;
427 			if (::posix_memalign(&p, alignment, size) != 0) {
428 				p = nullptr;
429 			}
430 			return p;
431 		#else
432 			return static_cast<gsl::owner<void *>>(aligned_alloc(alignment, size));
433 		#endif
434 		#else
435 			unused_var(alignment);
436 			return ::operator new(size);
437 		#endif
438 		}
439 
440 		static inline void deallocate(gsl::owner<void *> ptr, size_t size ) noexcept
441 		{
442 			//unused_var(size);
443 			dec_alloc_stat(size);
444 			#if (PUSE_ALIGNED_ALLOCATION)
445 				#if defined(_WIN32) || defined(_WIN64) || defined(_MSC_VER)
446 				// NOLINTNEXTLINE(cppcoreguidelines-no-malloc)
447 				_aligned_free(ptr);
448 				#else
449 				// NOLINTNEXTLINE(cppcoreguidelines-no-malloc)
450 				::free(ptr);
451 				#endif
452 			#else
453 				::operator delete(ptr);
454 			#endif
455 		}
456 
457 		bool operator ==(const aligned_arena &rhs) const noexcept
458 		{
459 			plib::unused_var(rhs);
460 			return true;
461 		}
462 
463 	};
464 
465 	struct std_arena : public arena_base<std_arena, true, true>
466 	{
467 		static inline void *allocate( size_t alignment, size_t size )
468 		{
469 			inc_alloc_stat(size);
470 			unused_var(alignment);
471 			return ::operator new(size);
472 		}
473 
474 		static inline void deallocate( void *ptr, size_t size ) noexcept
475 		{
476 			dec_alloc_stat(size);
477 			::operator delete(ptr);
478 		}
479 
480 		bool operator ==(const aligned_arena &rhs) const noexcept
481 		{
482 			plib::unused_var(rhs);
483 			return true;
484 		}
485 	};
486 
487 	namespace detail
488 	{
489 		template<typename T, typename ARENA, typename... Args>
490 		static inline T * alloc(Args&&... args)
491 		{
492 			auto *mem = ARENA::allocate(alignof(T), sizeof(T));
493 			try
494 			{
495 				// NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
496 				return new (mem) T(std::forward<Args>(args)...);
497 			}
498 			catch (...)
499 			{
500 				ARENA::deallocate(mem, sizeof(T));
501 				throw;
502 			}
503 		}
504 
505 		template<typename ARENA, typename T>
506 		static inline void free(T *ptr) noexcept
507 		{
508 			ptr->~T();
509 			ARENA::deallocate(ptr, sizeof(T));
510 		}
511 
512 		template<typename T, typename ARENA, typename... Args>
513 		static inline T * alloc(ARENA &arena, Args&&... args)
514 		{
515 			auto *mem = arena.allocate(alignof(T), sizeof(T));
516 			try
517 			{
518 				// NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
519 				return new (mem) T(std::forward<Args>(args)...);
520 			}
521 			catch (...)
522 			{
523 				arena.deallocate(mem, sizeof(T));
524 				throw;
525 			}
526 		}
527 
528 		template<typename ARENA, typename T>
529 		static inline void free(ARENA &arena, T *ptr) noexcept
530 		{
531 			ptr->~T();
532 			arena.deallocate(ptr, sizeof(T));
533 		}
534 	} // namespace detail
535 
536 
537 
538 	template<typename T, typename ARENA, typename... Args>
539 	static inline
540 	std::enable_if_t<ARENA::has_static_allocator, typename ARENA::template unique_ptr<T>>
541 	make_unique(Args&&... args)
542 	{
543 		using up_type = typename ARENA::template unique_ptr<T>;
544 		using deleter_type = typename ARENA::template deleter_type<T>;
545 		auto *mem = detail::alloc<T, ARENA>(std::forward<Args>(args)...);
546 		return up_type(mem, deleter_type());
547 	}
548 
549 	template<typename T, typename ARENA, typename... Args>
550 	static inline
551 	std::enable_if_t<!ARENA::has_static_allocator, typename ARENA::template unique_ptr<T>>
552 	make_unique(Args&&... args)
553 	{
554 		return make_unique<T>(ARENA::instance(), std::forward<Args>(args)...);
555 	}
556 
557 	template<typename T, typename ARENA, typename... Args>
558 	static inline
559 	typename ARENA::template unique_ptr<T>
560 	make_unique(ARENA &arena, Args&&... args)
561 	{
562 		using up_type = typename ARENA::template unique_ptr<T>;
563 		using deleter_type = typename ARENA::template deleter_type<T>;
564 		auto *mem = detail::alloc<T>(arena, std::forward<Args>(args)...);
565 		return up_type(mem, deleter_type(&arena));
566 	}
567 
568 	template<typename T, typename ARENA, typename... Args>
569 	static inline
570 	std::enable_if_t<ARENA::has_static_allocator, typename ARENA::template owned_ptr<T>>
571 	make_owned(Args&&... args)
572 	{
573 		using op_type = typename ARENA::template owned_ptr<T>;
574 		using deleter_type = typename ARENA::template deleter_type<T>;
575 		auto *mem = detail::alloc<T, ARENA>(std::forward<Args>(args)...);
576 		return op_type(mem, true, deleter_type());
577 	}
578 
579 	template<typename T, typename ARENA, typename... Args>
580 	static inline
581 	std::enable_if_t<!ARENA::has_static_allocator, typename ARENA::template owned_ptr<T>>
582 	make_owned(Args&&... args)
583 	{
584 		return make_owned<T>(ARENA::instance(), std::forward<Args>(args)...);
585 	}
586 
587 	template<typename T, typename ARENA, typename... Args>
588 	static inline typename ARENA::template owned_ptr<T> make_owned(ARENA &arena, Args&&... args)
589 	{
590 		using op_type = typename ARENA::template owned_ptr<T>;
591 		using deleter_type = typename ARENA::template deleter_type<T>;
592 		auto *mem = detail::alloc<T>(arena, std::forward<Args>(args)...);
593 		return op_type(mem, true, deleter_type(&arena));
594 	}
595 
596 
597 	template <class T, std::size_t ALIGN = alignof(T)>
598 	using aligned_allocator = aligned_arena::allocator_type<T, ALIGN>;
599 
600 	//============================================================
601 	// traits to determine alignment size and stride size
602 	// from types supporting alignment
603 	//============================================================
604 
605 	PDEFINE_HAS_MEMBER(has_align, align_size);
606 
607 	template <typename T, bool X>
608 	struct align_traits_base
609 	{
610 		static_assert(!has_align<T>::value, "no align");
611 		static constexpr const std::size_t align_size = alignof(std::max_align_t);
612 		static constexpr const std::size_t value_size = sizeof(typename T::value_type);
613 		static constexpr const std::size_t stride_size = lcm(align_size, value_size) / value_size;
614 	};
615 
616 	template <typename T>
617 	struct align_traits_base<T, true>
618 	{
619 		static_assert(has_align<T>::value, "no align");
620 		static constexpr const std::size_t align_size = T::align_size;
621 		static constexpr const std::size_t value_size = sizeof(typename T::value_type);
622 		static constexpr const std::size_t stride_size = lcm(align_size, value_size) / value_size;
623 	};
624 
625 	template <typename T>
626 	struct align_traits : public align_traits_base<T, has_align<T>::value>
627 	{};
628 
629 	template <typename BASEARENA = aligned_arena, std::size_t PG_SIZE = 1024>
630 	class paged_arena : public arena_base<paged_arena<BASEARENA, PG_SIZE>, true, true>
631 	{
632 	public:
633 		paged_arena() = default;
634 
635 		PCOPYASSIGNMOVE(paged_arena, delete)
636 
637 		~paged_arena() = default;
638 
639 		static void *allocate(size_t align, size_t size)
640 		{
641 			plib::unused_var(align);
642 			//size = ((size + PG_SIZE - 1) / PG_SIZE) * PG_SIZE;
643 			return arena().allocate(PG_SIZE, size);
644 		}
645 
646 		static void deallocate(void *ptr, size_t size) noexcept
647 		{
648 			//size = ((size + PG_SIZE - 1) / PG_SIZE) * PG_SIZE;
649 			arena().deallocate(ptr, size);
650 		}
651 
652 		bool operator ==(const paged_arena &rhs) const noexcept { return this == &rhs; }
653 
654 		static BASEARENA &arena() noexcept { static BASEARENA m_arena; return m_arena; }
655 	private:
656 	};
657 
658 	//============================================================
659 	// Aligned vector
660 	//============================================================
661 
662 	// FIXME: needs a separate file
663 	template <typename T, std::size_t ALIGN = PALIGN_VECTOROPT, typename A = paged_arena<>>//aligned_arena>
664 	class aligned_vector : public std::vector<T, typename A::template allocator_type<T, ALIGN>>
665 	{
666 	public:
667 		using base = std::vector<T, typename A::template allocator_type<T, ALIGN>>;
668 
669 		using base::base;
670 
671 	};
672 
673 } // namespace plib
674 
675 #endif // PALLOC_H_
676