1 (* Copyright (C) DooM 2D:Forever Developers
2 *
3 * This program is free software: you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation, either version 3 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 *)
16 {$INCLUDE a_modes.inc}
17 {.$DEFINE IDPOOL_CHECKS}
20 interface
22 uses
23 mempool;
26 // ////////////////////////////////////////////////////////////////////////// //
27 type
28 //TODO: implement getting n sequential ids
30 public
33 private
34 type
39 private
45 private
54 public
60 // returns InvalidId if there are no more free ids (or throws)
63 // returns InvalidId if there are no more free ids (or throws)
66 // it is NOT ok to release already released id
72 public
84 implementation
86 uses
87 SysUtils;
90 // ////////////////////////////////////////////////////////////////////////// //
92 begin
100 begin
107 var
109 begin
112 begin
115 if (f > 0) and (mRanges[f-1].last >= mRanges[f].first) then raise Exception.Create('invalid range order');
116 if (f > 0) and (mRanges[f-1].last+1 = mRanges[f].first) then raise Exception.Create('unmerged ranges');
123 var
125 begin
127 begin
128 if (mRanges[f].first > mRanges[f].last) then begin dump(); raise Exception.Create('invalid range'); end;
131 if (f > 0) and (mRanges[f-1].last >= mRanges[f].first) then begin dump(); raise Exception.Create('invalid range order'); end;
132 if (f > 0) and (mRanges[f-1].last+1 = mRanges[f].first) then begin dump(); raise Exception.Create('unmerged ranges'); end;
138 begin
147 function TIdPool.getFreeIds (): Integer; inline; begin result := Integer(mMaxId+1-mUsedIds); end;
152 var
155 begin
158 // -1: not found
162 // yay! use binary search to find the range
166 begin
168 //!assert((mid >= 0) and (mid < len));
179 var
181 begin
191 var
193 begin
197 if (ii >= 0) then result := not ((aid >= mRanges[ii].first) and (aid <= mRanges[ii].last)) else result := true;
201 // returns InvalidId if there are no more free ids (or throws)
203 var
205 begin
207 begin
208 // no more ids
211 exit;
214 // delete first range?
216 begin
219 end
220 else
221 begin
229 // returns InvalidId if there are no more free ids (or throws)
231 var
233 begin
235 begin
236 // no more ids
239 exit;
241 // invalid?
243 begin
246 exit;
248 // find range with this id
251 begin
254 exit;
256 // always return requested id
258 // can we shrink range head?
260 begin
261 // yep; range with the only id?
263 begin
264 // delete this range
267 end
268 else
269 begin
274 exit;
276 // can we shrink range tail?
278 begin
279 // yep; simply shrink, 'cause range with one id was processed in the previous `if`
283 exit;
285 // split this range to two
296 // it is NOT ok to release already released id
298 var
300 begin
301 if (aid > mMaxId) then raise Exception.Create(Format('TIdPool: cannot release invalid id %u', [aid]));
302 // no available ids?
304 begin
305 // just create new range
312 exit;
314 // before first available id?
316 begin
317 // can we grow first range?
319 begin
320 // yep
322 end
323 else
324 begin
325 // nope, insert new first range
335 exit;
337 // after last available id?
339 begin
340 // can we grow last range?
342 begin
343 // yep
345 end
346 else
347 begin
348 // nope, insert new last range
357 exit;
359 // alas, no more easy cases; find the nearest range
361 if (ii < 0) then raise Exception.Create(Format('TIdPool: cannot release invalid id %u', [aid]));
362 if (aid >= mRanges[ii].first) and (aid <= mRanges[ii].last) then raise Exception.Create(Format('TIdPool: cannot release unallocated id %u', [aid]));
363 // ii should contain range where `first` is less than `aid`
366 {$IF DEFINED(IDPOOL_DEBUG_DUMPS)}writeln('aid=', aid, '; ii=', ii, ': [', mRanges[ii].first, '-', mRanges[ii].last, ']');{$ENDIF}
367 // can grow this range at the end?
369 begin
371 // yep; can merge ranges?
373 begin
374 // merge
379 end
380 else
381 begin
382 // change
384 {$IF DEFINED(IDPOOL_DEBUG_DUMPS)}if (ii+1 < mRangeUsed) then writeln(' ii+1=', ii+1, ': [', mRanges[ii+1].first, '-', mRanges[ii+1].last, ']');{$ENDIF}
389 exit;
391 // can grow next range at the start?
393 begin
394 // yep; can merge ranges?
396 begin
397 // merge
401 end
402 else
403 begin
404 // change
409 exit;
411 // cannot grow anything, insert empty range after ii