1 14 15 package org.apache.activemq.kaha.impl.index.hash; 16 17 import java.io.IOException ; 18 import java.util.ArrayList ; 19 import java.util.List ; 20 21 26 class HashBin{ 27 28 private HashIndex hashIndex; 29 private int id; 30 private int maximumEntries; 31 private int size=0; 32 private List <HashPageInfo> hashPages=new ArrayList <HashPageInfo>(); 33 34 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 toString(){ 48 return "HashBin["+getId()+"]"; 49 } 50 51 public boolean equals(Object 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 { 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 { 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 { 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 { 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 { 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 { 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 { 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 { 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 { 236 int result=0; 237 int count=0; 238 for(HashPageInfo page:hashPages){ 239 if((index+1)<=(count+page.size())){ 240 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 { 260 int pageNo=index/maximumEntries; 261 HashPageInfo info=hashPages.get(pageNo); 262 if(info.size()>maximumEntries){ 263 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 { 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 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 { 296 for(HashPageInfo info:hashPages){ 297 info.end(); 298 } 299 } 300 } 301 | Popular Tags |