ONJava.com -- The Independent Source for Enterprise Java
oreilly.comSafari Books Online.Conferences.

advertisement

AddThis Social Bookmark Button

The Hashbelt Data Structure
Pages: 1, 2, 3, 4, 5

AbstractHashbeltExpirationSystem and its Subclasses

The next set of classes we need to discuss are AbstractHashbeltExpirationSystem, StandardHashbeltExpirationSystem, and UpdatingHashbeltExpirationSystem. These are the core of the framework; they maintain the "conveyor belt" part of the system and delegate the application-specific behavior to strategy classes.



We'll start by looking at the code for AbstractHashbeltExpirationSystem:

  package grosso.expiration.hashbelt;
  import grosso.expiration.*;
  import grosso.expiration.hashbelt.handlers.*;

  import java.util.*;

  /*
    AbstractHashbeltExpirationSystem.

    Abstract superclass that handles most of the conveyor belt
    details. The subclasses (Standard and Updating) implement
    add and get functionality to specify whether "reiserting" is the
    right behavior.
  */

  public abstract class AbstractHashbeltExpirationSystem<K,V> extends AbstractExpirationSystem<K,V>{
    protected static final int DEFAULT_NUMBER_OF_CONTAINERS = 5;
    protected static final long ONE_MINUTE = 60 * 1000;
    protected static final long DEFAULT_ROTATION_TIME = ONE_MINUTE;

    protected int _numberOfContainers;
    protected HashbeltContainer<K,V> [] _containers;
    protected ExpirationHandler<K,V> _expirationHandler;

    protected abstract HashbeltContainer<K,V> getNewContainer();
    public abstract void put(K key, V expirableObject);
    public abstract V get(K key);

  
    public AbstractHashbeltExpirationSystem(){
      this (DEFAULT_NUMBER_OF_CONTAINERS, DEFAULT_ROTATION_TIME, new NullExpirationHandler<K,V>());
    }

    public AbstractHashbeltExpirationSystem (int numberOfContainers, long rotationTime) {
      this (numberOfContainers, rotationTime, new NullExpirationHandler<K,V>());
    }

    public AbstractHashbeltExpirationSystem(ExpirationHandler<K,V> expirationHandler){
      this (DEFAULT_NUMBER_OF_CONTAINERS, DEFAULT_ROTATION_TIME, expirationHandler);
    }

    public AbstractHashbeltExpirationSystem (int numberOfContainers, long rotationTime, ExpirationHandler<K,V> expirationHandler ) {
      super(rotationTime);
      _numberOfContainers  = numberOfContainers;
      _expirationHandler  = expirationHandler;
      _containers  = new HashbeltContainer<K,V>[_numberOfContainers];
      for (int i = 0; i < _numberOfContainers; i ++) {
        _containers[i] = getNewContainer();
      }
    }

    public void remove(K key) {
      HashbeltContainer<K,V> container = findContainer(key);
      if (null != container) {
        container.remove(key);
      }
    }

    public synchronized void clear() {
      for (int index = 0 ; index < _numberOfContainers; index++ ) {
        _containers[index].clear();
      }
    }

    protected void expireObjects() {
      HashbeltContainer<K,V> newContainer = getNewContainer();
      HashbeltContainer<K,V> expiredContainer = rotateContainers(newContainer);
      _expirationHandler.handleExpiredContainer(expiredContainer);
    }

    protected synchronized HashbeltContainer<K,V> findContainer (K key) {
      for (int index = 0; index < _numberOfContainers; index ++) {
        if (null != _containers[index].get(key)) {
          return _containers[index];
        }
      }
      return null;
    }

    protected synchronized V findObjectForKey (K key) {
      V returnValue;
      for (int index = 0; index < _numberOfContainers; index ++) {
        returnValue = _containers[index].get(key);
        if (null != returnValue) {
          return returnValue;
        }
      }
      return null;
    }


    private synchronized HashbeltContainer<K,V> rotateContainers (HashbeltContainer<K,V> newContainer) {
    /*
      This doesn't do a single, in-place, array copy because we can't guarantee
      how the JDK implements the array copy (e.g. whether it''ll do the inplace
      copy correctly). It's much safer to use a second array.
    */

      HashbeltContainer<K,V> returnValue = _containers[_numberOfContainers - 1];
      HashbeltContainer<K,V>[] newContainers = new HashbeltContainer<K,V>[_numberOfContainers];
      System.arraycopy(_containers, 0, newContainers, 1, _numberOfContainers -1);
      _containers = newContainers;
      _containers[0] = newContainer;
      return returnValue;
    }
  }

All of the functionality in an instance of AbstractHashbeltExpirationSystem centers around one of two operations: finding the right container or rotating the containers. For example, the implementation of remove consists of two calls. The first call, to findContainer, finds the container an object is in. The second call removes the object from the container. Rotating the containers is only slightly more difficult. When the background thread (inherited from AbstractExpirationSystem) calls expireObject, the hashbelt creates a new container, uses the new container to perform the rotation algorithm, and then uses an instance of ExpirationHandler to expire all of the objects in the container (if necessary; the default expiration handler, NullExpirationHandler does nothing).

AbstractHashbeltExpirationSystem defines three abstract methods: get, put and getNewContainer. getNewContainer is new, and won't be implemented in the framework at all (it's left up to the application programmer to decide which implementation of HashbeltContainer to use). get and put are left abstract in AbstractHashbeltExpirationSystem because they have two very different implementations. One simply leaves the object where it was found in the expiration system (this is the behavior implemented in StandardHashbeltExpirationSystem) and one removes the object from the expiration system and inserts it back into the front, into _containers[0]. (This is the behavior implemented in UpdatingHashbeltExpirationSystem.)

Here's the code for StandardHashbeltExpirationSystem and UpdatingHashbeltExpirationSystem:

  package grosso.expiration.hashbelt;
  import grosso.expiration.*;

  import java.util.*;

  /*
    StandardHashbeltExpirationSystem.

    The standard implementation of get and put does not insert
    objects at the front of the conveyor belt.
  */

  public abstract class StandardHashbeltExpirationSystem <K,V>extends AbstractHashbeltExpirationSystem<K,V>{
    public StandardHashbeltExpirationSystem(){
      super ();
    }

    public StandardHashbeltExpirationSystem (int numberOfContainers, long rotationTime) {
      super(numberOfContainers, rotationTime);
    }

    public StandardHashbeltExpirationSystem(ExpirationHandler<K,V> expirationHandler){
      super (expirationHandler);
    }

    public StandardHashbeltExpirationSystem (int numberOfContainers, long rotationTime, ExpirationHandler<K,V> expirationHandler) {
      super(numberOfContainers, rotationTime, expirationHandler);
    }

    public void put(K key, V expirableObject ) {
      HashbeltContainer<K,V> container = findContainer(key);
      if (null == container) {
        _containers[0].put(key, expirableObject);
      }
    }

    public V get(K key) {
      return findObjectForKey(key);
    }
  }


  package grosso.expiration.hashbelt;
  import grosso.expiration.*;

  /*
    UpdatingHashbeltExpirationSystem.

    A subclass of AbstractHashbeltExpirationSystem that moves requested
    elements back into the first container when a get or put occurs.
    Suitable for information that is expired when it is not used for a
    while (cached data, session keys, that sort of thing).
  */

  public abstract class UpdatingHashbeltExpirationSystem<K,V>extends AbstractHashbeltExpirationSystem<K,V> {
    public UpdatingHashbeltExpirationSystem() {
      super();
    }

    public UpdatingHashbeltExpirationSystem (int numberOfContainers, long rotationTime) {
      super(numberOfContainers, rotationTime);
    }

    public UpdatingHashbeltExpirationSystem(ExpirationHandler<K,V> handler) {
      super(handler);
    }

    public UpdatingHashbeltExpirationSystem (int numberOfContainers, long rotationTime, ExpirationHandler<K,V> expirationHandler ) {
      super(numberOfContainers, rotationTime, expirationHandler);
    }

    public void put(K key, V expirableObject) {
      HashbeltContainer<K,V> container = findContainer(key);
      if (null != container) {
        container.remove(key);
      }
      _containers[0].put(key, expirableObject);
    }

    public V get(K key) {
      HashbeltContainer<K,V> container = findContainer(key);
      if (null == container) {
        return null;
      }
      V returnValue = container.get(key);
      container.remove(key);
      _containers[0].put(key, returnValue);
      return returnValue;
    }
  }

Pages: 1, 2, 3, 4, 5

Next Pagearrow