From 30f7ce6315b82400548455c6872a271dc1f00f50 Mon Sep 17 00:00:00 2001 From: Ketmar Dark Date: Fri, 25 Aug 2017 15:58:49 +0300 Subject: [PATCH] idpool: it is now possible to request the specified id --- src/shared/idpool.pas | 89 ++++++++++++++++++++++++++++++++----- src/shared/ztest_idpool.dpr | 22 ++++++++- 2 files changed, 100 insertions(+), 11 deletions(-) diff --git a/src/shared/idpool.pas b/src/shared/idpool.pas index efba5e6..7817cc1 100644 --- a/src/shared/idpool.pas +++ b/src/shared/idpool.pas @@ -14,7 +14,7 @@ * along with this program. If not, see . *) {$INCLUDE a_modes.inc} -{.$DEFINE IDPOOL_CHECKS} +{$DEFINE IDPOOL_CHECKS} unit idpool; interface @@ -56,6 +56,9 @@ type // returns InvalidId if there are no more free ids (or throws) function alloc (dothrow: Boolean=true): LongWord; + // returns InvalidId if there are no more free ids (or throws) + function alloc (aid: LongWord; dothrow: Boolean=true): LongWord; + // it is NOT ok to release already released id procedure release (aid: LongWord); @@ -74,7 +77,6 @@ type property capacity: Integer read getCapacity; end; - implementation uses @@ -119,11 +121,11 @@ var begin for f := 0 to mRangeUsed-1 do begin - if (mRanges[f].first > mRanges[f].last) then raise Exception.Create('invalid range'); - if (mRanges[f].first > mMaxId) then raise Exception.Create('invalid range'); - if (mRanges[f].last > mMaxId) then raise Exception.Create('invalid range'); - if (f > 0) and (mRanges[f-1].last >= mRanges[f].first) then raise Exception.Create('invalid range order'); - if (f > 0) and (mRanges[f-1].last+1 = mRanges[f].first) then raise Exception.Create('unmerged ranges'); + if (mRanges[f].first > mRanges[f].last) then begin dump(); raise Exception.Create('invalid range'); end; + if (mRanges[f].first > mMaxId) then begin dump(); raise Exception.Create('invalid range'); end; + if (mRanges[f].last > mMaxId) then begin dump(); raise Exception.Create('invalid range'); end; + if (f > 0) and (mRanges[f-1].last >= mRanges[f].first) then begin dump(); raise Exception.Create('invalid range order'); end; + if (f > 0) and (mRanges[f-1].last+1 = mRanges[f].first) then begin dump(); raise Exception.Create('unmerged ranges'); end; end; end; @@ -220,6 +222,73 @@ begin end; +// returns InvalidId if there are no more free ids (or throws) +function TIdPool.alloc (aid: LongWord; dothrow: Boolean=true): LongWord; +var + ii, c: Integer; +begin + if (mRangeUsed = 0) then + begin + // no more ids + if dothrow then raise Exception.Create('TIdPool: no more free ids'); + result := InvalidId; + exit; + end; + // invalid? + if (aid > mMaxId) then + begin + if dothrow then raise Exception.Create('TIdPool: cannot allocate invalid id'); + result := InvalidId; + exit; + end; + // find range with this id + ii := findRangeWithId(aid); + if (ii < 0) or (aid < mRanges[ii].first) or (aid > mRanges[ii].last) then + begin + if dothrow then raise Exception.Create('TIdPool: cannot allocate already allocated id'); + result := InvalidId; + exit; + end; + // always return requested id + result := aid; + // can we shrink range head? + if (aid = mRanges[ii].first) then + begin + // yep; range with the only id? + if (aid = mRanges[ii].last) then + begin + // delete this range + for c := ii+1 to mRangeUsed-1 do mRanges[c-1] := mRanges[c]; + Dec(mRangeUsed); + end + else + begin + mRanges[ii].first := aid+1; + end; + Inc(mUsedIds); + {$IF DEFINED(IDPOOL_CHECKS)}check();{$ENDIF} + exit; + end; + // can we shrink range tail? + if (aid = mRanges[ii].last) then + begin + // yep; simply shrink, 'cause range with one id was processed in the previous `if` + mRanges[ii].last := aid-1; + Inc(mUsedIds); + {$IF DEFINED(IDPOOL_CHECKS)}check();{$ENDIF} + exit; + end; + // split this range to two + if (mRangeUsed+1 > Length(mRanges)) then SetLength(mRanges, Length(mRanges)+1024); + for c := mRangeUsed downto ii+1 do mRanges[c] := mRanges[c-1]; + Inc(mRangeUsed); + mRanges[ii].last := aid-1; + mRanges[ii+1].first := aid+1; + Inc(mUsedIds); + {$IF DEFINED(IDPOOL_CHECKS)}check();{$ENDIF} +end; + + // it is NOT ok to release already released id procedure TIdPool.release (aid: LongWord); var @@ -250,7 +319,7 @@ begin else begin // nope, insert new first range - if (mRangeUsed+1 > Length(mRanges)) then SetLength(mRanges, Length(mRanges)*2); + if (mRangeUsed+1 > Length(mRanges)) then SetLength(mRanges, Length(mRanges)+1024); assert(mRangeUsed < Length(mRanges)); for c := mRangeUsed downto 1 do mRanges[c] := mRanges[c-1]; Inc(mRangeUsed); @@ -273,7 +342,7 @@ begin else begin // nope, insert new last range - if (mRangeUsed+1 > Length(mRanges)) then SetLength(mRanges, Length(mRanges)*2); + if (mRangeUsed+1 > Length(mRanges)) then SetLength(mRanges, Length(mRanges)+1024); assert(mRangeUsed < Length(mRanges)); mRanges[mRangeUsed].first := aid; mRanges[mRangeUsed].last := aid; @@ -336,7 +405,7 @@ begin exit; end; // cannot grow anything, insert empty range after ii - if (mRangeUsed = Length(mRanges)) then SetLength(mRanges, Length(mRanges)*2); + if (mRangeUsed = Length(mRanges)) then SetLength(mRanges, Length(mRanges)+1024); for c := mRangeUsed downto ii do mRanges[c+1] := mRanges[c]; Inc(ii); mRanges[ii].first := aid; diff --git a/src/shared/ztest_idpool.dpr b/src/shared/ztest_idpool.dpr index 393c43c..32d0fd0 100644 --- a/src/shared/ztest_idpool.dpr +++ b/src/shared/ztest_idpool.dpr @@ -48,11 +48,29 @@ var f, n: Integer; usedIds: Integer = 0; begin - ip := TIdPool.Create(65535*1024); + ip := TIdPool.Create(65535); SetLength(map, ip.maxId+1); for f := 0 to High(map) do map[f] := false; for f := 0 to High(map) div 2 do begin + while true do + begin + n := Random(ip.maxId+1); + if map[n] then + begin + if not ip.hasAlloced[n] then raise Exception.Create('invalid pool(0)'); + if ip.hasFree[n] then raise Exception.Create('invalid pool(1)'); + continue; + end; + break; + end; + if (ip.alloc(n) <> n) then raise Exception.Create('wutafuuuuu?!'); + map[n] := true; + Inc(usedIds); + if not ip.hasAlloced[n] then raise Exception.Create('invalid pool(3)'); + if ip.hasFree[n] then raise Exception.Create('invalid pool(4)'); + //ip.dump(); + { if ip.hasAlloced[f] then raise Exception.Create('invalid pool(0)'); if not ip.hasFree[f] then raise Exception.Create('invalid pool(1)'); if (ip.alloc <> f) then raise Exception.Create('invalid alloc(2)'); @@ -60,6 +78,7 @@ begin Inc(usedIds); if not ip.hasAlloced[f] then raise Exception.Create('invalid pool(3)'); if ip.hasFree[f] then raise Exception.Create('invalid pool(4)'); + } end; for f := 0 to 10000000 do begin @@ -107,6 +126,7 @@ begin if not ip.hasFree[f] then raise Exception.Create('invalid pool(e)'); end; end; + ip.Free(); end; -- 2.29.2