001: /*
002: *******************************************************************************
003: * Copyright (C) 1996-2004, International Business Machines Corporation and *
004: * others. All Rights Reserved. *
005: *******************************************************************************
006: */
007: package com.ibm.icu.impl;
008:
009: /**
010: * @internal
011: */
012: public class CalendarCache {
013: /**
014: * @internal
015: */
016: public CalendarCache() {
017: makeArrays(arraySize);
018: }
019:
020: private void makeArrays(int newSize) {
021: keys = new long[newSize];
022: values = new long[newSize];
023:
024: for (int i = 0; i < newSize; i++) {
025: values[i] = EMPTY;
026: }
027: arraySize = newSize;
028: threshold = (int) (arraySize * 0.75);
029: size = 0;
030: }
031:
032: /**
033: * @internal
034: */
035: public synchronized long get(long key) {
036: return values[findIndex(key)];
037: }
038:
039: /**
040: * @internal
041: */
042: public synchronized void put(long key, long value) {
043: if (size >= threshold) {
044: rehash();
045: }
046: int index = findIndex(key);
047:
048: keys[index] = key;
049: values[index] = value;
050: size++;
051: }
052:
053: private final int findIndex(long key) {
054: int index = hash(key);
055: int delta = 0;
056:
057: while (values[index] != EMPTY && keys[index] != key) {
058: if (delta == 0) {
059: delta = hash2(key);
060: }
061: index = (index + delta) % arraySize;
062: }
063: return index;
064: }
065:
066: private void rehash() {
067: int oldSize = arraySize;
068: long[] oldKeys = keys;
069: long[] oldValues = values;
070:
071: if (pIndex < primes.length - 1) {
072: arraySize = primes[++pIndex];
073: } else {
074: arraySize = arraySize * 2 + 1;
075: }
076: size = 0;
077:
078: makeArrays(arraySize);
079: for (int i = 0; i < oldSize; i++) {
080: if (oldValues[i] != EMPTY) {
081: put(oldKeys[i], oldValues[i]);
082: }
083: }
084: oldKeys = oldValues = null; // Help out the garbage collector
085: }
086:
087: /**
088: * Produce a uniformly-distributed hash value from an integer key.
089: * This is essentially a linear congruential random number generator
090: * that uses the key as its seed value.
091: */
092: private final int hash(long key) {
093: int h = (int) ((key * 15821 + 1) % arraySize);
094: if (h < 0) {
095: h += arraySize;
096: }
097: return h;
098: }
099:
100: private final int hash2(long key) {
101: return arraySize - 2 - (int) (key % (arraySize - 2));
102: }
103:
104: static private final int primes[] = { // 5, 17, 31, 47, // for testing
105: 61, 127, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071,
106: 262139, };
107:
108: private int pIndex = 0;
109: private int size = 0;
110: private int arraySize = primes[pIndex];
111: private int threshold = (arraySize * 3) / 4;
112:
113: private long[] keys = new long[arraySize];
114: private long[] values = new long[arraySize];
115:
116: /**
117: * @internal
118: */
119: static public long EMPTY = Long.MIN_VALUE;
120: }
|