1/* 2 ******************************************************************************* 3 * Copyright (C) 1996-2011, International Business Machines Corporation and * 4 * others. All Rights Reserved. * 5 ******************************************************************************* 6 */ 7package com.ibm.icu.impl; 8 9/** 10 * @internal 11 */ 12public class CalendarCache 13{ 14 /** 15 * @internal 16 */ 17 public CalendarCache() { 18 makeArrays(arraySize); 19 } 20 21 private void makeArrays(int newSize) { 22 keys = new long[newSize]; 23 values = new long[newSize]; 24 25 for (int i = 0; i < newSize; i++) { 26 values[i] = EMPTY; 27 } 28 arraySize = newSize; 29 threshold = (int)(arraySize * 0.75); 30 size = 0; 31 } 32 33 /** 34 * @internal 35 */ 36 public synchronized long get(long key) { 37 return values[findIndex(key)]; 38 } 39 40 /** 41 * @internal 42 */ 43 public synchronized void put(long key, long value) 44 { 45 if (size >= threshold) { 46 rehash(); 47 } 48 int index = findIndex(key); 49 50 keys[index] = key; 51 values[index] = value; 52 size++; 53 } 54 55 private final int findIndex(long key) { 56 int index = hash(key); 57 int delta = 0; 58 59 while (values[index] != EMPTY && keys[index] != key) 60 { 61 if (delta == 0) { 62 delta = hash2(key); 63 } 64 index = (index + delta) % arraySize; 65 } 66 return index; 67 } 68 69 private void rehash() 70 { 71 int oldSize = arraySize; 72 long[] oldKeys = keys; 73 long[] oldValues = values; 74 75 if (pIndex < primes.length - 1) { 76 arraySize = primes[++pIndex]; 77 } else { 78 arraySize = arraySize * 2 + 1; 79 } 80 size = 0; 81 82 makeArrays(arraySize); 83 for (int i = 0; i < oldSize; i++) { 84 if (oldValues[i] != EMPTY) { 85 put(oldKeys[i], oldValues[i]); 86 } 87 } 88 } 89 90 91 /** 92 * Produce a uniformly-distributed hash value from an integer key. 93 * This is essentially a linear congruential random number generator 94 * that uses the key as its seed value. 95 */ 96 private final int hash(long key) 97 { 98 int h = (int)((key * 15821 + 1) % arraySize); 99 if (h < 0) { 100 h += arraySize; 101 } 102 return h; 103 } 104 105 private final int hash2(long key) { 106 return arraySize - 2 - (int)(key % (arraySize-2) ); 107 } 108 109 static private final int primes[] = { // 5, 17, 31, 47, // for testing 110 61, 127, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 111 131071, 262139, 112 }; 113 114 private int pIndex = 0; 115 private int size = 0; 116 private int arraySize = primes[pIndex]; 117 private int threshold = (arraySize * 3) / 4; 118 119 private long[] keys = new long[arraySize]; 120 private long[] values = new long[arraySize]; 121 122 /** 123 * @internal 124 */ 125 static public long EMPTY = Long.MIN_VALUE; 126} 127