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 {$IFDEF USE_MEMPOOL}
23 uses
24 mempool;
25 {$ENDIF}
28 // ////////////////////////////////////////////////////////////////////////// //
29 type
30 //TODO: implement getting n sequential ids
32 public
35 private
36 type
41 private
47 private
56 public
62 // returns InvalidId if there are no more free ids (or throws)
65 // returns InvalidId if there are no more free ids (or throws)
68 // it is NOT ok to release already released id
74 public
86 implementation
88 uses
89 SysUtils;
92 // ////////////////////////////////////////////////////////////////////////// //
94 begin
102 begin
109 var
111 begin
114 begin
117 if (f > 0) and (mRanges[f-1].last >= mRanges[f].first) then raise Exception.Create('invalid range order');
118 if (f > 0) and (mRanges[f-1].last+1 = mRanges[f].first) then raise Exception.Create('unmerged ranges');
125 var
127 begin
129 begin
130 if (mRanges[f].first > mRanges[f].last) then begin dump(); raise Exception.Create('invalid range'); end;
133 if (f > 0) and (mRanges[f-1].last >= mRanges[f].first) then begin dump(); raise Exception.Create('invalid range order'); end;
134 if (f > 0) and (mRanges[f-1].last+1 = mRanges[f].first) then begin dump(); raise Exception.Create('unmerged ranges'); end;
140 begin
149 function TIdPool.getFreeIds (): Integer; inline; begin result := Integer(mMaxId+1-mUsedIds); end;
154 var
157 begin
160 // -1: not found
164 // yay! use binary search to find the range
168 begin
170 //!assert((mid >= 0) and (mid < len));
181 var
183 begin
193 var
195 begin
199 if (ii >= 0) then result := not ((aid >= mRanges[ii].first) and (aid <= mRanges[ii].last)) else result := true;
203 // returns InvalidId if there are no more free ids (or throws)
205 var
207 begin
209 begin
210 // no more ids
213 exit;
216 // delete first range?
218 begin
221 end
222 else
223 begin
231 // returns InvalidId if there are no more free ids (or throws)
233 var
235 begin
237 begin
238 // no more ids
241 exit;
243 // invalid?
245 begin
248 exit;
250 // find range with this id
253 begin
256 exit;
258 // always return requested id
260 // can we shrink range head?
262 begin
263 // yep; range with the only id?
265 begin
266 // delete this range
269 end
270 else
271 begin
276 exit;
278 // can we shrink range tail?
280 begin
281 // yep; simply shrink, 'cause range with one id was processed in the previous `if`
285 exit;
287 // split this range to two
298 // it is NOT ok to release already released id
300 var
302 begin
303 if (aid > mMaxId) then raise Exception.Create(Format('TIdPool: cannot release invalid id %u', [aid]));
304 // no available ids?
306 begin
307 // just create new range
314 exit;
316 // before first available id?
318 begin
319 // can we grow first range?
321 begin
322 // yep
324 end
325 else
326 begin
327 // nope, insert new first range
337 exit;
339 // after last available id?
341 begin
342 // can we grow last range?
344 begin
345 // yep
347 end
348 else
349 begin
350 // nope, insert new last range
359 exit;
361 // alas, no more easy cases; find the nearest range
363 if (ii < 0) then raise Exception.Create(Format('TIdPool: cannot release invalid id %u', [aid]));
364 if (aid >= mRanges[ii].first) and (aid <= mRanges[ii].last) then raise Exception.Create(Format('TIdPool: cannot release unallocated id %u', [aid]));
365 // ii should contain range where `first` is less than `aid`
368 {$IF DEFINED(IDPOOL_DEBUG_DUMPS)}writeln('aid=', aid, '; ii=', ii, ': [', mRanges[ii].first, '-', mRanges[ii].last, ']');{$ENDIF}
369 // can grow this range at the end?
371 begin
373 // yep; can merge ranges?
375 begin
376 // merge
381 end
382 else
383 begin
384 // change
386 {$IF DEFINED(IDPOOL_DEBUG_DUMPS)}if (ii+1 < mRangeUsed) then writeln(' ii+1=', ii+1, ': [', mRanges[ii+1].first, '-', mRanges[ii+1].last, ']');{$ENDIF}
391 exit;
393 // can grow next range at the start?
395 begin
396 // yep; can merge ranges?
398 begin
399 // merge
403 end
404 else
405 begin
406 // change
411 exit;
413 // cannot grow anything, insert empty range after ii