idpool.d

   1 // pool of numeric ids, with reusing; based on the code by Emil Persson, A.K.A. Humus ( http://www.humus.name )
   2 // Ported and improved by by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3 // Understanding is not required. Only obedience.
   4 //
   5 // This program is free software: you can redistribute it and/or modify
   6 // it under the terms of the GNU General Public License as published by
   7 // the Free Software Foundation, either version 3 of the License, or
   8 // (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program. If not, see <http://www.gnu.org/licenses/>.
  17 //
  18 // the properties of this system are as follows:
  19 //   * creating a new ID returns the smallest possible unused ID
  20 //   * creating a new range of IDs returns the smallest possible continuous range of the specified size
  21 //   * created IDs remain valid until destroyed
  22 //   * destroying an ID returns it to the pool and may be returned by subsequent allocations
  23 //   * the system is NOT thread-safe
  24 //
  25 // performance properties:
  26 //   * creating an ID is O(1) and generally super-cheap
  27 //   * destroying an ID is also cheap, but O(log(n)), where n is the current number of distinct available ranges
  28 //   * the system merges available ranges when IDs are destroyed, keeping said n generally very small in practice
  29 //   * after warmup, no further memory allocations should be necessary, or be very rare
  30 //   * the system uses very little memory
  31 //   * it is possible to construct a pathological case where fragmentation would cause n to become large; don't do that
  32 module iv.idpool;
  33
  34 alias IdPool16 = IdPoolImpl!ushort; ///
  35 alias IdPool32 = IdPoolImpl!uint; ///
  36
  37
  38 /** eneral IdPool implementation;
  39  *
  40  * WARNING! don't use copies of this struct, it WILL ruin everything!
  41  * copying is not disabled to allow copying when programmer thinks it is necessary.
  42  * if `allowZero` is true, zero id is valid, otherwise it is never returned.
  43  * `IDT.max` is ALWAYS invalid, and is used as "error result".
  44  */
  45 struct IdPoolImpl(IDT, bool allowZero=false) if (is(IDT == ubyte) || is(IDT == ushort) || is(IDT == uint)) {
  46 public:
  47   alias Type = IDT; ///
  48   enum Invalid = cast(IDT)IDT.max; /// "invalid id" value
  49
  50 private:
  51   static align(1) struct Range {
  52   align(1):
  53     Type first;
  54     Type last;
  55   }
  56
  57   size_t rangesmem; // sorted array of ranges of free IDs; Range*; use `size_t` to force GC ignoring this struct
  58   uint rngcount; // number of ranges in list
  59   uint rngsize; // total capacity of range list (NOT size in bytes!)
  60   Type idnextmaxid; // next id for `allocNext()`
  61
  62   @property inout(Range)* ranges () const pure inout nothrow @trusted @nogc { pragma(inline, true); return cast(typeof(return))rangesmem; }
  63
  64 private nothrow @trusted @nogc:
  65   // will NOT change rngcount if `doChange` is `false`
  66   void growRangeArray(bool doChange) (uint newcount) {
  67     enum GrowStep = 128;
  68     if (newcount <= rngcount) {
  69       static if (doChange) rngcount = newcount;
  70       return;
  71     }
  72     assert(rngcount <= rngsize);
  73     if (newcount > rngsize) {
  74       // need to grow
  75       import core.stdc.stdlib : realloc;
  76       if (rngsize >= uint.max/(Range.sizeof+8) || newcount >= uint.max/(Range.sizeof+8)) assert(0, "out of memory");
  77       rngsize = ((newcount+(GrowStep-1))/GrowStep)*GrowStep;
  78       size_t newmem = cast(size_t)realloc(cast(void*)rangesmem, rngsize*Range.sizeof);
  79       if (newmem == 0) assert(0, "out of memory");
  80       rangesmem = newmem;
  81     }
  82     assert(newcount <= rngsize);
  83     static if (doChange) rngcount = newcount;
  84   }
  85
  86   version(unittest) void checkRanges () {
  87     if (rngcount == 1) {
  88       if (ranges[0].last+1 == ranges[0].first) return;
  89     }
  90     foreach (immutable ridx, const ref Range r; ranges[0..rngcount]) {
  91       if (r.first > r.last) {
  92         import core.stdc.stdio; stderr.fprintf("INVALID RANGE #%u (first > last): %u, %u\n", ridx, cast(uint)r.first, cast(uint)r.last);
  93         dump;
  94         assert(0, "boom");
  95       }
  96       // check if we failed to merge ranges
  97       if (rngcount-ridx > 1 && r.last >= ranges[ridx+1].first) {
  98         import core.stdc.stdio; stderr.fprintf("FAILED TO MERGE RANGE #%u: last=%u, next_first=%u\n", ridx, cast(uint)r.last, cast(uint)(ranges[ridx+1].first));
  99         dump;
 100         assert(0, "boom");
 101       }
 102       if (ridx && r.first <= ranges[ridx-1].last) {
 103         import core.stdc.stdio; stderr.fprintf("FAILED TO SORT RANGES #%u: last=%u, next_first=%u\n", ridx, cast(uint)r.last, cast(uint)(ranges[ridx+1].first));
 104         dump;
 105         assert(0, "boom");
 106       }
 107     }
 108   }
 109
 110   void insertRange (uint index) {
 111     growRangeArray!false(rngcount+1);
 112     if (index < rngcount) {
 113       // really inserting
 114       import core.stdc.string : memmove;
 115       memmove(ranges+index+1, ranges+index, (rngcount-index)*Range.sizeof);
 116     }
 117     ++rngcount;
 118   }
 119
 120   void destroyRange (uint index) {
 121     import core.stdc.string : memmove;
 122     assert(rngcount > 0);
 123     if (--rngcount > 0) memmove(ranges+index, ranges+index+1, (rngcount-index)*Range.sizeof);
 124     version(unittest) checkRanges();
 125   }
 126
 127 public:
 128   ///
 129   this (Type aMaxId) { reset(aMaxId); }
 130
 131   ///
 132   ~this () {
 133     if (rangesmem) {
 134       import core.stdc.stdlib : free;
 135       free(cast(void*)rangesmem);
 136     }
 137   }
 138
 139   /// checks if the given id is in valid id range.
 140   static bool isValid (Type id) pure nothrow @safe @nogc {
 141     pragma(inline, true);
 142     static if (allowZero) return (id != Invalid); else return (id && id != Invalid);
 143   }
 144
 145   /// return next id for `allocNext()`. this is here just for completeness.
 146   @property nextSeqId () const pure { pragma(inline, true); static if (allowZero) { return idnextmaxid; } else { return (idnextmaxid ? idnextmaxid : 1); } }
 147
 148   /// remove all allocated ids, and set maximum available id.
 149   void reset (Type aMaxId=Type.max) {
 150     if (aMaxId < 1) assert(0, "are you nuts?");
 151     if (aMaxId == Type.max) --aMaxId; // to ease my life a little
 152     // start with a single range, from 0/1 to max allowed ID (specified)
 153     growRangeArray!true(1);
 154     static if (allowZero) ranges[0].first = 0; else ranges[0].first = 1;
 155     ranges[0].last = aMaxId;
 156     idnextmaxid = 0;
 157   }
 158
 159   /// allocate lowest unused id.
 160   /// returns `Invalid` if there are no more ids left.
 161   Type allocId () {
 162     if (rngcount == 0) {
 163       // wasn't inited, init with defaults
 164       growRangeArray!true(1);
 165       static if (allowZero) ranges[0].first = 0; else ranges[0].first = 1;
 166       ranges[0].last = Type.max-1;
 167     }
 168     auto rng = ranges;
 169     Type id = Invalid;
 170     if (rng.first <= rng.last) {
 171       id = rng.first;
 172       // if current range is full and there is another one, that will become the new current range
 173       if (rng.first == rng.last && rngcount > 1) destroyRange(0); else ++rng.first;
 174       version(unittest) checkRanges();
 175     }
 176     // otherwise we have no ranges left
 177     if (id != Invalid && id >= idnextmaxid) idnextmaxid = cast(Type)(id+1);
 178     return id;
 179   }
 180
 181   /// allocate the given id.
 182   /// returns id, or `Invalid` if this id was alrady allocated.
 183   Type allocId (Type aid) {
 184     static if (allowZero) {
 185       if (aid == Invalid) return Invalid;
 186     } else {
 187       if (aid == 0 || aid == Invalid) return Invalid;
 188     }
 189
 190     if (rngcount == 0) {
 191       // wasn't inited, create two ranges (before and after this id)
 192       if (aid >= idnextmaxid) idnextmaxid = cast(Type)(aid+1); // fix next max id
 193       // but check for special cases first
 194       static if (allowZero) enum LowestId = 0; else enum LowestId = 1;
 195       // lowest possible id?
 196       if (aid == LowestId) {
 197         growRangeArray!true(1);
 198         ranges[0].first = cast(Type)(LowestId+1);
 199         ranges[0].last = Type.max-1;
 200         version(unittest) checkRanges();
 201         return aid;
 202       }
 203       // highest possible id?
 204       if (aid == Type.max-1) {
 205         growRangeArray!true(1);
 206         ranges[0].first = cast(Type)LowestId;
 207         ranges[0].last = Type.max-2;
 208         version(unittest) checkRanges();
 209         return aid;
 210       }
 211       // create two ranges
 212       growRangeArray!true(2);
 213       ranges[0].first = cast(Type)LowestId;
 214       ranges[0].last = cast(Type)(aid-1);
 215       ranges[1].first = cast(Type)(aid+1);
 216       ranges[1].last = cast(Type)(Type.max-1);
 217       version(unittest) checkRanges();
 218       return aid;
 219     }
 220     // already inited, check if the given id is not allocated, and split ranges
 221     // binary search of the range list
 222     uint i0 = 0, i1 = rngcount-1;
 223     for (;;) {
 224       uint i = (i0+i1)/2; // guaranteed to not overflow, see `growRangeArray()`
 225       Range* rngi = ranges+i;
 226       if (aid < rngi.first) {
 227         if (i == i0) return Invalid; // already allocated
 228         // cull upper half of list
 229         i1 = i-1;
 230       } else if (aid > rngi.last) {
 231         if (i == i1) return Invalid; // already allocated
 232         // cull bottom half of list
 233         i0 = i+1;
 234       } else {
 235         // inside a free block, split it
 236         if (aid >= idnextmaxid) idnextmaxid = cast(Type)(aid+1); // fix next max id (this can be wrong when there are no memory for ranges, but meh)
 237         // check for corner case: do we want range's starting id?
 238         if (rngi.first == aid) {
 239           // if current range is full and there is another one, that will become the new current range
 240           if (rngi.first == rngi.last && rngcount > 1) destroyRange(i); else ++rngi.first;
 241           version(unittest) checkRanges();
 242           return aid;
 243         }
 244         // check for corner case: do we want range's ending id?
 245         if (rngi.last == aid) {
 246           // if current range is full and there is another one, that will become the new current range
 247           if (rngi.first == rngi.last) {
 248             if (rngcount > 1) destroyRange(i); else ++rngi.first; // turn range into invalid
 249           } else {
 250             --rngi.last;
 251           }
 252           version(unittest) checkRanges();
 253           return aid;
 254         }
 255         // have to split the range in two
 256         if (rngcount >= uint.max-2) return Invalid; // no room
 257         insertRange(i+1);
 258         rngi = ranges+i; // pointer may be invalidated by inserting, so update it
 259         rngi[1].last = rngi.last;
 260         rngi[1].first = cast(Type)(aid+1);
 261         rngi[0].last = cast(Type)(aid-1);
 262         assert(rngi[0].first <= rngi[0].last);
 263         assert(rngi[1].first <= rngi[1].last);
 264         assert(rngi[0].last+2 == rngi[1].first);
 265         version(unittest) checkRanges();
 266         return aid;
 267       }
 268     }
 269   }
 270
 271   /// allocate "next" id. "next" ids are always increasing, and will never duplicate (within the limits).
 272   /// returns id, or `Invalid` if this id was alrady allocated.
 273   Type allocNext () {
 274     static if (!allowZero) {
 275       if (idnextmaxid == 0) idnextmaxid = 1;
 276     }
 277     if (idnextmaxid == Type.max) return Invalid; // no more ids
 278     return allocId(idnextmaxid); // should never return `Invalid`, and will fix `idnextmaxid` by itself
 279   }
 280
 281   /// allocate `count` sequential ids with the lowest possible number.
 282   /// returns `Invalid` if the request cannot be satisfied.
 283   Type allocRange (uint count) {
 284     if (count == 0) return Invalid;
 285     if (count >= Type.max) return Invalid; // too many
 286     if (rngcount == 0) {
 287       // wasn't inited, init with defaults
 288       growRangeArray!true(1);
 289       static if (allowZero) ranges[0].first = 0; else ranges[0].first = 1;
 290       ranges[0].last = Type.max-1;
 291     }
 292     uint i = 0;
 293     do {
 294       uint rcnt = 1+ranges[i].last-ranges[i].first;
 295       if (count <= rcnt) {
 296         Type id = ranges[i].first;
 297         // if current range is full and there is another one, that will become the new current range
 298         if (count == rcnt && i+1 < rngcount) destroyRange(i); else ranges[i].first += count;
 299         version(unittest) checkRanges();
 300         return id;
 301       }
 302     } while (++i < rngcount);
 303     // no range of free IDs was large enough to create the requested continuous ID sequence
 304     return Invalid;
 305   }
 306
 307   /// release allocated id.
 308   /// returns `true` if `id` was a valid allocated one.
 309   bool releaseId (Type id) { return releaseRange(id, 1); }
 310
 311   /// release allocated id range.
 312   /// returns `true` if the rage was a valid allocated one.
 313   bool releaseRange (Type id, uint count) {
 314     if (count == 0 || rngcount == 0) return false;
 315     if (count >= Type.max) return false; // too many
 316
 317     static if (allowZero) {
 318       if (id == Invalid) return false;
 319     } else {
 320       if (id == 0 || id == Invalid) return false;
 321     }
 322
 323     uint endid = id+count;
 324     static if (is(Type == uint)) {
 325       if (endid <= id) return false; // overflow check; fuck you, C!
 326     } else {
 327       if (endid <= id || endid > Type.max) return false; // overflow check; fuck you, C!
 328     }
 329
 330     // binary search of the range list
 331     uint i0 = 0, i1 = rngcount-1;
 332     for (;;) {
 333       uint i = (i0+i1)/2; // guaranteed to not overflow, see `growRangeArray()`
 334       Range* rngi = ranges+i;
 335       if (id < rngi.first) {
 336         // before current range, check if neighboring
 337         if (endid >= rngi.first) {
 338           if (endid != rngi.first) return false; // overlaps a range of free IDs, thus (at least partially) invalid IDs
 339           // neighbor id, check if neighboring previous range too
 340           if (i > i0 && id-1 == ranges[i-1].last) {
 341             // merge with previous range
 342             ranges[i-1].last = rngi.last;
 343             destroyRange(i);
 344           } else {
 345             // just grow range
 346             rngi.first = id;
 347           }
 348           version(unittest) checkRanges();
 349           return true;
 350         } else {
 351           // non-neighbor id
 352           if (i != i0) {
 353             // cull upper half of list
 354             i1 = i-1;
 355           } else {
 356             // found our position in the list, insert the deleted range here
 357             insertRange(i);
 358             // refresh pointer
 359             rngi = ranges+i;
 360             rngi.first = id;
 361             rngi.last = cast(Type)(endid-1);
 362             version(unittest) checkRanges();
 363             return true;
 364           }
 365         }
 366       } else if (id > rngi.last) {
 367         // after current range, check if neighboring
 368         if (id-1 == rngi.last) {
 369           // neighbor id, check if neighboring next range too
 370           if (i < i1 && endid == ranges[i+1].first) {
 371             // merge with next range
 372             rngi.last = ranges[i+1].last;
 373             destroyRange(i+1);
 374           } else {
 375             // just grow range
 376             rngi.last += count;
 377           }
 378           version(unittest) checkRanges();
 379           return true;
 380         } else {
 381           // non-neighbor id
 382           if (i != i1) {
 383             // cull bottom half of list
 384             i0 = i+1;
 385           } else {
 386             // found our position in the list, insert the deleted range here
 387             insertRange(i+1);
 388             // get pointer to [i+1]
 389             rngi = ranges+i+1;
 390             rngi.first = id;
 391             rngi.last = cast(Type)(endid-1);
 392             version(unittest) checkRanges();
 393             return true;
 394           }
 395         }
 396       } else {
 397         // inside a free block, not a valid ID
 398         return false;
 399       }
 400     }
 401   }
 402
 403   /// is the gived id valid and allocated?
 404   bool isAllocated (Type id) const {
 405     if (rngcount == 0) return false; // anyway, 'cause not inited
 406     static if (allowZero) {
 407       if (id == Invalid) return false;
 408     } else {
 409       if (id == 0 || id == Invalid) return false;
 410     }
 411     // binary search of the range list
 412     uint i0 = 0, i1 = rngcount-1;
 413     for (;;) {
 414       uint i = (i0+i1)/2; // guaranteed to not overflow, see `growRangeArray()`
 415       const(Range)* rngi = ranges+i;
 416       if (id < rngi.first) {
 417         if (i == i0) return true;
 418         // cull upper half of list
 419         i1 = i-1;
 420       } else if (id > rngi.last) {
 421         if (i == i1) return true;
 422         // cull bottom half of list
 423         i0 = i+1;
 424       } else {
 425         // inside a free block, not a valid ID
 426         return false;
 427       }
 428     }
 429   }
 430
 431   /// count number of available free ids.
 432   uint countAvail () const {
 433     uint count = rngcount; // we are not keeping empty ranges, so it is safe to start with this
 434     foreach (const ref Range r; ranges[0..count]) count += r.last-r.first; // `last` is inclusive, but see the previous line
 435     return count;
 436   }
 437
 438   /// get largest available continuous free range.
 439   uint largestAvailRange () const {
 440     uint maxCount = 0;
 441     foreach (const ref Range r; ranges[0..rngcount]) {
 442       uint count = r.last-r.first+1; // `last` is inclusive
 443       if (count > maxCount) maxCount = count;
 444     }
 445     return maxCount;
 446   }
 447
 448   // debug dump
 449   void dump () const {
 450     import core.stdc.stdio : stderr, fprintf;
 451     if (rngcount == 0) { stderr.fprintf("<not-inited>\n"); return; }
 452     stderr.fprintf("<");
 453     foreach (immutable ridx, const ref Range r; ranges[0..rngcount]) {
 454       if (ridx) stderr.fprintf(",");
 455            if (r.first < r.last) stderr.fprintf("%u-%u", cast(uint)r.first, cast(uint)r.last);
 456       else if (r.first == r.last) stderr.fprintf("%u", cast(uint)r.first);
 457       else stderr.fprintf("-");
 458     }
 459     stderr.fprintf(">\n");
 460   }
 461 }
 462
 463
 464 version(iv_unittest_idpool) unittest {
 465   import iv.prng.pcg32;
 466   import iv.prng.seeder;
 467
 468   {
 469     IdPool16 xpool;
 470     { import core.stdc.stdio; printf("next max=%u\n", xpool.nextSeqId); }
 471
 472     ulong zseed = getUlongSeed;
 473     { import core.stdc.stdio; printf("phase 0 seed: %llu\n", zseed); }
 474     PCG32 zprng;
 475     zprng.seed(zseed, 42);
 476
 477     foreach (immutable oit; 0..5) {
 478       xpool.reset();
 479       foreach (immutable itr; 0..60000) {
 480         auto id = xpool.allocNext();
 481         assert(id == itr+1);
 482         assert(id == xpool.nextSeqId-1);
 483         // free random id
 484         auto rid = cast(xpool.Type)(zprng.front%(id+1));
 485         if (xpool.isAllocated(rid)) xpool.releaseId(rid);
 486         assert(!xpool.isAllocated(rid));
 487         if (rid == id) assert(!xpool.isAllocated(id)); else assert(xpool.isAllocated(id));
 488       }
 489     }
 490   }
 491
 492   IdPool16 pool;
 493   static bool[pool.Type.max+1] alloced = false;
 494
 495   // two invalid ids
 496   alloced[0] = true;
 497   alloced[pool.Invalid] = true;
 498   uint acount = 0;
 499   foreach (immutable _; 0..1_000_000) {
 500     auto xid = pool.allocId();
 501     if (!pool.isValid(xid)) {
 502       if (acount == pool.Type.max-1) break;
 503       assert(0, "fuuuuu");
 504     }
 505     ++acount;
 506     if (alloced[xid]) {
 507       { import core.stdc.stdio; printf("%u allocated twice\n", cast(uint)xid); }
 508       assert(0, "fuuuuuuuu");
 509     }
 510     alloced[xid] = true;
 511     //{ import core.stdc.stdio; printf("allocated: %u\n", cast(uint)xid); }
 512   }
 513   { import core.stdc.stdio; printf("phase 1 stats: acount=%u; rngcount=%u; rngsize=%u; avail=%u\n", acount, pool.rngcount, pool.rngsize, pool.countAvail); }
 514   assert(pool.countAvail == 0);
 515   assert(!pool.isAllocated(0));
 516   assert(!pool.isAllocated(pool.Invalid));
 517   foreach (immutable pool.Type n; 1..pool.Type.max) assert(pool.isAllocated(n));
 518
 519   ulong xseed = getUlongSeed;
 520   //xseed = 1102831282614566469UL;
 521   //xseed = 10585134441705064158UL;
 522   //xseed = 6483023210891954504UL;
 523   { import core.stdc.stdio; printf("phase 2 seed: %llu\n", xseed); }
 524   PCG32 prng;
 525   prng.seed(xseed, 42);
 526
 527   // two invalid ids
 528   pool.reset();
 529   alloced[] = false;
 530   alloced[0] = true;
 531   alloced[pool.Invalid] = true;
 532   acount = 0;
 533   uint getCount = 0, relCount = 0;
 534   //{ import core.stdc.stdio; printf("phase 2...\n"); }
 535   foreach (immutable nn; 0..10_000_000) {
 536     //{ import core.stdc.stdio; printf("nn=%u\n", nn); }
 537     pool.Type xid = cast(pool.Type)prng.front;
 538     prng.popFront();
 539     if (!pool.isValid(xid)) {
 540       assert(xid == 0 || xid == pool.Invalid);
 541       continue;
 542     }
 543     if (pool.isAllocated(xid)) {
 544       // release
 545       //if (nn == 145915) { import core.stdc.stdio; printf("RELEASING %u\n", cast(uint)xid); }
 546       assert(alloced[xid]);
 547       if (!pool.releaseId(xid)) assert(0, "fuuuu");
 548       alloced[xid] = false;
 549       assert(acount > 0);
 550       --acount;
 551       ++relCount;
 552     } else {
 553       // allocate new id
 554       xid = pool.allocId;
 555       assert(pool.isValid(xid));
 556       if (!pool.isAllocated(xid)) { import core.stdc.stdio; printf("failed at step %u; xid %u is not marked as allocated\n", nn, cast(uint)xid); }
 557       //assert(pool.isAllocated(xid));
 558       if (alloced[xid]) { import core.stdc.stdio; printf("failed at step %u; xid %u is already alloced\n", nn, cast(uint)xid); }
 559       assert(!alloced[xid]);
 560       ++acount;
 561       alloced[xid] = true;
 562       ++getCount;
 563     }
 564   }
 565   { import core.stdc.stdio; printf("phase 2 stats: getCount=%u; relCount=%u; acount=%u; rngcount=%u; rngsize=%u\n", getCount, relCount, acount, pool.rngcount, pool.rngsize); }
 566   // check if pool is consistent
 567   assert(pool.countAvail == pool.Type.max-1-acount);
 568   assert(!pool.isAllocated(0));
 569   assert(!pool.isAllocated(pool.Invalid));
 570   foreach (immutable pool.Type n; 1..pool.Type.max) assert(pool.isAllocated(n) == alloced[n]);
 571 }