Quadcap Embeddable Server

com/quadcap/util/collections/Cache.java

Go to the documentation of this file.

package com.quadcap.util.collections;

/* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.io.IOException;
import java.io.PrintWriter;

import java.util.Enumeration;
import java.util.Hashtable;

import com.quadcap.util.Debug;
import com.quadcap.util.DList;
import com.quadcap.util.DListItem;
import com.quadcap.util.ListException;

/**
 * This class manages a number of buffers on an underlying store.
 * <p>
 *
 * What about write-through policies?
 *
 * @author Stan Bailes
 */
public abstract class Cache {
    Object                      store;
    Object                      lock;
    int                         size;

    Hashtable                   t;
    DList                       lru = new DList();

    /**
     * Initialize the cache.
     *
     * @param s the underlying store
     * @param size the size of the cache
     */
    public void init(Object store, int size) {
        this.store = store;
        this.size = size;
        this.lock = this;
        lru.resize(size);
        t = new Hashtable();
    }

    /**
     * Specify the lock-object to be used to synchronize access to the
     * cache.  If the lock isn't specified, it defaults to the cache
     * object itself.
     *
     * @param lock the lock object
     */
    public void setLock(Object lock) {
        this.lock = lock;
    }

    /**
     * Search the cache for the specified key and return the associated
     * cache item if one was found.  Otherwise, find a free cache item
     * and initialize it from the underlying store.
     *
     * @param key the search key
     * @return the cache item associated with the specified key.
     */
    public Cacheable getCacheable(Object key) throws IOException {
        //Debug.println("getCacheable(" + key + ")");
        synchronized (lock) {
            // ---- check the cache first.
            Cacheable c = (Cacheable)t.get(key);
            if (c == null) {
                // ---- if not in the cache, find a free cache slot and
                // ----   fill it with this object.
                c = getCacheable();
                c.init(store, key);
                t.put(key, c);
            }

            // ---- move this object to the front of the LRU list.
            try {
                lru.moveFront(c.getDListItem());
            } catch (ListException e) {
                Debug.print(e);
            }
            c.incrRefCount();
            //checkCache();
            return c;
        }
    }

    void checkCache() {
        synchronized (lock) {
            Hashtable s = new Hashtable();
            // check that each item in the lru is in the hashtable
            try {
                boolean started = false;
                for (DListItem d = lru.head(); !started || d != lru.head();
                     d = d.next) {
                    started = true;
                    Cacheable c = (Cacheable)d.obj;
                    if (c == null) continue;
                    Object key = c.getKey();
                    Cacheable c1 = (Cacheable)t.get(key);
                    if (c1 != c) {
                        System.out.println("lru item not in hashtable: " +
                                           key);
                    }
                    s.put(key, c);
                }
            } catch (ListException e) {
                Debug.print(e);
            }
        
            // check that each item in the hashtable is actually in the lru
            for (Enumeration e = t.keys(); e.hasMoreElements(); ) {
                Object key = e.nextElement();
                if (s.get(key) == null) {
                    System.out.println("hashtable item not in lru: " + key);
                }
            }
        }
    }

    /**
     * Get the specified object from the cache, if available; from the
     * underlying store if not.  In any case, the object (if found)
     * should be in the cache after this call.<p>
     *
     * If the object isn't in the cache <b>OR</b> the underlying store,
     * this method should return null, and the contents of both the cache
     * and the underlying store should remain unchanged.<p>
     *
     * <b>This implementation doesn't change the underlying store, but
     * the cache ends up holding a CacheItem with a null data component.</b>
     * @param key the search key
     * @param return the data associated with the key
     */
    public Object get(Object key) throws IOException {
        Object data = null;
        synchronized (lock) {
            Cacheable c = getCacheable(key);
            try {
                data = c.getData();
            } finally {
                c.decrRefCount();
            }
        }
        return data;
    }

    /**
     * Store the object in the cache.  The object will be marked <i>dirty</i>,
     * and will eventually be written back to the underlying store.
     */
    public void put(Object key, Object val) throws IOException {
        synchronized (lock) {
            Cacheable c = getCacheable(key);
            try {
                c.setData(val);
            } finally {
                c.decrRefCount();
            }
        }
    }

    /**
     * Factory to create an empty cache slot.  Only a fixed number of
     * cache slots should be created, and they should then be recycled,
     * never destroyed.
     */
    abstract public Cacheable makeCacheable();

    /**
     * Find a free cache slot.  If necessary, seize an existing cache
     * slot, with preference for the "least recently used" item.
     * This function should only be called if the lock on the cache is
     * held by this thread.
     */
    Cacheable getCacheable() throws IOException {
        Cacheable c = null;
        DListItem d = lru.tail();
            
        while (d != null) {
            c = (Cacheable)d.obj;               
            if (c != null && c.getRefCount() > 0) {
                if (d == lru.head()) {
                    show(new PrintWriter(Debug.debugStream));
                    throw new RuntimeException("no free cache item");
                }
                d = d.prev;
            } else {
                break;  // 'c' contains the Cacheable we're looking for
            }
        }

        if (c == null) {
            d.obj = c = makeCacheable();
            c.setDListItem(d);
        } else {
            Object key = c.getKey();
            if (key != null) {
                //Debug.println("Cache: remove(" + key + ")");
                t.remove(key);
            }
            if (c.isDirty()) c.flush();
        }
        return c;
    }

    /**
     * Flush all modified items back to the underlying store.
     */
    public void flush() throws IOException {
        synchronized (lock) {
            boolean started = false;
            for (DListItem d = lru.head(); !started || d != lru.head();
                 d = d.next) {
                started = true;
                Cacheable c = (Cacheable)d.obj;
                if (c != null) {
                    // XXX I'm not sure I should be synchronizing on this
                    // XXX abstract object here.  Maybe let the implementing
                    // XXX class take care of it's own mutual exclusion.
                    // synchronized (c)
                    c.flush();
                }
            }
        }
    }

    public void show(PrintWriter os) {
        synchronized (lock) {
            lru.show(os, "\n");
        }
    }
}