1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.util; |
7 | |
8 | import org.h2.message.DbException; |
9 | |
10 | /** |
11 | * A hash map with int key and int values. There is a restriction: the |
12 | * value -1 (NOT_FOUND) cannot be stored in the map. 0 can be stored. |
13 | * An empty record has key=0 and value=0. |
14 | * A deleted record has key=0 and value=DELETED |
15 | */ |
16 | public class IntIntHashMap extends HashBase { |
17 | |
18 | /** |
19 | * The value indicating that the entry has not been found. |
20 | */ |
21 | public static final int NOT_FOUND = -1; |
22 | |
23 | private static final int DELETED = 1; |
24 | private int[] keys; |
25 | private int[] values; |
26 | private int zeroValue; |
27 | |
28 | @Override |
29 | protected void reset(int newLevel) { |
30 | super.reset(newLevel); |
31 | keys = new int[len]; |
32 | values = new int[len]; |
33 | } |
34 | |
35 | /** |
36 | * Store the given key-value pair. The value is overwritten or added. |
37 | * |
38 | * @param key the key |
39 | * @param value the value (-1 is not supported) |
40 | */ |
41 | public void put(int key, int value) { |
42 | if (key == 0) { |
43 | zeroKey = true; |
44 | zeroValue = value; |
45 | return; |
46 | } |
47 | checkSizePut(); |
48 | internalPut(key, value); |
49 | } |
50 | |
51 | private void internalPut(int key, int value) { |
52 | int index = getIndex(key); |
53 | int plus = 1; |
54 | int deleted = -1; |
55 | do { |
56 | int k = keys[index]; |
57 | if (k == 0) { |
58 | if (values[index] != DELETED) { |
59 | // found an empty record |
60 | if (deleted >= 0) { |
61 | index = deleted; |
62 | deletedCount--; |
63 | } |
64 | size++; |
65 | keys[index] = key; |
66 | values[index] = value; |
67 | return; |
68 | } |
69 | // found a deleted record |
70 | if (deleted < 0) { |
71 | deleted = index; |
72 | } |
73 | } else if (k == key) { |
74 | // update existing |
75 | values[index] = value; |
76 | return; |
77 | } |
78 | index = (index + plus++) & mask; |
79 | } while (plus <= len); |
80 | // no space |
81 | DbException.throwInternalError("hashmap is full"); |
82 | } |
83 | |
84 | /** |
85 | * Remove the key-value pair with the given key. |
86 | * |
87 | * @param key the key |
88 | */ |
89 | public void remove(int key) { |
90 | if (key == 0) { |
91 | zeroKey = false; |
92 | return; |
93 | } |
94 | checkSizeRemove(); |
95 | int index = getIndex(key); |
96 | int plus = 1; |
97 | do { |
98 | int k = keys[index]; |
99 | if (k == key) { |
100 | // found the record |
101 | keys[index] = 0; |
102 | values[index] = DELETED; |
103 | deletedCount++; |
104 | size--; |
105 | return; |
106 | } else if (k == 0 && values[index] == 0) { |
107 | // found an empty record |
108 | return; |
109 | } |
110 | index = (index + plus++) & mask; |
111 | } while (plus <= len); |
112 | // not found |
113 | } |
114 | |
115 | @Override |
116 | protected void rehash(int newLevel) { |
117 | int[] oldKeys = keys; |
118 | int[] oldValues = values; |
119 | reset(newLevel); |
120 | for (int i = 0; i < oldKeys.length; i++) { |
121 | int k = oldKeys[i]; |
122 | if (k != 0) { |
123 | // skip the checkSizePut so we don't end up |
124 | // accidentally recursing |
125 | internalPut(k, oldValues[i]); |
126 | } |
127 | } |
128 | } |
129 | |
130 | /** |
131 | * Get the value for the given key. This method returns NOT_FOUND if the |
132 | * entry has not been found. |
133 | * |
134 | * @param key the key |
135 | * @return the value or NOT_FOUND |
136 | */ |
137 | public int get(int key) { |
138 | if (key == 0) { |
139 | return zeroKey ? zeroValue : NOT_FOUND; |
140 | } |
141 | int index = getIndex(key); |
142 | int plus = 1; |
143 | do { |
144 | int k = keys[index]; |
145 | if (k == 0 && values[index] == 0) { |
146 | // found an empty record |
147 | return NOT_FOUND; |
148 | } else if (k == key) { |
149 | // found it |
150 | return values[index]; |
151 | } |
152 | index = (index + plus++) & mask; |
153 | } while (plus <= len); |
154 | return NOT_FOUND; |
155 | } |
156 | |
157 | } |