1 /*************************************************************************/
2 /*  pool_allocator.h                                                     */
3 /*************************************************************************/
4 /*                       This file is part of:                           */
5 /*                           GODOT ENGINE                                */
6 /*                      https://godotengine.org                          */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur.                 */
9 /* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md)    */
10 /*                                                                       */
11 /* Permission is hereby granted, free of charge, to any person obtaining */
12 /* a copy of this software and associated documentation files (the       */
13 /* "Software"), to deal in the Software without restriction, including   */
14 /* without limitation the rights to use, copy, modify, merge, publish,   */
15 /* distribute, sublicense, and/or sell copies of the Software, and to    */
16 /* permit persons to whom the Software is furnished to do so, subject to */
17 /* the following conditions:                                             */
18 /*                                                                       */
19 /* The above copyright notice and this permission notice shall be        */
20 /* included in all copies or substantial portions of the Software.       */
21 /*                                                                       */
22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
29 /*************************************************************************/
30 #ifndef POOL_ALLOCATOR_H
31 #define POOL_ALLOCATOR_H
32 
33 #include "typedefs.h"
34 
35 /**
36 	@author Juan Linietsky <reduzio@gmail.com>
37  * Generic Pool Allocator.
38  * This is a generic memory pool allocator, with locking, compacting and alignment. (@TODO alignment)
39  * It used as a standard way to manage alloction in a specific region of memory, such as texture memory,
40  * audio sample memory, or just any kind of memory overall.
41  * (@TODO) abstraction should be greater, because in many platforms, you need to manage a nonreachable memory.
42 */
43 
44 enum {
45 
46 	POOL_ALLOCATOR_INVALID_ID = -1 ///< default invalid value. use INVALID_ID( id ) to test
47 };
48 
49 class PoolAllocator {
50 public:
51 	typedef int ID;
52 
53 private:
54 	enum {
55 		CHECK_BITS = 8,
56 		CHECK_LEN = (1 << CHECK_BITS),
57 		CHECK_MASK = CHECK_LEN - 1
58 
59 	};
60 
61 	struct Entry {
62 
63 		unsigned int pos;
64 		unsigned int len;
65 		unsigned int lock;
66 		unsigned int check;
67 
clearEntry68 		inline void clear() {
69 			pos = 0;
70 			len = 0;
71 			lock = 0;
72 			check = 0;
73 		}
EntryEntry74 		Entry() { clear(); }
75 	};
76 
77 	typedef int EntryArrayPos;
78 	typedef int EntryIndicesPos;
79 
80 	Entry *entry_array;
81 	int *entry_indices;
82 	int entry_max;
83 	int entry_count;
84 
85 	uint8_t *pool;
86 	void *mem_ptr;
87 	int pool_size;
88 
89 	int free_mem;
90 	int free_mem_peak;
91 
92 	unsigned int check_count;
93 	int align;
94 
95 	bool needs_locking;
96 
entry_end(const Entry & p_entry)97 	inline int entry_end(const Entry &p_entry) const {
98 		return p_entry.pos + aligned(p_entry.len);
99 	}
aligned(int p_size)100 	inline int aligned(int p_size) const {
101 
102 		int rem = p_size % align;
103 		if (rem)
104 			p_size += align - rem;
105 
106 		return p_size;
107 	}
108 
109 	void compact(int p_up_to = -1);
110 	void compact_up(int p_from = 0);
111 	bool get_free_entry(EntryArrayPos *p_pos);
112 	bool find_hole(EntryArrayPos *p_pos, int p_for_size);
113 	bool find_entry_index(EntryIndicesPos *p_map_pos, Entry *p_entry);
114 	Entry *get_entry(ID p_mem);
115 	const Entry *get_entry(ID p_mem) const;
116 
117 	void create_pool(void *p_mem, int p_size, int p_max_entries);
118 
119 protected:
120 	virtual void mt_lock() const; ///< Reimplement for custom mt locking
121 	virtual void mt_unlock() const; ///< Reimplement for custom mt locking
122 
123 public:
124 	enum {
125 		DEFAULT_MAX_ALLOCS = 4096,
126 	};
127 
128 	ID alloc(int p_size); ///< Alloc memory, get an ID on success, POOL_ALOCATOR_INVALID_ID on failure
129 	void free(ID p_mem); ///< Free allocated memory
130 	Error resize(ID p_mem, int p_new_size); ///< resize a memory chunk
131 	int get_size(ID p_mem) const;
132 
133 	int get_free_mem(); ///< get free memory
134 	int get_used_mem() const;
135 	int get_free_peak(); ///< get free memory
136 
137 	Error lock(ID p_mem); //@todo move this out
138 	void *get(ID p_mem);
139 	const void *get(ID p_mem) const;
140 	void unlock(ID p_mem);
141 	bool is_locked(ID p_mem) const;
142 
143 	PoolAllocator(int p_size, bool p_needs_locking = false, int p_max_entries = DEFAULT_MAX_ALLOCS);
144 	PoolAllocator(void *p_mem, int p_size, int p_align = 1, bool p_needs_locking = false, int p_max_entries = DEFAULT_MAX_ALLOCS);
145 	PoolAllocator(int p_align, int p_size, bool p_needs_locking = false, int p_max_entries = DEFAULT_MAX_ALLOCS);
146 
147 	virtual ~PoolAllocator();
148 };
149 
150 #endif
151