01: /*
02: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
03: * (http://h2database.com/html/license.html).
04: * Initial Developer: H2 Group
05: */
06: package org.h2.util;
07:
08: import java.sql.SQLException;
09:
10: /**
11: * The base for other hash classes.
12: */
13: public abstract class HashBase {
14:
15: /**
16: * The bit mask to get the index from the hash code.
17: */
18: protected int mask;
19:
20: /**
21: * The number of slots in the table.
22: */
23: protected int len;
24:
25: /**
26: * The number of occupied slots, excluding the zero key (if any).
27: */
28: protected int size;
29:
30: /**
31: * The number of deleted slots.
32: */
33: protected int deletedCount;
34:
35: /**
36: * The level. The number of slots is 2 ^ level.
37: */
38: protected int level;
39:
40: /**
41: * Whether the zero key is used.
42: */
43: protected boolean zeroKey;
44:
45: private int maxSize, minSize, maxDeleted;
46: private static final int MAX_LOAD = 90;
47:
48: /**
49: * Increase the size of the underlying table and re-distribute the elements.
50: *
51: * @param newLevel the new level
52: */
53: protected abstract void rehash(int newLevel) throws SQLException;
54:
55: public HashBase() {
56: reset(2);
57: }
58:
59: public int size() {
60: return size + (zeroKey ? 1 : 0);
61: }
62:
63: protected void checkSizePut() throws SQLException {
64: if (deletedCount > size) {
65: rehash(level);
66: }
67: if (size + deletedCount >= maxSize) {
68: rehash(level + 1);
69: }
70: }
71:
72: protected void checkSizeRemove() throws SQLException {
73: if (size < minSize && level > 0) {
74: rehash(level - 1);
75: } else if (deletedCount > maxDeleted) {
76: rehash(level);
77: }
78: }
79:
80: protected void reset(int newLevel) {
81: minSize = size * 3 / 4;
82: size = 0;
83: level = newLevel;
84: len = 2 << level;
85: mask = len - 1;
86: maxSize = (int) (len * MAX_LOAD / 100L);
87: deletedCount = 0;
88: maxDeleted = 20 + len / 2;
89: }
90:
91: protected int getIndex(int hash) {
92: return hash & mask;
93: }
94:
95: }
|