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