001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.util;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.message.Message;
011:
012: /**
013: * A hash map with int key and int values. There is a restriction: the
014: * value -1 (NOT_FOUND) cannot be stored in the map. 0 can be stored.
015: * An empty record has key=0 and value=0.
016: * A deleted record has key=0 and value=DELETED
017: */
018: public class IntIntHashMap extends HashBase {
019: public static final int NOT_FOUND = -1;
020: private static final int DELETED = 1;
021: private int[] keys;
022: private int[] values;
023: private int zeroValue;
024:
025: protected void reset(int newLevel) {
026: super .reset(newLevel);
027: keys = new int[len];
028: values = new int[len];
029: }
030:
031: public void put(int key, int value) {
032: if (key == 0) {
033: zeroKey = true;
034: zeroValue = value;
035: }
036: try {
037: checkSizePut();
038: } catch (SQLException e) {
039: // in fact, it is never thrown
040: // TODO hash: maybe optimize it
041: }
042: int index = getIndex(key);
043: int plus = 1;
044: int deleted = -1;
045: do {
046: int k = keys[index];
047: if (k == 0) {
048: if (values[index] != DELETED) {
049: // found an empty record
050: if (deleted >= 0) {
051: index = deleted;
052: deletedCount--;
053: }
054: size++;
055: keys[index] = key;
056: values[index] = value;
057: return;
058: }
059: // found a deleted record
060: if (deleted < 0) {
061: deleted = index;
062: }
063: } else if (k == key) {
064: // update existing
065: values[index] = value;
066: return;
067: }
068: index = (index + plus++) & mask;
069: } while (plus <= len);
070: // no space
071: throw Message.getInternalError("hashmap is full");
072: }
073:
074: public void remove(int key) {
075: if (key == 0) {
076: zeroKey = false;
077: return;
078: }
079: try {
080: checkSizeRemove();
081: } catch (SQLException e) {
082: // in fact, it is never thrown
083: // TODO hash: maybe optimize it
084: }
085: int index = getIndex(key);
086: int plus = 1;
087: do {
088: int k = keys[index];
089: if (k == key) {
090: // found the record
091: keys[index] = 0;
092: values[index] = DELETED;
093: deletedCount++;
094: size--;
095: return;
096: } else if (k == 0 && values[index] == 0) {
097: // found an empty record
098: return;
099: }
100: index = (index + plus++) & mask;
101: k = keys[index];
102: } while (plus <= len);
103: // not found
104: }
105:
106: protected void rehash(int newLevel) {
107: int[] oldKeys = keys;
108: int[] oldValues = values;
109: reset(newLevel);
110: for (int i = 0; i < oldKeys.length; i++) {
111: int k = oldKeys[i];
112: if (k != 0) {
113: put(k, oldValues[i]);
114: }
115: }
116: }
117:
118: public int get(int key) {
119: if (key == 0) {
120: return zeroKey ? zeroValue : NOT_FOUND;
121: }
122: int index = getIndex(key);
123: int plus = 1;
124: do {
125: int k = keys[index];
126: if (k == 0 && values[index] == 0) {
127: // found an empty record
128: return NOT_FOUND;
129: } else if (k == key) {
130: // found it
131: return values[index];
132: }
133: index = (index + plus++) & mask;
134: } while (plus <= len);
135: return NOT_FOUND;
136: }
137:
138: }
|