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