KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > activemq > kaha > impl > index > hash > HashBin


1 /**
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE
4  * file distributed with this work for additional information regarding copyright ownership. The ASF licenses this file
5  * to You under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
6  * License. You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on
11  * an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the
12  * specific language governing permissions and limitations under the License.
13  */

14
15 package org.apache.activemq.kaha.impl.index.hash;
16
17 import java.io.IOException JavaDoc;
18 import java.util.ArrayList JavaDoc;
19 import java.util.List JavaDoc;
20
21 /**
22  * Bin in a HashIndex
23  *
24  * @version $Revision: 1.1.1.1 $
25  */

26 class HashBin{
27
28     private HashIndex hashIndex;
29     private int id;
30     private int maximumEntries;
31     private int size=0;
32     private List JavaDoc<HashPageInfo> hashPages=new ArrayList JavaDoc<HashPageInfo>();
33
34     /**
35      * Constructor
36      *
37      * @param hashIndex
38      * @param id
39      * @param maximumEntries
40      */

41     HashBin(HashIndex hashIndex,int id,int maximumEntries){
42         this.hashIndex=hashIndex;
43         this.id=id;
44         this.maximumEntries=maximumEntries;
45     }
46
47     public String JavaDoc toString(){
48         return "HashBin["+getId()+"]";
49     }
50
51     public boolean equals(Object JavaDoc o){
52         boolean result=false;
53         if(o instanceof HashBin){
54             HashBin other=(HashBin)o;
55             result=other.id==id;
56         }
57         return result;
58     }
59
60     public int hashCode(){
61         return (int)id;
62     }
63
64     int getId(){
65         return id;
66     }
67
68     void setId(int id){
69         this.id=id;
70     }
71
72     boolean isEmpty(){
73         return true;
74     }
75
76     int getMaximumEntries(){
77         return this.maximumEntries;
78     }
79
80     void setMaximumEntries(int maximumEntries){
81         this.maximumEntries=maximumEntries;
82     }
83
84     int size(){
85         return size;
86     }
87
88     HashPageInfo addHashPageInfo(long id,int size){
89         HashPageInfo info=new HashPageInfo(hashIndex);
90         info.setId(id);
91         info.setSize(size);
92         hashPages.add(info);
93         this.size+=size;
94         return info;
95     }
96
97     public HashEntry find(HashEntry key) throws IOException JavaDoc{
98         HashEntry result=null;
99         try{
100             int low=0;
101             int high=size()-1;
102             while(low<=high){
103                 int mid=(low+high)>>1;
104                 HashEntry te=getHashEntry(mid);
105                 int cmp=te.compareTo(key);
106                 if(cmp==0){
107                     result=te;
108                     break;
109                 }else if(cmp<0){
110                     low=mid+1;
111                 }else{
112                     high=mid-1;
113                 }
114             }
115         }finally{
116             end();
117         }
118         return result;
119     }
120
121     void put(HashEntry newEntry) throws IOException JavaDoc{
122         try{
123             boolean replace=false;
124             int low=0;
125             int high=size()-1;
126             while(low<=high){
127                 int mid=(low+high)>>1;
128                 HashEntry midVal=getHashEntry(mid);
129                 int cmp=midVal.compareTo(newEntry);
130                 if(cmp<0){
131                     low=mid+1;
132                 }else if(cmp>0){
133                     high=mid-1;
134                 }else{
135                     replace=true;
136                     midVal.setIndexOffset(newEntry.getIndexOffset());
137                     break;
138                 }
139             }
140             if(!replace){
141                 if (low > size()) {
142                    System.out.println("SIZE() " + size() + " low = " + low);
143                 }
144                 addHashEntry(low,newEntry);
145                 size++;
146             }
147         }finally{
148             end();
149         }
150     }
151
152     HashEntry remove(HashEntry entry) throws IOException JavaDoc{
153         HashEntry result = null;
154         try{
155             int low=0;
156             int high=size()-1;
157             while(low<=high){
158                 int mid=(low+high)>>1;
159                 HashEntry te=getHashEntry(mid);
160                 int cmp=te.compareTo(entry);
161                 if(cmp==0){
162                     result =te;
163                     removeHashEntry(mid);
164                     size--;
165                     break;
166                 }else if(cmp<0){
167                     low=mid+1;
168                 }else{
169                     high=mid-1;
170                 }
171             }
172         }finally{
173             end();
174         }
175         return result;
176     }
177
178     private void addHashEntry(int index,HashEntry entry) throws IOException JavaDoc{
179         HashPageInfo page=getInsertPage(index);
180         int offset=index%maximumEntries;
181         page.addHashEntry(offset,entry);
182         doOverFlow(index);
183     }
184
185     private HashEntry removeHashEntry(int index) throws IOException JavaDoc{
186         HashPageInfo page=getRetrievePage(index);
187         int offset=getRetrieveOffset(index);
188         HashEntry result=page.removeHashEntry(offset);
189         doUnderFlow(index);
190         return result;
191     }
192
193     private HashEntry getHashEntry(int index) throws IOException JavaDoc{
194         HashPageInfo page=getRetrievePage(index);
195         page.begin();
196         int offset=getRetrieveOffset(index);
197         HashEntry result=page.getHashEntry(offset);
198         return result;
199     }
200
201     private int maximumBinSize(){
202         return maximumEntries*hashPages.size();
203     }
204
205     private HashPageInfo getInsertPage(int index) throws IOException JavaDoc{
206         HashPageInfo result=null;
207         if(index>=maximumBinSize()){
208             HashPage page=hashIndex.createPage(id);
209             result=addHashPageInfo(page.getId(),0);
210             result.setPage(page);
211         }else{
212             int offset=index/maximumEntries;
213             result=hashPages.get(offset);
214         }
215         result.begin();
216         return result;
217     }
218
219     private HashPageInfo getRetrievePage(int index) throws IOException JavaDoc{
220         HashPageInfo result=null;
221         int count=0;
222         int pageNo=0;
223         for(HashPageInfo page:hashPages){
224             count+=page.size();
225             if(index<count){
226                 break;
227             }
228             pageNo++;
229         }
230         result=hashPages.get(pageNo);
231         result.begin();
232         return result;
233     }
234
235     private int getRetrieveOffset(int index) throws IOException JavaDoc{
236         int result=0;
237         int count=0;
238         for(HashPageInfo page:hashPages){
239             if((index+1)<=(count+page.size())){
240                 // count=count==0?count:count+1;
241
result=index-count;
242                 break;
243             }
244             count+=page.size();
245         }
246         return result;
247     }
248
249     private int getInsertPageNo(int index){
250         int result=index/maximumEntries;
251         return result;
252     }
253
254     private int getOffset(int index){
255         int result=index%maximumEntries;
256         return result;
257     }
258
259     private void doOverFlow(int index) throws IOException JavaDoc{
260         int pageNo=index/maximumEntries;
261         HashPageInfo info=hashPages.get(pageNo);
262         if(info.size()>maximumEntries){
263             // overflowed
264
HashEntry entry=info.removeHashEntry(info.size()-1);
265             doOverFlow(pageNo+1,entry);
266         }
267     }
268
269     private void doOverFlow(int pageNo,HashEntry entry) throws IOException JavaDoc{
270         HashPageInfo info=null;
271         if(pageNo>=hashPages.size()){
272             HashPage page=hashIndex.createPage(id);
273             info=addHashPageInfo(page.getId(),0);
274             info.setPage(page);
275         }else{
276             info=hashPages.get(pageNo);
277         }
278         info.begin();
279         info.addHashEntry(0,entry);
280         if(info.size()>maximumEntries){
281             // overflowed
282
HashEntry overflowed=info.removeHashEntry(info.size()-1);
283             doOverFlow(pageNo+1,overflowed);
284         }
285     }
286
287     private void doUnderFlow(int index){
288         int pageNo=index/maximumEntries;
289         int nextPageNo=pageNo+1;
290         if(nextPageNo<hashPages.size()){
291         }
292         HashPageInfo info=hashPages.get(pageNo);
293     }
294
295     private void end() throws IOException JavaDoc{
296         for(HashPageInfo info:hashPages){
297             info.end();
298         }
299     }
300 }
301
Popular Tags