lru.php

<?php

namespace Maxwell\Cache;

/**
 * Class PhpLruCache
 *
 * Inner node has following structure (it is stdClass)
 * until -> expiration time or null
 * key -> key
 * value -> value itself
 * prev -> previous node (reference)
 * next -> next node (reference)
 *
 * @package Maxwell\Cache
 */
class PhpLruCache implements CacheInterface, \Countable
{
    private $capacity;
    private $ttl;

    private $map = [];
    private $oldest = null;
    private $newest = null;

    /**
     * PhpLruCache constructor.
     *
     * @param int $capacity Expected maximum capacity
     * @param int $ttl Time to live in seconds, zero or negative value for infinity
     */
    public function __construct($capacity, $ttl)
    {
        if (!is_int($capacity) || $capacity < 1) {
            throw new \InvalidArgumentException('$capacity should be int and greater, than 0');
        }
        if (!is_int($ttl)) {
            throw new \InvalidArgumentException('$ttl must be integer');
        }

        $this->capacity = $capacity;
        $this->ttl = $ttl;
    }

    /**
     * Returns cache with requested parameters
     *
     * @param string $prefix
     * @param int $ttl Time in seconds
     * @return CacheInterface
     */
    public function getCache($prefix, $ttl)
    {
        return new self($this->capacity, $ttl);
    }

    /**
     * @inheritdoc
     */
    public function offsetExists($offset)
    {
        if (!array_key_exists($offset, $this->map)) {
            return false;
        }

        if ($this->ttl > 0 && $this->map[$offset]->until < time()) {
            // Value expired
            $this->offsetUnset($offset);
            return false;
        }

        return true;
    }

    /**
     * @inheritdoc
     */
    public function offsetGet($offset)
    {
        if (!$this->offsetExists($offset)) {
            return null;
        }

        $node = $this->map[$offset];
        if ($node !== $this->newest) {
            $this->placeNewestNode($node);
        }
        return $node->value;
    }

    /**
     * @inheritdoc
     */
    public function offsetSet($offset, $value)
    {
        // Removing old node, if it presents
        $this->offsetUnset($offset);

        // Building node
        $node = new \stdClass();
        $node->until = time() + $this->ttl;
        $node->key = $offset;
        $node->value = $value;
        $node->next = null;
        $node->prev = null;

        // Storing into map
        $this->map[$offset] = $node;

        // Adding to linked list
        $this->placeNewestNode($node);

        // Checking capacity
        if ($this->count() === $this->capacity + 1) {
            unset($this->map[$this->oldest->key]);
            $this->dropOldest();
        }
    }

    /**
     * @inheritdoc
     */
    public function offsetUnset($offset)
    {
        if (!isset($this->map[$offset])) {
            // Noting to delete
            return;
        }

        $node = $this->map[$offset];
        unset($this->map[$offset]);
        $this->cutNode($node);
    }

    /**
     * @inheritdoc
     */
    public function count()
    {
        return count($this->map);
    }

    /**
     * This method drops most oldest entry (MAP not changed)
     */
    private function dropOldest()
    {
        if ($this->oldest !== null) {
            if ($this->oldest->next === null) {
                $this->oldest = null;
                $this->newest = null;
            } else {
                $this->oldest->next->prev = null;
                $this->oldest = $this->oldest->next;
            }
        }
    }

    /**
     * This method places provided node to the beginning of the linked list
     *
     * @param \stdClass $node
     */
    private function placeNewestNode(\stdClass $node)
    {
        $this->cutNode($node);
        if ($this->oldest === null) {
            // Easy-peasy
            $this->oldest = $node;
            $this->newest = $node;
        } else {
            // Cross-linking
            $this->newest->next = $node;
            $node->prev = $this->newest;
            $this->newest = $node;
        }
    }

    /**
     * This methods cuts provided node from linked list
     *
     * @param \stdClass $node
     */
    private function cutNode(\stdClass $node)
    {
        if ($node->next !== null) {
            $node->next->prev = $node->prev;
        }
        if ($node->prev !== null) {
            $node->prev->next = $node->next;
        }
        if ($this->oldest === $node) {
            $this->oldest = $node->next;
        }
        if ($this->newest === $node) {
            $this->newest = $node->prev;
        }
        $node->next = null;
        $node->prev = null;
    }

    /**
     * Removes all entries from cache
     */
    public function flush()
    {
        $this->map = [];
        $this->newest = null;
        $this->oldest = null;
    }
}