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 java.util.ArrayList; |
9 | import org.h2.message.DbException; |
10 | import org.h2.value.Value; |
11 | import org.h2.value.ValueNull; |
12 | |
13 | /** |
14 | * This hash map supports keys of type Value. |
15 | * |
16 | * @param <V> the value type |
17 | */ |
18 | public class ValueHashMap<V> extends HashBase { |
19 | |
20 | private Value[] keys; |
21 | private V[] values; |
22 | |
23 | /** |
24 | * Create a new value hash map. |
25 | * |
26 | * @return the object |
27 | */ |
28 | public static <T> ValueHashMap<T> newInstance() { |
29 | return new ValueHashMap<T>(); |
30 | } |
31 | |
32 | @Override |
33 | @SuppressWarnings("unchecked") |
34 | protected void reset(int newLevel) { |
35 | super.reset(newLevel); |
36 | keys = new Value[len]; |
37 | values = (V[]) new Object[len]; |
38 | } |
39 | |
40 | @Override |
41 | protected void rehash(int newLevel) { |
42 | Value[] oldKeys = keys; |
43 | V[] oldValues = values; |
44 | reset(newLevel); |
45 | int len = oldKeys.length; |
46 | for (int i = 0; i < len; i++) { |
47 | Value k = oldKeys[i]; |
48 | if (k != null && k != ValueNull.DELETED) { |
49 | // skip the checkSizePut so we don't end up |
50 | // accidentally recursing |
51 | internalPut(k, oldValues[i]); |
52 | } |
53 | } |
54 | } |
55 | |
56 | private int getIndex(Value key) { |
57 | return key.hashCode() & mask; |
58 | } |
59 | |
60 | /** |
61 | * Add or update a key value pair. |
62 | * |
63 | * @param key the key |
64 | * @param value the new value |
65 | */ |
66 | public void put(Value key, V value) { |
67 | checkSizePut(); |
68 | internalPut(key, value); |
69 | } |
70 | |
71 | private void internalPut(Value key, V value) { |
72 | int index = getIndex(key); |
73 | int plus = 1; |
74 | int deleted = -1; |
75 | do { |
76 | Value k = keys[index]; |
77 | if (k == null) { |
78 | // found an empty record |
79 | if (deleted >= 0) { |
80 | index = deleted; |
81 | deletedCount--; |
82 | } |
83 | size++; |
84 | keys[index] = key; |
85 | values[index] = value; |
86 | return; |
87 | } else if (k == ValueNull.DELETED) { |
88 | // found a deleted record |
89 | if (deleted < 0) { |
90 | deleted = index; |
91 | } |
92 | } else if (k.equals(key)) { |
93 | // update existing |
94 | values[index] = value; |
95 | return; |
96 | } |
97 | index = (index + plus++) & mask; |
98 | } while (plus <= len); |
99 | // no space |
100 | DbException.throwInternalError("hashmap is full"); |
101 | } |
102 | |
103 | /** |
104 | * Remove a key value pair. |
105 | * |
106 | * @param key the key |
107 | */ |
108 | public void remove(Value key) { |
109 | checkSizeRemove(); |
110 | int index = getIndex(key); |
111 | int plus = 1; |
112 | do { |
113 | Value k = keys[index]; |
114 | if (k == null) { |
115 | // found an empty record |
116 | return; |
117 | } else if (k == ValueNull.DELETED) { |
118 | // found a deleted record |
119 | } else if (k.equals(key)) { |
120 | // found the record |
121 | keys[index] = ValueNull.DELETED; |
122 | values[index] = null; |
123 | deletedCount++; |
124 | size--; |
125 | return; |
126 | } |
127 | index = (index + plus++) & mask; |
128 | } while (plus <= len); |
129 | // not found |
130 | } |
131 | |
132 | /** |
133 | * Get the value for this key. This method returns null if the key was not |
134 | * found. |
135 | * |
136 | * @param key the key |
137 | * @return the value for the given key |
138 | */ |
139 | public V get(Value key) { |
140 | int index = getIndex(key); |
141 | int plus = 1; |
142 | do { |
143 | Value k = keys[index]; |
144 | if (k == null) { |
145 | // found an empty record |
146 | return null; |
147 | } else if (k == ValueNull.DELETED) { |
148 | // found a deleted record |
149 | } else if (k.equals(key)) { |
150 | // found it |
151 | return values[index]; |
152 | } |
153 | index = (index + plus++) & mask; |
154 | } while (plus <= len); |
155 | return null; |
156 | } |
157 | |
158 | /** |
159 | * Get the list of keys. |
160 | * |
161 | * @return all keys |
162 | */ |
163 | public ArrayList<Value> keys() { |
164 | ArrayList<Value> list = New.arrayList(size); |
165 | for (Value k : keys) { |
166 | if (k != null && k != ValueNull.DELETED) { |
167 | list.add(k); |
168 | } |
169 | } |
170 | return list; |
171 | } |
172 | |
173 | /** |
174 | * Get the list of values. |
175 | * |
176 | * @return all values |
177 | */ |
178 | public ArrayList<V> values() { |
179 | ArrayList<V> list = New.arrayList(size); |
180 | int len = keys.length; |
181 | for (int i = 0; i < len; i++) { |
182 | Value k = keys[i]; |
183 | if (k != null && k != ValueNull.DELETED) { |
184 | list.add(values[i]); |
185 | } |
186 | } |
187 | return list; |
188 | } |
189 | |
190 | } |