SCClassLibrary/Common/Control/Engine.sc

   1 NodeIDAllocator
   2 {
   3         var <user, initTemp, temp, perm, mask, permFreed;
   4         // support 32 users
   5
   6         *new { arg user=0, initTemp = 1000;
   7                 if (user > 31) { "NodeIDAllocator user id > 31".error; ^nil };
   8                 ^super.newCopyArgs(user, initTemp).reset
   9         }
  10         reset {
  11                 mask = user << 26;
  12                 temp = initTemp;
  13                 perm = 2;
  14                 permFreed = IdentitySet.new;
  15         }
  16         alloc {
  17                 var x;
  18                 x = temp;
  19                 temp = (x + 1).wrap(initTemp, 0x03FFFFFF);
  20                 ^x | mask
  21         }
  22         allocPerm {
  23                 var x;
  24                 if(permFreed.size > 0) {
  25                         x = permFreed.minItem;
  26                         permFreed.remove(x);
  27                 } {
  28                         x = perm;
  29                         perm = (x + 1).min(initTemp - 1);
  30                 }
  31                 ^x | mask
  32         }
  33         freePerm { |id|
  34                         // should not add a temp node id to the freed-permanent collection
  35                 id = id bitAnd: 0x03FFFFFF;
  36                 if(id < initTemp) { permFreed.add(id) }
  37         }
  38 }
  39
  40
  41 PowerOfTwoBlock
  42 {
  43         var <address, <size, <>next;
  44         *new { arg address, size;
  45                 ^super.newCopyArgs(address, size)
  46         }
  47 }
  48
  49 PowerOfTwoAllocator
  50 {
  51         // THIS IS THE RECOMMENDED ALLOCATOR FOR BUSES AND BUFFERS
  52         var size, array, freeLists, pos=0;
  53
  54         *new { arg size, pos=0;
  55                 ^super.newCopyArgs(size, Array.newClear(size), Array.newClear(32), pos)
  56         }
  57         alloc { arg n;
  58                 var sizeClass, node, address;
  59                 n = n.nextPowerOfTwo;
  60                 sizeClass = n.log2Ceil;
  61
  62                 node = freeLists.at(sizeClass);
  63                 if (node.notNil, {
  64                         freeLists.put(sizeClass, node.next);
  65                         ^node.address
  66                 });
  67                 if (pos + n <= size, {
  68                         array.put(pos, PowerOfTwoBlock(pos, n));
  69                         address = pos;
  70                         pos = pos + n;
  71                         ^address
  72                 });
  73                 ^nil
  74         }
  75         free { arg address;
  76                 var node, sizeClass,next;
  77
  78                 if((node = array.at(address)).notNil,{
  79
  80                         sizeClass = node.size.log2Ceil;
  81                         node.next = freeLists.at(sizeClass);
  82                         freeLists.put(sizeClass, node);
  83                         array.put(address, nil);
  84
  85                 });
  86         }
  87         blocks {
  88                 ^array.select({ arg b; b.notNil })
  89         }
  90 }
  91
  92 LRUNumberAllocator
  93 {
  94         // implements a least recently used ID allocator.
  95
  96         var lo, hi;
  97         var array, size, head=0, tail=0;
  98
  99         *new { arg lo, hi;
 100                 ^super.newCopyArgs(lo, hi).init
 101         }
 102         init {
 103                 size = hi-lo+1;
 104                 array = Array.newClear(size);
 105                 for(lo, hi-1, { arg i, j; array.put(j, i) });
 106                 head = size-1;
 107                 tail=0;
 108         }
 109         free { arg id;
 110                 var nextIndex;
 111                 nextIndex = (head+1) % size;
 112                 if ( nextIndex == tail, { ^nil }); // full
 113                 array.put(head, id);
 114                 head = nextIndex;
 115         }
 116         alloc {
 117                 var id;
 118                 if (head == tail, { ^nil }); // empty
 119                 id = array.at(tail);
 120                 tail = (tail+1) % size;
 121                 ^id
 122         }
 123 }
 124
 125 StackNumberAllocator
 126 {
 127         var lo, hi, freeList, next;
 128
 129         *new { arg lo, hi;
 130                 ^super.newCopyArgs(lo, hi).init
 131         }
 132         init {
 133                 next = lo - 1;
 134         }
 135         alloc {
 136                 if (freeList.size > 0, { ^freeList.pop });
 137                 if (next < hi, { ^next = next + 1; });
 138                 ^nil
 139         }
 140         free { arg inIndex;
 141                 freeList = freeList.add(inIndex);
 142         }
 143 }
 144
 145 RingNumberAllocator
 146 {
 147         var lo, hi, next;
 148
 149         *new { arg lo, hi;
 150                 ^super.newCopyArgs(lo, hi).init
 151         }
 152         init {
 153                 next = hi;
 154         }
 155         alloc {
 156                 ^next = (next + 1).wrap(lo,hi)
 157         }
 158 }
 159
 160
 161 // by hjh: for better handling of dynamic allocation
 162
 163 ContiguousBlock {
 164
 165         var     <start, <size, <>used = false;  // assume free; owner must say otherwise
 166
 167         *new { |start, size| ^super.newCopyArgs(start, size) }
 168
 169         address { ^start }
 170
 171         adjoins { |block|
 172                 ^(start < block.start and: { start + size >= block.start })
 173                         or: { start > block.start and: { block.start + block.size >= start } }
 174         }
 175
 176         join { |block|
 177                 var newstart;
 178                 this.adjoins(block).if({
 179                         ^this.class.new(newstart = min(start, block.start),
 180                                 max(start + size, block.start + block.size) - newstart)
 181                 }, {
 182                         ^nil
 183                 });
 184         }
 185
 186         split { |span|
 187                 (span < size).if({
 188                         ^[this.class.new(start, span),
 189                                 this.class.new(start + span, size - span)]
 190                 }, {
 191                         (span == size).if({
 192                                 ^[this, nil]
 193                         }, { ^nil });
 194                 });
 195         }
 196
 197         storeArgs { ^[start, size, used] }
 198         printOn { |stream| this.storeOn(stream) }
 199 }
 200
 201
 202 ContiguousBlockAllocator {
 203         var     size, array, freed, pos, top;
 204
 205         *new { |size, pos = 0|
 206                 ^super.newCopyArgs(size, Array.newClear(size).put(pos, ContiguousBlock(pos, size-pos)),
 207                         IdentityDictionary.new, pos, pos);
 208         }
 209
 210         alloc { |n = 1|
 211                 var     block;
 212                 (block = this.findAvailable(n)).notNil.if({
 213                         ^this.prReserve(block.start, n, block).start
 214                 }, { ^nil });
 215         }
 216
 217         reserve { |address, size = 1, warn = true|
 218                 var     block, new;
 219                 ((block = array[address] ?? { this.findNext(address) }).notNil and:
 220                                 { block.used and:
 221                                 { address + size > block.start } }).if({
 222                         warn.if({ "The block at (%, %) is already in use and cannot be reserved."
 223                                 .format(address, size).warn; });
 224                 }, {
 225                         (block.start == address).if({
 226                                 new = this.prReserve(address, size, block);
 227                                 ^new;
 228                         }, {
 229                                 ((block = this.findPrevious(address)).notNil and:
 230                                                 { block.used and:
 231                                                 { block.start + block.size > address } }).if({
 232                                         warn.if({ "The block at (%, %) is already in use and cannot be reserved."
 233                                                 .format(address, size).warn; });
 234                                 }, {
 235                                         new = this.prReserve(address, size, nil, block);
 236                                         ^new;
 237                                 });
 238                         });
 239                 });
 240                 ^nil
 241         }
 242
 243         free { |address|
 244                 var     block,
 245                         prev, next, temp;
 246                 ((block = array[address]).notNil and: { block.used }).if({
 247                         block.used = false;
 248                         this.addToFreed(block);
 249                         ((prev = this.findPrevious(address)).notNil and: { prev.used.not }).if({
 250                                 (temp = prev.join(block)).notNil.if({
 251                                                 // if block is the last one, reduce the top
 252                                         (block.start == top).if({ top = temp.start });
 253                                         array[temp.start] = temp;
 254                                         array[block.start] = nil;
 255                                         this.removeFromFreed(prev).removeFromFreed(block);
 256                                         (top > temp.start).if({ this.addToFreed(temp); });
 257                                         block = temp;
 258                                 });
 259                         });
 260                         ((next = this.findNext(block.start)).notNil and: { next.used.not }).if({
 261                                 (temp = next.join(block)).notNil.if({
 262                                                 // if next is the last one, reduce the top
 263                                         (next.start == top).if({ top = temp.start });
 264                                         array[temp.start] = temp;
 265                                         array[next.start] = nil;
 266                                         this.removeFromFreed(next).removeFromFreed(block);
 267                                         (top > temp.start).if({ this.addToFreed(temp); });
 268                                 });
 269                         });
 270                 });
 271         }
 272
 273         blocks {
 274                 ^array.select({ arg b; b.notNil and: { b.used } })
 275         }
 276
 277         findAvailable { |n|
 278                 (freed[n].size > 0).if({ ^freed[n].choose });
 279
 280                 freed.keysValuesDo({ |size, set|
 281                         (size >= n and: { set.size > 0 }).if({
 282                                 ^set.choose
 283                         });
 284                 });
 285
 286                 (top + n > size or: { array[top].used }).if({ ^nil });
 287                 ^array[top]
 288         }
 289
 290         addToFreed { |block|
 291                 freed[block.size].isNil.if({ freed[block.size] = IdentitySet.new });
 292                 freed[block.size].add(block);
 293         }
 294
 295         removeFromFreed { |block|
 296                 freed[block.size].tryPerform(\remove, block);
 297                         // I tested without gc; performance is about half as efficient without it
 298                 (freed[block.size].size == 0).if({ freed.removeAt(block.size) });
 299         }
 300
 301         findPrevious { |address|
 302                 forBy(address-1, pos, -1, { |i|
 303                         array[i].notNil.if({ ^array[i] });
 304                 });
 305                 ^nil
 306         }
 307
 308         findNext { |address|
 309                 var     temp;
 310                 (temp = array[address]).notNil.if({
 311                         ^array[temp.start + temp.size]
 312                 }, {
 313                         for(address+1, top, { |i|
 314                                 array[i].notNil.if({ ^array[i] });
 315                         });
 316                 });
 317                 ^nil
 318         }
 319
 320         prReserve { |address, size, availBlock, prevBlock|
 321                 var     new, leftover;
 322                 (availBlock.isNil and: { prevBlock.isNil }).if({
 323                         prevBlock = this.findPrevious(address);
 324                 });
 325                 availBlock = availBlock ? prevBlock;
 326                 (availBlock.start < address).if({
 327                         #leftover, availBlock = this.prSplit(availBlock,
 328                                 address - availBlock.start, false);
 329                 });
 330                 ^this.prSplit(availBlock, size, true)[0];
 331         }
 332
 333         prSplit { |availBlock, n, used = true|
 334                 var     new, leftover;
 335                 #new, leftover = availBlock.split(n);
 336                 new.used = used;
 337                 this.removeFromFreed(availBlock);
 338                 used.not.if({ this.addToFreed(new) });
 339                 array[new.start] = new;
 340                 leftover.notNil.if({
 341                         array[leftover.start] = leftover;
 342                         top = max(top, leftover.start);
 343                         (top > leftover.start).if({ this.addToFreed(leftover); });
 344                 });
 345                 ^[new, leftover]
 346         }
 347
 348         debug { |text|
 349                 Post << text << ":\n\nArray:\n";
 350                 array.do({ |item, i|
 351                         item.notNil.if({ Post << i << ": " << item << "\n"; });
 352                 });
 353                 Post << "\nFree sets:\n";
 354                 freed.keysValuesDo({ |size, set|
 355                         Post << size << ": " <<< set << "\n";
 356                 });
 357         }
 358 }