/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.allocator;

import java.lang.ref.*;
import java.util.*;

import edu.emory.mathcs.backport.java.util.concurrent.*;
import edu.emory.mathcs.backport.java.util.Queue;

/**
 * Memory pool used by {@link PoolingAllocator}.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */

class BufferPool {
    private final Queue[] pool;

    public BufferPool() {
        pool = new Queue[27];
        for (int i=0; i<pool.length; i++) {
            /** @todo try various queue implementations */
            pool[i] = new LinkedBlockingQueue();
        }
    }

    public byte[] get(int desiredsize, boolean clear) {
        int idx = getSlot(desiredsize);

        byte[] data;

        // try to find buf in the queue (optimistic - no locking)
        if ((data = getFromQueue(pool[idx])) != null) {
            if (clear) Arrays.fill(data, 0, desiredsize, (byte)0);
            return data;
        }

        if (idx<26) {
            // try also the next queue (with buffers 2x size)
            if ((data = getFromQueue(pool[idx+1])) != null) {
                if (clear) Arrays.fill(data, 0, desiredsize, (byte)0);
                return data;
            }
        }

        // not found, allocate new
        return new byte[16 << idx];
    }

    private byte[] getFromQueue(Queue q) {
        byte[] data;
        Reference ref;
        while (true) {
            // get subsequent buffers until end or not-null found
            // (references are weak so buffers can possibly be null)
            ref = (Reference)q.poll();
            if (ref == null) {
                // no more items in this queue
                return null;
            }
            data = (byte[])ref.get();
            if (data != null) {
                // found!
                return data;
            }
        }
    }

    public void reclaim(byte[] data) {
        int idx = getSlot(data.length);
        pool[idx].offer(new WeakReference(data));
    }

    private static int getSlot(int num) {
        if (num < 0) throw new IllegalArgumentException();
        if (num <= 16) return 0;
        return (log(num-1)+1)-4;
    }
//
//    private static int getSizeForSlot(int num) {
//        return 16 << num;
//    }

    public static int log(int n) {
        int result = 0;
        if (n < 0) throw new IllegalArgumentException();
        for (; n > 0; n >>= 1) result++;
        return result;
    }

    public static int nextPowerOfTwo(int n) {
        return 1 << (log(n-1)+1);
    }
}
