Quadcap Embeddable Database

com/quadcap/util/collections/LongMap.java

Go to the documentation of this file.

package com.quadcap.util.collections;

/* Copyright 1999 - 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.util.Iterator;

import com.quadcap.util.Debug;

/**
 * A map with long values as keys
 *
 * @author Stan Bailes
 */
public class LongMap {
    int                         size    = 0;
    Entry[]                     entries;
    Entry                       freeList;

    /**
     * Create an empty map with a specified number of buckets.
     */
    public LongMap(int initSize) {
        initSize |= 1;
        while (!isPrime(initSize)) initSize += 2;
        entries = new Entry[initSize];
    }

    /**
     * Return the Object with the specified key value
     */
    public synchronized final Object get(long key) {
        int h = hash(key);
        for (Entry entry = entries[h]; entry != null; entry = entry.next) {
            if (entry.key == key) return entry.val;
        }
        return null;
    }

    /**
     * Insert a key, value pair
     */
    public synchronized final void put(long key, Object val) {
        int h = hash(key);
        for (Entry entry = entries[h]; entry != null; entry = entry.next) {
            if (entry.key == key) {
                entry.val = val;
                return;
            }
        }
        Entry entry = getEntry(key, val);
        entry.next = entries[h];
        entries[h] = entry;
    }

    /**
     * Remove the specified key
     */
    public synchronized final void remove(long key) {
        int h = hash(key);
        Entry prev = null;
        Entry entry = entries[h];
        while (entry != null) {
            Entry next = entry.next;
            if (entry.key == key) {
                if (prev == null) {
                    entries[h] = next;
                } else {
                    prev.next = next;
                }
                freeEntry(entry);
                return;
            }
            prev = entry;
            entry = next;
        }
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("{");
        LongIterator k = keys();
        String delim = "";
        while (k.hasNext()) {
            long v = k.nextLong();
            Object d = get(v);
            sb.append(delim);
            sb.append(v);
            sb.append('=');
            sb.append(String.valueOf(d));
            delim = ",";
        }
        sb.append("}");
        return sb.toString();
    }
            
            

    /**
     * Return the number of entries
     */
    public final int size() { return size; }

    public final int buckets() { return entries.length; }

    //-------------------------------------------------------
    final Entry getEntry(long key, Object val) {
        Entry entry = freeList;
        if (entry == null) {
            entry = new Entry();
        } else {
            freeList = entry.next;
        }
        entry.key = key;
        entry.val = val;
        size++;
        return entry;
    }

    final void freeEntry(Entry entry) {
        size--;
        entry.val = null;
        entry.next = freeList;
        freeList = entry;
    }

    final boolean isPrime(int x) {
        return IntMap.isPrime(x);
    }

    public LongIterator keys() {
        return new LongMapIterator(this);
    }

    final int hash(long key) {
        int h = (int)(key % entries.length);
        if (h < 0) {
            h = 0 - h;
        }
        return h;
    }

    class Entry {
        long            key;
        Object          val;
        Entry           next;
    }

    public class LongMapIterator implements LongIterator {
        LongMap                 map;
        int                     epos            = 0;
        Entry                   entry           = null;
        Entry                   last            = null;
        
        public LongMapIterator(LongMap map) {
            this.map = map;
            advance();
        }

        public boolean hasNext() {
            return entry != null;
        }

        void advance() {
            last = entry;
            if (entry != null && entry.next != null) {
                entry = entry.next;
            } else {
                entry = null;
            }
            while (epos < map.entries.length && entry == null) {
                entry = map.entries[epos++];
            }
        }
            
        public Object next() {
            Long ret = null;
            if (entry != null) {
                ret = new Long(entry.key);
                advance();
            }
            return ret;
        }

        public long nextLong() {
            long ret = 0;
            if (entry != null) {
                ret = entry.key;
                advance();
            }
            return ret;
        }

        public void remove() {
            if (last != null) {
                map.remove(last.key);
                last = null;
            }
        }
    }
}