001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.wicket.pageStore.disk; 018 019import java.io.Serializable; 020import java.util.ArrayList; 021import java.util.List; 022 023import org.apache.wicket.pageStore.IPersistedPage; 024import org.apache.wicket.util.collections.IntHashMap; 025import org.apache.wicket.util.lang.Bytes; 026 027/** 028 * Manages positions and size of chunks of data in a file. 029 * <p> 030 * The data is stored inside the file in a cyclic way. Newer pages are placed after older ones, 031 * until the maximum file size is reached. After that, the next page is stored in the beginning of 032 * the file. 033 * 034 * @author Matej Knopp 035 */ 036public class PageWindowManager implements Serializable 037{ 038 private static final long serialVersionUID = 1L; 039 040 /** 041 * Contains information about a page inside the file. 042 * 043 * @author Matej Knopp 044 */ 045 public static class FileWindow implements IPersistedPage, Serializable 046 { 047 private static final long serialVersionUID = 1L; 048 049 /** id of data or -1 if the window is empty */ 050 private int id; 051 052 private String type; 053 054 /** offset in the file where the serialized page data begins */ 055 private int filePartOffset; 056 057 /** size of serialized page data */ 058 private int filePartSize; 059 060 @Override 061 public int getPageId() 062 { 063 return id; 064 } 065 066 @Override 067 public String getPageType() 068 { 069 return type; 070 } 071 072 @Override 073 public Bytes getPageSize() 074 { 075 return Bytes.bytes(filePartSize); 076 } 077 078 public int getFilePartOffset() 079 { 080 return filePartOffset; 081 } 082 083 public int getFilePartSize() 084 { 085 return filePartSize; 086 } 087 } 088 089 private final List<FileWindow> windows = new ArrayList<>(); 090 091 /** 092 * map from page id to list of pagewindow indices (referring to the windows list) - to improve 093 * searching speed the index must be cleaned when the instances in the windows list change their 094 * indexes (e.g. items are shifted on page window removal) 095 */ 096 private IntHashMap<Integer> idToWindowIndex = null; 097 098 /** 099 * Inversed index of #idToWindowIndex 100 */ 101 private IntHashMap<Integer> windowIndexToPageId = null; 102 103 /** index of last added page */ 104 private int indexPointer = -1; 105 106 private int totalSize = 0; 107 108 /** 109 * Maximum page size. After this size is exceeded, the pages will be saved starting at the 110 * beginning of file. 111 */ 112 private final long maxSize; 113 114 /** 115 * 116 * @param pageId 117 * @param windowIndex 118 */ 119 private void putWindowIndex(int pageId, int windowIndex) 120 { 121 if (idToWindowIndex != null && pageId != -1 && windowIndex != -1) 122 { 123 Integer oldPageId = windowIndexToPageId.remove(windowIndex); 124 if (oldPageId != null) 125 { 126 idToWindowIndex.remove(oldPageId); 127 } 128 idToWindowIndex.put(pageId, windowIndex); 129 windowIndexToPageId.put(windowIndex, pageId); 130 } 131 } 132 133 /** 134 * 135 * @param pageId 136 */ 137 private void removeWindowIndex(int pageId) 138 { 139 Integer windowIndex = idToWindowIndex.remove(pageId); 140 if (windowIndex != null) 141 { 142 windowIndexToPageId.remove(windowIndex); 143 } 144 } 145 146 /** 147 * 148 */ 149 private void rebuildIndices() 150 { 151 idToWindowIndex = null; 152 idToWindowIndex = new IntHashMap<>(); 153 windowIndexToPageId = null; 154 windowIndexToPageId = new IntHashMap<>(); 155 for (int i = 0; i < windows.size(); ++i) 156 { 157 FileWindow window = windows.get(i); 158 putWindowIndex(window.id, i); 159 } 160 } 161 162 /** 163 * Returns the index of the given page in the {@link #windows} list. 164 * 165 * @param pageId 166 * @return window index 167 */ 168 private int getWindowIndex(int pageId) 169 { 170 if (idToWindowIndex == null) 171 { 172 rebuildIndices(); 173 } 174 175 Integer result = idToWindowIndex.get(pageId); 176 return result != null ? result : -1; 177 } 178 179 /** 180 * Increments the {@link #indexPointer}. If the maximum file size has been reached, the 181 * {@link #indexPointer} is set to 0. 182 * 183 * @return new index pointer 184 */ 185 private int incrementIndexPointer() 186 { 187 if ((maxSize > 0) && (totalSize >= maxSize) && (indexPointer == windows.size() - 1)) 188 { 189 indexPointer = 0; 190 } 191 else 192 { 193 ++indexPointer; 194 } 195 return indexPointer; 196 } 197 198 /** 199 * Returns the offset in file of the window on given index. The offset is counted by getting the 200 * previous page offset and adding the previous page size to it. 201 * 202 * @param index 203 * @return window file offset 204 */ 205 private int getWindowFileOffset(int index) 206 { 207 if (index > 0) 208 { 209 FileWindow window = windows.get(index - 1); 210 return window.filePartOffset + window.filePartSize; 211 } 212 return 0; 213 } 214 215 /** 216 * Splits the window with given index to two windows. First of those will have size specified by 217 * the argument, the other one will fill up the rest of the original window. 218 * 219 * @param index 220 * @param size 221 */ 222 private void splitWindow(int index, int size) 223 { 224 FileWindow window = windows.get(index); 225 int delta = window.filePartSize - size; 226 227 if (index == windows.size() - 1) 228 { 229 // if this is last window 230 totalSize -= delta; 231 window.filePartSize = size; 232 } 233 else if (window.filePartSize != size) 234 { 235 FileWindow newWindow = new FileWindow(); 236 newWindow.id = -1; 237 window.filePartSize = size; 238 239 windows.add(index + 1, newWindow); 240 241 newWindow.filePartOffset = getWindowFileOffset(index + 1); 242 newWindow.filePartSize = delta; 243 } 244 245 idToWindowIndex = null; 246 windowIndexToPageId = null; 247 } 248 249 /** 250 * Merges the window with given index with the next window. The resulting window will have size 251 * of the two windows summed together. 252 * 253 * @param index 254 */ 255 private void mergeWindowWithNext(int index) 256 { 257 if (index < windows.size() - 1) 258 { 259 FileWindow window = windows.get(index); 260 FileWindow next = windows.get(index + 1); 261 window.filePartSize += next.filePartSize; 262 263 windows.remove(index + 1); 264 idToWindowIndex = null; // reset index 265 windowIndexToPageId = null; 266 } 267 } 268 269 /** 270 * Adjusts the window on given index to the specified size. If the new size is smaller than the 271 * window size, the window will be split. Otherwise the window will be merged with as many 272 * subsequent window as necessary. In case the window is last window in the file, the size will 273 * be adjusted without splitting or merging. 274 * 275 * @param index 276 * @param size 277 */ 278 private void adjustWindowSize(int index, int size) 279 { 280 FileWindow window = windows.get(index); 281 282 // last window, just adjust size 283 if (index == windows.size() - 1) 284 { 285 int delta = size - window.filePartSize; 286 totalSize += delta; 287 window.filePartSize = size; 288 } 289 else 290 { 291 // merge as many times as necessary 292 while (window.filePartSize < size && index < windows.size() - 1) 293 { 294 mergeWindowWithNext(index); 295 } 296 297 // done merging - do we have enough room ? 298 if (window.filePartSize < size) 299 { 300 // no, this is the last window 301 int delta = size - window.filePartSize; 302 totalSize += delta; 303 window.filePartSize = size; 304 } 305 else 306 { 307 // yes, we might want to split the window, so that we don't lose 308 // space when the created window was too big 309 splitWindow(index, size); 310 } 311 } 312 313 window.id = -1; 314 } 315 316 /** 317 * Allocates window on given index with to size. If the index is pointing to existing window, 318 * the window size will be adjusted. Otherwise a new window with appropriated size will be 319 * created. 320 * 321 * @param index 322 * @param size 323 * @return page window 324 */ 325 private FileWindow allocatePageWindow(int index, int size) 326 { 327 final FileWindow window; 328 329 // new window 330 if (index == windows.size()) 331 { 332 // new page window 333 window = new FileWindow(); 334 window.filePartOffset = getWindowFileOffset(index); 335 totalSize += size; 336 window.filePartSize = size; 337 windows.add(window); 338 } 339 else 340 { 341 // get the window 342 window = windows.get(index); 343 344 // adjust if necessary 345 if (window.filePartSize != size) 346 { 347 adjustWindowSize(index, size); 348 } 349 } 350 351 return window; 352 } 353 354 /** 355 * Creates and returns a new page window for given page. 356 * 357 * @param pageId 358 * @param pageType 359 * @param size 360 * @return page window 361 */ 362 public synchronized FileWindow createPageWindow(int pageId, String pageType, int size) 363 { 364 int index = getWindowIndex(pageId); 365 366 // if we found the page window, mark it as invalid 367 if (index != -1) 368 { 369 removeWindowIndex(pageId); 370 (windows.get(index)).id = -1; 371 } 372 373 // if we are not going to reuse a page window (because it's not on 374 // indexPointer position or because we didn't find it), increment the 375 // indexPointer 376 if (index == -1 || index != indexPointer) 377 { 378 index = incrementIndexPointer(); 379 } 380 381 FileWindow window = allocatePageWindow(index, size); 382 window.id = pageId; 383 window.type = pageType; 384 385 putWindowIndex(pageId, index); 386 return window; 387 } 388 389 /** 390 * Returns the page window for given page or null if no window was found. 391 * 392 * @param pageId 393 * @return page window or null 394 */ 395 public synchronized FileWindow getPageWindow(int pageId) 396 { 397 int index = getWindowIndex(pageId); 398 if (index != -1) 399 { 400 return windows.get(index); 401 } 402 return null; 403 } 404 405 /** 406 * Removes the page window for given page. 407 * 408 * @param pageId 409 */ 410 public synchronized void removePage(int pageId) 411 { 412 int index = getWindowIndex(pageId); 413 if (index != -1) 414 { 415 FileWindow window = windows.get(index); 416 removeWindowIndex(pageId); 417 if (index == windows.size() - 1) 418 { 419 windows.remove(index); 420 totalSize -= window.filePartSize; 421 if (indexPointer == index) 422 { 423 --indexPointer; 424 } 425 } 426 else 427 { 428 window.id = -1; 429 } 430 } 431 } 432 433 /** 434 * Returns last n saved page windows. 435 * 436 * @return list of page windows 437 */ 438 public synchronized List<FileWindow> getFileWindows() 439 { 440 List<FileWindow> result = new ArrayList<>(); 441 442 // start from current index to 0 443 int currentIndex = indexPointer; 444 445 do 446 { 447 if (currentIndex == -1) 448 { 449 break; 450 } 451 452 if (currentIndex < windows.size()) 453 { 454 FileWindow window = windows.get(currentIndex); 455 if (window.id != -1) 456 { 457 result.add(window); 458 } 459 } 460 461 --currentIndex; 462 if (currentIndex == -1) 463 { 464 // rewind to the last entry and collect all entries until current index 465 currentIndex = windows.size() - 1; 466 } 467 } 468 while (currentIndex != indexPointer); 469 470 return result; 471 } 472 473 /** 474 * Creates a new PageWindowManager. 475 * 476 * @param maxSize 477 * maximum page size. After this size is exceeded, the pages will be saved starting 478 * at the beginning of file 479 */ 480 public PageWindowManager(long maxSize) 481 { 482 this.maxSize = maxSize; 483 } 484 485 /** 486 * Returns the size of all saved pages 487 * 488 * @return total size 489 */ 490 public synchronized int getTotalSize() 491 { 492 return totalSize; 493 } 494}