dart/editor/attic/plugins/com.google.dart.indexer/src/com/google/dart/indexer/pagedstorage/util/CacheLRU.java - external/dart - Git at Google

 /*
  * Copyright (c) 2011, the Dart project authors.
  *
  * Licensed under the Eclipse Public License v1.0 (the "License"); you may not use this file except
  * in compliance with the License. You may obtain a copy of the License at
  *
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Unless required by applicable law or agreed to in writing, software distributed under the License
  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.dart.indexer.pagedstorage.util;

 import com.google.dart.indexer.IndexerPlugin;
 import com.google.dart.indexer.debug.IndexerDebugOptions;
 import com.google.dart.indexer.pagedstorage.DebugConstants;
 import com.google.dart.indexer.pagedstorage.exceptions.PagedStorageException;
 import com.google.dart.indexer.storage.paged.store.CacheObject;
 import com.google.dart.indexer.storage.paged.store.CacheWriter;

 /**
  * A cache implementation based on the last recently used (LRU) algorithm.
  */
 public class CacheLRU implements Cache {
   static final String TYPE_NAME = "LRU";

   private final CacheWriter writer;
   private final CacheObject head = new CacheHead();
   private final int len;
   private final int mask;
   private int maxSize;
   private CacheObject[] values;
   private int recordCount;
   private int sizeMemory;

   private CacheLRU(CacheWriter writer, int maxKb) {
     this.maxSize = maxKb * 1024 / 4;
     this.writer = writer;
     this.len = MathUtils.nextPowerOf2(maxSize / 64);
     this.mask = len - 1;
     MathUtils.checkPowerOf2(len);
     clear();
   }

   @Override
   public void clear() {
     head.next = head.previous = head;
     // first set to null - avoiding out of memory
     values = null;
     values = new CacheObject[len];
     recordCount = 0;
     sizeMemory = 0;
   }

   @Override
   public CacheObject find(int pos) {
     CacheObject rec = values[pos & mask];
     while (rec != null && rec.getPos() != pos) {
       rec = rec.chained;
     }
     return rec;
   }

   @Override
   public CacheObject get(int pos) {
     CacheObject rec = find(pos);
     if (rec != null) {
       removeFromLinkedList(rec);
       addToFront(rec);
     }
     return rec;
   }

   @Override
   public ObjectArray<CacheObject> getAllChanged() {
     // TODO cache: should probably use the LRU list
     ObjectArray<CacheObject> list = ObjectArray.newInstance();
     for (int i = 0; i < len; i++) {
       CacheObject rec = values[i];
       while (rec != null) {
         if (rec.isChanged()) {
           list.add(rec);
           if (list.size() >= recordCount) {
             if (DebugConstants.CHECK) {
               if (list.size() > recordCount) {
                 throw new AssertionError("cache chain error");
               }
             } else {
               break;
             }
           }
         }
         rec = rec.chained;
       }
     }
     return list;
   }

   @Override
   public int getMaxSize() {
     return maxSize;
   }

   @Override
   public int getSize() {
     return sizeMemory;
   }

   @Override
   public String getTypeName() {
     return TYPE_NAME;
   }

   @Override
   public void put(CacheObject rec) throws PagedStorageException {
     if (DebugConstants.CHECK) {
       // int pos = rec.getPos();
       // for (int i = 0; i < rec.getBlockCount(); i++) {
       // CacheObject old = find(pos + i);
       // if (old != null) {
       // Message.throwInternalError("try to add a record twice pos:" + pos +
       // " i:" + i);
       // }
       // }
     }
     int index = rec.getPos() & mask;
     rec.chained = values[index];
     values[index] = rec;
     recordCount++;
     sizeMemory += rec.getMemorySize();
     addToFront(rec);
     removeOldIfRequired();
   }

   @Override
   public void remove(int pos) {
     int index = pos & mask;
     CacheObject rec = values[index];
     if (rec == null) {
       return;
     }
     if (rec.getPos() == pos) {
       values[index] = rec.chained;
     } else {
       CacheObject last;
       do {
         last = rec;
         rec = rec.chained;
         if (rec == null) {
           return;
         }
       } while (rec.getPos() != pos);
       last.chained = rec.chained;
     }
     recordCount--;
     sizeMemory -= rec.getMemorySize();
     removeFromLinkedList(rec);
     if (DebugConstants.CHECK) {
       rec.chained = null;
       if (find(pos) != null) {
         throw new AssertionError("not removed!");
       }
     }
   }

   @Override
   public void setMaxSize(int maxKb) throws PagedStorageException {
     int newSize = maxKb * 1024 / 4;
     maxSize = newSize < 0 ? 0 : newSize;
     // can not resize, otherwise existing records are lost
     // resize(maxSize);
     removeOldIfRequired();
   }

   @Override
   public CacheObject update(int pos, CacheObject rec) throws PagedStorageException {
     CacheObject old = find(pos);
     if (old == null) {
       put(rec);
     } else {
       if (DebugConstants.CHECK) {
         if (old != rec) {
           throw new IllegalArgumentException(
               "Attemp to write conflicting records into cache - pos:" + pos + " old:" + old
                   + " new:" + rec);
         }
       }
       removeFromLinkedList(rec);
       addToFront(rec);
     }
     return old;
   }

   private void addToFront(CacheObject rec) {
     if (DebugConstants.CHECK && rec == head) {
       throw new IllegalArgumentException("try to move head");
     }
     rec.next = head;
     rec.previous = head.previous;
     rec.previous.next = rec;
     head.previous = rec;
   }

   private void removeFromLinkedList(CacheObject rec) {
     if (DebugConstants.CHECK && rec == head) {
       throw new IllegalArgumentException("try to remove head");
     }
     rec.previous.next = rec.next;
     rec.next.previous = rec.previous;
     // TODO cache: mystery: why is this required? needs more memory if we
     // don't do this
     rec.next = null;
     rec.previous = null;
   }

   private void removeOld() throws PagedStorageException {
     int i = 0;
     ObjectArray<CacheObject> changed = ObjectArray.newInstance();
     while (sizeMemory * 4 > maxSize * 3 && recordCount > Constants.CACHE_MIN_RECORDS) {
       i++;
       if (i >= recordCount * 2) {
         // hopefully this does not happen too much, but it could happen
         // theoretically
         IndexerPlugin.getLogger().trace(IndexerDebugOptions.RARE_ANOMALIES,
             "Cannot remove records, cache size too small?");
         break;
       }
       CacheObject last = head.next;
       if (DebugConstants.CHECK && last == head) {
         throw new AssertionError("try to remove head");
       }
       // we are not allowed to remove it if the log is not yet written
       // (because we need to log before writing the data)
       // also, can't write it if the record is pinned
       if (!last.canRemove()) {
         removeFromLinkedList(last);
         addToFront(last);
         continue;
       }
       remove(last.getPos());
       if (last.isChanged()) {
         changed.add(last);
       }
     }
     if (changed.size() > 0) {
       CacheObject.sort(changed);
       for (i = 0; i < changed.size(); i++) {
         CacheObject rec = changed.get(i);
         writer.writeBack(rec);
       }
     }
   }

   private void removeOldIfRequired() throws PagedStorageException {
     // a small method, to allow inlining
     if (sizeMemory >= maxSize) {
       removeOld();
     }
   }
 }
	/*
	* Copyright (c) 2011, the Dart project authors.
	*
	* Licensed under the Eclipse Public License v1.0 (the "License"); you may not use this file except
	* in compliance with the License. You may obtain a copy of the License at
	*
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Unless required by applicable law or agreed to in writing, software distributed under the License
	* is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
	* or implied. See the License for the specific language governing permissions and limitations under
	* the License.
	*/
	package com.google.dart.indexer.pagedstorage.util;

	import com.google.dart.indexer.IndexerPlugin;
	import com.google.dart.indexer.debug.IndexerDebugOptions;
	import com.google.dart.indexer.pagedstorage.DebugConstants;
	import com.google.dart.indexer.pagedstorage.exceptions.PagedStorageException;
	import com.google.dart.indexer.storage.paged.store.CacheObject;
	import com.google.dart.indexer.storage.paged.store.CacheWriter;

	/**
	* A cache implementation based on the last recently used (LRU) algorithm.
	*/
	public class CacheLRU implements Cache {
	static final String TYPE_NAME = "LRU";

	private final CacheWriter writer;
	private final CacheObject head = new CacheHead();
	private final int len;
	private final int mask;
	private int maxSize;
	private CacheObject[] values;
	private int recordCount;
	private int sizeMemory;

	private CacheLRU(CacheWriter writer, int maxKb) {
	this.maxSize = maxKb * 1024 / 4;
	this.writer = writer;
	this.len = MathUtils.nextPowerOf2(maxSize / 64);
	this.mask = len - 1;
	MathUtils.checkPowerOf2(len);
	clear();
	}

	@Override
	public void clear() {
	head.next = head.previous = head;
	// first set to null - avoiding out of memory
	values = null;
	values = new CacheObject[len];
	recordCount = 0;
	sizeMemory = 0;
	}

	@Override
	public CacheObject find(int pos) {
	CacheObject rec = values[pos & mask];
	while (rec != null && rec.getPos() != pos) {
	rec = rec.chained;
	}
	return rec;
	}

	@Override
	public CacheObject get(int pos) {
	CacheObject rec = find(pos);
	if (rec != null) {
	removeFromLinkedList(rec);
	addToFront(rec);
	}
	return rec;
	}

	@Override
	public ObjectArray<CacheObject> getAllChanged() {
	// TODO cache: should probably use the LRU list
	ObjectArray<CacheObject> list = ObjectArray.newInstance();
	for (int i = 0; i < len; i++) {
	CacheObject rec = values[i];
	while (rec != null) {
	if (rec.isChanged()) {
	list.add(rec);
	if (list.size() >= recordCount) {
	if (DebugConstants.CHECK) {
	if (list.size() > recordCount) {
	throw new AssertionError("cache chain error");
	}
	} else {
	break;
	}
	}
	}
	rec = rec.chained;
	}
	}
	return list;
	}

	@Override
	public int getMaxSize() {
	return maxSize;
	}

	@Override
	public int getSize() {
	return sizeMemory;
	}

	@Override
	public String getTypeName() {
	return TYPE_NAME;
	}

	@Override
	public void put(CacheObject rec) throws PagedStorageException {
	if (DebugConstants.CHECK) {
	// int pos = rec.getPos();
	// for (int i = 0; i < rec.getBlockCount(); i++) {
	// CacheObject old = find(pos + i);
	// if (old != null) {
	// Message.throwInternalError("try to add a record twice pos:" + pos +
	// " i:" + i);
	// }
	// }
	}
	int index = rec.getPos() & mask;
	rec.chained = values[index];
	values[index] = rec;
	recordCount++;
	sizeMemory += rec.getMemorySize();
	addToFront(rec);
	removeOldIfRequired();
	}

	@Override
	public void remove(int pos) {
	int index = pos & mask;
	CacheObject rec = values[index];
	if (rec == null) {
	return;
	}
	if (rec.getPos() == pos) {
	values[index] = rec.chained;
	} else {
	CacheObject last;
	do {
	last = rec;
	rec = rec.chained;
	if (rec == null) {
	return;
	}
	} while (rec.getPos() != pos);
	last.chained = rec.chained;
	}
	recordCount--;
	sizeMemory -= rec.getMemorySize();
	removeFromLinkedList(rec);
	if (DebugConstants.CHECK) {
	rec.chained = null;
	if (find(pos) != null) {
	throw new AssertionError("not removed!");
	}
	}
	}

	@Override
	public void setMaxSize(int maxKb) throws PagedStorageException {
	int newSize = maxKb * 1024 / 4;
	maxSize = newSize < 0 ? 0 : newSize;
	// can not resize, otherwise existing records are lost
	// resize(maxSize);
	removeOldIfRequired();
	}

	@Override
	public CacheObject update(int pos, CacheObject rec) throws PagedStorageException {
	CacheObject old = find(pos);
	if (old == null) {
	put(rec);
	} else {
	if (DebugConstants.CHECK) {
	if (old != rec) {
	throw new IllegalArgumentException(
	"Attemp to write conflicting records into cache - pos:" + pos + " old:" + old
	+ " new:" + rec);
	}
	}
	removeFromLinkedList(rec);
	addToFront(rec);
	}
	return old;
	}

	private void addToFront(CacheObject rec) {
	if (DebugConstants.CHECK && rec == head) {
	throw new IllegalArgumentException("try to move head");
	}
	rec.next = head;
	rec.previous = head.previous;
	rec.previous.next = rec;
	head.previous = rec;
	}

	private void removeFromLinkedList(CacheObject rec) {
	if (DebugConstants.CHECK && rec == head) {
	throw new IllegalArgumentException("try to remove head");
	}
	rec.previous.next = rec.next;
	rec.next.previous = rec.previous;
	// TODO cache: mystery: why is this required? needs more memory if we
	// don't do this
	rec.next = null;
	rec.previous = null;
	}

	private void removeOld() throws PagedStorageException {
	int i = 0;
	ObjectArray<CacheObject> changed = ObjectArray.newInstance();
	while (sizeMemory * 4 > maxSize * 3 && recordCount > Constants.CACHE_MIN_RECORDS) {
	i++;
	if (i >= recordCount * 2) {
	// hopefully this does not happen too much, but it could happen
	// theoretically
	IndexerPlugin.getLogger().trace(IndexerDebugOptions.RARE_ANOMALIES,
	"Cannot remove records, cache size too small?");
	break;
	}
	CacheObject last = head.next;
	if (DebugConstants.CHECK && last == head) {
	throw new AssertionError("try to remove head");
	}
	// we are not allowed to remove it if the log is not yet written
	// (because we need to log before writing the data)
	// also, can't write it if the record is pinned
	if (!last.canRemove()) {
	removeFromLinkedList(last);
	addToFront(last);
	continue;
	}
	remove(last.getPos());
	if (last.isChanged()) {
	changed.add(last);
	}
	}
	if (changed.size() > 0) {
	CacheObject.sort(changed);
	for (i = 0; i < changed.size(); i++) {
	CacheObject rec = changed.get(i);
	writer.writeBack(rec);
	}
	}
	}

	private void removeOldIfRequired() throws PagedStorageException {
	// a small method, to allow inlining
	if (sizeMemory >= maxSize) {
	removeOld();
	}
	}
	}