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