File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\util\IntIntHashMap.java.html

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