1 //----------------------------------------------------------------------
2 // This software is part of the Haiku distribution and is covered
3 // by the MIT License.
4 //---------------------------------------------------------------------
5
6 #include <stdio.h>
7 #include <string.h>
8
9 #include <new>
10
11 #include <disk_device_manager.h>
12 #include <PartitioningInfo.h>
13
14 #include <syscalls.h>
15 #include <ddm_userland_interface_defs.h>
16
17
18 using namespace std;
19
20
21 //#define TRACING 1
22 #if TRACING
23 # define TRACE(x) printf x
24 #else
25 # define TRACE(x)
26 #endif
27
28
29 // constructor
BPartitioningInfo()30 BPartitioningInfo::BPartitioningInfo()
31 :
32 fPartitionID(-1),
33 fSpaces(NULL),
34 fCount(0),
35 fCapacity(0)
36 {
37 }
38
39
40 // destructor
~BPartitioningInfo()41 BPartitioningInfo::~BPartitioningInfo()
42 {
43 Unset();
44 }
45
46
47 // SetTo
48 status_t
SetTo(off_t offset,off_t size)49 BPartitioningInfo::SetTo(off_t offset, off_t size)
50 {
51 TRACE(("%p - BPartitioningInfo::SetTo(offset = %lld, size = %lld)\n", this, offset, size));
52
53 fPartitionID = -1;
54 delete[] fSpaces;
55
56 if (size > 0) {
57 fSpaces = new(nothrow) partitionable_space_data[1];
58 if (!fSpaces)
59 return B_NO_MEMORY;
60
61 fCount = 1;
62 fSpaces[0].offset = offset;
63 fSpaces[0].size = size;
64 } else {
65 fSpaces = NULL;
66 fCount = 0;
67 }
68
69 fCapacity = fCount;
70
71 return B_OK;
72 }
73
74
75 // Unset
76 void
Unset()77 BPartitioningInfo::Unset()
78 {
79 delete[] fSpaces;
80 fPartitionID = -1;
81 fSpaces = NULL;
82 fCount = 0;
83 fCapacity = 0;
84 }
85
86
87 // ExcludeOccupiedSpace
88 status_t
ExcludeOccupiedSpace(off_t offset,off_t size)89 BPartitioningInfo::ExcludeOccupiedSpace(off_t offset, off_t size)
90 {
91 if (size <= 0)
92 return B_OK;
93
94 TRACE(("%p - BPartitioningInfo::ExcludeOccupiedSpace(offset = %lld, "
95 "size = %lld)\n", this, offset, size));
96
97 int32 leftIndex = -1;
98 int32 rightIndex = -1;
99 for (int32 i = 0; i < fCount; i++) {
100 if (leftIndex == -1
101 && offset < fSpaces[i].offset + fSpaces[i].size) {
102 leftIndex = i;
103 }
104
105 if (fSpaces[i].offset < offset + size)
106 rightIndex = i;
107 }
108
109 TRACE((" leftIndex = %ld, rightIndex = %ld\n", leftIndex, rightIndex));
110
111 // If there's no intersection with any free space, we're done.
112 if (leftIndex == -1 || rightIndex == -1 || leftIndex > rightIndex)
113 return B_OK;
114
115 partitionable_space_data& leftSpace = fSpaces[leftIndex];
116 partitionable_space_data& rightSpace = fSpaces[rightIndex];
117
118 off_t rightSpaceEnd = rightSpace.offset + rightSpace.size;
119
120 // special case: split a single space in two
121 if (leftIndex == rightIndex && leftSpace.offset < offset
122 && rightSpaceEnd > offset + size) {
123
124 TRACE((" splitting space at %ld\n", leftIndex));
125
126 // add a space after this one
127 status_t error = _InsertSpaces(leftIndex + 1, 1);
128 if (error != B_OK)
129 return error;
130
131 // IMPORTANT: after calling _InsertSpace(), one can not
132 // use the partitionable_space_data references "leftSpace"
133 // and "rightSpace" anymore (declared above)!
134
135 partitionable_space_data& space = fSpaces[leftIndex];
136 partitionable_space_data& newSpace = fSpaces[leftIndex + 1];
137
138 space.size = offset - space.offset;
139
140 newSpace.offset = offset + size;
141 newSpace.size = rightSpaceEnd - newSpace.offset;
142
143 #ifdef TRACING
144 PrintToStream();
145 #endif
146 return B_OK;
147 }
148
149 // check whether the first affected space is eaten completely
150 int32 deleteFirst = leftIndex;
151 if (leftSpace.offset < offset) {
152 leftSpace.size = offset - leftSpace.offset;
153
154 TRACE((" left space remains, new size is %lld\n", leftSpace.size));
155
156 deleteFirst++;
157 }
158
159 // check whether the last affected space is eaten completely
160 int32 deleteLast = rightIndex;
161 if (rightSpaceEnd > offset + size) {
162 rightSpace.offset = offset + size;
163 rightSpace.size = rightSpaceEnd - rightSpace.offset;
164
165 TRACE((" right space remains, new offset = %lld, size = %lld\n",
166 rightSpace.offset, rightSpace.size));
167
168 deleteLast--;
169 }
170
171 // remove all spaces that are completely eaten
172 if (deleteFirst <= deleteLast)
173 _RemoveSpaces(deleteFirst, deleteLast - deleteFirst + 1);
174
175 #ifdef TRACING
176 PrintToStream();
177 #endif
178 return B_OK;
179 }
180
181
182 // PartitionID
183 partition_id
PartitionID() const184 BPartitioningInfo::PartitionID() const
185 {
186 return fPartitionID;
187 }
188
189
190 // GetPartitionableSpaceAt
191 status_t
GetPartitionableSpaceAt(int32 index,off_t * offset,off_t * size) const192 BPartitioningInfo::GetPartitionableSpaceAt(int32 index, off_t* offset,
193 off_t *size) const
194 {
195 if (!fSpaces)
196 return B_NO_INIT;
197 if (!offset || !size)
198 return B_BAD_VALUE;
199 if (index < 0 || index >= fCount)
200 return B_BAD_INDEX;
201 *offset = fSpaces[index].offset;
202 *size = fSpaces[index].size;
203 return B_OK;
204 }
205
206
207 // CountPartitionableSpaces
208 int32
CountPartitionableSpaces() const209 BPartitioningInfo::CountPartitionableSpaces() const
210 {
211 return fCount;
212 }
213
214
215 // PrintToStream
216 void
PrintToStream() const217 BPartitioningInfo::PrintToStream() const
218 {
219 if (!fSpaces) {
220 printf("BPartitioningInfo is not initialized\n");
221 return;
222 }
223 printf("BPartitioningInfo has %" B_PRId32 " spaces:\n", fCount);
224 for (int32 i = 0; i < fCount; i++) {
225 printf(" space at %" B_PRId32 ": offset = %" B_PRId64 ", size = %"
226 B_PRId64 "\n", i, fSpaces[i].offset, fSpaces[i].size);
227 }
228 }
229
230
231 // #pragma mark -
232
233
234 // _InsertSpaces
235 status_t
_InsertSpaces(int32 index,int32 count)236 BPartitioningInfo::_InsertSpaces(int32 index, int32 count)
237 {
238 if (index <= 0 || index > fCount || count <= 0)
239 return B_BAD_VALUE;
240
241 // If the capacity is sufficient, we just need to copy the spaces to create
242 // a gap.
243 if (fCount + count <= fCapacity) {
244 memmove(fSpaces + index + count, fSpaces + index,
245 (fCount - index) * sizeof(partitionable_space_data));
246 fCount += count;
247 return B_OK;
248 }
249
250 // alloc new array
251 int32 capacity = (fCount + count) * 2;
252 // add a bit room for further resizing
253
254 partitionable_space_data* spaces
255 = new(nothrow) partitionable_space_data[capacity];
256 if (!spaces)
257 return B_NO_MEMORY;
258
259 // copy items
260 memcpy(spaces, fSpaces, index * sizeof(partitionable_space_data));
261 memcpy(spaces + index + count, fSpaces + index,
262 (fCount - index) * sizeof(partitionable_space_data));
263
264 delete[] fSpaces;
265 fSpaces = spaces;
266 fCapacity = capacity;
267 fCount += count;
268
269 return B_OK;
270 }
271
272
273 // _RemoveSpaces
274 void
_RemoveSpaces(int32 index,int32 count)275 BPartitioningInfo::_RemoveSpaces(int32 index, int32 count)
276 {
277 if (index < 0 || count <= 0 || index + count > fCount)
278 return;
279
280 if (count < fCount) {
281 int32 endIndex = index + count;
282 memmove(fSpaces + index, fSpaces + endIndex,
283 (fCount - endIndex) * sizeof(partitionable_space_data));
284 }
285
286 fCount -= count;
287 }
288