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