package org.apache.fop.fo.properties;

import java.lang.ref.WeakReference;

/**
 *  Dedicated cache, meant for storing canonical 
 *  <code>org.apache.fop.fo.properties.Property</code> instances.
 *  
 */
public final class PropertyCache {

    /** the segments array */
    private CacheSegment[] segments = new CacheSegment[8];
    /** the entry table */
    private CachedEntry[] table = new CachedEntry[8];
    
    /* same hash function as used by java.util.HashMap */
    static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^= (h >>> 14);
        h += (h << 4);
        h ^= (h >>> 10);
        return h;
    }
    
    /* shortcut function */
    static boolean eq(Property p, Property q) {
        return (p == q || (p != null && p.equals(q)));
    }
    
    /*
     * Class modeling a cached entry.
     */
    private final class CachedEntry {
        private final CachedEntry next;
        private volatile WeakReference p;
        private final int hash;
        
        /* main constructor */
        CachedEntry(Property p, CachedEntry next) {
            this.next = next;
            this.p = new WeakReference(p);
            this.hash = p.hashCode();
        }
        
        /* clone constructor */
        CachedEntry(CachedEntry old, CachedEntry next) {
            this.next = next;
            this.p = old.p;
            this.hash = old.hash;
        }
        
    }
    
    /*
     * Wrapper objects to synchronize on.
     */
    private final class CacheSegment {
        private int count = 0;
    }
    
    /*
     * Class modeling a cleanup thread.
     * Once run() is called, the locked segment will be 
     * traversed, removing any obsolete entries.
     */
    private final class CacheCleaner implements Runnable {
        
        private int segment;
        
        CacheCleaner(int segment) {
            this.segment = segment;
        }
        
        public void run() {
            //System.out.println("Cleaning segment " + this.segment);
            CacheSegment segment = segments[this.segment];
            synchronized (segment) {
                /* check first to see if another cleaner thread already
                 * pushed the number of entries back below the threshold
                 */
                if (segment.count < (2 * segments.length)) {
                    return;
                }
                
                CachedEntry first = table[this.segment];
                int oldCount = segment.count;
                for (CachedEntry e = first; e != null; e = e.next) {
                    WeakReference ref = e.p;
                    if (ref != null && ref.get() == null) {
                        /* remove obsolete entry
                        /* 1. clear value, cause interference for non-blocking get() */
                        e.p = null;
                        
                        /* 2. clone the segment, without the obsolete entry */
                        CachedEntry head = e.next;
                        for (CachedEntry c = first; c != e; c = c.next) {
                            head = new CachedEntry(c, head);
                        }
                        table[this.segment] = head;
                        segment.count--;
                    }
                }
                if (oldCount == segment.count) {
                    /* cleanup had no effect, try rehashing */
                    rehash();
                }
            }
        }
    }
    
    /*
     * Puts a new Property in the cache.
     */
    private final void put(Property p) {
        
        int hash = hash(p) & (segments.length - 1);
        CacheSegment segment = segments[hash];
        
        synchronized (segment) {
            CachedEntry entry = table[hash];
            
            if (entry == null) {
                entry = new CachedEntry(p, null);
                table[hash] = entry;
                segment.count++;
            } else {
                WeakReference ref = entry.p;
                if (ref != null && eq((Property) ref.get(), p)) {
                    return;
                } else {
                    CachedEntry newEntry = new CachedEntry(p, entry);
                    table[hash] = newEntry;
                    segment.count++;
                }
            }
            
            if (segment.count > (2 * segments.length)) {
                /* launch cleanup thread */
                Thread cleaner = new Thread(new CacheCleaner(hash));
                cleaner.start();
            }
        }
    }
    

    /*
     * Gets a cached instance. Returns null if not found.
     */
    private final Property get(Property p) {
        
        int hash = hash(p) & (segments.length - 1);
        
        CachedEntry entry = table[hash];
        WeakReference r;
        Property q;
        
        /* try non-synched first */
        for (CachedEntry e = entry; e != null; e = e.next) {
            if (e.hash == p.hashCode()
                    && (r = e.p) != null
                    && (q = (Property) r.get()) != null
                    &&  eq(q, p)) {
                /* force re-check */
                if (e.p != null) {
                    /* ok, safe to return the cached instance */
                    return q;
                } else {
                    /* removed by CacheCleaner? */
                    break;
                }
            }
        }
        
        /* retry synched, only if the above attempt did not succeed */
        CacheSegment segment = segments[hash];
        synchronized (segment) {
            for (CachedEntry e = entry; e != null; e = e.next) {
                if (e.hash == p.hashCode()
                        && (r = e.p) != null
                        && (q = (Property) r.get()) != null
                        &&  eq(q, p)) {
                    return q;
                }
            }
        }
        return null;
    }
    
    /*
     * Performs a check on the segments first to see how many precisely exceed
     * the threshold ( 2 x segments.length ). 
     * If this number exceeds half the amount of segments, extends the cache 
     * and redistributes the entries
     */
    private void rehash() {
        
        /* double the amount of buckets */
        int newLength = segments.length << 1;
        if (newLength > 0) {
            /* lock and redistribute */
            synchronized (this) {
                
                /* Check segmentcounts first */
                int countSegments = 0;
                int threshold = segments.length * 2;
                for (int i = segments.length; --i >= 0;) {
                    if (segments[i].count > threshold) {
                        countSegments++;
                    }
                }
                
                if (countSegments <= (segments.length / 2)) {
                    return;
                }
                
                //System.out.println("Re-hashing...");
                CacheSegment[] newSegments = new CacheSegment[newLength];
                CachedEntry[] newTable = new CachedEntry[newLength];
                
                int hash;
                WeakReference ref;
                Property p;
                newLength--;
                for (int i = newTable.length; --i >= 0;) {
                    newSegments[i] = new CacheSegment();
                }
                
                for (int i = table.length; --i >= 0;) {
                    for (CachedEntry c = table[i]; c != null; c = c.next) {
                        ref = c.p;
                        if ((p = (Property) ref.get()) != null) {
                            hash = hash(p) & newLength;
                            newTable[hash] = new CachedEntry(c, newTable[hash]);
                            newSegments[hash].count++;
                        }
                    }
                }
                segments = newSegments;
                table = newTable;
            }
        }
    }
    
    /**
     * Default constructor. 
     */
    public PropertyCache() {
        for (int i = 8; --i >= 0;) {
            segments[i] = new CacheSegment();
        }
    }
    
    /**
     *  Checks if the given <code>Property</code> is present in the cache - 
     *  if so, returns a reference to the cached instance. 
     *  Otherwise the given object is added to the cache and returned.
     *  
     *  @param prop the Property instance to check for
     *  @return the cached instance
     */
    public Property fetch(Property prop) {
        
        if (prop == null) {
            return null;
        }

        Property cacheEntry = get(prop);
        if (cacheEntry != null) {
            return cacheEntry;                
        }
        put(prop);
        return prop;
    }
    
}