KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > h2 > util > IntIntHashMap


1 /*
2  * Copyright 2004-2006 H2 Group. Licensed under the H2 License, Version 1.0 (http://h2database.com/html/license.html).
3  * Initial Developer: H2 Group
4  */
5 package org.h2.util;
6
7 import java.sql.SQLException JavaDoc;
8
9 import org.h2.message.Message;
10
11 /**
12  * An empty record has key=0 and value=0
13  * A deleted record has key=0 and value=DELETED
14  * value NOT_FOUND: -1; this value cannot be stored in the map (however 0 can be stored)
15  * @author Thomas
16  */
17 public class IntIntHashMap extends HashBase {
18     public static final int NOT_FOUND = -1;
19     private static final int DELETED = 1;
20     private int[] keys;
21     private int[] values;
22     private int zeroValue;
23
24     protected void reset(int newLevel) {
25         super.reset(newLevel);
26         keys = new int[len];
27         values = new int[len];
28     }
29
30     public void put(int key, int value) {
31         if(key==0) {
32             zeroKey = true;
33             zeroValue = value;
34         }
35         try {
36             checkSizePut();
37         } catch(SQLException JavaDoc e) {
38             // in fact, it is never thrown
39 // TODO hash: maybe optimize it
40 }
41         int index = getIndex(key);
42         int plus = 1;
43         int deleted = -1;
44         do {
45             int k = keys[index];
46             if(k==0) {
47                 if(values[index] != DELETED) {
48                     // found an empty record
49 if(deleted>=0) {
50                         index = deleted;
51                         deletedCount--;
52                     }
53                     size++;
54                     keys[index] = key;
55                     values[index] = value;
56                     return;
57                 }
58                 // found a deleted record
59 if(deleted<0) {
60                     deleted = index;
61                 }
62             } else if(k==key) {
63                 // update existing
64 values[index] = value;
65                 return;
66             }
67             index = (index + plus++) & mask;
68         } while(plus <= len);
69         // no space
70 throw Message.getInternalError("hashmap is full");
71     }
72
73     public void remove(int key) {
74         if(key == 0) {
75             zeroKey = false;
76             return;
77         }
78         try {
79             checkSizeRemove();
80         } catch(SQLException JavaDoc e) {
81             // in fact, it is never thrown
82 // TODO hash: maybe optimize it
83 }
84         int index = getIndex(key);
85         int plus = 1;
86         do {
87             int k = keys[index];
88             if(k==key) {
89                 // found the record
90 keys[index] = 0;
91                 values[index] = DELETED;
92                 deletedCount++;
93                 size--;
94                 return;
95             } else if(k==0 && values[index] == 0) {
96                 // found an empty record
97 return;
98             }
99             index = (index + plus++) & mask;
100             k = keys[index];
101         } while(plus <= len);
102         // not found
103 }
104
105     protected void rehash(int newLevel) {
106         int[] oldKeys = keys;
107         int[] oldValues = values;
108         reset(newLevel);
109         for(int i=0; i<oldKeys.length; i++) {
110             int k = oldKeys[i];
111             if(k != 0) {
112                 put(k, oldValues[i]);
113             }
114         }
115     }
116
117     public int get(int key) {
118         if(key == 0) {
119             return zeroKey ? zeroValue : NOT_FOUND;
120         }
121         int index = getIndex(key);
122         int plus = 1;
123         do {
124             int k = keys[index];
125             if(k==0 && values[index]==0) {
126                 // found an empty record
127 return NOT_FOUND;
128             } else if(k==key) {
129                 // found it
130 return values[index];
131             }
132             index = (index + plus++) & mask;
133         } while(plus <= len);
134         return NOT_FOUND;
135     }
136
137 }
138
Popular Tags