1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5#include "BsRenderBeastPrerequisites.h"
6#include "Allocators/BsPoolAlloc.h"
7
8namespace bs { namespace ct
9{
10 /** @addtogroup RenderBeast
11 * @{
12 */
13
14 /** Information about an allocation in a single row of a texture. */
15 struct TextureRowAllocation
16 {
17 /** Starting pixels of the allocation. */
18 uint16_t x = 0, y = 0;
19
20 /** Number of pixels in the allocation. */
21 uint32_t length = 0;
22 };
23
24 /** Allocates elements of variable size within rows of a texture. */
25 template<uint32_t WIDTH, uint32_t HEIGHT>
26 class TextureRowAllocator : public INonCopyable
27 {
28 public:
29 TextureRowAllocator();
30 ~TextureRowAllocator();
31
32 /**
33 * Attempts to allocate a new region of size @p length pixels. Returned allocation will have the same size as the
34 * requested size if sucessful.
35 */
36 TextureRowAllocation alloc(uint32_t length);
37
38 /** Frees a previously allocated region. */
39 void free(const TextureRowAllocation& alloc);
40
41 private:
42 /** Describes a single contigous region of a texture row. */
43 struct RowRegion
44 {
45 // Note: 'next' must be the first member because of shenanigans we do in alloc() and free()
46 RowRegion* next = nullptr;
47 uint32_t x = 0;
48 uint32_t length = WIDTH;
49 };
50
51 RowRegion* mFreeRegions[HEIGHT];
52 PoolAlloc<sizeof(RowRegion), HEIGHT * 2> mAlloc;
53 };
54
55 template <uint32_t WIDTH, uint32_t HEIGHT>
56 TextureRowAllocator<WIDTH, HEIGHT>::TextureRowAllocator()
57 {
58 for(uint32_t i = 0; i < HEIGHT; i++)
59 mFreeRegions[i] = mAlloc.template construct<RowRegion>();
60 }
61
62 template <uint32_t WIDTH, uint32_t HEIGHT>
63 TextureRowAllocator<WIDTH, HEIGHT>::~TextureRowAllocator()
64 {
65 for(uint32_t i = 0; i < HEIGHT; i++)
66 {
67 RowRegion* region = mFreeRegions[i];
68 while(region)
69 {
70 RowRegion* curRegion = region;
71 region = region->next;
72
73 mAlloc.free(curRegion);
74 }
75 }
76 }
77
78 template<uint32_t WIDTH, uint32_t HEIGHT>
79 TextureRowAllocation TextureRowAllocator<WIDTH, HEIGHT>::alloc(uint32_t length)
80 {
81 TextureRowAllocation output;
82
83 for(uint32_t i = 0; i < HEIGHT; i++)
84 {
85 RowRegion* region = mFreeRegions[i];
86 RowRegion* prevRegion = (RowRegion*)&mFreeRegions[i]; // This ensures an assignment to prevRegion->next changes the entry of mFreeRegions
87 while(region)
88 {
89 if(region->length == length)
90 {
91 output.x = region->x;
92 output.y = i;
93 output.length = length;
94
95 prevRegion->next = region->next;
96 mAlloc.free(region);
97
98 return output;
99 }
100
101 if(region->length > length)
102 {
103 output.x = region->x;
104 output.y = i;
105 output.length = length;
106
107 region->x += length;
108 region->length -= length;
109
110 return output;
111 }
112
113 prevRegion = region;
114 region = region->next;
115 }
116 }
117
118 return output;
119 }
120
121 template <uint32_t WIDTH, uint32_t HEIGHT>
122 void TextureRowAllocator<WIDTH, HEIGHT>::free(const TextureRowAllocation& alloc)
123 {
124 if(alloc.length == 0)
125 return;
126
127 RowRegion* region = mFreeRegions[alloc.y];
128 RowRegion* prevRegion = (RowRegion*)&mFreeRegions[alloc.y]; // This ensures an assignment to prevRegion->next changes the entry of mFreeRegions
129
130 if(region)
131 {
132 // Find the location where to insert the free region
133 while (region && alloc.x > (region->x + region->length))
134 {
135 prevRegion = region;
136 region = region->next;
137 }
138
139 if(region)
140 {
141 // End of the allocation is the beginning of this region
142 if((alloc.x + alloc.length) == region->x)
143 {
144 region->x -= alloc.length;
145 region->length += alloc.length;
146
147 return;
148 }
149
150 // Beginning of the allocation is at the end of this region
151 const uint32_t regionEnd = region->x + region->length;
152 if (alloc.x == regionEnd)
153 {
154 region->length += alloc.length;
155
156 // Merge any directly following regions
157 prevRegion = region;
158 region = region->next;
159
160 while(region && region->x == (prevRegion->x + prevRegion->length))
161 {
162 prevRegion->length += region->length;
163 prevRegion->next = region->next;
164
165 RowRegion* toDelete = region;
166 region = region->next;
167
168 mAlloc.free(toDelete);
169 }
170
171 return;
172 }
173 }
174 }
175
176 auto newRegion = (RowRegion*)mAlloc.alloc();
177 newRegion->x = alloc.x;
178 newRegion->length = alloc.length;
179 newRegion->next = region;
180
181 prevRegion->next = newRegion;
182 }
183
184 /* @} */
185}}
186