Buddy Resource Allocation

I needed it for a private project and thought it might be helpful for someone else.
Ever had the problem of needing to share a limited resource between several program components?
As teached in operating systems course there is a method called “Buddy Memory Allocation” which is used to share the computer’s memory between the different applications running on the OS.
I have ported this to php, you can use it for any amount of resources and no matter what type.

<?php

/**
 * Each BuddyNode manages part of the resource.
 * And may even divide this part again.
 * Is used to build a binary tree.
 * @author Florian Schnell
 */
class BuddyNode
{
	public $start;
	public $exp;
	public $parent;
	public $free;
	public $amount;
	public $buddy_left;
	public $buddy_right;
}

/**
 * Manages resources of a limited amount.
 * Use the request method to receive a buddy node
 * matching the required value.
 * If resource is not needed anymore use free to
 * share with others again.
 * @author Florian Schnell
 */
class BuddyResourcesManager
{
	protected $total;
	protected $blocks;
	protected $root;

	function __construct($min, $max)
	{
		$this->total = abs($min) + $max;

		// create main buddy node
		$this->root = new BuddyNode();
		$this->root->start = 0;
		$this->root->parent = null;
		$this->root->free = true;
		$this->root->amount = $this->total;
		$this->root->buddy_left = null;
		$this->root->buddy_right = null;

		// init buddy list ...
		$this->lists[1] = array($this->root);
	}

	/**
	 * Retrieves the specified amount of resources.
	 * @param integer $amount
	 * @return BuddyNode
	 */
	function request($amount)
	{
		$exp_fit = floor(log($this->total / $amount, 2));

		// try to get an available block in right size ...
		$exp = $exp_fit;
		while (!isset($this->lists[$exp]))
			$exp--;

		$free = false;
		do
		{
			if ($exp < 1) // no resources available!
				return false;

			// check if there's a free buddy on this level ...
			foreach ($this->lists[$exp] as $buddy)
			{
				if ($buddy->free)
				{
					$free = $buddy;
					if ($exp == $exp_fit){
						$free->free = false;
						return $free;
					}
					break;
				}
			}

			// try next level ...
			$exp--;

		} while (!$free);

		// break blocks apart until they have the right size ...
		while ($exp_fit > $exp)
		{
			$this->splitBuddyNode($free);
			$free = $free->buddy_left;
			$exp++;
		}

		$free->free = false;
		return $free;
	}

	/**
	 * This method deallocates the retrieved part of
	 * the resource so that others can access it again.
	 * @param BuddyNode $buddy
	 */
	function free(BuddyNode $buddy)
	{
		$buddy->free = true;

		do
		{
			$buddy = $buddy->parent;
			if ($buddy->buddy_left->free
				&& $buddy->buddy_right->free)
			{
				$buddy->buddy_left->parent = null;
				$buddy->buddy_right->parent = null;
				$buddy->buddy_left = null;
				$buddy->buddy_right = null;
				$buddy->free = true;
			}
		} while ($buddy->parent && $buddy->free);
	}

	/**
	 * Take one BuddyNode that is a leaf and split it
	 * into a left and a right node.
	 * @param BuddyNode $parent
	 */
	protected function splitBuddyNode(BuddyNode $parent)
	{
		// only if this node is not in use
		if (!$parent->free)
			return;

		// can't split already split nodes
		if ($parent->buddy_left != null
			&& $parent->buddy_right != null)
			return;

		$subsize = $parent->amount / 2;
		$parent->free = false;

		// build left leaf
		$buddy = new BuddyNode();
		$buddy->exp = $parent->exp+1;
		$buddy->parent = $parent;
		$buddy->amount = $subsize;
		$buddy->free = true;
		$buddy->start = $parent->start;
		$parent->buddy_left = $buddy;
		$this->lists[$buddy->exp][] = $buddy;

		// build right leaf
		$buddy = new BuddyNode();
		$buddy->exp = $parent->exp+1;
		$buddy->parent = $parent;
		$buddy->amount = $subsize;
		$buddy->free = true;
		$buddy->start = $parent->start
			+ $parent->buddy_left->amount;
		$parent->buddy_right = $buddy;
		$this->lists[$buddy->exp][] = $buddy;
	}
}

?>

First create a new object of type BuddyResourcesManager, you need to give a min and a max value. Normally you would set min to zero and set the max value to the available amount of the resource. After that you can the object’s methods request and free to simply get more resources if needed or return any if not anymore.
Hope it helps, cheers.