# Buddy Memory Allocation

A regularly used method for allocating space within a fixed region is **Buddy Memory Allocation**.
This system works like a tree, where each branch either has a boolean value or branches to another set of the same.

8 | |||||||

4 | 4 | ||||||

2 | 2 | 2 | 2 | ||||

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

```
class BMA{
constructor(parent = null, size = 8){
this.parent = parent;
this.a = false;
this.b = false;
this.size = size;
}
get(start, end){}
set(start, end){}
merge(target){}
find(val, length){}
}
```

```
set(start, end){
val = (val == true);
let size = e - s;
//...
```

```
//...
//Fills sect A
if (s == 0 && e == this.size){
this.a = val;
// There is no reason for this branch to exist anymore
if (this.b == val && this.parent){
this.parent.merge(this);
}
//End execution since the desired section only fills this space.
return this;
}
//Fills sect B
if (s == this.size && e == this.size + this.size){
this.b = val;
if (this.a == val && this.parent){
this.parent.merge(this);
}
return this;
}
//...
```

```
//...
// Collides with sect A, and is changing a value
if (s < this.size && this.a != val){
if (!(this.a instanceof BMA)){
let was = this.a;
this.a = new BMA(this, this.size/2); // Create a new sub branch
this.a.a = this.a.b = was; // Apply the old value to the default value of the new branches
}
// Confine the range to fit within the sub-branch, and parse the value down the tree.
this.a.set(s, Math.min(this.size, e), val);
}
// Collides with sect B, and is chaning a value
if (e > this.size && this.b != val){
s -= this.size;
e -= this.size;
if (!(this.b instanceof BMA)){
let was = this.b;
this.b = new BMA(this, this.size/2);
this.b.a = this.b.b = was;
}
this.b.set(Math.max(0, s), e, val);
}
//...
```

```
//...
if (this.parent && this.a==this.b){
this.parent.merge(this);
}
return;
}
```

```
get (s, e){
// Only in sect A
if (s < this.size && e <= this.size){
// If a is another branch, then parse forward the request
if (this.a instanceof BMA){
return this.a.get(s, e);
}
// If a is true return 1, else return -1
return this.a ? 1 : -1;
}
// Only in sect B
if (s > this.size){
if (this.b instanceof BMA){
return this.b.get(
s-this.size, //Make the pointers relative
e-this.size
);
}
return this.b ? 1 : -1;
}
//...
```

```
//...
let a = null;
let b = null;
// If the request collides with branch A
if (s < this.size){
if (this.a instanceof BMA){
a = this.a.get(
s,
Math.min(this.size, e) // Ensure that the parsed end pointer isn't going out of the branch
);
}else{
a = this.a ? 1 : -1;
}
if (a === 0){
return 0;
}
}
// If the request collides with branch B
if (e > this.size){
if (this.b instanceof BMA){
b = this.b.get(s-this.size, e-this.size);
}else{
b = this.b ? 1 : -1;
}
if (b === 0){
return 0;
}
}
// If one of the branches's didn't actually collide with the request
if (a === null){
return b;
}
if (b === null){
return a;
}
if (a === b){
return a;
}else{
return 0;
}
}
```

```
hit (val, size){
// The request won't fit, at this depth, so there's no point
// Checking deeper branches since they will just have less
// space
if (this.size < size){
return NaN;
}
// If the request matches an available branch
if (this.a === val){
return {pos: 0, size: this.size}
}else if (this.b === val){
return {pos: this.size, size: this.size}
}
let a = NaN;
let b = NaN;
if (this.a instanceof BMA){
a = this.a.hit(val, size);
// Tight fit found
// There will be no better solutions, only equal best
if (a != NaN && a.size == size){
return a;
}
}
if (this.b instanceof BMA){
b = this.b.hit(val, size);
if (b != NaN && a.size == size){
return b;
}
}
// If an option is NaN, then return the other option
let na = isFinite(a) && isNaN(a);
let nb = isFinite(b) && isNaN(b);
if (na && nb){
return NaN;
}
if (!na && nb){
return a;
}
if (na && !nb){
return b;
}
// Both options a & b will work,
// Select which ever one is smallest,
// Prioritising a
if (a.size < b.size){
return a;
}
if (b.size > a.size){
b.pos += this.size; // Make the pos relative to this depth
return b;
}
if (a.size === b.size){
return a;
}
throw new Error()
}
```

```
class BMAX{
constructor(length){
this.root - new BMA();
this.length = this.root.size *2;
}
set (s, e, val){
return this.root.set(s,e,val);
}
get (s,e){
return this.root.get(s,e);
}
find(size, val){
return this.root.hit(val === true, size);
}
extend(amount = 1){
let ol = this.length;
if (amount < 1){
amount = 1;
}
// Make the current root into a branch of a new root
while(this.length - ol < amount){
let t = new BMA(undefined, this.length);
t.a = this.root;
t.a.parent = t;
this.root = t;
this.length = this.root.size*2;
}
}
}
```